Navigation mesh
A navigation mesh, or navmesh, is an abstract data structure used in artificial intelligence applications to aid agents in path-finding through complicated spaces. This approach has been known since at least the mid-1980s in robotics, where it has been called a meadow map,Template:Sen and was popularized in video game AI in 2000.
Description
A navigation mesh is a collection of two-dimensional convex polygons (a polygon mesh) that define which areas of an environment are traversal 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.
Path-finding within one of these polygons can be done trivially in a straight line because the polygon is convex and traversal. Path-finding between polygons in the mesh can be done with one of the large number of graph search algorithms, such as A*.[1] Agents on a navmesh can thus avoid computationally expensive collision detection checks with obstacles that are part of the environment.
Representing traversal 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 traversal areas that overlap above and below at different heights.[2] The polygons of various sizes and shapes in navigation meshes can represent arbitrary environments with greater accuracy than regular grids can.[3]
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.[4] 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.[5]
History
In robotics, using linked convex polygons in this manner has been called "meadow mapping",[6] 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 Path-finding 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
- ^ S nook 2000, p. 294–295.
- ^ Snook 2000, p. 289.
- ^ Brand 2009, p. 4.
- ^ Brand 2009, p. 10.
- ^ van Toll, Cook IV & Geraerts 2012.
- ^ Tozour 2002, p. 171.
- ^ Arkin 1986.
- ^ Golodetz 2013.
- ^ van Waveren 2001, p. 24–46.
References
- Team Fortress 2 Mann VS Machine Mode and Quake III's Bots