Navigation Mesh

Live Demo: NavMesh

A navigation mesh is a set of convex polygons (usually triangles) covering the walkable surfaces of a level. Instead of testing every world point for walkability, AI agents pathfind through connected triangles and then smooth the resulting path through shared edges. The nightshade navmesh combines Recast generation, three pathfinding algorithms, funnel-based path smoothing, and an agent movement system with local avoidance.

NavMesh generation

Generation runs the Recast pipeline through the rerecast crate. The pipeline has 13 steps.

1. Build trimesh. Collect every mesh vertex and index from the scene.
2. Mark walkable triangles. Classify each triangle by slope against the walkable threshold.
3. Create heightfield. Rasterize the scene into a voxel grid at the configured cell size and height.
4. Rasterize triangles. Project each walkable triangle into the heightfield.
5. Filter obstacles. Remove low-hanging obstacles, ledge spans, and low-height spans agents cannot traverse.
6. Compact heightfield. Convert to a more efficient representation for region building.
7. Erode walkable area. Shrink walkable areas by the agent radius so agents do not clip walls.
8. Build distance field. Compute the distance from each cell to the nearest boundary.
9. Create regions. Group connected cells into regions with watershed partitioning. min_region_size (default 8) filters tiny regions and merge_region_size (default 20) combines small adjacent ones.
10. Build contours. Trace region boundaries into simplified contour polygons controlled by max_simplification_error.
11. Convert to polygon mesh. Triangulate contours into convex polygons up to max_vertices_per_polygon (default 6).
12. Generate detail mesh. Add interior detail vertices for height accuracy, controlled by detail_sample_dist and detail_sample_max_error.
13. Convert to NavMeshWorld. Build the engine's navmesh data structure with adjacency and spatial hash.

Pathfinding algorithms

Three algorithms are available.

A* (default) explores nodes ordered by f = g + h, where g is the cost so far and h is the straight-line distance to the goal. It finds the optimal path efficiently by prioritizing nodes closer to the destination.

Dijkstra explores nodes ordered by g only, ignoring direction to the goal. It explores more nodes but guarantees the shortest path even with complex cost functions.

Greedy best-first explores nodes ordered by h only, ignoring path cost. It is the fastest of the three and the only one of the three that can miss the optimal path. The failure case is concave obstacles.

All three operate on the triangle adjacency graph. Edges connect triangles that share an edge, and costs are the distances between triangle centers.

Funnel algorithm

Raw paths through the navmesh are sequences of triangle centers, which zig-zag unnecessarily. The funnel algorithm produces straight, natural-looking paths in three steps.

1. Portal collection. Extract the shared edges (portals) between consecutive triangles in the path.
2. Funnel narrowing. Maintain a funnel of left and right boundaries that starts wide at the first portal. As portals are consumed, the funnel narrows. When a portal would flip the funnel inside-out, emit the funnel apex as a waypoint and restart from there.
3. Simplification. Remove waypoints that do not improve the path within an epsilon tolerance (collinear-point removal).

The result is the shortest path through the triangle corridor that does not cross any triangle boundaries.

Agent movement

Five systems run each frame inside run_navmesh_systems.

1. Triangle tracking. Find which navmesh triangle each agent occupies using point-in-triangle tests with barycentric coordinates.
2. Path processing. Agents in PathPending state get their path computed, smoothed, and simplified. The state transitions to Moving or NoPath.
3. Local avoidance. Repulsive forces between nearby agents (within agent_radius * 2.5) prevent crowding. The avoidance velocity is blended at 25% with the primary movement direction.
4. Movement. Advance agents along waypoints at their configured speed. Sample the navmesh height at each new position using barycentric interpolation for vertical alignment. The maximum step height is 1.0 unit, which prevents teleporting through terrain.
5. Surface snapping. Idle and arrived agents are snapped to the navmesh surface when their Y position drifts more than 0.01 units.

Enabling navmesh

[dependencies]
nightshade = { git = "...", features = ["engine", "navmesh"] }

Generating a navmesh

#![allow(unused)]
fn main() {
use nightshade::ecs::navmesh::*;

fn setup_navmesh(world: &mut World) {
    let config = RecastNavMeshConfig::default();
    generate_navmesh_recast(world, &config);
}
}

NavMesh configuration

#![allow(unused)]
fn main() {
pub struct RecastNavMeshConfig {
    pub agent_radius: f32,              // Character collision radius (0.4)
    pub agent_height: f32,              // Character height (1.8)
    pub cell_size_fraction: f32,        // XZ voxel resolution divisor (3.0)
    pub cell_height_fraction: f32,      // Y voxel resolution divisor (6.0)
    pub walkable_climb: f32,            // Max step height (0.4)
    pub walkable_slope_angle: f32,      // Max walkable slope in degrees (45)
    pub min_region_size: i32,           // Min region area (8)
    pub merge_region_size: i32,         // Region merge threshold (20)
    pub max_simplification_error: f32,  // Contour simplification (1.3)
    pub max_vertices_per_polygon: i32,  // Polygon complexity (6)
    pub detail_sample_dist: f32,        // Detail mesh sampling (6.0)
    pub detail_sample_max_error: f32,   // Detail mesh error (1.0)
}
}

Agent state machine

Idle -> PathPending -> Moving -> Arrived
              |
           NoPath

Creating agents

#![allow(unused)]
fn main() {
let agent = spawn_navmesh_agent(world, position, speed);
}

Setting destinations

#![allow(unused)]
fn main() {
set_agent_destination(world, agent, target_position);
}

Running the navigation system

#![allow(unused)]
fn main() {
fn run_systems(&mut self, world: &mut World) {
    run_navmesh_systems(world);
}
}

Checking agent status

#![allow(unused)]
fn main() {
match get_agent_state(world, agent) {
    NavMeshAgentState::Idle => { /* waiting */ }
    NavMeshAgentState::PathPending => { /* computing */ }
    NavMeshAgentState::Moving => { /* walking */ }
    NavMeshAgentState::Arrived => { /* at destination */ }
    NavMeshAgentState::NoPath => { /* unreachable */ }
}
}

Patrol behavior

#![allow(unused)]
fn main() {
struct PatrolBehavior {
    waypoints: Vec<Vec3>,
    current_waypoint: usize,
}

fn update_patrol(world: &mut World, agent: Entity, patrol: &mut PatrolBehavior) {
    if matches!(get_agent_state(world, agent), NavMeshAgentState::Arrived) {
        patrol.current_waypoint = (patrol.current_waypoint + 1) % patrol.waypoints.len();
        set_agent_destination(world, agent, patrol.waypoints[patrol.current_waypoint]);
    }
}
}

Debug visualization

#![allow(unused)]
fn main() {
set_navmesh_debug_draw(world, true);
}

The debug visualization draws navmesh triangles as green wireframe (offset 0.15 units above the surface), agent paths as yellow lines between waypoints, the current path segment as a cyan line from agent to next waypoint, waypoints as orange crosses, and the destination as a magenta diamond marker with a vertical pole.

NavMeshWorld resource

The generated navmesh lives in world.resources.navmesh as a NavMeshWorld.

• Vertices. All navmesh vertex positions.
• Triangles. Walkable triangles with center, normal, area, and edge indices.
• Edges. Triangle edges with indices of the two triangles they belong to, used for portal detection.
• Adjacency. HashMap<usize, Vec<NavMeshConnection>> mapping each triangle to its neighbors with traversal costs.
• Spatial hash. A grid-based spatial index for fast point-in-triangle queries.