A* 길찾기 최적화: NavMesh와 Flow Field를 활용한 수십 마리 몬스터의 동시 경로 탐색

Grid 기반 A*의 한계와 NavMesh 전환

Top-down 뷰나 RTS, Hack & Slash 장르의 게임에서는 수십 마리의 몬스터가 동시에 플레이어를 추적하는 상황이 자주 발생합니다. 가장 표준적인 길찾기 알고리즘인 A*는 그리드(Grid) 맵에서 단순하고 직관적으로 동작하지만 맵의 크기가 커지고 연산 대상 개체가 늘어날수록 급격한 성능 저하를 일으킵니다.

그리드 기반 A* 알고리즘의 노드 탐색 비용 평가식은 다음과 같습니다.

f(n) = g(n) + h(n)

여기서 $g(n)$ 은 시작 위치에서 현재 노드 $n$ 까지 이동하는 데 소요된 실제 비용이며 $h(n)$ 은 현재 노드에서 목표 지점까지의 예상 남은 비용(휴리스틱)입니다. 2D 그리드에서 유클리드 거리를 휴리스틱으로 사용하면 식은 다음과 같습니다. 3D 공간에서는 이에 $z$ 축 차이의 제곱을 더합니다.

h(n) = \sqrt{(x_{target} - x_n)^2 + (y_{target} - y_n)^2}

그리드 방식은 공간을 동일한 크기의 타일로 분할하므로 맵 해상도가 높아질수록 노드 수가 폭발적으로 증가합니다. 복잡도 탐색을 프레임마다 수십 개의 몬스터 개체가 개별적으로 실행하면 CPU 메인 스레드에 심각한 병목 현상이 생깁니다.

Grid 기반 노드와 NavMesh 다각형 노드의 그래프 크기 비교

NavMesh(Navigation Mesh)는 이러한 문제를 줄일 수 있습니다. 3D 지형의 이동 가능 영역을 볼록 다각형 단위로 표현하므로, 고해상도 균일 그리드와 비교해 그래프 노드 수를 크게 줄일 수 있습니다. 실제 감소 폭은 맵 형태와 베이크 설정에 따라 달라집니다.

NavMesh 기반 A* 최적화와 경로 단순화

NavMesh를 도입하더라도 동시 이동 개체가 많아지면 추가 최적화가 필요할 수 있습니다. 다각형 그래프 탐색은 보통 통과할 폴리곤 통로를 찾습니다. 이 통로에서 포털의 중점만 이어 붙이는 단순 후처리는 불필요하게 꺾일 수 있으므로, 포털 양쪽 끝점을 이용하는 퍼널(String Pulling) 알고리즘으로 경로를 다듬을 수 있습니다.

flowchart TD
    A[글로벌 목표 지점 설정] --> B[NavMesh 볼록 다각형 A* 탐색]
    B --> C[경로 폴리곤 포털 Portal 형성]
    C --> D[퍼널 알고리즘으로 최단 직선 경로 산출]
    D --> E[RVO/ORCA 기반 로컬 충돌 회피 적용]

퍼널 알고리즘 (Funnel Algorithm / String Pulling)

NavMesh A*를 통해 지나가야 할 볼록 다각형들의 리스트를 구한 뒤 에이전트가 지그재그로 이동하지 않고 자연스럽게 이동하도록 경로를 다듬는 단계가 필요합니다.

퍼널 알고리즘은 다각형의 접경선(Portal)을 양쪽 꼭짓점으로 좁혀가는 모형을 사용하여 실시간으로 에이전트의 이동 경로를 팽팽한 끈을 당기듯 최단 직선 경로로 단순화합니다. 이를 통해 지형 코너를 매끄럽게 도는 이동을 계산량 부담 없이 구현할 수 있습니다.

퍼널 알고리즘 vs 위치보간: 경로 최적화와 이동 처리의 차이

대규모 몬스터 군집을 위한 고급 최적화 전략

NavMesh A*와 퍼널 알고리즘만으로 수백 마리의 에이전트를 실시간으로 처리하기에는 여전히 한계가 있습니다. 많은 개체가 동시에 이동할 때는 알고리즘 패러다임을 전환해야 합니다.

상위 섹터 그래프와 하위 NavMesh를 결합한 계층적 길찾기 구조

1. 계층적 길찾기 (Hierarchical Pathfinding, HPA*)

넓은 지도를 여러 개의 상위 섹터(Sector) 노드로 구분합니다.

상위 그래프 탐색: 섹터 사이의 포털·진입점을 추상 노드로 두고 출발지에서 목적지까지 지나갈 섹터 경로를 탐색합니다.
하위 경로 구성: 선택된 섹터 경로를 따라 각 섹터의 진입점과 출구점 사이의 세부 경로를 연결합니다. 섹터 내부 경로를 미리 계산해 둘지 필요할 때 탐색할지는 맵 갱신 빈도와 메모리 예산에 따라 정합니다.

계층 그래프는 전체 맵을 매번 세부 탐색하는 일을 줄일 수 있지만, 절감 폭은 섹터 크기와 포털 구성, 맵 구조에 따라 달라집니다. 대표 맵에서 전체 경로 비용과 탐색 노드 수를 측정해 효과를 확인해야 합니다.

2. 단일 목표 다수 개체: 플로우 필드 (Flow Field)

추적 대상이 플레이어 1명이고 몬스터 100마리가 해당 플레이어를 향해 뛰어오는 구조라면 몬스터 각각 A* 탐색을 돌리는 것은 심각한 낭비입니다.

대신 플레이어 위치를 기준으로 맵에 방향 벡터장(Vector Field)을 생성합니다. 각 그리드/셀에는 목표까지의 누적 비용이 줄어드는 방향을 저장하고, 몬스터는 현재 셀의 벡터를 조회해 이동합니다. 플레이어의 목표 셀이 바뀌면 필드를 다시 계산하거나 갱신해야 합니다.

플로우 필드의 이동 방향 벡터는 비용장(Cost Field)의 기울기로 결정됩니다.

\vec{V}(x, y) \approx -\nabla C(x, y)

여기서 $C(x, y)$ 는 목표 지점으로부터의 누적 이동 비용(Cost Distance)이며 $-\nabla C$ 는 비용이 가장 빠르게 감소하는 방향을 뜻합니다. 필드를 만든 뒤 각 몬스터가 현재 셀의 방향을 조회하는 비용은 $O(1)$ 이지만, 전체 몬스터를 갱신하는 비용은 개체 수 $N$ 에 따라 $O(N)$ 으로 증가합니다. 필드 재계산 비용도 맵의 셀과 연결 구조에 따라 달라집니다.

C++ 기반 NavMesh A* 및 퍼널 구현 구조 예제

NavMesh 기반 노드 탐색과 포털 데이터를 다루는 C++ 자료 구조 및 퍼널 알고리즘의 개략 예시입니다. 아래 함수는 포털 처리 부분을 의도적으로 생략한 뼈대이며, 실제 경로 계산 구현은 아닙니다.

#include <vector>
#include <cmath>

struct Vector3 {
    float x, y, z;
};

struct NavPolygon {
    int id;
    std::vector<Vector3> vertices;
    std::vector<int> neighborIds;
    Vector3 center;
};

struct Portal {
    Vector3 left;
    Vector3 right;
};

// 퍼널 알고리즘 예시 핵심 로직
std::vector<Vector3> StringPulling(const std::vector<Portal>& portals, const Vector3& start, const Vector3& end) {
    std::vector<Vector3> path;
    path.push_back(start);

    Vector3 apex = start;
    Vector3 portalLeft = start;
    Vector3 portalRight = start;

    for (size_t i = 0; i < portals.size(); ++i) {
        const Vector3& left = portals[i].left;
        const Vector3& right = portals[i].right;

        // 퍼널 범위를 포털 꼭짓점으로 점진적으로 좁혀가는 계산 진행
        // (실제 프로젝트에서는 외적 Cross Product 연산으로 좌/우 회전 방향 검증)
    }

    path.push_back(end);
    return path;
}

정리하며

수십 마리 이상의 몬스터가 동시에 이동하는 시스템에서는 연산 단위를 줄이는 최적화가 유용합니다.

NavMesh 전환: 공간을 볼록 다각형 노드로 표현하여 그래프 노드 수 절감
퍼널 알고리즘: 다각형 경로를 최단 직선 타깃 포인트로 매끄럽게 단순화
플로우 필드 도입: 단일 목표에 대해 필드를 만든 뒤 셀별 방향 조회는 $O(1)$ 이며 전체 개체 갱신은 $O(N)$
로컬 회피(RVO/ORCA) 분리: 광역 길찾기(NavMesh)와 개체 간 충돌 회피 역할을 분리

상황에 맞는 최적화 조합을 적용하고 대표 장면에서 프로파일링하면 목표 프레임 예산에 맞는 군집 AI를 구성할 수 있습니다.