Validating Navmesh using Geometry: Voxel-Based Analysis with Prioritized Exploration
Ramesh Raghavan, Ojas Sharma, Sebastien Larrue, Alan Isaac Kunder, Aakash Sai, Rishi Mathur · 2026
Read Validating Navmesh using Geometry: Voxel-Based Analysis with Prioritized Exploration by Ramesh Raghavan, Ojas Sharma, Sebastien Larrue, Alan Isaac Kunder, Aakash Sai, Rishi Mathur (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21397.txt.
Introduction
Ramesh Raghavan and co-authors present a method for validating navmeshes using geometry, with voxel-based analysis and prioritized exploration. Navmesh flaws break pathing for non-playable characters in game worlds. Navmeshes are built from world geometry, but terrain edits and moved assets during development create mismatches with the actual world. Existing automated checks rely on exploration agents and reinforcement learning, using navmesh data itself or judging behavior indirectly. The new method instead checks on its own whether the navmesh reflects walkable space defined by underlying geometry.
Catalog record
| CREATOR | Ramesh Raghavan, Ojas Sharma, Sebastien Larrue, Alan Isaac Kunder, Aakash Sai, Rishi Mathur |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47684 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.21397
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Validating Navmesh using Geometry: Voxel-Based Analysis with Prioritized Exploration Ramesh Raghavan, Ojas Sharma, Sebastien Larrue, Alan Isaac Kunder, Aakash Sai, Rishi Mathur Abstract Navigation mesh (Navmesh) inconsistencies affect the player experience by directly impacting the navigation systems used by non-playable characters (NPCs) in game environments. While navmeshes are generated from world geometry using well-established algorithms, environments change throughout development as terrain is adjusted and assets are moved or replaced. Due to the large scale of these environments, frequent updates, and dependencies on collision data and navmesh generation parameters, navmeshes are not always regenerated in sync with environmental changes, resulting in mismatches between the navmesh and the actual environment. Existing automated approaches attempt to detect navigation issues using exploration agents, reinforcement learning, and other agent-driven techniques. However, since these methods typically rely on the navigation data itself or evaluate navigation behavior indirectly, they do not explicitly verify whether the navigation representation accurately reflects the true walkable space defined by the underlying geometry. This paper presents a framework for validating navigation meshes through an independent, geometry-driven analysis of navmesh correctness. The approach reconstructs walkable space directly from environment geometry using a voxel-based representation, followed by constraint-aware traversal and connectivity evaluation. Rather than treating validation as uniform exploration, it is formulated as a prioritized search problem over the voxel space, where reinforcement learning is used to guide sampling toward regions more likely to exhibit inconsistencies. At each sampled location, reachability derived from the voxel representation is compared against reachability obtained from the navmesh via engine-level queries. Compared to uniform and random sampling strategies, the proposed method improves validation efficiency by reducing the number of samples needed to adequately explore the validation space. Experiments across multiple large-scale open-world game environments show that the approach consistently lowers exploration effort while maintaining similar defect detection coverage. The framework runs offline within the game engine and can be integrated into automated quality assurance pipelines, allowing it to scale with large and continuously evolving environments. Since the method relies primarily on geometry and engine queries, it can be adapted across different game engines with minimal changes, making it suitable for production-level deployment. I Introduction Navigation meshes (navmeshes) are widely used in video games to represent traversable regions and support pathfinding for non-playable characters (NPCs). They specify which parts of an environment are walkable and how those regions connect, forming the basis for efficient navigation in complex game worlds. In large-scale game development, environments rarely remain static. Designers and artists continuously update terrain, assets, and collision geometry as the world evolves, and navmeshes are typically regenerated through build or integration pipelines to reflect these changes. In practice, however, keeping the navmesh perfectly aligned with the underlying geometry is not always straightforward. The scale of modern environments, frequent updates, and dependencies on collision data and generation parameters can introduce mismatches. Even small changes or slightly misaligned collision data may result in missing or incorrect walkable regions, which in turn can cause unexpected traversal paths or navigation failures for NPCs during gameplay. Fig. 1: Example of a navmesh inconsistency where the baked navmesh does not match the underlying geometry, leading to broken traversal in the highlighted region. Detecting these issues is often inefficient. Traditional approaches rely heavily on manual testing or agent-based exploration [ 1 , 2 , 4 ] , where problems are inferred indirectly from navigation behavior, such as agents getting stuck or failing to reach their targets. These methods detect issues only after they manifest at runtime, are computationally expensive, and are difficult to integrate into automated pipelines. A direct method for validating navmesh correctness independent of runtime behavior remains lacking. To address this, navmesh validation is formulated as a geometry-consistency problem, where the objective is to verify whether the navmesh accurately represents walkable space derived from environment geometry. An offline framework is introduced that reconstructs walkable space using a voxel-based representation, followed by constraint-aware traversal and connectivity analysis. Let V denote the set of voxels derived from terrain and collision geometry, and let W\subseteq V represent walkable voxels. Connectivity is represented as G=(W,E), (1) where E defines adjacency between neighboring voxels. Since voxelized environments can be large, exhaustive validation is expensive and uniform exploration is inefficient, as inconsistencies are often localized. Therefore, the validation is treated as a prioritized exploration problem and use reinforcement learning to guide sampling toward regions more likely to contain inconsistencies. Importantly, reinforcement learning is used for prioritization rather than simulating navigation behavior. For each sampled location, reachability derived from the voxel model R_{vox}(w) is compared with navmesh reachability R_{nav}(w) . A potential inconsistency is detected when R_{nav}(w)\neq R_{vox}(w), (2) indicating a mismatch between geometry-derived walkability and navmesh connectivity. Detected inconsistencies are refined using tolerance-based filtering and spatial clustering. At a high level, navmesh validation is formulated as a geometry-consistency problem based on reachability agreement between two independent representations of walkable space. Instead of relying on agent behavior or assuming the correctness of the navmesh, the proposed method explicitly identifies inconsistencies as regions where geometry-derived reachability and navmesh reachability differ. This formulation enables direct verification of navigation correctness independent of runtime simulation and decouples validation from navigation execution. The key contributions of this work are: • A formulation of navmesh validation as a geometry-consistency problem, enabling direct verification of navigation correctness independent of agent-based exploration. • A voxel-based representation of walkable space with constraint-aware traversal, capturing walkable regions from terrain and collision data. • A learning-guided exploration strategy that prioritizes regions with a higher likelihood of navigation inconsistencies, improving validation efficiency over both uniform and heuristic sampling strategies. • An offline validation pipeline that is designed to integrate with automated QA workflows in large-scale game development. II Related Work Research on navigation systems in games encompasses automated gameplay testing, exploration-based bug detection, navmesh construction, and coverage-driven exploration strategies. Existing studies often identify navigation issues indirectly by analyzing agent behavior during gameplay, whereas others aim to enhance navmesh generation algorithms. Despite these efforts, direct validation of navmesh correctness remains relatively unexplored. In contrast, this study directly validates navmesh correctness by comparing it to geometry-derived walkable space. II-A Automated Gameplay Testing and Exploration Automated exploration techniques are widely used to evaluate complex game environments. A well-known example is the Go-Explore framework [ 1 ] , which enables systematic exploration of large state spaces. Similar methods have been applied to automated gameplay testing and navigation validation through exploration-driven agents [ 2 , 7 ] . Reinforcement learning has also been explored to identify navigation or collision issues by observing agent behavior under different policies [ 4 ] . However, these approaches (e.g., [ 2 ] ) primarily rely on behavioral signals and remain closely tied to agent policies, making direct verification of the underlying navigation representation difficult. More broadly, automated game testing research has explored reinforcement learning, evolutionary methods, and coverage-driven exploration strategies for detecting gameplay bugs and unreachable states [ 20 , 21 ] . Recent work has also investigated vision-language models for video game QA tasks such as glitch detection, visual regression testing, and bug report generation [ 26 ] . However, these approaches still rely on runtime interaction or visual inference rather than explicitly validating the correctness of the underlying navigation representation. II-B