알고리즘 - 에이스타 알고리즘

에이스타 알고리즘은 그래프/트리 검색 알고리즘의 일종입니다.

 

특히, 게임에서 많이 사용되는 최단거리 길찾기 알고리즘이며, 다익스트라의 개념을 확장하여 만들었습니다.

 다익스트라는 최종 위치가 따로 정해져 있지 않기 때문에 시작 노드로부터 모든 경로에 대한 최단 거리를 구하게 되기 때문에 불필요한 탐색이 있다는 단점이 있습니다. 하지만 에이스타 알고리즘은 기존에 다익스트라가 비용이 가장 작은 값을 꺼낸 것에 비해 새로운 방식으로 값을 저장하여, 해당 값이 가장 작은 값을 꺼내어 이동하게 됩니다.

 

에이스타 알고리즘에서 사용되는 값의 계산은 이렇습니다.

f = g + h

f  : 최종 점수로, 작을수록 좋으며 경로에 따라 달라진다.

g : 시작 점에서 해당 좌표까지 이동하는데 드는 비용, 작을수록 좋으며 경로에 따라 달라진다.

h : 목적지에 얼마나 가까운지를 나타냄, 작을수록 좋으며 해당 노드에 위치에 따라 값은 고정된다.

 

우선, 해당 위치에서 이동할 수 있는 방향을 지정하고, 해당 방향들에 대한 '비용'을 지정합니다. 그 다음에는 시작 위치와 도착 위치를 지정하고, 시작 위치를 우선순위 큐에 넣고, 우선순위 큐가 빌때까지 반복하여 방문하지 않은 노드에 대해서 이동 가능한 경로를 우선순위 큐에 추가하고 재귀적으로 탐색해나아갑니다.

 

 

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

	int32	f;		// f = g + h
	int32	g;	
	Pos	pos;
};

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

	Pos start = _pos;
	Pos dest = _board->GetExitPos();
	//_path.clear();
	//_path.push_back(start);

	enum
	{
		DIR_COUNT = 8
	};

	Pos front[8] =
	{
		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
	// closed[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) 뒤늦게 더 좋은 경로가 발견될 수 있음 -> 예외 처리 필수 
	// - opneList에서 찾아서 제거한다거나,
	// - 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;
		}
	}
	
	// TODO
	_path.clear();
	_pathIndex = 0;

	// 거슬러 올라가기
	Pos pos = dest;

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

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

		pos = parent[pos];
	}

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

 

 이상으로 에이스타 알고리즘에 대한 설명을 마치겠습니다. 포바~!