A* 알고리즘 공부

참조:http://www.gisdeveloper.co.kr/?p=3897

 

다익스트라 알고리즘과의 차이

 

다익스트라 알고리즘 - 시작 노드만을 기점으로 모든 노드에대한 최단경로를 파악

A* 알고리즘 - 시작지점과 목적지점을 지정해 둚으로써 두 노드간의 최단경로를 파악

 

직선상의 거리를 안다는 가정하의 이론

 

시작지 0과 목적지 6이라고 가정할경우 그래프 예시

1번노드로 간경우와 3번노드로 간경우

리스트의 종류는 OpenList, CloseList가 있다.

 

OpenList - 앞으로 방문할 수 있는 지역(마지막으로 간 노드에서 인접한 노드)

CloseList - 이미 방문한 지역(계산에서 제외한다)

 

0번이 시작이기 때문에 ClostList에 0번을 넣고 시작한다.

 

0번이랑 연결된 모든 노드들을 Open List에 집어넣는다.(1,3이 있다)

Open List에 들어가는 구조체의 정보는

Parent Node - 부모노드(현재는 0번)

G - 시작노드에서 현재 노드까지의 길이

H - 현재 노드에서 목적지 노드까지 추측 거리

F - G+H

 

1의 노드값을 예로들면

Parent Node - 0

G - 5.6

H - 12

F - 17.6

H의 계산 방법은 1번에서 6번까지의 거리를 피타고라스의 법칙등으로 계산한다

 

지금의 예시는 다익스트라 알고리즘 식 길찾기지만 보통 A*는 게임에서 사용하고

타일구조로 되어있다.배열의 길이로 계산해도 되고(장애물이 없다고 판단),

결과값의 좌표 그자체를 Distance해도 된다.

 

결과적으로

1의 F - 17.6

3의 F - 16.8

이므로 더 가깝다고 판단되는 3번노드를 Close List에 추가한다.

 

CloseList - 0,3

OpenList - 1(아직 연산이 안끝났으므로 남아있다),2,5

이렇게 진행이 된다.

 

3번을 기점으로 2,6번 OpenList

 

2번의 경우

G - 12.4

F - 19.4

 

5번의경우

G - 13.3

F - 18.8

 

3번으로 갔을경우의 최종목적지는

0 - 3 - 5 - 6으로

18.8의 길이가 나온다.

 

이제 1번쪽 계산을 해보자

 

1번을 CloseList에 넣고 2 4번을 OpenList에 넣는다

2번의경우는 이미 계산된 결과값이 있는데, 둘을 비교해서 나은값으로 갱신시킨다.

 

현재 2

G - 9.9

F - 16.9

 

과거 2

G - 12.4

F - 19.4

 

이므로 현재의 2가 더 짧기 때문에 갱신시켜준다.

 

4번의 경우

G - 12.1

F - 17.3

 

결과적으로 정산하면

 

2의 F - 16.9

4의 F - 17.3

5의 F - 18.8

 

0 - 1 - 2 - 6이 최종적으로 결정된다.

 

타일기반이 좀 더 계산이 쉽다.

타일모양이 이렇다고 가정 시, 대각선을 제외하고 계산하면,

x - 2, y - 6이므로 f는 8이 된다고 계산하면 된다.

대각선을 몇으로 줄지는 개발자 마음이다.

 

타일 기준으로 코드를 한번 만들어봤다.

bwall은 사실 TILE 구조체 안에 넣어도 되는데, 콘솔상에서 입력하기 편하기 위해 따로 배열을 만들었다.

#include<stdio.h>
#include <windows.h>
#include <math.h>
#include <stack>
using namespace std;
#define MAX 10
typedef struct TILE
{
	int x;
	int y;
	int g;				//시작점으로부터 현재 위치까지의 소요된 비용
	int h;				//현재 위치로부터 목적지까지의 예상 비용.(장애물을 고려하지않음)
	bool closed;		//방문여부
	TILE* prevTile;		//이전 타일
	//f = g + h
}TILE;

TILE tile[MAX][MAX];

bool bWall[MAX][MAX] = {	{1,1,1,1,1,1,1,1,1,1},
							{1,0,0,0,0,0,0,0,0,1},
							{1,0,0,1,0,0,0,0,0,1},
							{1,0,0,1,0,0,0,0,0,1},
							{1,0,0,1,1,1,1,1,0,1},
							{1,0,0,1,0,0,0,1,0,1},
							{1,0,0,1,0,1,0,1,0,1},
							{1,0,0,1,0,1,1,1,0,1},
							{1,0,0,0,0,0,0,0,0,1},
							{1,1,1,1,1,1,1,1,1,1} };

int num;
POINT player,goal;
#pragma warning(disable:4996)

void gotoxy(int x, int y)
{
	COORD Pos;
	Pos.X = x;
	Pos.Y = y;
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), Pos);
}

bool isCanMove(int x, int y)
{
	//범위 밖이면 캔슬
	if (x < 0 || x >= MAX || y < 0 || y >= MAX)
		return false;
	//벽에 막혔다면 캔슬
	if (bWall[y][x] == 1)
		return false;
	//닫힌 지역이면 캔슬
	if (tile[y][x].closed == true)
		return false;
	return true;
}

//벽이있으면 대각선으로 움직일수 없다
bool isWallCross(int x1, int y1, int x2, int y2)
{
	int x = x2 - x1;
	int y = y2 - y1;
	//대각선만 유입
	if (abs(x) == 1 && abs(y) == 1)
	{
		if (x == 1 && bWall[y][x + 1])
			return false;
		else if (x == -1 && bWall[y][x - 1])
			return false;
		else if (y == 1 && bWall[y + 1][x])
			return false;
		else if (y == -1 && bWall[y - 1][x])
			return false;

		return true;
	}
	return false;
}


void Astar(TILE* nowTile, TILE* endTile)
{
	nowTile->closed = true;
	if (nowTile->x == endTile->x && nowTile->y == endTile->y)
		return;

	TILE* nextClose = nullptr;
	//주변을 살핀다
	for (int y = nowTile->y -1; y < nowTile->y + 2; y++)
	{
		for (int x = nowTile->x -1; x < nowTile->x + 2; x++)
		{
			if (isCanMove(x, y) == false)
				continue;

			if(isWallCross(nowTile->x,nowTile->y,x,y))
				continue;
			
			if (tile[y][x].prevTile == nullptr ||
				//이미 한번 지나갔던 타일이고 closed가 아니라면
				tile[y][x].g + tile[y][x].h > nowTile->g + 1 + abs(nowTile->x - endTile->x) + abs(nowTile->y - endTile->y))
			{
				tile[y][x].prevTile = nowTile;
				tile[y][x].g = nowTile->g + 1;		//인접타일은 1칸차이라고 친다.
				tile[y][x].h = abs(x - endTile->x) + abs(y - endTile->y);
			}
			else
				continue;

			//다음 닫을 리스트가 없거나, f가 더 적다고 할경우 바꿔준다
			if (nextClose == nullptr || 
				nextClose->g + nextClose->h > tile[y][x].g + tile[y][x].h)
				nextClose = &tile[y][x];
		}
	}
	if (nextClose != nullptr)
	{
		Astar(nextClose, endTile);
	}
}

int main(void) {
	//플레이어 시작위치
	player.x = 1;
	player.y = 5;
	goal.x = 6;
	goal.y = 6;

	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			tile[i][j].g = tile[i][j].h = 0;
			tile[i][j].prevTile = nullptr;
			tile[i][j].closed = false;
			tile[i][j].x = j;
			tile[i][j].y = i;
 		}
	}
	
	Astar(&tile[player.y][player.x], &tile[goal.y][goal.x]);
	stack<TILE*> Res;
	TILE* tilepivot = &tile[goal.y][goal.x];
	while (tilepivot != nullptr)
	{
		Res.push(tilepivot);
		tilepivot = tilepivot->prevTile;
	}
	while (1)
	{
		//그려주기 구문
		gotoxy(0, 0);
		for (int y = 0; y < 10; y++)
		{
			for (int x = 0; x < 10; x++)
			{
				if (bWall[y][x])
					printf("■");
				else
					printf("  ");
			}
			printf("\n");
		}
		gotoxy(goal.x * 2, goal.y);
		printf("G");

		gotoxy(player.x * 2, player.y);
		printf("＠");

		if (Res.empty() == false)
		{
			player.x = Res.top()->x;
			player.y = Res.top()->y;
			Res.pop();
		}
		//텀을 두고 보여준다
		Sleep(1000);
	}
 	return 0;
}

코드의 결과물