[알고리즘] A* (A Star)

A* Algorithm

• 다익스트라를 확장해 만든 경로 탐색 알고리즘
• 휴리스틱(Heuristic) 기반의 경로 탐색 알고리즘
• F(n) = H(n) + G(n) (최종 가중치 = 목적지까지의 거리 + 이동 비용)
  • F(n) : 출발 노드에서 도착 노드까지 경로의 전체 가중치 합
  • H(n) : 현재 노드에서 목적지 노드까지의 추정 경로 가중치 (휴리스틱 기반)
  • G(n) : 출발 노드에서 현재 노드까지의 경로 가중치
  • F(n)이 가장 최소가 되는 노드를 다음 탐색 노드로 지정한다. (우선순위 큐를 사용)
• 휴리스틱 함수를 통해 어떻게 설계하는지에 따라 알고리즘의 성능이 달라진다.
  • 유클리드 거리 (Euclidean Distance): 대각선 포함, 자유롭게 모든 방향으로 이동 가능
  • 맨해튼 거리 (Manhattan Distance) : 가로/세로 방향으로만 이동 가능
• 언리얼 에서는 NavMesh를 사용하지 못하는 경우 (점프, 사다리 등의 거리 계산)에 사용할 수 있다.
• 또는 NavMesh는 런타임 환경에서의 길찾기 거리 갱신이 어려운 경우 등에 사용할 수 있다.
• 게임 내 자동 길찾기의 경우 미니맵 UI에 보여지는 최단거리 표시 등

※ 휴리스틱 : 최선의 방향을 추정하는 방식 또는 기준.

 

유클리드 VS 맨해튼 VS BFS

https://www.researchgate.net/figure/Green-line-Manhattan-distance-Red-line-euclidean-distance-Blue-line-equivalent-to-8_fig4_331302550

 

 

BFS : 파란 선

맨해튼 : 녹색 선

유클리드 : 빨간 선

 

다익스트라(Dijkstra) Vs A* (A Star)

https://devforum.roblox.com/t/how-does-apathfinding-work/271356/2

 

다익스트라 :

목표 지점까지의 모든 방향을 균일하게 탐색하며, 최단 경로를 보장하지만 비 효율적인 탐색 범위가 발생할 수 있습니다.

 

A*

목표까지의 거리를 계산하고, 그 거리를 노드의 전체 가중치에 더하여 F(n) = H(n) + G(n)으로 바꾸는 추가적인 휴리스틱 방식을 통해 이를 수행합니다.

실제 비용과 경험적 추측을 혼합하여 가장 낮은 F(n)값을 기준으로 노드를 탐색합니다.

 

 

 

---

출처 및 참고내역

https://devforum.roblox.com/t/how-does-apathfinding-work/271356/2

https://www.geeksforgeeks.org/a-search-algorithm/