경로탐색 알고리즘(게임) (Pathfinding Algorithm in Games)
한 줄 정의: NPC나 유닛이 게임 공간 내에서 목적지까지의 최적 경로를 계산하는 알고리즘을 말한다. A* 알고리즘이 대표적이며, 내비게이션 메시와 결합하여 구현되는 경우가 많다.
쉽게 풀면
게임 속 캐릭터가 목적지까지 가는 가장 좋은 길을 찾아내는 계산 방법이다.
논문에서는 이렇게 쓰입니다
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths.
이 논문은 A* 알고리즘을 최초로 제시했으며, 이후 대다수 게임의 경로탐색 시스템의 이론적 기반이 되었다.
주의할 점
정적 경로탐색은 동적으로 변화하는 게임 환경(다른 유닛의 이동 등)을 반영하지 못해 실시간 재계산이나 로컬 회피 알고리즘과 결합해야 한다.