Navigation meshes

A navigation mesh is a simplified triangulated surface that covers the walkable area of a scene. Pathfinding runs over this surface rather than the full scene geometry, so queries stay fast regardless of how detailed the world is.

Meep’s navmesh is a NavigationMesh — a topology of triangular faces with a BVH sitting on top. All path queries go through the same object.

Building a navmesh

NavigationMesh.build takes your scene geometry as a BinaryTopology and an agent description, and produces the walkable surface:

import { NavigationMesh } from "@woosh/meep-engine/src/engine/navigation/mesh/NavigationMesh.js";
import Vector3             from "@woosh/meep-engine/src/core/geom/Vector3.js";

const navmesh = new NavigationMesh();

navmesh.build({
    source,                              // BinaryTopology of the scene
    agent_radius:          0.4,          // metres; faces narrower than 2× this are eroded away
    agent_height:          1.8,          // metres; faces with insufficient overhead clearance are removed
    agent_max_climb_angle: Math.PI / 4,  // radians; steeper faces are excluded (default π/4)
    up:                    Vector3.up,   // world-up axis used for the climb-angle test (default Y)
});

All parameters except source are optional and fall back to safe defaults (agent_radius = 0, agent_height = 2, agent_max_climb_angle = π/4, up = Vector3.up).

Build parameters

Parameter	Type	Default	Meaning
`source`	`BinaryTopology`	required	Triangulated scene geometry to derive the mesh from.
`agent_radius`	`number`	`0`	Half-width of the agent. Faces narrower than twice this radius are eroded away.
`agent_height`	`number`	`2`	Agent standing height. Faces with insufficient vertical clearance are removed.
`agent_max_climb_angle`	`number`	`Math.PI / 4`	Maximum slope angle (radians) an agent can traverse. Steeper faces are excluded.
`up`	`Vector3`	`Vector3.up`	World up-axis against which slope angles are measured.

The build steps are: triangulate and fuse duplicate edges → merge coincident vertices → compute face normals → erode faces that violate the climb-angle constraint → enforce height clearance → rebuild adjacency → construct the BVH.

Querying a path

find_path writes a sequence of 3-D waypoints into a caller-supplied Float32Array and returns the number of points written. Points are packed XYZ triples.

const output = new Float32Array(1024 * 3); // size for up to 1024 waypoints

const count = navmesh.find_path(
    output,
    sx, sy, sz,   // start position (world space)
    gx, gy, gz,   // goal position (world space)
);

if (count === 0) {
    // no path — disconnected topology or empty mesh
} else {
    for (let i = 0; i < count; i++) {
        const x = output[i * 3];
        const y = output[i * 3 + 1];
        const z = output[i * 3 + 2];
    }
}

Signature:

find_path(output: Float32Array, sx, sy, sz, gx, gy, gz): number

Returns 0 if the mesh is empty, either point falls outside the mesh, or the topology is disconnected between them.
The first point equals the start position; the last point equals the goal position snapped onto the mesh surface.
The output buffer must have room for the full path. A cap of 1 024 points per query is hard-coded; paths requiring more faces are truncated by the A* search.

The path-finding pipeline

Each find_path call runs three stages:

Face snapping. The BVH finds the nearest face to the start and goal positions. If both land on the same face, the result is the two-point straight line and the pipeline stops early.
A over the face graph.* bt_mesh_face_find_path runs A* across the triangle adjacency graph from start face to goal face. The heuristic is squared centroid distance. The result is a sequence of face IDs, capped at 1 024 faces.
Funnel / string-pull. funnel_string_pull converts the face sequence into the minimal set of 3-D waypoints by threading a tight string through the portals (shared edges) between consecutive faces. This removes unnecessary bends that the face-level A* introduces.

The BVH is used for face snapping (step 1); the topology graph is used for A* (step 2); the per-face vertex data is used for portal construction and string-pull (step 3). All three scratch buffers are module-level, so find_path is allocation-free at query time.

Grid-based A*

For tile-based or grid worlds, a lighter alternative is available:

import { find_path_on_grid_astar } from "@woosh/meep-engine/src/engine/navigation/grid/find_path_on_grid_astar.js";

// field: flat typed array, width × height cells
// start / goal: flat indices into the field
// block_value: the value that marks an impassable cell
const path = find_path_on_grid_astar(field, width, height, start, goal, block_value);
// returns number[] of cell indices, start → goal, or [] if no path

The grid variant returns an array of cell indices with collinear segments collapsed (only turning-point indices are recorded). It uses 4-connected neighbours and a squared-distance heuristic.

Where to go next

Navigation agents — attach Path, PathFollower, and PathFollowingSystem to move an entity along a queried path.
Spatial queries — raycasts and overlap tests against physics geometry.