기하학적 구조를 이용한 Navmesh 검증: 우선순위 탐색을 활용한 복셀 기반 분석

내비게이션 메쉬 (Navigation mesh, Navmesh)의 불일치는 게임 환경 내 비플레이어 캐릭터 (Non-playable characters, NPCs)가 사용하는 내비게이션 시스템에 직접적인 영향을 미쳐 플레이어 경험을 저해합니다. Navmesh는 잘 확립된 알고리즘을 사용하여 월드 기하학 (Geometry)으로부터 생성되지만, 개발 과정에서 지형이 조정되거나 에셋이 이동 또는 교체됨에 따라 환경이 변화하며, 결과적으로 Navmesh와 실제 환경 간의 불일치가 발생합니다. 기존의 자동화된 접근 방식들은 탐색 에이전트 (Exploration agents)와 강화학습 (Reinforcement learning) 기술을 사용하여 내비게이션 문제를 탐지하려고 시도합니다. 그러나 이러한 방법들은 내비게이션 데이터 자체에 의존하거나 내비게이션 동작을 간접적으로 평가하기 때문에, 내비게이션 표현이 하위 기하학에 의해 정의된 보행 가능 공간 (Walkable space)을 명시적으로 반영하는지 여부를 검증하지 못합니다. 본 논문은 Navmesh의 정확성을 기하학 기반의 독립적인 분석을 통해 검증하는 프레임워크를 제시합니다. 이 접근 방식은 복셀 기반 표현 (Voxel-based representation)을 사용하여 환경 기하학으로부터 보행 가능 공간을 직접 재구성한 다음, 제약 조건 인식 순회 (Constraint-aware traversal) 및 연결성 평가를 수행합니다. 검증은 복셀 공간에 대한 우선순위 탐색 문제로 공식화되며, 여기서 강화학습 (Reinforcement learning)은 불일치가 나타날 가능성이 더 높은 영역으로 샘플링을 유도합니다. 각 샘플링된 위치에서, 복셀 표현으로부터 도출된 도달 가능성 (Reachability)을 엔진 수준의 쿼리를 통해 얻은 Navmesh의 도달 가능성과 비교합니다. 여러 대규모 오픈 월드 게임 환경에 걸친 실험을 통해, 이 접근 방식이 결함 탐지 범위 (Defect detection coverage)를 유사하게 유지하면서도 탐색 노력 (Exploration effort)을 일관되게 낮춘다는 것을 보여줍니다. 이 프레임워크는 게임 엔진 내에서 오프라인으로 실행되며 자동화된 품질 보증 (Quality assurance) 파이프라인에 통합될 수 있습니다. 이 방법은 기하학에 의존하기 때문에 최소한의 변경만으로 다양한 게임 엔진에 맞춰 조정될 수 있어 실제 제작 환경 (Production deployment)에 적용하기 적합합니다.