경로탐색 알고리즘(게임) (Pathfinding Algorithm in Games)
쉽게 풀면
게임 속 캐릭터가 목적지까지 가는 가장 좋은 길을 찾아내는 계산 방법이다.
왜 중요한가
게임 캐릭터가 장애물을 피해 목표지점까지 최적경로를 찾도록 하는 알고리즘으로, A* 알고리즘이 대표적이며 NPC의 자연스러운 이동을 구현하는 게임 AI 프로그래밍의 기초 기술로 다뤄진다. A* 알고리즘의 성능은 목적지까지의 거리를 과대평가하지 않는 발견적 함수(휴리스틱)의 정확도에 크게 좌우되며, 이 함수를 어떻게 설계하느냐가 실시간 게임에서 탐색 속도를 좌우하는 핵심 변수다. 점프나 등반이 가능한 3차원 지형에서는 평면 그래프 대신 3차원 내비게이션 볼륨을 구축해야 해 계산 복잡도가 크게 늘어난다.
논문에서는 이렇게 쓰입니다
이 논문은 A* 알고리즘을 최초로 제시했으며, 이후 대다수 게임의 경로탐색 시스템의 이론적 기반이 되었다.
탐색 공간을 단순화하면 실시간 경로탐색이 가능해진다는 뜻입니다.
조금 더 깊게 보면
경로탐색 알고리즘은 이론적으로 최단경로를 정확히 계산할 수 있지만, 실시간으로 다수의 캐릭터가 동시에 경로를 계산해야 하는 게임 환경에서는 정확성보다 계산 효율성을 우선해 근사적 경로를 빠르게 찾는 실용적 타협이 흔히 이뤄진다. 다수의 유닛이 동시에 이동하는 전략 게임에서는 각 유닛이 개별적으로 A*를 계산하는 대신, 흐름장(플로우 필드) 기법으로 목적지 하나에 대한 이동 방향 맵을 한 번만 계산해 모든 유닛이 공유하는 방식으로 연산량을 크게 줄인다. 탐색 공간을 그리드가 아니라 내비게이션 메시(다각형 조각)로 표현하면 대각선 이동이나 불규칙한 지형에서도 더 자연스럽고 효율적인 경로를 계산할 수 있다. 계층적 경로탐색(먼저 큰 구역 단위로 대략적 경로를 잡고 세부 경로는 나중에 계산하는 방식)은 매우 큰 맵에서 연산량을 크게 줄이는 기법으로 쓰인다.
주의할 점
정적 경로탐색은 동적으로 변화하는 게임 환경(다른 유닛의 이동 등)을 반영하지 못해 실시간 재계산이나 로컬 회피 알고리즘과 결합해야 한다.