개요
어떤 점 A에서 B로 캐릭터나 unit을 이동시키는 알고리즘을 말한다. Path Finding은 Shortest path problem과 밀접한 연관이 있다. 그래프 이론과 관련하여 어떤 경로가 최선의 경로인지를 파악하는 알고리즘이 Path Finding이다.
노드들을 만드는 방법
- Waypoints: 미리 정해진 waypoint를 이용하는 방식
- Precomputation: 미리 계산한 거리 벡터를 이용하는 방식
- Quantization: 게임의 공간을 나누는 방식
- Localization: 나뉘어진 공간에서 캐릭터의 위치를 기반으로 노드를 찾는 방식