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.

    • 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