Path finding

개요

어떤 점 A에서 B로 캐릭터나 unit을 이동시키는 알고리즘을 말한다. Path Finding은 Shortest path problem과 밀접한 연관이 있다. 그래프 이론과 관련하여 어떤 경로가 최선의 경로인지를 파악하는 알고리즘이 Path Finding이다.

노드들을 만드는 방법

1. Waypoints: 미리 정해진 waypoint를 이용하는 방식
2. Precomputation: 미리 계산한 거리 벡터를 이용하는 방식
3. Quantization: 게임의 공간을 나누는 방식
4. Localization: 나뉘어진 공간에서 캐릭터의 위치를 기반으로 노드를 찾는 방식

종류

1. A* 알고리즘
2. BFS
3. TBA*
4. LRTA*
5. IDA*
6. RIBS
7. HPA*

참고

https://qiao.github.io/PathFinding.js/visual/

https://www.kevanahlquist.com/osm_pathfinding/