3-4. A*(A-Star) 알고리즘

0. 다익스트라 vs A*

(1) 목적지와 계산

다익스트라는 시작 노드에서부터 모든 노드를 탐색하여 최단 경로로 진행, 목적지에 대한 정보가 없음

A*는 시작점 노드에서 목적지 노드까지의 최단 거리 연산

 

1. A* 알고리즘

 F = G + H
(1) F(Heuristic Cost Function) ; 최종 점수(작을수록 좋음, 경로에 따라 달라짐), 전체 비용
(2) G ; 시작점에서 해당 좌표까지 이동하는데 드는 비용(작을수록 좋음, 경로에 따라 달라짐)
(3) H(Heuristic) ; 현재 노드에서 목표 노드까지의 이동 비용 (작을수록 좋음, 고정된 값)

 

- 구현 전 유의사항

1) 예약(발견) 시스템 구현 ; 연결되어 있는 다른 노드를 발견, 노드에 대한 코스트 계산 후 예약
2) 뒤늦게 더 좋은 경로가 발견되면 예외 처리

 

2. A* 알고리즘 - Player.cpp

(1) 기본 구조

void Player::AStar()
{
	// 가중치 점수 매기기
	// F = G + H
	// F ; 최종 점수(작을수록 좋음, 경로에 따라 달라짐)
	// G ; 시작점에서 해당 좌표까지 이동하는데 드는 비용(작을수록 좋음, 경로에 따라 달라짐)
	// H ; 목적지에서 얼마나 가까운가 (작을수록 좋음, 고정된 값)

	Pos start = _pos;
	Pos dest = _board->GetExitPos();

	enum
	{
		DIR_COUNT = 4
	};

	Pos front[] = // { y, x }
	{
		Pos { -1 , 0}, // UP
		Pos { 0 , -1}, // LEFT
		Pos { 1 , 0}, // DOWN
		Pos { 0 , 1}, // RIGHT
		Pos {-1, -1}, // UP_LEFT
		Pos {1, -1}, // DOWN_LEFT
		Pos {1, 1}, // DOWN_RIGHT
		Pos {-1, 1}, // UP_RIGHT
	};

	int32 cost[] =
	{
		10, // UP
		10, // LEFT
		10, // DOWN
		10, // RIGHT
		14, // 대각선 (10 * 1.4)
		14,
		14,
		14,
	};

	const int32 size = _board->GetSize();

추후에 대각선 이동을 고려하여 4개의 포지션 값과 비용을 추가한다.

대각선으로 이동하는 비용은 약 10 * 1.4인 14이다.

(가로 = 10, 세로 = 10, 대각선 = 10*root(2) = 14.1 ...)

 

(2) PQNode 구조체

struct PQNode
{
	bool operator<(const PQNode& other) const { return f < other.f; }
	bool operator>(const PQNode& other) const { return f > other.f; }

	int32	f;
	int32	g;
	Pos	pos;
};

P점과 Q점 사이의 계산을 위한 구조체이다.

비용을 계산하기 위한 f와 g, 위치를 선언하고 연산자 오버로딩을 이용하여 입력된 값과 비용 함수 f를 비교할 수 있도록 해준다.

 

(3) 초기값 설정

	// Closed List ; 방문한 노드
	// close[y][x] ; (y, x)에 방문했는지 여부
	vector<vector<bool>> closed(size, vector<bool>(size, false));

	// best[y][x] ; 지금까지 (y, x)에 대한 가장 좋은 비용(작을수록 좋음), 값이 커지면 맵으로 바꾸는게 나음
	vector<vector<int32>> best(size, vector<int32>(size, INT32_MAX));

	// 부모 추적
	map<Pos, Pos> parent;

	// Open List ; 발견된 노드
	priority_queue<PQNode, vector<PQNode>, greater<PQNode>> pq;
    
	{
		int32 g = 0;
		int32 h = 10 * (abs(dest.y - start.y) + abs(dest.x - start.x)); 
		pq.push(PQNode{ g + h, g, start }); // 값 예약
		best[start.y][start.x] = g + h;
		parent[start] = start;
	}

방문한 노드에 대한 이중 배열인 close와 가장 좋은 비용을 이중 배열로 나타낸 배열인 best를 선언한다.

부모를 추적하기 위해 parent를 map으로 구성한다. 키와 값은 모두 Pos 형(좌표)이다.

발견된 노드를 관리하는 우선순위 큐를 내림차순으로 만들어서 (ex : 50, 40, 30, 20, 10) 저장한다.

이 때 큐의 top을 추출하면 가장 좋은 값(가장 작은 값)이 된다.

 

 

이후의 휴리스틱 비용 함수인 f를 계산하기 위한 g와 h에 대한 초기값을 세팅한다.

priority_queue에 f 함수와 g와 start 값을 예약한다.

이후에 최단거리 best 값은 f 함수의 값을, 부모의 시작 노드는 시작 노드로 설정해준다.

 

3. priority_queue를 활용한 A* 알고리즘 구현

while (pq.empty() == false)
	{
		// 제일 좋은 후보를 찾기
		PQNode node = pq.top(); // f가 가장 작은 값
		pq.pop();

		// 동일한 좌표를 여러 경로로 찾아서 더 빠른 경로로 인해 이미 방문된 경우 스킵
		if (closed[node.pos.y][node.pos.x]) // closed 사용
			continue; 

		// 방문
		closed[node.pos.y][node.pos.x] = true;

		// 목적지에 도착했으면 종료
		if (node.pos == dest)
			break;

		for (int32 dir = 0; dir < DIR_COUNT; dir++)
		{
			Pos nextPos = node.pos + front[dir]; // 바라보는 방향에 따라
			// 갈 수 있는 지역인가?
			if (CanGo(nextPos) == false)
				continue;
			// 이미 방문한 곳이면 스킵
			if (closed[nextPos.y][nextPos.x])
				continue;

			// 비용 계산
			int32 g = node.g + cost[dir]; // 이전 좌표까지의 g값 + 다음 방문할 노드의 비용
			int32 h = 10 * (abs(dest.y - nextPos.y) + abs(dest.x - nextPos.x)); // 목적지에서 지금 좌표까지의 거리 * 10
			// 다른 경로에서 더 빠른 길을 찾았으면 스킵
			if (best[nextPos.y][nextPos.x] <= g + h)
				continue;

			// 예약 진행
			best[nextPos.y][nextPos.x] = g + h;
			pq.push(PQNode{ g + h, g, nextPos });
			parent[nextPos] = node.pos;
		}
	}

우선 순위 큐가 텅 빌때 까지 반복문을 시행한다.

 

3-1. 최단 거리로 이동하기

(1) 제일 좋은 후보군(최단 거리에 알맞은) 찾기

while (pq.empty() == false)
	{
		// 제일 좋은 후보를 찾기
		PQNode node = pq.top(); // f가 가장 작은 값
		pq.pop();

먼저 priority_queue인 pq에는 f 함수, g 값, start 값 중에 가장 작은 값이 top에 위치해 있다.

그래서 node에서 제일 좋은 후보군을 top()으로 찾아 pop을 해준다.

 

(2) 이미 방문한 좌표이면 스킵, 방문한 좌표는 기록하기

		// 동일한 좌표를 여러 경로로 찾아서 더 빠른 경로로 인해 이미 방문된 경우 스킵
		if (closed[node.pos.y][node.pos.x]) // closed 사용
			continue; 

		// 방문
		closed[node.pos.y][node.pos.x] = true;

closed 배열을 이용해서 진행중인 길이 아닌 더 빠른 경로를 찾은 경우 무시하도록 설정한다.

체크를 하지 않으면 왔던 길을 뒤로 돌아갔다가 앞으로 갔다가 하기 때문에, 이미 방문한 노드를 체크하는 것이다.

노드를 방문했으면 closed 배열을 이용해서 해당 좌표를 true로 바꿔준다.

 

(3) 목적지에 도착했으면 종료하기

		// 목적지에 도착했으면 종료
		if (node.pos == dest)
			break;

지금 방문한 node의 포지션을 체크해서 dest의 포지션과 일치하면 break로 반복문을 탈출한다.

 

3-2. 진행 경로에 대한 계산

(1) 갈 수 있는 방향 체크

		for (int32 dir = 0; dir < DIR_COUNT; dir++)
		{
			Pos nextPos = node.pos + front[dir]; // 바라보는 방향에 따라
			// 갈 수 있는 지역인가?
			if (CanGo(nextPos) == false)
				continue;
			// 이미 방문한 곳이면 스킵
			if (closed[nextPos.y][nextPos.x])
				continue;

다음 노드(진행할 노드) = 현재 위치의 노드 + 바라보는 방향에 있는 노드

다음 노드가 벽인지 아닌지 체크하는 CanGo 함수를 이용해서 갈 수 없으면 continue로 건너뛰기 한다.

이후에 dir이 1씩 증가하면서 UP -> LEFT -> DOWN -> RIGHT 각 방향을 체크한다.

여기에서도 다음 방문할 노드가 이미 방문한 곳인지 체크해준다.

(4방향을 모두 체크하기 때문에 이미 방문한 노드가 다음 노드가 될 수도 있기 때문)

 

(2) f 함수(Heuristic Cost Function) 계산(f = g + h)

			// 비용 계산
			int32 g = node.g + cost[dir]; // 이전 좌표까지의 g값 + 다음 방문할 노드의 비용
			int32 h = 10 * (abs(dest.y - nextPos.y) + abs(dest.x - nextPos.x)); // 목적지에서 지금 좌표까지의 거리 * 10
			// 다른 경로에서 더 빠른 길을 찾았으면 스킵
			if (best[nextPos.y][nextPos.x] <= g + h)
				continue;

다음 노드를 기준으로 계산한다. 

지금 노드까지의 g 값과 바라보는 다음 노드의 비용을 더한 값이 새로운 g 값이 된다.

h는 목적지에서 다음 노드까지의 거리의 절대값이다.

이후에 f 값보다 더 좋은 값(더 빠른 길)을 찾았다면 스킵하도록 한다.

(거리가 같은 최단 거리가 두 개 나오면 갈팡질팡 하는 것을 방지)

 

(3) 다음 이동 예약하기

			// 예약 진행
			best[nextPos.y][nextPos.x] = g + h;
			pq.push(PQNode{ g + h, g, nextPos });
			parent[nextPos] = node.pos;
		}

best 배열에 지금까지 찾은 가장 빠른 길인 f 함수 값을 저장한다.

priority_queue에 f 함수 값, g 값, 다음 노드의 위치 값을 밀어넣고 다음 노드의 부모를 지금 노드로 지정한다.

 

이후에 각 방향별로 다시 (1)번부터 체크하고 4방향을 모두 체크했으면 pq가 텅 빌때 까지

후보군 찾기 -> 이미 방문한 좌표 스킵 -> 방문 좌표 기록 -> 갈 수 있는 방향 체크 -> f 계산 -> 이동 예약

의 순서가 반복된다.

 

4. 도착지에 도착하면 새로운 맵을 생성하기

void Player::Update(uint64 deltaTick)
{	// 0.1초 지연
	if (_pathIndex >= _path.size())
	{
		_board->GenerateMap();
		Init(_board);
		return;
	}