NavmeshGirl: Dad, what is outside the navmeshDad: The killplanes, do not go there.
A navmesh is a mesh of convex polygons that are used for path finding. It is a bit like giving the mobs a floor plan of where they are allowed to walk. The mesh is used as a search space where each polygon is a node and each edge between them is a link.
Dynamic: Possible to modify navmesh but is expansive.
Localization: Need custom data structure to speed up find a node from a world position as search all polygons is expensive :).
Memory Usage: Medium memory usage as polygon can cover any area.
It can by made by a artist, a levels designer, generated by a tool or a combination of any of these.
CalculatePath: Calculate a path between two points return the resulting path if any.
Sample: Given a position this returns the closest point that is on the navmesh.
Raycast: Trace a line between two points on the navmesh. If the ray hits a navmesh boundary return the data of what was hit.
Generating 2D Navmeshes - 2014
Navigation Graph Generation - 2011
Smoothing a Navigation Mesh Path, AIGPW3 p129-139. - 2006.
AIGP5: Automatic Cover Finding with Navigation Meshes. - 2005.
AIGP3: A Fast Approach To Navigation Meshes. p 307-320. - 2002.
AIGP: Simplified 3D Movement and Pathfinding Using Navigation Meshes. p 288-304. - 2000.