경로 탐색(게임 AI)

경로 탐색(게임 AI)은 게임 월드 내에서 장애물을 회피하여 시작점에서 목적지까지 이르는 최적의 경로를 찾는 기술이다.

그래프 알고리즘

대부분의 경로 탐색은 월드를 노드(Node)와 엣지(Edge)로 구성된 그래프로 추상화하여 처리한다.

• 다익스트라 알고리즘(Dijkstra's Algorithm): 모든 노드에 대해 최단 거리를 찾는 기초 알고리즘이다.
• A* 알고리즘: 휴리스틱(Heuristic)을 도입하여 목표 방향을 우선적으로 탐색하는, 게임에서 가장 널리 쓰이는 알고리즘이다.

월드 표현 방식

• 타일 그래프(Tile Graphs): 월드를 사각형이나 육각형 격자로 나누는 방식.
• 네비게이션 메시(Navigation Meshes): 걸어 다닐 수 있는 지형을 폴리곤으로 정의하는 방식. 현대 3D 게임의 표준이다.
• 가시성 그래프(Points of Visibility): 장애물의 모서리를 연결하여 그래프를 생성하는 방식.

고급 기법

• 계층적 경로 탐색(Hierarchical Pathfinding): 월드를 구역 단위로 나누어 거시적 경로를 먼저 찾고, 세부 구역 내에서 미시적 경로를 찾는 방식. 대규모 맵에서 성능을 최적화한다.
• 경로 평활화(Path Smoothing): 그래프 탐색 결과인 지그재그 경로를 부드러운 곡선이나 직선으로 다듬는 과정.
• 동적 경로 탐색: 실시간으로 변화하는 장애물에 대응하기 위한 기술.