[알고리즘] A* 길찾기 알고리즘

A*는 점수를 매겨 길을 찾는다.

F = G + H 

F : 최종 점수(작을수록 좋음, 경로에 따라 달라짐)

G : 시작점에서 해당 좌표까지 이동하는데 드는 비용(작을수록 좋음, 경로에 따라 달라짐)

H : 목적지에서 얼마나 가까운지(작을수록 좋음, 고정)

 

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

 

먼저 방문했는지 여부를 closed, 가장 좋은 비용을 best, 부모를 parent, pq에 F값이 작은 순서대로 집어넣는다.

 

	//pq loop 시작!
    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;
		}
	}//pq loop 끝!

시작점에서 현재 지점까지 거리 g, 현재 지점부터 목적지까지 거리 h로 계산한다.

cost[dir]은 상하좌우 비용이 10, 대각선 비용들이 각각 14로 계산한다.

best에 비용을 저장하고 pq에 노드를 집어넣는다. 

 

// 거꾸로 거슬러 올라간다
	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());

 

그리고  _path에 자신의 부모를 저장하는 방식으로 거꾸로 거슬러 올라간 다음 reverse로 반전시켜준다.