Navmesh

Girl: Dad, what is outside the navmesh
Dad: 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.
  • Model: Navmesh made by artists as they make the level.
  • Generated: The navigation mesh can be generated from the collision geometry in the game.
  • Edit: A editor for the navmesh makes it possible to modify generated ones or create new ones.
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
Subpages (3): Edit Model Navmesh Generation
Comments