Navmesh
Girl: 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.
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
- Mapping the Island’s Walkable Surfaces - 2012
- Navigation Graph Generation - 2011
- Navigation #GDC11
- Trivial navigation mesh generation I - 2010
- Trivial navigation mesh generation II - 2010
- There’s a Hole in Your NavMesh, Dear Zombie - 2009
- Grid Computing for Artificial Intelligence - 2007
- 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.
- Bethesda Tutorial Navmesh