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, triangulated
    agent_radius:            0.4,          // metres; the walkable area is inset by this
    agent_height:            1.8,          // metres; overhead obstacles are carved out
    agent_max_step_height:   0.3,          // metres; bridge stair-height gaps
    agent_max_step_distance: 0.5,          // metres; bridge lateral gaps
    agent_max_climb_angle:   Math.PI / 4,  // radians; steeper faces are excluded
    up:                      Vector3.up,   // world-up axis for the climb-angle test
});

source must be triangulated - run bt_mesh_triangulate first if it is not - and must have consistent outward winding, since a single face normal cannot distinguish a correctly wound floor from a flipped one.

It must also be a manifold walkable surface, not a pile of solids. Level geometry from a brush-based editor is a set of interpenetrating closed volumes - a floor brush is a sealed box whose top happens to be a floor - and fed in directly it produces a navmesh that routes almost nothing. Extract the walkable surface first: keep triangles whose normal passes the walk threshold and drop those whose space above is solid. Render geometry is not a substitute either; it produces an empty build, which is a legitimate answer to bad input and is reported as zero faces. Repair with bt_merge_vertices_by_distance, then bt_mesh_fuse_duplicate_edges, then bt_mesh_resolve_t_junctions - in that order, on a triangulated mesh - and check with bt_mesh_validate / bt_mesh_is_manifold. Neither check is run for you, because a full manifold check costs more than most builds. Repair cannot union two overlapping coplanar floor brushes; that needs a boolean union upstream. For brush-based levels, a waypoint graph traced with the collision system’s shape cast often routes more than a repaired navmesh does.

Build parameters

The build runs roughly: compute face normals and drop faces that are too steep or degenerate → weld the resulting soup and fuse duplicate edges → resolve T-junctions → erode each island’s outer boundary by the agent radius → carve obstacle footprints, pre-dilated by the radius → bridge steps and gaps if asked → split pinched vertices → fill sliver holes → collapse the redundant triangulation inherited from the render geometry → recompute face normals. NavigationMesh.build then constructs the face BVH with bt_mesh_build_face_bvh.

Build hardening

Three details are worth knowing when a navmesh comes out with unwalkable seams:

• One weld distance, NAVMESH_WELD_DISTANCE = 1e-6, is used everywhere the build merges positions. It exists to reunite the same corner reached by different arithmetic - the erosion’s cut band and the obstacle carve both reconstruct shared points per source triangle - not to simplify anything. Float32 storage resolution raises it where it is finer.
• A short-edge kill pre-pass runs before every merge. A face with an edge shorter than what the merge treats as one point survives the merge as a loop that visits the same vertex twice - a non-manifold edge, which is an unwalkable boundary. bt_mesh_kill_short_edges removes those faces first; bt_mesh_split_pinched_vertices afterwards separates vertices where two sheets of surface meet at a single point, which is what a hairline crack from the carve leaves behind and what otherwise stops every boundary walk dead.
• Overhead obstacles are carved as footprints, not sampled. A group of overhead faces sharing a vertex is carved as its convex hull when the group’s triangles tile that hull, and triangle by triangle when they do not - an L-shape, a doorway frame, two obstacles that merely touch. Both routes carve the same ground wherever the hull is valid (dilation by a disc distributes over union); the hull is kept only because it is cheaper. The result is the true offset of the obstacle - straight along edges, a clean arc at corners - rather than the wavy contour that sampling-then-eroding produced. Footprints go in a quad-tree, so each soup triangle only tests the ones that can overlap it: O(m log k) for m soup triangles and k footprints.

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. It assumes the surface is manifold and does not check: on a non-manifold surface it can read a released vertex and throw from inside Polyanya rather than return 0. If the input is in doubt, validate once at build time rather than defensively per query.

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 or the start and goal faces are in different connected components.
• The first and last points are the start and goal snapped onto the mesh surface, so they may differ from the raw inputs when those lie off the mesh.
• The output buffer must have room for the full path; size it for the worst case you expect.

The path-finding pipeline

Each find_path call runs two stages:

1. Face snapping. bt_mesh_find_nearest_face uses the BVH to find the nearest face to each of the start and goal positions. Each snapped point is then nudged a thousandth of the way toward its face’s centroid: the search degenerates when a point sits exactly on a triangle edge, which snapped, grid-aligned queries do constantly.

2. Polyanya. bt_mesh_face_find_path_polyanya computes the exact any-angle geodesic across the surface (Cui, Harabor and Grastien, IJCAI 2017). Search nodes are (root, interval) pairs - an interval on a mesh edge, seen from a point the path is already taut through - and expanding one projects the visibility cone into the triangle beyond, clipping it against that triangle’s far edges. The path turns only at obstacle corners; there is no corridor-then-string-pull step, because there is no corridor.

The search is planar but intrinsic: it follows the surface by unfolding each triangle into the frame accumulated along its own corridor, so the costs are true geodesic distances on a sloped or folded navmesh, not only on a flat one. No global up-axis is assumed. The A* heuristic measures with straight 3-D chords, which lower-bound the geodesic and are therefore admissible.

The output follows the surface too. It is subdivided wherever the geodesic crosses a face boundary, so every emitted segment lies within a single triangle and the path never flies over a convex crease nor tunnels through a concave fold. Collinear runs are collapsed, so on a planar mesh what comes out is just the minimal corner polyline.

Scratch buffers are module-level, so find_path is allocation-free at query time once the search-node pool has grown to size. bt_mesh_face_find_path - plain A* over the triangle adjacency graph - and funnel_string_pull ship, but NavigationMesh.find_path does not use them.

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.
• Math & geometry - BinaryTopology and the bt_* family the navmesh is built and queried with.