[A* & Heap] Chapter 04. A* 길찾기 알고리즘

GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/b09c4e2a981618692e07cbbad085fe32267f16d9

A* 길찾기 알고리즘 · developeSHG/Data_Structure-Algorithm@b09c4e2

 

 

 

---

 

 

그럼 이전까지 학습한걸로 예전에 진행했던 Maze(미로)에서 길찾기 알고리즘을 좀 더 최적화해보자.

 

다익스트라와 BFS를 생각해보면 시작점의 개념은 있었지만, 뚜렷하게 목적지란 개념은 없었다. 물론 탐색과정에서 목적지를 발견하면 멈추라는 명령을 내리긴 했지만, 그건 어디까지나 중간에 탐색하다 멈추는 개념이었지 처음부터 목적지를 향해서 달려가는 개념은 아니었다.

 

---

 

만약 플레이어가 이동한다면, 클릭한 위치까지 장애물이 없기 때문에 그냥 클릭한 위치를 바라보고 직진으로 이동하기만 하면 된다.

하지만 대부분의 게임에서는 장애물이 있고 장애물을 만나면 피해서 가야 되고 또한 목표물까지 최단거리로 찾아 가야 한다.

이러한 최단거리 알고리즘은 BFS 와 다익스트라 알고리즘과 같은 그래프 알고리즘이 존재한다

BFS는 길을 가는 경로에 가중치가 없는 경로를 찾아 갈 때 유용하지만, 즉 A 도시에서 B와 C가 연결 되었는데 B와 C가 가는 경로의 비용이 모두 동일하다면 BFS로 찾는 것이 가능하다

하지만 A와 B를 가는 거리와 A에서 C를 가는 거리의 비용이 서로 다르다면 BFS로 찾기가 힘들어 진다.

이때 사용하는 것이 다익스트라 알고리즘인데, 다익스트라 알고리즘은 출발점을 기준으로 모든 경로의 최단거리 비용을 추출할 때 사용한다.

다익스트라 알고리즘은 현재까지 진행 경로 중에서 가장 작은 값을 뽑아 내는데 비해 이것을 약간 개선해서 예측값을 두고 예측값이 더 적은 것을 찾아 내는 것이 A*알고리즘이다

게임에서와 같이 출발점과 목표지점이 있는 경우 A*알고리즘을 사용하게 되는데 A*알고리즘은 다음과 같은 방법으로 목적지를 찾아 가게 된다.

 

---

 

다시 말해 A*와 다익스트라가 가장 크게 달라지는 부분은 A*는 목적지라는 명확한 개념이 생긴다. 그 외에 부분은 크게 달라지는 것이 없다. 

다익스트라 알고리즘을 다시 복기해보면 간선마자 가중치가 존재해서 누적된 가중치가 기준에 맞았던 즉, 발견한 경로중에서 가장 우월한 후보를 선택해서 그 경로를 방문하는 식으로 순차적으로 진행되었다. 

A*는 시작점을 기준으로 현재 위치까지 얼마나 떨어져있냐를 판단할 뿐만 아니라, 목적지까지도 얼마나 가까워졌는지 두 가지 요소를 동시에 고려한다. 두 가지 요소를 고려해서 원하는 정책을 설정해 각각 점수를 매겨줄 것이고, 그 점수를 통해서 가장 좋은 후보를 골라 실행된다까지는 다익스트라와 크게 다르지 않다.

즉 A*는 다익스트라와 동일하게 각 점수를 매겨서 제일 좋은 점수에 해당하는 것을 실행하겠다 라는 것은 변함없지만, 그 점수를 매기는 방식이 더 세밀한 것이다. 

 

결국 A*는 평가하는 시스템, 점수를 어떻게 매기는지에 따라 최단거리가 될 수도 있지만, 안될 수도 있다. 굉장히 랜덤성이 있는 알고리즘이다.

하지만, 대부분 상황에서 목적지에서 얼마나 가까워졌냐를 계산할 때, 현재 지점에서 목적지까지 거리를 계산해도 될것이고,  아니면 x와 y의 차이에 대한 절대값을 계산해 목적지까지 가까워지는 것을 유도하게끔 평가값을 맞춰주면 대부분 최단 거리로 만들 수 있다.

 

---

 

// 점수 매기기
// F = G + H
// F = 최종 점수 (작을 수록 좋음, 경로에 따라 달라짐)
// G = 시작점에서 해당 좌표까지 이동하는데 드는 비용 (작을 수록 좋음, 경로에 따라 달라짐)
// H(휴리스틱) = 목적지에서 얼마나 가까운지 (작을 수록 좋음, 고정)

 

[※ 정리 (대표적인 그래프 탐색 알고리즘들과 A*의 차이) ※]

BFS :  가중치가 없는 그래프에서 최단 경로를 찾는 완전 탐색 알고리즘

다익스트라 : 가중치 그래프에서 시작 노드를 기준으로 모든 노드까지의 최단거리를 구하는 그리디 알고리즘

A* : 가중치 그래프에서 시작 노드에서 목표 노드까지의 최단 경로만 구하려 하는 그리디 알고리즘

 

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

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

	enum
	{
		DIR_COUNT = 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,
		14,
		14,
		14
	};

	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에서 찾아서 제거한다거나.
	// - pq에서 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)된 경우 스킵
		// [선택. 둘 중에 하나만 돌려도 가능]
		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());
}