기술 요약: 지오메트리를 활용한 내비게이션 메시 검증: 우선순위 탐색을 통한 볼록 기반 분석

문제 제기

내비게이션 메시 (navmesh) 는 비디오 게임에서 비플레이어 캐릭터 (NPC) 의 이동에 필수적이며, 보행 가능 영역과 연결성을 정의합니다. 그러나 대규모 게임 개발에서 환경은 동적이며, 지형, 애셋, 충돌 지오메트리는 빈번하게 변경됩니다. 결과적으로 내비게이션 메시는 이러한 변경 사항과 완벽하게 동기화되어 재생성되지 않는 경우가 많아, 내비게이션 데이터와 하부 지오메트리가 정의하는 실제 보행 가능 공간 간의 불일치가 발생합니다.

기존의 자동화된 검증 방법은 주로 에이전트 기반 탐색 (예: 강화 학습 에이전트가 세상을 탐색하는 것) 이나 런타임 행동 분석에 의존합니다. 이러한 접근 방식은 에이전트가 갇히거나 목표 지점에 도달하지 못하는 것과 같은 문제를 간접적으로 추론할 뿐, 내비게이션 표현이 실제 지오메트리를 정확하게 반영하는지 명시적으로 검증하지는 않습니다. 또한, 이러한 방법들은 계산 비용이 많이 들고 자동화된 파이프라인에 통합하기 어려우며, 런타임 실패로 즉시 나타나지 않는 구조적 불일치를 탐지하지 못하는 경우가 많습니다. 런타임 시뮬레이션과 독립적으로 내비게이션 메시의 정확성을 검증할 수 있는 직접적인 오프라인 방법이 부족합니다.

방법론

본 논문은 내비게이션 메시 검증을 지오메트리 일관성 문제로 취급하는 오프라인 프레임워크를 제안합니다. 에이전트 행동을 시뮬레이션하는 대신, 시스템은 환경 지오메트리에서 보행 가능 공간을 독립적으로 재구성하여 엔진이 생성한 내비게이션 메시와 비교합니다. 방법론은 세 가지 주요 구성 요소로 이루어져 있습니다:

1. 볼록 기반 보행 가능 공간 재구성

시스템은 볼록 기반 표현을 사용하여 지형 및 충돌 지오메트리에서 직접 보행 가능 공간에 대한 독립적인 참조를 재구성합니다:

• 볼록화 (Voxelization): 지형 높이도 (heightmaps) 와 애셋 충돌 메시가 이산적인 3 차원 볼록 그리드로 변환됩니다.
• 제약 조건 인식 분류: 각 볼록은 게임 엔진 설정에서 파생된 내비게이션 제약 조건 (경사 제한, 계단 높이, 에이전트 반지름, 수직 여유 공간) 에 대해 평가됩니다. 이러한 제약 조건을 충족하지 못하는 볼록은 폐기됩니다.
• 연결성 그래프: 남은 보행 가능 볼록들은 이웃 반경에 따라 결정되는 인접성을 가진 그래프 $G_v = (V_w, E)$를 형성합니다. 홍수 채우기 (flood-fill) 알고리즘이 주요 연결 요소를 추출하여 고립된 아티팩트를 제거함으로써, 지오메트리에서 유도된 도달 가능성 모델 $R_{vox}$를 생성합니다.

2. 학습 기반 우선순위 탐색

대규모 볼록 공간에 대한 포괄적인 검증을 수행하는 것은 계산적으로 불가능하므로, 프레임워크는 탐색을 우선순위 탐색 문제로 공식화합니다:

• 강화 학습 (RL): 더블 딥 Q-네트워크 (DDQN) 가 샘플링 과정을 안내하도록 훈련됩니다. RL 에이전트는 내비게이션을 시뮬레이션하는 것이 아니라, 불일치가 발생할 가능성이 높은 영역을 우선순위로 지정하는 정책을 학습합니다.
• 상태 및 보상: 상태에는 지역적 지오메트리 컨텍스트, 의미론적 중요성 (예: 순찰 경로 또는 스폰 포인트와의 근접성), 그리고 탐색 이력이 포함됩니다. 보상 함수는 의미론적으로 중요한 영역을 방문하도록 장려하면서 불필요한 단계와 재방문을 패널티로 부과합니다.
• 우선순위 경험 재생: 훈련 과정은 가치 높거나 구조적으로 복잡한 영역과 관련된 전이 (transitions) 에 초점을 맞추기 위해 우선순위 경험 재생을 사용하여 수렴을 가속화합니다.

3. 일관성 검증

RL 기반 정책에 의해 샘플링된 각 위치마다:

• 시스템은 엔진에 쿼리를 수행하여 생성된 내비게이션 메시에서의 도달 가능성 ($R_{nav}$) 을 확인합니다.
• $R_{nav}$를 지오메트리에서 유도된 도달 가능성 $R_{vox}$와 비교합니다.
• 불일치 ($R_{nav} \neq R_{vox}$) 는 잠재적인 불일치를 표시합니다.
• 후처리: 탐지된 불일치는 볼록 이산화로 인한 경미한 아티팩트를 제거하고 구조적으로 중요한 결함 영역만 유지하기 위해 허용 오차 기반 필터링과 공간 클러스터링 (연결 요소 분석) 을 거칩니다.

주요 기여

1. 지오메트리 일관성 공식화: 본 논문은 에이전트 행동 및 런타임 시뮬레이션과 검증을 분리하여, 지오메트리에서 유도된 보행 가능성과 내비게이션 메시 연결성 간의 직접적인 비교로 내비게이션 메시 검증을 공식화합니다.
2. 볼록 기반 참조 모델: 원시 지형 및 충돌 데이터에서 보행 가능 공간을 재구성하는 제약 조건 인식 볼록 기반 표현을 도입하여, 검증을 위한 독립적인 기준 진실 (ground truth) 로서 역할을 합니다.
3. 학습 기반 탐색: 본 연구는 강화 학습을 내비게이션 시뮬레이션이 아닌 탐색 우선순위 지정에 활용함을 보여줍니다. 이 접근 방식은 결함이 있을 가능성이 높은 영역에 샘플링을 집중함으로써 균일 및 휴리스틱 샘플링 전략을 능가하며 검증 효율성을 크게 향상시킵니다.
4. 프로덕션 준비 파이프라인: 이 프레임워크는 게임 엔진 내에 통합된 오프라인 도구로 설계되어, 대규모 진화형 환경을 위한 자동화된 QA 워크플로우에 병렬 처리 및 통합이 가능합니다.

실험 결과

이 프레임워크는 Unity 및 Ubisoft 의 Anvil 엔진을 사용하여 여러 대규모 프로덕션 환경에서 평가되었습니다.

• 효율성: 학습 기반 우선순위 전략은 유사한 커버리지 수준 (85% 중요도 가중 커버리지) 을 달성하기 위해 포괄적 탐색 (BFS/DFS) 보다 약 45% 적은 샘플을, 휴리스틱 중요도 기반 샘플링보다 24% 적은 샘플을 필요로 했습니다.
• 탐지: 탐지율은 모든 방법에서 유사하게 나타났으나 (~87% ~ ~92.6%), 제안된 방법은 가장 높은 탐지율 (92.6%) 을 달성하면서도 가장 적은 샘플 수 (기준 대비 55%) 로 수행되었습니다.
• 오탐 (False Positives): 허용 오차 기반 필터링 및 클러스터링 후 처리 덕분에 우선순위 RL 접근 방식은 다른 전략과 유사하거나 더 낮은 오탐율 (4.1%) 을 유지했습니다.
• 확장성: 재구성 및 검증 시간은 프로덕션 사용에 실용적인 것으로 나타났으며, 대규모 영역에 대한 전체 검증은 1~7 분 내에 완료되었습니다.

중요성 및 주장

본 논문은 이 접근 방식이 내비게이션 메시 정확성을 검증하는 직접적, 결정론적, 반복 가능한 방법을 제공한다고 주장합니다. 주로 지오메트리와 엔진 쿼리에 의존함으로써, 이 방법은 최소한의 변경으로 다양한 게임 엔진에 적용 가능합니다.

이 방법의 중요성은 "에이전트 실패를 통해 버그를 찾는 것"에서 "지오메트리 비교를 통한 구조적 일관성 검증"으로의 패러다임 전환에 있습니다. 이는 에이전트가 즉시 갇히게 하지 않더라도 세계 디자인과 내비게이션 데이터 간의 근본적인 불일치를 나타내는 내비게이션 오류를 탐지할 수 있게 합니다. 이 프레임워크는 현대 오픈 월드 게임 개발의 빠른 반복 주기에 맞춰 확장 가능하고 자동화된 품질 보증을 가능하게 하여, 비싼 런타임 시뮬레이션 없이도 내비게이션 데이터가 진화하는 게임 환경과 동기화되도록 보장합니다.