Hubbry Logo
Navigation meshNavigation meshMain
Open search
Navigation mesh
Community hub
Navigation mesh
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Navigation mesh
Navigation mesh
Navigation mesh
View on Wikipedia
from Wikipedia

A navigation mesh, or navmesh, is an abstract data structure used in artificial intelligence applications to aid agents in pathfinding through complicated spaces. This approach has been known since at least the mid-1980s in robotics, where it has been called a meadow map,[1] and was popularized in video game AI in 2000.

Description

[edit]

A navigation mesh is a collection of two-dimensional convex polygons (a polygon mesh) that define which areas of an environment are traversable by agents. In other words, a character in a game could freely walk around within these areas unobstructed by trees, lava, or other barriers that are part of the environment. Adjacent polygons are connected to each other in a graph.

Pathfinding within one of these polygons can be done trivially in a straight line because the polygon is convex and traversable. Pathfinding between polygons in the mesh can be done with one of the large number of graph search algorithms, such as A*.[2] Agents on a navmesh can thus avoid computationally expensive collision detection checks with obstacles that are part of the environment.

Representing traversable areas in a 2D-like form simplifies calculations that would otherwise need to be done in the "true" 3D environment, yet unlike a 2D grid it allows traversable areas that overlap above and below at different heights.[3] The polygons of various sizes and shapes in navigation meshes can represent arbitrary environments with greater accuracy than regular grids can.[4]

Creation

[edit]

Navigation meshes can be created manually, automatically, or by some combination of the two. In video games, a level designer might manually define the polygons of the navmesh in a level editor. This approach can be quite labor intensive.[5] Alternatively, an application could be created that takes the level geometry as input and automatically outputs a navmesh.

It is commonly assumed that the environment represented by a navmesh is static – it does not change over time – and thus the navmesh can be created offline and be immutable. However, there has been some investigation of online updating of navmeshes for dynamic environments.[6]

History

[edit]

In robotics, using linked convex polygons in this manner has been called "meadow mapping",[1] coined in a 1986 technical report by Ronald C. Arkin.[7]

Navigation meshes in video game artificial intelligence are usually credited to Greg Snook's 2000 article "Simplified 3D Movement and Pathfinding Using Navigation Meshes" in Game Programming Gems.[8] In 2001, J.M.P. van Waveren described a similar structure with convex and connected 3D polygons, dubbed the "Area Awareness System", used for bots in Quake III Arena.[9]

Notes

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Navigation mesh

View on Grokipedia
from Grokipedia
A navigation mesh, commonly abbreviated as navmesh, is a geometric in that represents the traversable surfaces of a virtual 3D environment as a collection of interconnected convex polygons, typically triangles, forming a graph suitable for efficient and by agents. It discretizes the free space (walkable areas excluding obstacles) into a cell complex, allowing algorithms like A* to compute collision-free paths that appear natural and optimal within the constraints of agent size and environment geometry. The concept of navigation meshes originated in the computer games industry in the early 2000s, with foundational contributions including Greg Snook's 2000 description of simplified 3D movement techniques using such meshes and Paul Tozour's 2002 method for constructing near-optimal versions to minimize path computation costs. These early works built on broader principles, such as and graphs, to address the limitations of grid-based in complex, irregular environments like those in video games or simulations. Over time, navigation meshes have evolved to support dynamic updates for changing environments, multi-layered structures (e.g., multi-story buildings), and , with key advancements like Marcelo Kallmann's 2014 local clearance triangulations enabling robust encoding of agent clearance distances for safer navigation. Navigation meshes are generated through methods that fall into exact and approximate categories: exact approaches, such as explicit corridor maps or local clearance triangulations, produce precise polygonal decompositions with provable linear in the number of obstacles, while voxel-based techniques like Recast voxelize the environment into a 3D grid before extracting and simplifying walkable surfaces into polygons for broader applicability to arbitrary . Compared to uniform grids, navigation meshes offer significant advantages, including fewer nodes for sparser graphs that yield shorter, more direct paths; better handling of uneven without axis-aligned artifacts; and easier integration with rendering meshes for real-time applications in games, , and . They facilitate not only single-agent path queries but also collective behaviors, such as or evasion, by providing a shared representation of navigable .

Fundamentals

Definition and Basic Concepts

A navigation mesh, often abbreviated as navmesh, is an abstract composed of two-dimensional convex polygons that represent traversable areas in a three-dimensional environment. These polygons, typically arranged in a representation where boundaries are defined on a with associated heights, cover walkable surfaces such as floors and ramps while excluding obstacles like walls or pits. By approximating the environment's in this manner, a navigation mesh provides a compact and efficient model for spatial reasoning in virtual worlds. This structure simplifies navigation by partitioning complex spaces into non-overlapping, walkable regions that are connected at their edges, allowing agents to move freely within each polygon via straight-line paths. Adjacent polygons share edges known as portals, which serve as gateways for transitioning between regions and enable algorithms to compute smooth, collision-free trajectories across the mesh. Additionally, off-mesh links connect non-adjacent polygons or handle special movements, such as jumps over gaps or climbing ladders, by defining direct shortcuts outside the standard walkable surface. Navigation meshes play a prerequisite role in AI pathfinding for autonomous agents, such as robots in simulated environments or non-player characters in video games, by transforming the continuous space into a discrete graph suitable for search-based planning. This discretization facilitates efficient computation of viable routes, often serving as input to graph search algorithms like A* for finding optimal paths from start to goal positions.

Mathematical Representation

A navigation mesh can be formalized as a G=(V,E,F)G = (V, E, F), where the vertices VV correspond to the corners of the polygons defining the walkable areas, the edges EE represent the boundaries between adjacent polygons or portals connecting non-adjacent regions, and the faces FF are the convex polygons partitioning the free space. The geometric properties of this representation ensure that each face in FF is a , typically a or simple , which guarantees that any two points within the same face can be connected by a straight-line path without intersecting obstacles. Validation of these properties often involves triangulation techniques, such as , to confirm convexity and non-overlapping faces while preserving the empty-circle criterion for robust partitioning. For efficient traversal, the graph employs adjacency lists to store neighboring faces for each vertex or face, enabling rapid queries for connected regions during path planning. In three-dimensional extensions, additional data such as height values at vertices or angles along edges are incorporated to model vertical constraints and variations. Path costs between adjacent polygons are typically based on the distance between their representative points, such as centroids, with possible adjustments for terrain features like slopes.

Construction Methods

Manual Creation

Manual creation of navigation meshes involves designers directly configuring walkable areas within level editors of game engines, such as Unity or , to define precise polygonal representations for static environments. In Unity, using the AI Navigation package (as of Unity 2022 and later), this process involves adding a NavMeshSurface component to a GameObject that encloses the area, configuring agent radius and height in the component's settings, specifying input sources (such as static geometry marked via the Static Editor Flags in the Inspector), and then baking the surface to generate the polygons. Similarly, in , designers place Nav Mesh Bounds Volume actors to enclose the level area, then use Navigation Modifier Volumes to manually shape or exclude regions from the generated mesh, ensuring alignment with the environment's layout. Key guidelines for polygon design emphasize maintaining convexity to guarantee straight-line movement within each cell, as non-convex shapes can introduce artifacts. Designers avoid creating thin corridors narrower than the agent's to prevent failures, and explicitly mark obstacles by applying navigation blockers or modifiers to exclude unwalkable areas like walls or furniture. Special cases, such as multi-level structures, require separate navigation surfaces or layers; for instance, Unity's NavMeshSurface component allows assigning distinct meshes to different floors, while off-mesh connections handle transitions like jumps or ladders by placing OffMeshLink components between non-adjacent areas. In , Navigation Proxy Links serve a similar purpose, manually connecting disparate mesh sections for non-walkable paths such as stairs or gaps. The advantages of manual control include highly optimized meshes tailored to fixed levels, reducing computational overhead and enabling fine-tuned agent behavior in predictable environments.

Automated Generation

Automated generation of navigation meshes involves computational algorithms that process 3D to produce polygonal representations of traversable spaces, enabling efficient in large-scale environments such as video games or robotic simulations. These methods prioritize scalability by decomposing complex scenes into manageable polygons while accounting for agent constraints like size and mobility. Key approaches include partitioning techniques that ensure complete coverage of free space without manual intervention, falling into exact and approximate categories. Exact methods produce precise decompositions with guarantees on complexity. For example, Local Clearance (LCT) compute a where each triangle encodes the local clearance distance to obstacles, allowing robust for agents of varying sizes; the construction involves refinement operations on an initial triangulation to insert clearance information, achieving linear complexity in obstacle count. Similarly, Explicit Corridor Maps (ECM) use the (a Voronoi-like structure) to define corridor-based regions between obstacles, constructed in O(n log n) time by computing bisectors and annotations for connectivity, providing exact paths without approximation errors and supporting multi-layered environments. Voronoi diagram-based methods partition the free space around obstacles by constructing regions equidistant from obstacle boundaries, forming a or that defines convex navigation polygons. This approach, rooted in , generates meshes by computing Voronoi cells from obstacle vertices and edges, ensuring safe clearance for agents and avoiding narrow passages unsuitable for . For instance, in environments with obstacles, the diagram's edges serve as connectivity links in the resulting graph representation, promoting scalability for large worlds by reducing polygon counts through natural space division. Such methods excel in handling irregular geometries, as demonstrated in growth-based extensions where Voronoi partitioning integrates with adaptive region expansion to cover 100% of traversable areas, outperforming alternatives like in region quality and completeness. Wavefront propagation and flood-fill algorithms build polygons by expanding regions from seed points placed near obstacles, iteratively growing traversable areas until boundaries are defined. In the Iterative Wavefront Edge Expansion method, seeds are positioned adjacent to obstruction edges, and expansion proceeds via radial sweeps to detect event points like parallel edges or vertices, resolving collisions by splitting or contracting polygons to form convex cells. This , with a time complexity of O(n*m) where n is the number of obstructions and m is the number of regions, ensures high-order meshes with fewer degenerate polygons compared to traditional . Flood-fill variants, often used in region growing, propagate from walkable voxels to group connected areas, filtering based on and before contour tracing to extract boundaries, enabling robust construction in voxelized inputs. For dynamic environments where obstacles change in real-time, incremental updates repair only affected regions to maintain without full regeneration. Techniques inspired by Voronoi diagrams use local adjustments: upon obstacle insertion, bisectors are computed to split cells in O(x + log n) time (x updated edges, n total vertices), while deletion recomputes the axis within the freed cell in O(x log x) time, preserving connectivity via an Explicit Corridor Map. Hierarchical navmeshes address scalability by creating multi-level abstractions, where lower-level polygons are clustered into higher-level nodes using k-way partitioning, supporting real-time modifications through localized updates and reducing overhead in vast scenes. For example, the HNA* hierarchy achieves up to 7.7x speedup over standard A* by precomputing sub-paths across levels, with partitioning minimizing edge cuts for efficient dynamic adjustments. Popular tools like the Recast/Detour library facilitate runtime generation by voxelizing input meshes, applying walkability filters, and producing tiled navmeshes for streaming large worlds. Recast's process includes rasterization into voxels, non-walkable filtering, and polygonal region division via contouring, with handling queries on the output. Customization occurs through parameters such as agent radius, which shrinks traversable areas to ensure clearance (typically set to the maximum agent size), and max slope, which defines the steepest walkable angle (e.g., 45 degrees) to exclude inclines beyond agent capability, allowing tailored meshes for diverse agent types without recomputing the entire structure. Tiled outputs support incremental updates by regenerating only modified tiles, enhancing performance in dynamic scenarios.

Pathfinding Applications

Core Algorithms

Navigation meshes enable efficient pathfinding by representing traversable areas as a graph of interconnected convex polygons, where each polygon serves as a node and shared edges act as connections. The primary algorithm for resolving path queries on this graph is an adaptation of the A* search algorithm, which finds an optimal path from a starting point to a goal by exploring nodes in order of increasing estimated total cost. In this context, the cost function f(n) for a node n is defined as f(n) = g(n) + h(n), where g(n) is the exact path cost accumulated from the start node to n—typically the sum of Euclidean distances along the traversed edges—and h(n) is an admissible heuristic estimating the cost from n to the goal, commonly the straight-line Euclidean distance from n to the goal position, ensuring the algorithm remains optimal since the navmesh approximates free space without obstacles within polygons. The raw path output by A* often consists of a sequence of polygon centers or entry/exit points, resulting in jagged routes that hug polygon boundaries unnecessarily. To produce smoother, more natural trajectories, post-processing techniques such as the funnel algorithm (also known as string pulling) are applied to the sequence of polygons forming a "channel" between start and goal. This method iteratively tightens the path by identifying left and right apex vertices along the channel boundaries—treating shared edges as portals—and connecting the start directly to visible apexes or the goal via straight lines that remain within the valid area, effectively minimizing length while avoiding obstacles. The Simple Stupid Funnel Algorithm, a efficient variant, processes vertices in counter-clockwise order to update apexes dynamically, ensuring the final path comprises few straight-line segments suitable for agent steering. For multi-agent scenarios, where multiple agents navigate simultaneously on the same navmesh, global paths from A* are combined with local collision avoidance using Reciprocal Velocity Obstacles (RVO). RVO computes preferred velocities for each agent by considering the relative velocities and positions of neighbors, selecting a new that minimizes deviation from the global path while ensuring no collisions occur within a ; this reciprocal approach assumes symmetric agent reactions, reducing oscillations in dense crowds. Integration involves sampling agent positions on the navmesh for global planning and applying RVO updates at each simulation step to adjust velocities locally, enabling realistic group behaviors without central coordination. Navmesh queries extend beyond basic paths to support diverse applications, including point-to-point via A* on the graph, area searches that identify all reachable regions within a specified or cone (often using or distance fields on the graph), and random generation for or behaviors by uniformly sampling points on the mesh surface and snapping them to the nearest valid location via or proximity tests. These operations leverage the mesh's geometric structure for fast resolution, with point location queries enabling efficient insertion of start/goal points into polygons.

Integration in AI Systems

Navigation meshes are embedded into broader AI frameworks by serving as a queryable that informs agent in systems like behavior trees and finite state machines. In behavior trees, navigation mesh queries are executed as part of leaf actions to compute feasible paths, enabling agents to adaptively pursue goals or evade obstacles while maintaining hierarchical task decomposition. For example, a reinforcement learning-enhanced agent in games uses navmesh invocation to switch between global navigation and local maneuvers, dynamically predicted by the AI model to preserve behavioral diversity over rigid rule-based alternatives. Similarly, finite state machines integrate navmesh in movement states, where transitions trigger queries to generate trajectories toward waypoints, ensuring responsive locomotion within predefined behavioral modes. In video games, this systemic integration supports realistic agent behaviors, as seen in series titles where navmesh data drives AI planning by evaluating reachability to the player or interactive objects, pruning infeasible actions to optimize decisions like engaging in melee combat or retreating to ranged positions. In robotics, navigation meshes are incorporated into the (ROS) via specialized stacks like Mesh Navigation, which processes 3D triangle meshes to generate paths on irregular terrains, layering obstacle and traversability data for autonomous vehicle control. These examples highlight how navmesh queries feed into higher-level AI loops, such as action selection in planners, to produce context-aware movement without recomputing full environments. Handling large-scale environments often involves hierarchical navmesh structures, where a global coarse provides high-level and local fine-grained meshes refine immediate actions, reducing computational overhead in expansive worlds. This approach combines long-horizon planning on integrated traversability maps with short-term prediction, allowing agents to navigate dynamic obstacles while adhering to overarching goals. For instance, A* adaptations on the global mesh generate subgoals that guide local reactive policies. Multi-agent coordination leverages shared navigation meshes to enable simulations and , where agents query the common mesh for collision-free paths and velocity adjustments, promoting emergent group behaviors like or evacuation flows. In such systems, the mesh's polygonal representation ensures scalable interactions among hundreds of agents, with techniques like clearance-based adjustments preventing bottlenecks at narrow passages.

Advantages and Limitations

Key Benefits

Navigation meshes provide significant computational efficiency over traditional grid-based pathfinding methods by using fewer nodes—polygons instead of numerous grid cells—which reduces the graph size and enables faster real-time path queries, particularly in complex environments where grid resolution can lead to exponential increases in processing time. This efficiency stems from the mesh's ability to represent walkable areas more coarsely yet accurately, allowing algorithms like A* to traverse smaller graphs without sacrificing path optimality. A key advantage is the generation of more natural paths through straight-line traversal within convex polygons, which eliminates the grid-like artifacts such as unnatural zigzagging or stair-step movements that occur when agents are constrained to cell edges or corners. This approach leverages the geometric properties of the mesh to produce smoother, more realistic trajectories that align closely with human-like navigation. In three-dimensional terrains, navigation meshes excel in scalability by intuitively accommodating slopes, varying heights, and irregular obstacles through their surface-adhering polygonal structure, outperforming waypoint systems that demand manual placement and struggle with continuous elevation changes. This makes them particularly suitable for simulations of complex outdoor or indoor environments with varying , where such complexity would otherwise require excessive waypoint density. Furthermore, navigation meshes achieve high memory efficiency with their compact polygonal representations, which store only essential connectivity data for large-scale environments, contrasting with the dense storage demands of grid-based alternatives.

Challenges and Drawbacks

Traditional navigation meshes are typically static data structures, which poses significant challenges in dynamic environments where obstacles or terrain change frequently. Updating the mesh to account for moving objects or environmental modifications often requires recomputing affected portions or the entire structure, an operation that is computationally expensive and often impractical in real-time applications without specialized methods. This limitation stems from the assumption in most basic path planners that obstacles remain fixed, leading to outdated paths or the need for frequent regenerations that can disrupt ongoing simulations. Automated generation of navigation meshes, particularly using voxel-based methods like those in Recast, introduces complexity in producing optimal polygons, especially in highly irregular or cluttered spaces. These approaches rely on grid resolutions that can misalign with environmental geometry, resulting in suboptimal decompositions such as missed navigable areas or overly fragmented polygons. The mathematical complexity of exact methods, such as Exact Cell Decomposition with O(n log n) construction time in 2D, further exacerbates generation overhead in complex scenes. Edge cases, including narrow passages and vertical navigation, highlight additional drawbacks that increase overall complexity. In narrow corridors, voxel alignment and agent radius considerations often lead to incomplete coverage, with methods like Constrained Delaunay Graphs failing to capture tight spaces even at high resolutions above 90%. Vertical transitions, such as climbing or jumping between levels, require supplementary off-mesh links to bridge disconnected surfaces, adding manual configuration and potential points of failure in the mesh topology. In very large or densely populated scenes, navigation meshes can suffer performance bottlenecks, particularly during multi-agent path queries. Voxel-based generators like Recast may exceed memory limits in expansive environments, leading to crashes or excessive preprocessing times, while the detailed increases the computational cost of algorithms compared to simpler representations. This scalability issue is pronounced in scenarios with numerous agents, where query resolution times grow due to the mesh's intricate structure.

History and Development

Origins in Robotics

The origins of navigation meshes trace back to robotics research in the mid-1980s, where they emerged as a structured approach to enable efficient path planning for mobile robots in complex environments. In 1986, Ronald C. Arkin introduced the concept of "meadow maps" in his work on vision-based navigation. A meadow map represents the robot's free space as a hybrid structure: a of the traversable area into interconnected convex polygonal regions, augmented with a vertex graph that connects these regions. This polygonal partitioning is achieved through recursive subdivision of the initial bounding area, accounting for obstacle models derived from data, allowing for global path computation via graph-based algorithms such as A*. The purpose was to provide a discrete, query-efficient representation that balanced computational demands with the need for collision-free trajectories in indoor settings. Meadow maps evolved from earlier reactive navigation techniques, particularly artificial potential fields, which had gained prominence around the same time for their real-time reactivity but were prone to local minima traps and lacked global optimality guarantees. Potential fields model the environment with attractive forces toward goals and repulsive forces from obstacles, guiding the robot via gradient descent; however, they often failed in cluttered spaces without additional mechanisms. In contrast, polygonal representations like meadow maps offered exact, topology-preserving decompositions that supported deliberate planning, shifting toward hybrid systems combining global deliberation with local reactivity. Arkin's subsequent development of the AuRA (Autonomous Robot Architecture) in 1987 integrated meadow maps into a hierarchical framework, where high-level path planning on the mesh informed low-level motor schema-based control for dynamic obstacle avoidance. This hierarchical approach enabled robust navigation by sequencing plans across abstraction levels, from coarse polygonal routes to fine-grained sensor-driven adjustments. Advancements in the 1990s further refined these polygonal methods through exact cell decomposition techniques, which systematically partition free space into non-overlapping cells—often trapezoids or convex polygons—ensuring complete coverage without overlaps or gaps. Seminal work in this era, building on foundations, emphasized practical algorithms for real-time decomposition in robotic systems, such as trapezoidal decompositions that facilitate visibility graphs for shortest-path queries. These methods improved upon earlier approximations by guaranteeing completeness in path existence checks, crucial for reliable in uncertain environments. Key contributions included efficient handling of polygonal obstacles via linear-time decompositions, as explored in robotics-specific implementations for . Early applications of these navigation mesh precursors appeared in autonomous s for indoor localization and navigation tasks. Arkin's system, tested on platforms like the Denning equipped with ultrasonic and video sensors, used maps to localize the within mapped environments and generate executable paths, demonstrating feasibility in structured indoor spaces. Similar polygonal representations supported path in early autonomous vehicles, such as those developed at institutions like , where decomposed maps aided in obstacle avoidance and trajectory generation during on-road and off-road trials in the late 1980s and 1990s. These efforts highlighted the meshes' role in bridging , , and control for real-world robotic deployment.

Adoption in Video Games

The adoption of navigation meshes in video games gained momentum in the early 2000s, as developers sought efficient solutions for AI pathfinding in complex 3D environments beyond traditional grid-based methods. This shift simplified movement calculations by representing walkable areas as interconnected polygons, enabling more natural NPC behaviors without excessive computational overhead. A pivotal introduction came through Greg Snook's chapter in the 2000 anthology Game Programming Gems, where he detailed practical techniques for "Simplified 3D Movement and Using Navigation Meshes," making the concept accessible and applicable to game development workflows. This work emphasized generating convex polygons from level to support seamless traversal, influencing subsequent AI implementations in the industry. One of the earliest commercial applications appeared in 2001 with J.M.P. van Waveren's master's thesis on the bot AI, which incorporated an Area Awareness System (AAS) functioning as a navigation mesh. The AAS divided environments into convex polygonal areas with defined connectivity, allowing bots to perform automated through arbitrary 3D spaces in real-time multiplayer matches. By the mid-2000s, navigation meshes became staples in major engines, streamlining integration for developers. Unreal Engine's NavMesh system, introduced in version 3 around 2006, provided automated generation and querying tools based on the Recast library, supporting dynamic updates for AI in action-oriented titles. Unity followed suit with built-in NavMesh support starting in version 3.5 in 2010, offering editor-based baking and runtime components like NavMeshAgent for straightforward path computation. These tools profoundly impacted open-world and multiplayer genres by enabling scalable NPC navigation. In (2011), navigation meshes underpin the expansive world, allowing hundreds of NPCs to follow realistic paths across , doors, and obstacles without manual scripting for every route. In multiplayer games like , they facilitate dynamic NPC behaviors, such as bots adapting to player-induced changes in combat arenas for fluid, responsive encounters.

Recent Advancements

Since the 2010s, hierarchical navigation meshes have emerged as a significant advancement to enhance pathfinding efficiency in large-scale environments. The Hierarchical NavMesh Path-finding algorithm (HNA*), introduced in 2016, employs a bottom-up approach using multilevel k-way partitioning to construct multi-resolution layers that abstract the navigation mesh into coarser hierarchies for global planning and finer details for local refinement. This structure enables global-to-local path queries by first searching high-level clusters and then refining sub-paths, significantly reducing the number of nodes evaluated compared to standard A* on flat navmeshes. Evaluations demonstrate speedups of up to 7.7 times in pathfinding queries while preserving geometric accuracy, making it suitable for real-time applications in expansive virtual worlds. Advancements in dynamic updates have addressed the limitations of static navmeshes by incorporating techniques for real-time adaptation to changing environments, particularly through the . Local repair methods focus on incrementally modifying only affected regions of the mesh in response to obstacles or terrain alterations, avoiding full rebuilds to maintain performance. Recent in dynamic path planning has further optimized these updates for autonomous systems, achieving real-time replanning with improved smoothness and avoidance in evolving scenarios. Additionally, GPU-accelerated regeneration has gained traction, leveraging parallel processing to voxelize and triangulate meshes rapidly, enabling frequent updates in high-fidelity simulations without compromising latency. Current tools have incorporated these advancements for practical deployment, notably in game engines and . Unity's AI Navigation package, updated through versions 1.1 and beyond since 2023, supports runtime navmesh baking via NavMeshSurface components, allowing dynamic generation and updates for procedurally loaded scenes with minimal performance impact. In VR/AR and , navmeshes facilitate immersive navigation; for instance, the NavARNode framework (2025) dynamically constructs navmeshes from user-placed AR nodes for indoor , integrating A* for multi-floor traversability without pre-modeled environments. Such applications extend to robotic systems, where vision-guided navmeshes enable autonomous wheeled navigation in 3D dynamic spaces using RGB-D sensors for real-time obstacle integration.

References

  1. https://www.cs.umd.edu/class/spring2018/cmsc425/Lects/lect15-nav-mesh.pdf
  2. http://graphics.ucmerced.edu/papers/16-chap-navm.pdf
  3. https://www.cs.upc.edu/~npelechano/MIG2016_Wouter.pdf
  4. http://graphics.ucmerced.edu/papers/14-tog-lct.pdf
  5. https://www.researchgate.net/publication/271406656_Automatic_Generated_Navigation_Mesh_Algorithm_on_3D_Game_Scene
  6. http://gamma.cs.unc.edu/Menge/docs/code/menge/html/class_menge_1_1_nav_mesh.html
  7. https://dl.acm.org/doi/10.1145/2994258.2994262
  8. https://www.ijcai.org/proceedings/2017/0070.pdf
  9. https://www.gamedev.net/tutorials/programming/artificial-intelligence/navigation-meshes-and-pathfinding-r4880/
  10. https://www.diva-portal.org/smash/get/diva2:1560399/FULLTEXT01.pdf
  11. https://www.jdxdev.com/blog/2021/07/06/rts-pathfinding-2-dynamic-navmesh-with-constrained-delaunay-triangles/
  12. https://www.mdpi.com/2032-6653/16/7/382
  13. https://www.gamedev.net/forums/topic/706750-creating-a-navigation-mesh-2d/
  14. https://learn.unity.com/tutorial/fps-mod-Create-and-Bake-the-NavMesh?projectId=5d9c91a4edbc2a03209169ab
  15. https://docs.unity3d.com/Packages/[email protected]/manual/NavMeshSurface.html
  16. https://dev.epicgames.com/documentation/en-us/unreal-engine/overview-of-how-to-modify-the-navigation-mesh-in-unreal-engine
  17. https://docs.unity3d.com/Packages/[email protected]/manual/index.html
  18. https://docs.unity3d.com/ScriptReference/OffMeshLink.html
  19. https://recastnav.com/
  20. https://webspace.science.uu.nl/~gerae101/pdf/The_Explicit_Corridor_Map_-_Using_the_Medial_Axis_for_Real-Time_Path_Planning_and_Crowd_Simulation_SoCG_2016.pdf
  21. https://ninercommons.charlotte.edu/record/870/files/Hale_uncc_0694D_10272.pdf
  22. http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter19_Creating_High-Order_Navigation_Meshes_through_Iterative_Wavefront_Edge_Expansions.pdf
  23. https://doi.org/10.1002/cav.1468
  24. https://www.cs.upc.edu/~npelechano/Pelechano_HNAstar_prePrint.pdf
  25. https://recastnav.com/structrcConfig.html
  26. http://paper.ijcsns.org/07_book/201212/20121208.pdf
  27. https://www.researchgate.net/publication/221073351_Reciprocal_Velocity_Obstacles_for_Real-Time_Multi-agent_Navigation
  28. https://arxiv.org/pdf/2410.04936
  29. https://ieeexplore.ieee.org/document/10162655
  30. https://www.gamedeveloper.com/programming/postmortem-ai-action-planning-on-assassins-creed-odyssey-and-immortals-fenyx-rising-
  31. https://github.com/naturerobots/mesh_navigation
  32. https://arxiv.org/pdf/2408.00343
  33. https://www.researchgate.net/publication/306026033_3D_Navigation_Mesh_Generation_for_Path_Planning_in_Uneven_Terrain
  34. https://www.researchgate.net/publication/236903107_A_Navigation_Mesh_for_Dynamic_Environments
  35. https://web.cs.umass.edu/publication/docs/1988/UM-CS-1988-007.pdf
  36. https://www.ri.cmu.edu/pub_files/pub3/singh_sanjiv_1991_1/singh_sanjiv_1991_1.pdf
  37. https://www.gamedev.net/tutorials/programming/artificial-intelligence/navigation-graph-generation-r2805/
  38. http://www.kbs.twi.tudelft.nl/docs/MSc/2001/Waveren_Jean-Paul_van/thesis.pdf
  39. https://www.afkmods.com/index.php?/topic/5229-navmesh-repair/
  40. https://dl.acm.org/doi/10.1016/j.cag.2016.05.023
  41. https://www.mdpi.com/1424-8220/24/24/8089
  42. http://www.diva-portal.org/smash/get/diva2:1104795/FULLTEXT02.pdf
  43. https://www.mdpi.com/2078-2489/16/6/478
  44. https://www.mdpi.com/2076-3417/15/5/2323
Add your contribution
Related Hubs
User Avatar
No comments yet.