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.
Planning:
Smoothing:
Navmesh Creation
It can by made by a artist, a levels designer, generated by a tool or a combination of any of these.
Common operations
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.
Dynamic Navmesh
Reference
Clearance for diversity of agents’ sizes in Navigation Meshes - 2015
Getting off the NavMesh: Navigating in Fully 3D Environments - 2015
Generating 2D Navmeshes - 2014
A Generalized Exact Arbitrary Clearance Technique for Navigation Meshes. - 2013
Navigation Graph Generation - 2011
Navigation #GDC11
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.