게임에서 경로 찾기(Pathfinding) 알고리즘 종류 - 다익스트라 , A*, D*, 기타

게임에서 경로 찾기(Pathfinding) 알고리즘 종류 - 다익스트라 , A*, D*, 기타

게임에서 경로 찾기 알고리즘(Pathfinding algorithms)은 주로 게임 내 캐릭터가 목표 지점에 도달하기 위해 장애물을 피하면서 최적의 경로를 찾는 데 사용됩니다. 
Pathfinding
https://en.wikipedia.org/wiki/Pathfinding

 

다익스트라 알고리즘 (Dijkstra's Algorithm)

다익스트라 알고리즘은 최단 경로 찾기에 사용되는 알고리즘으로 모든 노드에 대해 시작점에서부터의 거리를 계산하고 가장 짧은 거리를 가지는 노드를 계속해서 선택하여 경로를 확장하는 방법을 사용합니다.
A* 알고리즘의 간단한 버전으로 A*와 달리 휴리스틱을 사용하지 않으며 모든 노드에 대해 최단 거리를 계산합니다.
제한된 환경이나 작은 맵에서 경로를 계산하는 데 유용하지만 모든 경로를 탐색하기 때문에 A*에 비해 속도가 느립니다(특히 큰 맵에서 비효율적)
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

A* 

A* 알고리즘  (A-star Algorithm) 은 Dijkstra 알고리즘의 변형으로 최단 경로를 찾을 때 사용하는 가장 널리 사용되는 그래프 탐색 및 경로 찾기 알고리즘 중 하나입니다. 가중치 그래프 , 소스 노드, 목표 노드가 주어지면  소스에서 목표까지의 가장 짧은 경로를 찾습니다(경로의 비용과 경로를 목표까지 확장하는 데 필요한 비용 추정치를 계산)
메인 루프의 각 반복에서 어떤 경로를 확장할지 결정. 각 노드에 대해 두 가지 값을 계산하고 다음을 최소화하는 경로를 선택 
f(n) = g(n) + h(n)
n - 경로의 다음 노드
g(n) - 시작 노드에서 n까지 경로 비용
h(n) - n에서 목표 지점까지의 가장 저렴한 경로의 비용을 추정하는 휴리스틱 함수
f(n) - 총 비용으로 이 값을 최소화하는 경로를 선택
https://en.wikipedia.org/wiki/A*_search_algorithm

D* 

D* 알고리즘  (D-Star Algorithm) 은 동적 경로 계획에 적합한 알고리즘으로 A*와 비슷한 방식으로 경로를 찾지만 환경이 변할 때 경로를 효율적으로 수정할 수 있다는 점에서 차별화됩니다. 경로가 변경되었거나 장애물이 추가되거나 제거되었을 때 기존 경로를 다시 계산하지 않고 변경된 부분만 수정합니다. 실시간으로 변경되는 동적 환경 변화에 적응하는 데 유용합니다.
https://en.wikipedia.org/wiki/D*

Any-angle Path Planning

A* 알고리즘과 같은 기존의 격자 기반 경로 찾기 방식 (Grid-based pathfinding)에서 각도 제한을 없애고 더 자유로운 경로를 찾아주는 기법. 기존의 격자 기반 경로 찾기에서는 그리드 시스템에서 이동방향 및 각도에 제한이있지만 8방향(또는 4방향) Any-angle path planning에서는 모든 각도에서 이동할 수 있는 경로를 찾음
https://en.wikipedia.org/wiki/Any-angle_path_planning

격자 기반 경로 찾기

격자 기반 경로 찾기 (Grid-based pathfinding)  시스템에서는 맵을 격자(Grid) 형태로 나누고 각 셀은 노드가 됩니다.  이 격자 셀 안에서 이동할 수 있는지 여부를 판단하여 경로를 찾습니다. 예를 들어 게임에서 2D 맵을 10x10 격자 형태로 나누면 각 셀은 하나의 노드가 되고 로봇이나 캐릭터는 한 셀에서 다른 셀로 이동하면서 목표 지점에 도달하려고 할것입니다.

각도 제한 - 격자 기반 경로 찾기에서 컴퓨터가 경로 계산을 단순화하고 효율적으로 하기 위해 정해진 방향 (8방향또는 4방향) 및 각도로 이동을 허용합니다.
8방향 이동 -  한 셀에서 다른 셀로 가는 경로는 상, 하, 좌, 우, 그리고 대각선 방향으로만 가능
4방향 이동 - 한 셀에서 다른 셀로 가는 경로는 수평(왼쪽-오른쪽)과 수직(위-아래) 방향으로만 이동

 

Waypoint 기반 경로 찾기 (Waypoint-based Pathfinding)

이 방법은 특정 지점들(웨이포인트)을 연결하는 방식으로 경로를 찾는 알고리즘입니다. 각 웨이포인트는 미리 정의된 경로 지점이므로 경로 탐색을 단순화할 수 있습니다.

웨이포인트들을 연결하여 경로를 정의하고 그 경로를 따라 이동합니다.
경로 계산이 빠르고 고정된 경로를 따르므로 예측이 가능하지만 환경이 변할 때 경로를 다시 설정해야 할 수 있습니다.

 

네비게이션 메쉬(Navigation Mesh)

2D 또는 3D 공간에서 이동 가능한 영역을 정의하는 메쉬를 생성하여 그 안에서 경로를 찾도록 합니다.
월드의 이동 가능한 영역을 네트워크(다각형 형태)처럼 나누어 AI가 이동할 수 있는 경로를 탐색합니다. 주로 3D 게임에서 AI가 장애물을 인식하고 우회하도록 만들 때 사용됩니다. 미리 계산된 메쉬를 사용하므로 실시간 계산에서 매우 빠르고 효율적이며 복잡한 3D 환경에서도 잘 동작합니다.