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 공간에서 휴리스틱 평가 함수로 유클리드 거리를 사용하면 식은 다음과 같이 정의됩니다.

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

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

NavMesh(Navigation Mesh)는 이러한 문제를 구조적으로 해결합니다. 3D 지형에서 이동 가능한 구역(Walkable Area)을 불필요한 격자로 나누는 대신 볼록 다각형(Convex Polygon) 단위로 삼각분할하여 그래프 노드의 수를 수백 분의 일 수준으로 줄여줍니다.

---

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

NavMesh를 도입하더라도 동시 이동 개체가 많아지면 추가적인 최적화 기법이 필수적입니다. 단순 NavMesh A* 탐색은 다각형과 다각형 사이의 공유 변(Edge) 중심점들을 잇는 꺾인 선 형태의 경로를 생성하기 때문입니다.

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

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

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

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

---

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

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

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

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

• 상위 그래프 탐색: 출발 섹터에서 목적지 섹터까지의 대략적인 경로를 상위 그래프(Coarse Graph) 상에서 빠르게 탐색합니다.
• 하위 NavMesh 탐색: 에이전트가 현재 속한 섹터 내부에서만 세부 NavMesh A* 탐색을 실행합니다.

전체 맵 탐색 노드 수를 획기적으로 줄여 먼 거리의 길찾기 연산 시간을 90% 이상 단축할 수 있습니다.

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

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

대신 플레이어 위치를 기준으로 맵 전체에 방향 벡터장(Vector Field)을 1회 생성합니다. 각 그리드/셀마다 플레이어로 향하는 가장 빠른 방향 벡터를 저장하고 몬스터는 현재 자신이 속한 위치의 벡터 방향으로 이동만 수행합니다.

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

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

여기서 $C(x, y)$는 목표 지점으로부터의 누적 이동 비용(Cost Distance)이며 $-\nabla C$는 비용이 가장 빠르게 감소하는 방향을 뜻합니다. 몬스터 수가 아무리 증가해도 길찾기 연산 비용은 $O(1)$에 가깝게 유지됩니다.

---

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

실제 게임 엔진 C++ 환경에서 NavMesh 기반 노드 탐색과 포털(Portal) 데이터를 다루는 핵심 구조체 및 알고리즘 흐름 예시입니다.

#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;
}

---

정리하며

수십 마리 이상의 몬스터가 동시 이동하는 시스템을 구축할 때는 연산 단위 자체를 낮추는 최적화가 필수입니다.

1. NavMesh 전환: 공간을 볼록 다각형 노드로 표현하여 그래프 노드 수 절감
2. 퍼널 알고리즘: 다각형 경로를 최단 직선 타깃 포인트로 매끄럽게 단순화
3. 플로우 필드 도입: 플레이어 단일 목표 추적 시 몬스터 개수와 무관하게 $O(1)$ 이동 처리
4. 로컬 회피(RVO) 분리: 대역 길찾기(NavMesh)와 개체 간 충돌 회피(RVO) 역할을 분리하여 연산 효율 극대화

상황에 맞는 최적화 조합을 적용하면 프레임 드랍 없이 부드러운 군집 AI를 구현할 수 있습니다.