Unity Tilemap에서 A* 알고리즘으로 최단경로 찾기

최단 경로 찾기 알고리즘

최단 경로 찾기 알고리즘에는 여러가지 알고리즘들이 있는데, 상황에 따라 다르게 사용할 수 있다.

게임이 어떤 케이스인지 생각해보고 적용하면 된다.

• 한 개의 시작노드와 한 개의 도착노드
  • Greedy Best First Search - 휴리스틱 값에 기반한 우선순위 큐 사용. 즉 f(x) = h(x)
  • A* - 게임에 주로 사용된다. 아래 설명 참고
• 한 개의 시작노드와 여러 개의 도착노드, 또는 여러 개의 시작노드와 한 개의 도착노드
  • Breadth First Search(BFS) - 가중치 없는 간선
  • Dijkstra(다익스트라) - 음수가 아닌 가중치가 있는 간선
  • Bellman-Ford(벨만포드) - 양수 또는 음수 가중치가 있는 간선
• 여러 개의 시작노드와 여러 개의 도착노드
  • Floyd-Warshall(플로이드 워샬)
  • Johnson's Algorithm(존슨 알고리즘)

각 알고리즘을 따로 설명하기에는 너무 내용이 많고, A* 알고리즘만 설명하겠다.

 

A* 알고리즘

A* 알고리즘은 다익스트라 알고리즘을 확장하여 만들어진 알고리즘이다. 현재 노드의 비용을 g(x), 현재 노드에서 다음 노드로 이동할 때 휴리스틱 함수를 h(x)라고 할 때, 이 둘을 더한 f(x) = g(x) + h(x)가 최소가 되는 노드를 우선적으로 탐색하는 방법이다. 따라서 일반적으로 오름차순 우선순위 큐를 사용한다.

h(x)가 추가된 것이 다익스트라와의 차이점이다.

 

휴리스틱 함수 h(x)를 어떻게 만들지가 관건인데, 이 글에서는 2D 타일맵에서 상하좌우 및 대각선 탐색을 할 것이므로 맨해튼 거리와 체비쇼프 거리를 사용한다.

 

맨해튼 거리는 택시 거리라고도 불리는 것으로, 두 점의 x좌표 차이와 y좌표 차이를 더한 값이다.

즉, |x1 - x2| + |y1 - y2|이다. 상하좌우만으로 이동할 수 있을 때, 맨해튼 거리를 이용해서 노드 간 거리를 구한다.

 

체비쇼프 거리는 체스판 거리라고도 불리는 것으로, 두 점의 x좌표 차이와 y좌표 차이 중 큰 값을 갖는 거리이다.

즉, max(|x1 - x2|, |y1 - y2|)이다. 상하좌우 및 대각선으로 이동할 때, 체비쇼프 거리를 이용해서 노드 간 거리를 구한다. 

 

구현

실제 유니티에서의 구현은 코드와 사용법 등은 github에 올려놓았다.

유니티의 .NET 버전을 변경하지 않아 C# 6.0부터 지원되는 우선순위 큐를 사용하지 않았다. 대신 리스트를 순회하며 일일이 찾는 방법을 사용해 조금 비효율적이다.

하지만 알고리즘을 이해하는 데는 무리가 없을 것이라 생각한다.

GitHub - virtus2/rectangular-tilemap-pathfinder: 유니티 직사각형 타일맵의 A* 알고리즘 길찾기

 

참고

본 글의 내용이 이해하기 어렵다면 아래 글을 차근차근 읽어보면 굉장히 많은 도움이 될 것이다.

https://www.redblobgames.com/pathfinding/tower-defense/

Flow Field Pathfinding for Tower Defense

https://www.redblobgames.com/pathfinding/a-star/introduction.html

Red Blob Games: Introduction to A*