navmeshes

A navmesh, or navigation mesh, is a data structure used in games and robotics to represent the traversable space in a 3D environment. It consists of a collection of polygons that define walkable surfaces, while non-walkable areas such as walls are omitted. Polygons are typically convex to simplify pathfinding, and the mesh includes connectivity data and optional traversal costs.

Generation is usually performed by baking from the scene, applying constraints like maximum slope, step height, and minimum area. Tools let designers edit the result or add off-mesh links for actions such as jumping or climbing. In dynamic scenes, navmeshes may be rebuilt or updated incrementally.

Data structure and routing: Navmeshes form a graph where polygons are nodes and shared edges or portals are connections. Pathfinding uses algorithms such as A* or Dijkstra on this graph, producing a sequence of polygons that an agent can traverse, which is then converted into a concrete path.

Movement: After a path is found, agents perform smoothing and steering to follow the route, while local obstacle avoidance handles moving obstacles and temporary obstructions.

Advantages and limitations: Navmeshes reduce the search space and handle variable terrain, making navigation more robust in 3D spaces. They require careful generation and maintenance; changing geometry may necessitate re-baking, and highly dynamic scenes can be challenging to support efficiently.

Variants: Off-mesh links for jumps, ladders, or teleporters extend the model. Dynamic navmeshes adapt to changes, while hybrid approaches combine navmeshes with other representations like grids when appropriate.