A navigation mesh, or navmesh, is an
abstract data structure
In computer science, an abstract data type (ADT) is a mathematical model for data types, defined by its behavior (semantics) from the point of view of a ''user'' of the data, specifically in terms of possible values, possible operations on data ...
used in
artificial intelligence
Artificial intelligence (AI) is the capability of computer, computational systems to perform tasks typically associated with human intelligence, such as learning, reasoning, problem-solving, perception, and decision-making. It is a field of re ...
applications to aid
agents in
pathfinding
Pathfinding or pathing is the search, by a computer application, for the shortest route between two points. It is a more practical variant on Maze-solving algorithm, solving mazes. This field of research is based heavily on Dijkstra's algorith ...
through complicated spaces. This approach has been known since at least the mid-1980s in
robotics
Robotics is the interdisciplinary study and practice of the design, construction, operation, and use of robots.
Within mechanical engineering, robotics is the design and construction of the physical structures of robots, while in computer s ...
, 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 polygon
In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is ...
s (a
polygon mesh
In 3D computer graphics and solid modeling, a polygon mesh is a collection of , s and s that defines the shape of a polyhedron, polyhedral object's surface. It simplifies Rendering (computer graphics), rendering, as in a wire-frame model. The fac ...
) 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
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
.
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
Collision detection is the computational problem of detecting an intersection of two or more objects in virtual space. More precisely, it deals with the questions of ''if'', ''when'' and ''where'' two or more objects intersect. Collision detect ...
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 might manually define the polygons of the navmesh in a
level editor
A level editor (also known as a map, campaign or scenario editor) is a game development tool used to design Level (video games), levels, maps, campaigns and virtual worlds for a video game. An individual involved with the development of game levels ...
. 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
In computer technology and telecommunications, online indicates a state of connectivity, and offline indicates a disconnected state. In modern terminology, this usually refers to an Internet connection, but (especially when expressed as "on li ...
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
A technical report (also scientific report) is a document that describes the process, progress, or results of technical or scientific research or the state of a technical or scientific research problem. It might also include recommendations and ...
by
Ronald C. Arkin.
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
The British Overseas Territories (BOTs) or alternatively referred to as the United Kingdom Overseas Territories (UKOTs) are the fourteen dependent territory, territories with a constitutional and historical link with the United Kingdom that, ...
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 engineering