NavMesh 기반 몬스터 Pathfinding과 경로 최적화 기법

NavMesh가 해결하는 문제

몬스터의 이동은 단순히 목표 위치를 향해 직선으로 이동하는 문제가 아니다. 벽, 장애물, 낭떠러지처럼 이동할 수 없는 공간을 피하면서 자연스러운 경로를 찾아야 한다. 이때 모든 지형을 격자로 나누고 탐색하면 구현은 단순하지만 넓은 월드와 많은 에이전트에서는 탐색 비용이 빠르게 커진다.

NavMesh는 실제로 이동 가능한 표면만 다각형 영역으로 표현한다. 몬스터는 이동 불가능한 공간을 탐색 대상에서 제외하고 연결된 다각형을 따라 목표까지의 경로를 찾는다. 지상 몬스터, 비행 몬스터, 수영 몬스터처럼 이동 규칙이 다른 경우에는 별도의 NavMesh 영역이나 에이전트 설정을 두는 방식으로 확장할 수 있다.

NavMesh 다각형 위에서 장애물을 피해 목표를 향하는 몬스터 경로

경로 탐색의 기본 흐름

대부분의 NavMesh 시스템은 다음 단계를 거친다.

시작 위치와 목표 위치를 가장 가까운 NavMesh 위 점으로 보정한다.
시작 다각형과 목표 다각형 사이에서 다각형 연결 관계를 탐색한다.
탐색 결과를 통로 형태의 경로로 만든다.
통로 안에서 실제 이동에 적합한 코너 지점을 계산한다.
이동 중 목표나 환경이 바뀌면 필요한 경우에만 경로를 다시 계산한다.

다각형 그래프 탐색에는 보통 A*가 사용된다. A*의 평가는 현재까지의 누적 비용과 목표까지의 추정 비용을 더해 결정한다.

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

여기서 $g(n)$ 은 시작점부터 현재 노드까지의 비용이고 $h(n)$ 은 현재 노드에서 목표까지의 예상 비용이다. 휴리스틱이 실제 최단 비용을 과대평가하지 않으면 최단 경로를 유지하면서 불필요한 탐색을 줄일 수 있다.

경로는 찾았지만 움직임이 어색한 이유

NavMesh 경로가 존재한다고 해서 몬스터가 곧바로 자연스럽게 움직이는 것은 아니다. 흔한 문제는 다음과 같다.

코너마다 정확히 꺾으려다 지그재그 이동이 발생한다.
목표가 조금 움직일 때마다 경로를 재탐색한다.
좁은 통로에 여러 몬스터가 동시에 진입해 서로 밀린다.
목표가 NavMesh 밖에 있어 계속 도달 불가능한 경로를 요청한다.

따라서 경로 탐색과 실제 조향을 분리해서 설계하는 것이 중요하다. 경로 탐색은 상대적으로 비싼 전역 판단이고 조향은 매 프레임 또는 짧은 주기마다 수행하는 지역 판단이다.

코너 수 줄이기와 경로 평활화

경로 결과가 여러 코너를 포함한다면 모든 점을 반드시 방문할 필요는 없다. 현재 위치에서 더 먼 코너까지 직선 이동이 가능한지 검사하고 가능하다면 중간 코너를 건너뛴다. 이를 line of sight 검사 또는 string pulling 계열의 경로 평활화라고 부른다.

NavMesh 통로에서는 funnel 알고리즘이 대표적이다. 좌우 경계점으로 이루어진 통로를 따라가며 실제로 필요한 꺾임만 골라낸다. 엔진의 NavMesh 에이전트가 코너 목록을 제공하더라도 게임 규칙에 맞는 후처리는 별도로 고려할 수 있다.

bool CanSkipToCorner(const Vector3& current, const Vector3& candidate)
{
    NavMeshHit hit;
    return NavMesh::Raycast(current, candidate, hit) == false;
}

void AdvanceCorner(Path& path, const Vector3& current)
{
    while (path.nextCorner + 1 < path.corners.size())
    {
        const Vector3& farther = path.corners[path.nextCorner + 1];
        if (!CanSkipToCorner(current, farther))
            break;

        ++path.nextCorner;
    }
}

이 방식은 코너 수를 줄여 움직임을 부드럽게 만들지만 벽을 통과하지 않도록 NavMesh 레이캐스트나 충돌 검사를 사용해야 한다. 단순 물리 레이캐스트만으로 판단하면 NavMesh 상의 이동 가능 여부와 불일치할 수 있다.

재탐색 빈도 제어

가장 비용이 큰 실수 중 하나는 추적 대상의 위치가 갱신될 때마다 모든 몬스터가 경로를 다시 계산하는 것이다. 목표가 계속 움직이더라도 이전 경로가 한동안 유효할 수 있다.

재탐색은 다음 조건을 조합해 제한하는 편이 좋다.

목표가 마지막 경로 요청 위치에서 일정 거리 이상 이동했을 때
현재 경로의 남은 길이가 의미 있게 달라졌을 때
장애물 변경으로 경로가 막혔을 때
일정 시간 이상 경로를 갱신하지 않았을 때
몬스터가 진행하지 못하는 상태가 일정 시간 지속됐을 때

bool ShouldRepath(Vector3 targetPosition, float now)
{
    const float targetMoveThreshold = 1.5f;
    const float minRepathInterval = 0.25f;

    if (now - lastPathRequestTime < minRepathInterval)
        return false;

    if (Vector3.Distance(targetPosition, lastRequestedTarget) >= targetMoveThreshold)
        return true;

    return agent.isPathStale || IsStuck();
}

이 값들은 고정된 정답이 아니다. 빠르게 이동하는 보스와 느린 근접 몬스터는 서로 다른 임계값을 가져야 한다. 특히 다수의 몬스터가 같은 플레이어를 추적하는 게임에서는 재탐색 요청을 프레임마다 분산하는 것만으로도 순간적인 CPU 부하를 크게 줄일 수 있다.

군집 이동: 전역 경로와 지역 회피를 분리한다

NavMesh 경로는 목적지까지 가는 큰 방향을 제시할 뿐 바로 옆 몬스터와의 충돌까지 완벽하게 해결하지는 않는다. 수십 마리가 같은 목표를 추적할 때는 전역 경로와 지역 회피를 함께 다뤄야 한다.

전역 경로는 낮은 빈도로 계산하고 지역 회피는 주변 에이전트의 속도와 거리만 보고 짧은 시간 범위에서 조정한다. 대표적인 방법으로는 분리 조향, 우선순위 기반 회피, RVO(Reciprocal Velocity Obstacles) 계열 회피가 있다.

Vector3 CalculateSteering(const Vector3& desiredVelocity,
                          const Vector3& separationVelocity,
                          float maxSpeed)
{
    Vector3 velocity = desiredVelocity + separationVelocity;
    return ClampMagnitude(velocity, maxSpeed);
}

분리 조향만으로도 간단한 군집은 처리할 수 있지만 좁은 문 앞에서는 서로 밀어내며 정체될 수 있다. 이런 구간에는 통과 우선순위를 주거나 목표 주변에 여러 개의 도착 슬롯을 배정하는 방식이 더 안정적이다.

여러 몬스터가 공통 경로를 따르되 지역 회피로 간격을 유지하는 모습

목표 지점을 그대로 쓰지 말아야 하는 경우

플레이어의 실제 위치가 NavMesh 밖에 있거나 벽 너머에 있거나 몬스터가 설 수 없는 높이에 있을 수 있다. 이 위치를 그대로 목적지로 사용하면 경로 실패가 반복될 수 있다.

목표를 설정하기 전에 가까운 유효 NavMesh 점을 찾고 공격 사거리 안에서 멈춰야 하는 몬스터라면 플레이어 위치 대신 공격 가능한 접근 지점을 목적지로 잡는 것이 좋다. 여러 몬스터가 한 점으로 몰리는 것도 줄일 수 있다.

bool TryGetReachableTarget(Vector3 desiredTarget, out Vector3 navTarget)
{
    if (NavMesh.SamplePosition(desiredTarget, out var hit, 2.0f, NavMesh.AllAreas))
    {
        navTarget = hit.position;
        return true;
    }

    navTarget = default;
    return false;
}

단, 탐색 반경을 지나치게 크게 두면 벽 반대편이나 다른 층의 NavMesh를 선택할 수 있다. 게임의 층 구조와 이동 규칙에 맞춰 반경과 영역 마스크를 제한해야 한다.

동적 장애물은 필요한 곳에만 사용한다

문, 상자, 이동 발판처럼 환경이 바뀌는 요소는 NavMesh에 영향을 준다. 하지만 모든 움직이는 오브젝트를 매 순간 NavMesh 장애물로 처리하면 갱신 비용이 커질 수 있다.

작은 오브젝트나 다른 몬스터는 지역 회피와 물리 충돌로 처리하고 실제로 통로를 닫거나 열어 경로 자체를 바꾸는 요소에만 동적 장애물 또는 NavMesh 갱신을 적용하는 편이 일반적이다. 자주 변하는 대형 지형이라면 NavMesh를 매번 다시 굽는 방식보다 타일 단위 갱신이나 별도 링크 활성화가 적합한지 검토해야 한다.

측정 기준을 먼저 정한다

최적화는 체감만으로 판단하기 어렵다. 다음 수치를 기록하면 병목을 찾기 쉽다.

초당 경로 요청 수와 성공률
경로 계산 시간의 평균 및 최대값
몬스터 한 마리당 평균 코너 수
정체 상태에 머문 시간
지역 회피 계산 시간
NavMesh 갱신 횟수와 갱신 시간

예를 들어 경로 계산 시간은 낮은데 몬스터가 자주 멈춘다면 문제는 A*가 아니라 지역 회피나 목적지 배정일 가능성이 높다. 반대로 특정 순간에 프레임이 튄다면 같은 프레임에 몰린 경로 요청이나 동적 NavMesh 갱신을 먼저 의심할 수 있다.

정리

NavMesh 기반 이동의 핵심은 최단 경로만 찾는 데 있지 않다. 경로를 필요한 시점에만 계산하고 코너를 정리하며 주변 충돌은 지역 회피로 해결해야 많은 몬스터가 있어도 안정적으로 동작한다.

먼저 경로 요청 수와 재탐색 조건을 측정하고 그다음 경로 평활화와 군집 회피를 적용하는 순서가 좋다. 이 순서로 접근하면 시각적 자연스러움과 성능 문제를 분리해서 해결할 수 있다.