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.
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
In computer science, graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by the order in which the vertices are visited. Tree traversal ...
algorithms, such as
A*. 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. The polygons of various sizes and shapes in navigation meshes can represent arbitrary environments with greater accuracy than regular grids can.
Creation
Navigation meshes can be created manually, automatically, or by some combination of the two. In video games, a
level designer
In video games, a level (also referred to as a map, stage, or round in some older games) is any space available to the player during the course of completion of an objective. Video game levels generally have progressively-increasing difficulty ...
might manually define the polygons of the navmesh in a
level editor. This approach can be quite labor intensive. 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.
History
In robotics, using linked convex polygons in this manner has been called "meadow mapping", coined in a 1986
technical report by
Ronald C. Arkin
Ronald Craig Arkin (born 1949) is an American roboticist and roboethicist, and a Regents' Professor in the School of Interactive Computing, College of Computing at the Georgia Institute of Technology. He is known for the motor schema techniq ...
.
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''. 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''.
Notes
References
*
*
*
*
*
*
*
External links
UDK: Navigation Mesh ReferenceSource Engine: Navigation MeshesCry Engine Navigation And AI
{{DEFAULTSORT:Navigation Mesh
Graph data structures
Video game development
Computational physics
Robotics