Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Navigation mesh
Geometry data for pathfinding

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, and was popularized in video game AI in 2000.

We don't have any images related to Navigation mesh yet.
We don't have any YouTube videos related to Navigation mesh yet.
We don't have any PDF documents related to Navigation mesh yet.
We don't have any Books related to Navigation mesh yet.
We don't have any archived web articles related to Navigation mesh yet.

Description

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

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

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

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.9 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.10

Notes

References

  1. Tozour 2002, p. 171. - Tozour, Paul (2002). "Building a Near-Optimal Navigation Mesh". In Rabin, Steve (ed.). AI Game Programming Wisdom. Charles River Media. pp. 171–185. ISBN 1-58450-077-8. https://archive.org/details/aigameprogrammin00rabi_088 ↩

  2. Snook 2000, p. 294–295. - Snook, Greg (2000). "Simplified 3D Movement and Pathfinding Using Navigation Meshes". In DeLoura, Mark (ed.). Game Programming Gems. Charles River Media. pp. 288–304. ISBN 1-58450-049-2. ↩

  3. Snook 2000, p. 289. - Snook, Greg (2000). "Simplified 3D Movement and Pathfinding Using Navigation Meshes". In DeLoura, Mark (ed.). Game Programming Gems. Charles River Media. pp. 288–304. ISBN 1-58450-049-2. ↩

  4. Brand 2009, p. 4. - Brand, Sandy (2009). Efficient obstacle avoidance using autonomously generated navigation meshes (PDF) (Master thesis). Delft University of Technology. Retrieved 2015-06-09. http://repository.tudelft.nl/assets/uuid:f558ade0-a168-42ff-a878-09d1cf1e5eb9/Thesis_Sandy_Brand_2009.pdf ↩

  5. Brand 2009, p. 10. - Brand, Sandy (2009). Efficient obstacle avoidance using autonomously generated navigation meshes (PDF) (Master thesis). Delft University of Technology. Retrieved 2015-06-09. http://repository.tudelft.nl/assets/uuid:f558ade0-a168-42ff-a878-09d1cf1e5eb9/Thesis_Sandy_Brand_2009.pdf ↩

  6. van Toll, Cook IV & Geraerts 2012. - van Toll, Wouter G.; Cook IV, Atlas F.; Geraerts, Roland (2012). "A navigation mesh for dynamic environments" (PDF). Computer Animation and Virtual Worlds. 23 (6). John Wiley & Sons: 535–546. doi:10.1002/cav.1468. S2CID 2996937. Retrieved 2015-06-09. http://www.staff.science.uu.nl/~gerae101/pdf/CAVW_Dynamic_ECM.pdf ↩

  7. Tozour 2002, p. 171. - Tozour, Paul (2002). "Building a Near-Optimal Navigation Mesh". In Rabin, Steve (ed.). AI Game Programming Wisdom. Charles River Media. pp. 171–185. ISBN 1-58450-077-8. https://archive.org/details/aigameprogrammin00rabi_088 ↩

  8. Arkin 1986. - Arkin, Ronald C. (1986). "Path Planning for a Vision-Based Autonomous Robot" (PDF) (Technical Report). University of Massachusetts. http://www.cc.gatech.edu/ai/robot-lab/online-publications/ieee/path86.pdf ↩

  9. Golodetz 2013. - Golodetz, Stuart (October 2013). "Automatic Navigation Mesh Generation in Configuration Space". Overload. 117. ACCU. http://accu.org/index.php/journals/1838 ↩

  10. van Waveren 2001, p. 24–46. - van Waveren, J.M.P. (2001-01-28). The Quake III Arena Bot (PDF) (M.Sc. thesis). Delft University of Technology. http://www.kbs.twi.tudelft.nl/docs/MSc/2001/Waveren_Jean-Paul_van/thesis.pdf ↩