Navigation mesh

Source: Wikipedia, the free encyclopedia.

A navigation mesh, or navmesh, is an

video game AI
in 2000.

Description

A navigation mesh is a collection of two-dimensional

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 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",[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

  1. ^ a b Tozour 2002, p. 171.
  2. ^ Snook 2000, p. 294–295.
  3. ^ Snook 2000, p. 289.
  4. ^ Brand 2009, p. 4.
  5. ^ Brand 2009, p. 10.
  6. ^ van Toll, Cook IV & Geraerts 2012.
  7. ^ Arkin 1986.
  8. ^ Golodetz 2013.
  9. ^ van Waveren 2001, p. 24–46.

References

  • Arkin, Ronald C. (1986). "Path Planning for a Vision-Based Autonomous Robot" (PDF) (Technical Report). University of Massachusetts. {{cite journal}}: Cite journal requires |journal= (help)
  • Brand, Sandy (2009). Efficient obstacle avoidance using autonomously generated navigation meshes (PDF) (Master thesis). Delft University of Technology. Retrieved 2015-06-09.
  • Golodetz, Stuart (October 2013). "Automatic Navigation Mesh Generation in Configuration Space". Overload. 117. ACCU.
  • 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
    .
  • 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
    .
  • 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.
    S2CID 2996937
    . Retrieved 2015-06-09.
  • van Waveren, J.M.P. (2001-01-28). The Quake III Arena Bot (PDF) (M.Sc. thesis). Delft University of Technology.

External links

Retrieved from "https://en.wikipedia.org/w/index.php?title=Navigation_mesh&oldid=1216651065"