길 찾기 알고리즘의 대표적인 예로 A * 알고리즘이 존재한다!
최단 경로로 시작점부터 목표지점까지 경로를 탐색하는 알고리즘으로서 매우 재미있고 유용한 알고리즘이다.
A* 알고리즘은 지난 블로그에 작성한 DFS, BFS 알고리즘의 활용버전이라고 생각하며 앞으로 공부해볼 다익스타라 알고리즘과 흡사한 유형이라고 생각할 수 있겠다.
A* 알고리즘
● A * 알고리즘 : 출발 꼭짓점에서부터 목표 꼭짓점까지 최단 경로를 탐색하는 휴라스틱기반의 그래프 탐색 알고리즘.
계산 방식
● F(n) = g(n) + h(n)
- g(n) = 시작 노드부터 현재 노드까지의 비용
- h(n) = 현재 노드에서 목표 노드까지의 예상 비용
보통 h(n)을 휴리스틱 함수라고 일컫는다.
해당 휴리스틱 함수를 어떻게 지정하냐에 따라, 알고리즘 형태 결정
● 모든 경로를 다 찾지 않음 => 최단 경로 구하는 알고리즘에 적합
따라서, 목적지에 얼마나 가까운 정점인지를 판단하는 피타고라스의 정의로 시작점부터 목적지까지 남은 거리를 직선적으로 혹은 노드를 지나쳐 걸리는 시간을 계산할 수 있음
고라니 TV의 A * 알고리즘 영상을 참고했다.
열린리스트와 닫힌 리스트를 통해서 조건에 충족하는 근접 노드들을 방문하면서, 시작에서 도착지점까지의 이동경로를 계산하였을때, 최적의 길인 알고리즘을 구현할 수 있다.
이론적으로 생각하는 것보다, 바로 실전에 응용하여 적용시켜보도록 하겠다.
C# 유니티 구현
void OpenListAdd(int checkX, int checkY)
{
// 상하좌우 범위를 벗어나지 않고, 벽이 아니면서, 닫힌리스트에 없다면
if (checkX >= bottomLeft.x && checkX < topRight.x + 1 && checkY >= bottomLeft.y && checkY < topRight.y + 1 && !NodeArray[checkX - bottomLeft.x, checkY - bottomLeft.y].isWall && !ClosedList.Contains(NodeArray[checkX - bottomLeft.x, checkY - bottomLeft.y]))
{
// 대각선 허용시, 벽 사이로 통과 안됨
if (allowDiagonal) if (NodeArray[CurNode.x - bottomLeft.x, checkY - bottomLeft.y].isWall && NodeArray[checkX - bottomLeft.x, CurNode.y - bottomLeft.y].isWall) return;
// 코너를 가로질러 가지 않을시, 이동 중에 수직수평 장애물이 있으면 안됨
if (dontCrossCorner) if (NodeArray[CurNode.x - bottomLeft.x, checkY - bottomLeft.y].isWall || NodeArray[checkX - bottomLeft.x, CurNode.y - bottomLeft.y].isWall) return;
// 이웃노드에 넣고, 직선은 10, 대각선은 14비용
Node NeighborNode = NodeArray[checkX - bottomLeft.x, checkY - bottomLeft.y];
int MoveCost = CurNode.G + (CurNode.x - checkX == 0 || CurNode.y - checkY == 0 ? 10 : 14);
// 이동비용이 이웃노드G보다 작거나 또는 열린리스트에 이웃노드가 없다면 G, H, ParentNode를 설정 후 열린리스트에 추가
if (MoveCost < NeighborNode.G || !OpenList.Contains(NeighborNode))
{
NeighborNode.G = MoveCost;
NeighborNode.H = (Mathf.Abs(NeighborNode.x - TargetNode.x) + Mathf.Abs(NeighborNode.y - TargetNode.y)) * 10;
NeighborNode.ParentNode = CurNode;
OpenList.Add(NeighborNode);
}
}
