Navigation mesh

A navigation mesh, or navmesh, is an abstract data structure used in artificial intelligence applications to help agents find paths through complicated spaces. It is a collection of two-dimensional convex polygons, a polygon mesh, that mark which areas of an environment an agent can traverse, with adjacent polygons connected to each other in a graph. Movement inside one convex polygon is a straight line, and movement between polygons can be found with a graph search algorithm such as A*, so agents avoid costly collision checks against obstacles in the environment. Unlike a two-dimensional grid, a navmesh can represent traversable areas that overlap above and below at different heights, and its polygons of varying sizes can describe arbitrary environments more accurately than regular grids. Meshes can be built by hand in a level editor, generated automatically from level geometry, or both. The approach has been known since at least the mid-1980s in robotics, where it was called a meadow map, and it was popularized in video game AI in 2000.