[C++ 자/알 Note] A* 길찾기 알고리즘

다익스트라의 한계

최단 거리를 찾기 위한 완전탐색에 가깝다

그리고 가중치의 합만이 우선순위 조건으로 된다

 

A* 알고리즘

일반적인 BFS, 다익스트라는

시작점만을 기준으로 탐색을 진행했다

반면, A* 길찾기 알고리즘은

목적지를 추가해 해당 기준도 탐색한다는 것이다

 

다시 말해,

기존 시작점 개념 뿐 아니라

목적지라는 개념을 추가해서

목적지와의 관계에서 우선순위 조건을 설정해

거기에 맞게 탐색하는 것이 특징이다

 

최단거리는 보장되지 않지만

목적지로부터의 특정 우선순위 조건을 자유자재로 설정 가능하다

예를 들어

정사각형 맵에서

출발지가 왼쪽 상단이고 목적지가 오른쪽 하단인 경우,

계속 탐색하면서 오른쪽 하단과 최대한 가깝게 길을 탐색하도록 하는

경향 및 특징을 주입 가능하다

 

F = G + H

위의 기준을 설정하는 데 사용되는 개념은 "F = G + H"이다

예를 들어 길을 찾는 경우에서

F: 최종 점수 (작을수록 좋음, 같은 현재지점이더라도 경로에 따라 달라짐)

G: 시작점에서 현재 좌표로 이동하는 비용 (작을 수록 좋음, 같은 현재지점이더라도 경로에 따라 달라짐)

H: 현재 좌표로부터 목적지까지 얼마나 가까운지 (작을수록 좋음, 같은 현재지점이면 값 고정)

 

Open List와 Closed List

Open List: 아직 탐색하지 않은 후보 노드들을 관리
Closed List: 이미 탐색한 노드들을 기록하여 중복 방지를 위한 관리

A* 알고리즘을 구현할 때 Open List와 Closed List에서 각각

어떤 식으로 관리할지에 따라서 코드는 달라질 수 있다

 

구현 주의사항

- 예약(발견)

예약(발견) 시스템을 사용해서
이미 더 좋은 경로를 찾았다면 스킵하도록 구현

- 예외 처리

뒤늦게 더 좋은 경로가 발견될 수 있기에

예외 처리는 반드시 신경써줘야한다

 

- OpenList 내부 방식
OpenList 배열이나 리스트를 만들어

가장 좋은 후보를 순회하면서 찾아 제거하는 방식도 가능하다

여기서는

Priority Queue에서 pop 하면서

반복문을 돌며, 가장 좋은 후보를 찾아내는 방식이

시간을 아낄 수 있다

 

A* 길찾기 알고리즘 구현

void Player::AStar()
{
	Pos start = _pos;
	Pos dest = _board->GetExitPos();

	enum
	{
		DIR_COUNT = 8// 대각선 이동 여부에 따라서 4 or 8
	};

	Pos front[] =
	{
		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,	// UP_LEFT
		14, // DOWN_LEFT
		14, // DOWN_RIGHT
		14  // UP_RIGHT
	};

	const int32 size = _board->GetSize();

	// ClosedList
	// 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;

	// OpenList
	priority_queue<PQNode, vector<PQNode>, greater<PQNode>> pq;

	// 1) 예약(발견) 시스템 구현
	// - 이미 더 좋은 경로를 찾았다면 스킵
	// 2) 뒤늦게 더 좋은 경로가 발견될 수 있음 -> 예외 처리 필수
	// - OpenList에서 찾아서 제거하는 방식도 가능하지만
	// - Priority Queue에서 pop한 다음에 무시하는 방식 가능

	// 초기값
	{
		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;
	}

	while (pq.empty() == false)
	{
		// 제일 좋은 후보를 찾는다
		PQNode node = pq.top();
		pq.pop();

		// 동일한 좌표를 여러 경로로 찾아서
		// 더 빠른 경로로 인해서 이미 방문(closed)된 경우 스킵
		// [선택] closed or best 두 방식 중 하나를 선택해서 작성하면 된다
		if (closed[node.pos.y][node.pos.x])
			continue;
		if (best[node.pos.y][node.pos.x] < node.f)
			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];
			int32 h = 10 * (abs(dest.y - nextPos.y) + abs(dest.x - nextPos.x));
			// 다른 경로에서 더 빠른 길을 찾았으면 스킵
			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;
		}
	}

	// 거꾸로 거슬러 올라간다
	Pos pos = dest;

	_path.clear();
	_pathIndex = 0;

	while (true)
	{
		_path.push_back(pos);

		// 시작점은 자신이 곧 부모이다
		if (pos == parent[pos])
			break;

		pos = parent[pos];
	}

	std::reverse(_path.begin(), _path.end());
}