상황

게임에서 몬스터 관련 작업을 하다보면 Navmesh와 관련하여 작업을 해야하는 상황이 있다.

예를 들어 몬스터 반경 30m 영역을 탐색해서, Navmesh가 깔린 곳 중 가장 높은 곳으로 이동하고 싶다고 생각해보자.

어떤 방법들로 이 상황을 해결할 수 있을까?

방법

방법 1. ProjectPointToNavigation

가장 간단한 방법은 for문으로 영역을 돌면서 `ProjectPointToNavigation’를 통해 점들을 NavMesh 상에 내리는 것이다.

코드 상으로는 다음과 같다.

  UFUNCTION(BlueprintCallable, Category = "NavPoly")
static void FindNavPoints(APawn* Actor)
{
    UWorld* World = Actor ? Actor->GetWorld() : nullptr;
    UNavigationSystemV1* NavSys = UNavigationSystemV1::GetCurrent(World);
    if (!NavSys) return;

    FVector Origin = Actor->GetActorLocation();
    float Radius = 1000.f;

    // Query box의 Z 높이를 적절히 주어야 함 (너무 낮으면 NavMesh를 못 찾음)
    FVector QueryExtent(50.f, 50.f, 300.f);  // X, Y: 지름 정도 / Z: NavMesh 높이 tolerance

    // 반지름 내 점들을 샘플링
    for (int i = 0; i < 36; ++i)
    {
        float AngleDeg = i * 10.f;
        FVector Offset = FVector(FMath::Cos(FMath::DegreesToRadians(AngleDeg)), FMath::Sin(FMath::DegreesToRadians(AngleDeg)), 0) * Radius;
        FVector TestPoint = Origin + Offset;

        FNavLocation ProjectedLocation;
        bool bProjected = NavSys->ProjectPointToNavigation(TestPoint, ProjectedLocation, QueryExtent);

        if (bProjected)
        {
            // 성공적으로 NavMesh 위로 프로젝션
            DrawDebugSphere(World, ProjectedLocation.Location, 25.f, 8, FColor::Green, false, 2.0f);
        }
        else
        {
            // 실패: NavMesh 바깥
            DrawDebugSphere(World, TestPoint, 25.f, 8, FColor::Red, false, 2.0f);
        }
    }
}

이 방법은 잘 동작하지만 두 가지 문제가 있다.

  1. 최적화 문제: 점을 Project 시키기 위해서는 QueryExtent를 적절한 크기로 지정해주어야하는데 z축 길이를 얼마 정도로 설정해야 하는가
  2. 성능 문제: ProjectPointToNavigation가 상당한 비용을 유발

그렇기에 일반적인 상황에서라면 괜찮지만 대규모로 탐색을 해야한다면 (설령 캐싱을 해서 추후엔 효율이 좋아지더라도) 좀 더 효율적인 방법을 써야할 것이다. 안 그러면 함수 한번 돌리는데 몇 ms가 측정될 것이다.

방법 2. RecastNavMesh

아래 코드와 같이 RecastNavMesh를 활용하여 검색하는 방법이 존재한다.

  #include "NavMesh/RecastNavMesh.h"

UFUNCTION(BlueprintCallable, Category = "NavPoly")
static void FindNavPointsOptimized(AActor* Actor, FVector Direction, float HalfSearchAngleDeg, float MinDist, float MaxDist)
{
    if (!Actor) return;

    UNavigationSystemV1* NavSys = UNavigationSystemV1::GetCurrent(Actor->GetWorld());
    if (!NavSys) return;

    ARecastNavMesh* RecastNavMesh = Cast<ARecastNavMesh>(NavSys->GetDefaultNavDataInstance());
    if (!RecastNavMesh) return;

    const FVector Origin = Actor->GetActorLocation();

    // 1. NavMesh Bounds Box 설정
    FBox SearchBox(
        Origin - FVector(MaxDist, MaxDist, 1000),
        Origin + FVector(MaxDist, MaxDist, 1000)
    );
    
    // 2. NavMesh 상의 폴리곤 검색
    TArray<FNavPoly> PolysInRange;
    RecastNavMesh->GetPolysInBox(SearchBox, PolysInRange);

    for (const auto& [Ref, Center] : PolysInRange)
    {
        DrawDebugSphere(Actor->GetWorld(), Center, 25.f, 8, FColor::Green, false, 3.0f);
    }
}

이 방식을 썻을 경우 캐릭터 주위를 대규모로 탐색하면 아래와 같이 점들이 꽃히게 된다.

균일하지도않고 모든 점을 탐색하지도 않는다.

하지만 전 범위에 걸쳐 Navmesh 상의 점들을 탐색하기엔 충분할 것이다.



이 방식에 대해 자세히 알아볼 것인데 그 전에 간단히 개념들을 정리해두려고 한다.

정리

UNavigationSystemV1

  • 언리얼의 최상위 내비게이션 관리자
  • NavMesh를 생성하고, 경로를 찾고, 폴리곤 정보를 쿼리할 수 있게 해줌
  • GetCurrent()로 현재 월드에 할당된 NavSys를 가져옴

ARecastNavMesh

  • 실제 NavMesh 데이터를 들고 있는 Actor 클래스
  • 내부적으로 Recast/Detour를 사용
  • GetDefaultNavDataInstance()는 현재 사용 중인 기본 NavMesh를 반환

Recast

“Navigation mesh generation toolset for games” → 게임용 NavMesh를 자동 생성해주는 오픈소스 C++ 라이브러리입니다.

Recast의 주요 기능

  • 3D 레벨을 voxelize (복셀화) 해서 보행 가능한 공간만 추출
  • 이 공간을 Convex Polygon(오목하지 않은 다각형) 으로 분해
  • 결과적으로 AI가 움직일 수 있는 2D 추상화된 영역 생성
  • Output: dtNavMesh (Detour의 입력)

Recast 처리 흐름 

  1. Level geometry (mesh, collider)
↓
2. Voxelization + Walkable Span 추출
↓
3. Region 분할 → Contour → Polygonization
↓
4. Navigation Mesh(dtNavMesh) 생성 완료

Detour

“Pathfinding and spatial reasoning toolset for games” → 위에서 만든 NavMesh를 기반으로 AI 경로 탐색을 수행하는 C++ 라이브러리.

Detour의 주요 기능

  • A* 알고리즘으로 폴리곤 간 경로 탐색
  • NavPolyRef를 기반으로 시작점~목표점 사이의 최적 경로 계산
  • StraightPath, SmoothPath 제공
  • 경로 따라 이동 가능한 위치 반환

Detour 처리 흐름 

  Input: dtNavMesh, start pos, end pos
↓
1. FindNearestPoly(start), FindNearestPoly(end)
↓
2. Pathfinding (A*)
↓
3. Return polygon list, then smooth path

FNavPoly

  • 하나의 폴리곤 단위 정보
  • 내부에 NavPolyRef(폴리곤 핸들)과 Center(중심 위치)가 있음
  • GetPolysInBox() 는 박스 영역 내의 NavMesh 폴리곤들을 가져옴

Recast + Detour 통합 개념

위 개념들을 종합했을 때 Unreal이 동작하는 방식은 아래와 같이 요약됨.

  [ Unreal Level ]
     ↓
[ Recast: NavMesh 생성 ]
     ↓
[ Detour: 경로 탐색 ]
     ↓
[ AI 이동 ]