NavMesh navigation

Files

src

lib

src/main.js

// A capsule, built as a Shade `Geometry`.
//
// meep 3 ships seven primitive generators (box, plane, polyhedron, octahedron,
// torus, cylinder, torus knot) and a capsule is not one of them, so the demos
// that draw capsule-shaped bodies carry this local builder. Same convention as
// the physics `CapsuleShape3D` it usually accompanies: `radius` is the cap
// radius, `height` is the length of the cylindrical middle (so the total tip to
// tip length is `height + 2 * radius`), and the axis is Y.

import { Attribute } from "@woosh/meep-engine/src/shade/renderer/geometry/Attribute.js";
import { Geometry } from "@woosh/meep-engine/src/shade/renderer/geometry/Geometry.js";
import { StandardAttributes } from "@woosh/meep-engine/src/shade/renderer/geometry/StandardAttributes.js";

/**
 * @param {number} [radius] cap radius
 * @param {number} [height] length of the cylindrical middle section
 * @param {number} [capSegments] rings per hemisphere
 * @param {number} [radialSegments] segments around the axis
 * @returns {Geometry}
 */
export function make_capsule_geometry(radius = 0.5, height = 1, capSegments = 8, radialSegments = 16) {
    const positions = [];
    const normals = [];
    const uvs = [];
    const indices = [];

    const halfHeight = height / 2;

    // Rings from the top pole to the bottom pole. The two hemispheres are swept
    // by polar angle; the middle is a single pair of rings offset along Y, so
    // the seam between cap and cylinder shares its vertices' normals.
    const rings = [];

    for (let i = 0; i <= capSegments; i++) {
        const v = (i / capSegments) * (Math.PI / 2);   // 0 at the pole, PI/2 at the equator

        rings.push({ y: halfHeight + Math.cos(v) * radius, r: Math.sin(v) * radius, ny: Math.cos(v), offset: halfHeight });
    }

    for (let i = 0; i <= capSegments; i++) {
        const v = (Math.PI / 2) + (i / capSegments) * (Math.PI / 2);

        rings.push({ y: -halfHeight + Math.cos(v) * radius, r: Math.sin(v) * radius, ny: Math.cos(v), offset: -halfHeight });
    }

    const totalLength = height + 2 * radius;

    for (let ri = 0; ri < rings.length; ri++) {
        const ring = rings[ri];

        for (let s = 0; s <= radialSegments; s++) {
            const u = s / radialSegments;
            const theta = u * Math.PI * 2;

            const cos = Math.cos(theta);
            const sin = Math.sin(theta);

            positions.push(ring.r * cos, ring.y, ring.r * sin);

            // The normal of a capsule is the normal of the sphere its point
            // belongs to, which is the point taken relative to that cap's centre.
            const nx = ring.r * cos;
            const nz = ring.r * sin;
            const ny = ring.ny * radius;
            const len = Math.hypot(nx, ny, nz) || 1;

            normals.push(nx / len, ny / len, nz / len);

            uvs.push(u, (ring.y + totalLength / 2) / totalLength);
        }
    }

    const perRing = radialSegments + 1;

    for (let ri = 0; ri < rings.length - 1; ri++) {
        for (let s = 0; s < radialSegments; s++) {
            const a = ri * perRing + s;
            const b = a + 1;
            const c = a + perRing;
            const d = c + 1;

            // Counter-clockwise seen from outside, matching every Shade
            // primitive: the winding order is what the renderer uses to tell a
            // front face from a back one, and getting it backwards leaves the
            // capsule lit as if it were inside out.
            indices.push(a, b, c);
            indices.push(b, d, c);
        }
    }

    const geometry = new Geometry();

    geometry.name = "Capsule";

    geometry.index = Attribute.from(new Uint32Array(indices), 1, StandardAttributes.Index);
    geometry.addAttribute(Attribute.from(new Float32Array(positions), 3, StandardAttributes.Position));
    geometry.addAttribute(Attribute.from(new Float32Array(normals), 3, StandardAttributes.Normal));
    geometry.addAttribute(Attribute.from(new Float32Array(uvs), 2, StandardAttributes.TextureCoordinates0));

    return geometry;
}

// NavMesh navigation — a Meep example.
//
// Sections:
//   §1  Tunables                     agent + level dimensions, seeds
//   §2  Engine bootstrap             systems, camera, lights
//   §3  Geometry helpers             quad/triangle soup builders
//   §4  Level generator              seeded platforms + ramp + obstacles
//   §5  NavMesh build                BinaryTopology source -> NavigationMesh
//   §6  NavMesh overlay              transparent-blue fill + gizmo wireframe
//   §7  Agent + path visualisation   capsule, Path, PathFollower, PathDisplay
//   §8  Click-to-navigate            screen ray -> NavigationMesh.find_path
//   §9  HUD, buttons, frame loop
//
// Two platforms at different heights are joined by a ramp. A few obstacles are
// scattered on top; the engine carves them (and the platform edges) out of a
// navigation mesh that respects the agent's radius and height. Click anywhere
// on the ground and the capsule walks the routed path. "Randomize" rebuilds the
// whole level from a fresh seed; the first load is always the same seed.

// ─── Imports ────────────────────────────────────────────────────────────────

import { Color } from "@woosh/meep-engine/src/core/color/Color.js";
import Vector2 from "@woosh/meep-engine/src/core/geom/Vector2.js";
import Vector3 from "@woosh/meep-engine/src/core/geom/Vector3.js";
import { randomFloatBetween } from "@woosh/meep-engine/src/core/math/random/randomFloatBetween.js";
import { seededRandom } from "@woosh/meep-engine/src/core/math/random/seededRandom.js";

import { EngineHarness } from "@woosh/meep-engine/src/engine/EngineHarness.js";
import { Light } from "@woosh/meep-engine/src/engine/graphics/ecs/light/Light.js";
import { LightType } from "@woosh/meep-engine/src/engine/graphics/ecs/light/LightType.js";

import Entity from "@woosh/meep-engine/src/engine/ecs/Entity.js";
import { Transform64 } from "@woosh/meep-engine/src/engine/ecs/transform/Transform64.js";
import { t64_announce_change } from "@woosh/meep-engine/src/engine/ecs/transform/t64_announce_change.js";

import { ShadedGeometry } from "@woosh/meep-engine/src/engine/graphics/ecs/mesh-v2/ShadedGeometry.js";
import { ShadedGeometryFlags } from "@woosh/meep-engine/src/engine/graphics/ecs/mesh-v2/ShadedGeometryFlags.js";
import { ShadedGeometrySystem } from "@woosh/meep-engine/src/engine/graphics3/ShadedGeometrySystem.js";

// Shade's geometry + material types. There is no capsule among the seven
// primitive generators, so the agent carries a local builder.
import { Attribute } from "@woosh/meep-engine/src/shade/renderer/geometry/Attribute.js";
import { Geometry } from "@woosh/meep-engine/src/shade/renderer/geometry/Geometry.js";
import { StandardAttributes } from "@woosh/meep-engine/src/shade/renderer/geometry/StandardAttributes.js";
import { make_box_geometry } from "@woosh/meep-engine/src/shade/renderer/geometry/primitives/make_box_geometry.js";
import {
    meshlet_geometry_build_from_geometry
} from "@woosh/meep-engine/src/shade/renderer/geometry/meshlet_geometry_build_from_geometry.js";
import {
    MeshoptClusterizer
} from "@woosh/meep-engine/src/shade/renderer/geometry/meshlet/build/meshoptimizer/meshopt_clusterizer.js";
import { StandardShadeMaterial } from "@woosh/meep-engine/src/shade/renderer/material/StandardShadeMaterial.js";
import { ShadeDrawSide } from "@woosh/meep-engine/src/shade/renderer/material/ShadeDrawSide.js";
import { TransparencyMode } from "@woosh/meep-engine/src/shade/renderer/material/TransparencyMode.js";

import { make_capsule_geometry } from "./lib/make_capsule_geometry.js";

import Path from "@woosh/meep-engine/src/engine/navigation/ecs/components/Path.js";
import { PathEvents } from "@woosh/meep-engine/src/engine/navigation/ecs/components/PathEvents.js";
import PathFollower from "@woosh/meep-engine/src/engine/navigation/ecs/path_following/PathFollower.js";
import { PathFollowerFlags } from "@woosh/meep-engine/src/engine/navigation/ecs/path_following/PathFollowerFlags.js";
import PathFollowingSystem from "@woosh/meep-engine/src/engine/navigation/ecs/path_following/PathFollowingSystem.js";

import { PathDisplay } from "@woosh/meep-engine/src/engine/graphics/ecs/path/PathDisplay.js";
import { PathDisplaySpec } from "@woosh/meep-engine/src/engine/graphics/ecs/path/PathDisplaySpec.js";
import { PathDisplaySystem } from "@woosh/meep-engine/src/engine/graphics3/PathDisplaySystem.js";
import { PathDisplayType } from "@woosh/meep-engine/src/engine/graphics/ecs/path/PathDisplayType.js";
import { TubePathStyle } from "@woosh/meep-engine/src/engine/graphics/ecs/path/tube/TubePathStyle.js";
import { TubeMaterialType } from "@woosh/meep-engine/src/engine/graphics/ecs/path/tube/TubeMaterialType.js";
import { BasicMaterialDefinition } from "@woosh/meep-engine/src/engine/graphics/ecs/path/tube/BasicMaterialDefinition.js";
import { CapType } from "@woosh/meep-engine/src/engine/graphics/ecs/path/tube/CapType.js";

// The navmesh wireframe is drawn with the engine's immediate-mode debug API:
// Gizmo records line segments, DebugDrawSystem turns one frame of them into
// screen-space-width quads on the renderer's dynamic-geometry path.
import { DebugDrawSystem } from "@woosh/meep-engine/src/engine/graphics3/DebugDrawSystem.js";
import { Gizmo } from "@woosh/meep-engine/src/engine/graphics/render/gizmo/Gizmo.js";

import { NavigationMesh } from "@woosh/meep-engine/src/engine/navigation/mesh/NavigationMesh.js";
import { BinaryTopology } from "@woosh/meep-engine/src/core/geom/3d/topology/struct/binary/BinaryTopology.js";
import {
    bt_mesh_from_unindexed_geometry
} from "@woosh/meep-engine/src/core/geom/3d/topology/struct/binary/io/bt_mesh_from_unindexed_geometry.js";
import { tri3_raycast } from "@woosh/meep-engine/src/core/geom/3d/triangle/tri3_raycast.js";

// ─── §1  Tunables ─────────────────────────────────────────────────────────────

const AGENT_RADIUS = 0.4;   // capsule radius — also the navmesh erosion distance
const AGENT_CYL_HEIGHT = 0.8;   // cylindrical mid-section of the capsule
const AGENT_TOTAL_HEIGHT = AGENT_CYL_HEIGHT + 2 * AGENT_RADIUS;   // 1.6 — navmesh clearance
const AGENT_SPEED = 5.0;   // world units / second
const AGENT_CLIMB_ANGLE = 0.9;   // radians (~51°) — the ramp must be gentler than this

const BLOCKER_HEIGHT = 0.5;   // obstacle "ceiling" height fed to the navmesh (< AGENT_TOTAL_HEIGHT)
const PILLAR_HEIGHT = 1.3;   // visible obstacle height
const PLATFORM_THICKNESS = 1.2;   // visible slab depth below the walk surface
const RAMP_THICKNESS = 0.5;

const NAV_FILL_LIFT = 0.04;   // lift the overlay off the surface to avoid z-fighting
const NAV_WIRE_LIFT = 0.06;   // wireframe slightly higher so it sorts above the fill
const PATH_LIFT = 0.12;   // float the path tube just above the ground

// First load is deterministic; "Randomize" reseeds from the clock-ish source the
// brief asks for. seededRandom makes every level fully reproducible from its seed.
const INITIAL_SEED = 0x1A2B3C;

// find_path writes packed XYZ triples; the mesh A* is capped at ~1k faces, so a
// few thousand points is a safe upper bound for the funnelled output.
const pathOut = new Float32Array(4096 * 3);

// ─── §2  Engine bootstrap ─────────────────────────────────────────────────────

const engine = await EngineHarness.bootstrap({
    configuration: (config, engine) => {
        // Draws every entity carrying a ShadedGeometry (platforms, ramp,
        // obstacles, the capsule, and the navmesh overlay). It takes the
        // graphics facade and the one Shade scene the harness draws into.
        config.addSystem(new ShadedGeometrySystem(engine.graphics, EngineHarness.shadeScene(engine)));

        // Navigation: PathFollowingSystem drives Transform64 from Path + PathFollower.
        config.addSystem(new PathFollowingSystem());

        // PathDisplaySystem turns a Path + PathDisplay into renderable geometry
        // (here, a tube). Under Shade it owns its meshes directly and registers
        // its own render extension on startup — no child entities, no plugin.
        config.addSystem(new PathDisplaySystem(engine.graphics));

        // Draws whatever Gizmo recorded this frame — §6 uses it for the navmesh
        // wireframe, which Shade has no material flag for. Its line width is a
        // property of the pass, in CSS pixels of the display.
        const debugDraw = new DebugDrawSystem(engine.graphics);
        debugDraw.line_width = 1;
        config.addSystem(debugDraw);
    },
});

await EngineHarness.buildBasics({
    engine,
    enableTerrain: false,
    enableWater: false,
    enableLights: true,
    enableShadows: true,
    shadowmapResolution: 1024,
    focus: new Vector3(0, 1.0, 0),
    distance: 58,
    pitch: 0.92,
    yaw: 0.6,
    cameraFieldOfView: 36,
    cameraFarDistance: 600,
    cameraController: true,   // drag to orbit, scroll to zoom
    showFps: false,
});

// Exposure and key light, the same in every demo on this site. Shade's automatic
// exposure is off: these scenes are lit to be looked at, not adapted to, and an
// adapting frame makes two screenshots of the same demo disagree. That leaves
// the light doing the work - and a directional light's intensity is read as lux,
// where the harness's default of 0.9 is a value from the three.js era that only
// ever looked lit because auto-exposure opened up to meet it.
engine.graphics.renderer.feature_automatic_exposure_enabled = false;

engine.entityManager.dataset.traverseEntities([Light], (light) => {
    if (light.type.getValue() === LightType.DIRECTION) {
        light.intensity.set(6);
    }
});

// meshlet_geometry_build_from_geometry clusters geometry with meshoptimizer,
// which is WebAssembly instantiated asynchronously and awaited by nobody. Every
// geometry below is built after this point.
await MeshoptClusterizer.ready;

const ecd = engine.entityManager.dataset;

// Register every component type we attach directly. registerComponentType is
// idempotent, so this is safe even where a system already registered one.
for (const Type of [Transform64, ShadedGeometry, Path, PathFollower, PathDisplay]) {
    ecd.registerComponentType(Type);
}

// ─── Shared materials (created once; geometry is per-level) ──────────────────
//
// Shade's PBR material. The hex colours are sRGB (what a designer types) and the
// renderer works in linear light, so each is decoded once here.

function standardMaterial(hexColor, roughness, metalness) {
    const material = new StandardShadeMaterial();

    material.diffuse_color.copy(Color.from_sRGB_to_linear(Color.parse(hexColor)));
    material.roughness_factor = roughness;
    material.metallic_factor = metalness;

    return material;
}

const platformMaterial = standardMaterial("#8a909c", 0.95, 0.0);
const rampMaterial = standardMaterial("#a7adb8", 0.95, 0.0);
const obstacleMaterial = standardMaterial("#3b424e", 0.9, 0.05);
const agentMaterial = standardMaterial("#ff8a3d", 0.5, 0.1);

// NavMesh overlay fill. TransparencyMode.Transparent plus an alpha in the
// diffuse colour routes it into the renderer's order-independent transparency
// pass, so it composites over the level as a see-through debug film.
// draw_side = Double keeps it visible from underneath the upper platform.
const navFillMaterial = standardMaterial("#2e7bff", 1.0, 0.0);
navFillMaterial.transparency_mode = TransparencyMode.Transparent;
navFillMaterial.draw_side = ShadeDrawSide.Double;
navFillMaterial.diffuse_color.a = 0.2;

// The wireframe colour, as linear RGBA for Gizmo (which records straight into
// the HDR scene colour, before tonemapping).
const NAV_WIRE_COLOR = (() => {
    const c = Color.from_sRGB_to_linear(Color.parse("#05070b"));
    return [c.r, c.g, c.b, 0.5];
})();

// Agent geometry is fixed; shift it up so the capsule's base sits at the entity
// origin (which the PathFollower parks on the ground surface). Shade's Geometry
// has no `translate`, so the offset is written into the position attribute
// before the geometry is clustered.
const capsuleGeometry = meshlet_geometry_build_from_geometry(
    translateY(
        make_capsule_geometry(AGENT_RADIUS, AGENT_CYL_HEIGHT, 8, 16),
        AGENT_CYL_HEIGHT / 2 + AGENT_RADIUS,
    ),
);

function translateY(geometry, dy) {
    const position = geometry.getAttribute(StandardAttributes.Position);
    const data = position.data;

    for (let i = 1; i < data.length; i += 3) {
        data[i] += dy;
    }

    return geometry;
}

// ─── §3  Geometry helpers ────────────────────────────────────────────────────

// A quad given as four corners P(u,v): p00=(u0,v0), p10=(u1,v0), p01=(u0,v1),
// p11=(u1,v1). The default winding makes the face point "up" (its normal has a
// positive Y component); pass flip=true for a downward-facing quad. Each point
// is [x, y, z].
function pushQuad(out, p00, p10, p01, p11, flip = false) {
    if (!flip) {
        // up: (p00, p01, p10) and (p10, p01, p11)
        out.push(p00[0], p00[1], p00[2], p01[0], p01[1], p01[2], p10[0], p10[1], p10[2]);
        out.push(p10[0], p10[1], p10[2], p01[0], p01[1], p01[2], p11[0], p11[1], p11[2]);
    } else {
        // down: reverse winding
        out.push(p00[0], p00[1], p00[2], p10[0], p10[1], p10[2], p01[0], p01[1], p01[2]);
        out.push(p10[0], p10[1], p10[2], p11[0], p11[1], p11[2], p01[0], p01[1], p01[2]);
    }
}

// A flat axis-aligned rectangle on the y-plane, in the XZ range [x0,x1]×[z0,z1].
function pushFloorRect(out, x0, x1, z0, z1, y, flip = false) {
    pushQuad(out,
        [x0, y, z0], [x1, y, z0],
        [x0, y, z1], [x1, y, z1],
        flip
    );
}

// A flat XYZ triangle soup as a Shade Geometry. No index, no normals: the
// meshlet builder generates a sequential index and per-face normals for us.
function geometryFromSoup(positions, name) {
    const geometry = new Geometry();

    geometry.name = name;
    geometry.addAttribute(Attribute.from(new Float32Array(positions), 3, StandardAttributes.Position));

    return geometry;
}

// ─── §4  Level generator ─────────────────────────────────────────────────────

function clamp(v, lo, hi) {
    return v < lo ? lo : (v > hi ? hi : v);
}

// Pick a fully-reproducible level layout from the seeded RNG. The whole thing is
// centred on the X axis so a fixed camera frames any randomised variant.
function generateLayout(rng) {
    const aw = randomFloatBetween(rng, 12, 16);
    const ad = randomFloatBetween(rng, 12, 16);
    const bw = randomFloatBetween(rng, 12, 16);
    const bd = randomFloatBetween(rng, 12, 16);

    const yB = randomFloatBetween(rng, 2.6, 3.8);   // height of the upper platform
    const gap = randomFloatBetween(rng, 5.5, 7.5);   // ramp horizontal run

    const total = aw + gap + bw;

    const Ax0 = -total / 2, Ax1 = Ax0 + aw;
    const Bx0 = Ax1 + gap, Bx1 = Bx0 + bw;

    const Az0 = -ad / 2, Az1 = ad / 2;
    const Bz0 = -bd / 2, Bz1 = bd / 2;

    // The ramp lives in the Z-overlap of the two platforms, set back a little
    // from both edges so the platforms keep a strip on either side of it.
    const overlapMin = Math.max(Az0, Bz0);
    const overlapMax = Math.min(Az1, Bz1);
    const overlapSize = overlapMax - overlapMin;

    const margin = 1.2;
    const rampW = clamp(randomFloatBetween(rng, 3.0, 4.5), 2.0, overlapSize - 2 * margin);
    const rampZc = randomFloatBetween(rng, overlapMin + margin + rampW / 2, overlapMax - margin - rampW / 2);
    const rampZ0 = rampZc - rampW / 2;
    const rampZ1 = rampZc + rampW / 2;

    const layout = {
        Ax0, Ax1, Az0, Az1,
        Bx0, Bx1, Bz0, Bz1,
        yB, rampZ0, rampZ1, rampZc, rampW,
        agentStart: new Vector3((Ax0 + Ax1) / 2, 0, (Az0 + Az1) / 2),
        obstacles: [],
    };

    // Obstacles: a couple per platform, inset from the edges and clear of the
    // ramp mouth and the agent's start tile.
    const aAvoid = [
        { x: layout.agentStart.x, z: layout.agentStart.z, r: 3.5 },
        { x: Ax1, z: rampZc, r: rampW / 2 + 2.5 },
    ];
    const bAvoid = [
        { x: Bx0, z: rampZc, r: rampW / 2 + 2.5 },
    ];

    placeObstacles(rng, layout, { x0: Ax0, x1: Ax1, z0: Az0, z1: Az1, floorY: 0 }, 2, aAvoid);
    placeObstacles(rng, layout, { x0: Bx0, x1: Bx1, z0: Bz0, z1: Bz1, floorY: yB }, 2, bAvoid);

    return layout;
}

function placeObstacles(rng, layout, rect, count, avoid) {
    const edge = 1.8;
    let attempts = 0;

    // rect.floorY is unique per platform (0 vs yB), so this counts only the
    // obstacles already placed on THIS platform.
    while (countTotalOn(layout, rect.floorY) < count && attempts < 100) {
        attempts++;

        const ow = randomFloatBetween(rng, 1.6, 2.6);
        const od = randomFloatBetween(rng, 1.6, 2.6);

        const xLo = rect.x0 + edge + ow / 2, xHi = rect.x1 - edge - ow / 2;
        const zLo = rect.z0 + edge + od / 2, zHi = rect.z1 - edge - od / 2;
        if (xHi <= xLo || zHi <= zLo) break;

        const x = randomFloatBetween(rng, xLo, xHi);
        const z = randomFloatBetween(rng, zLo, zHi);

        let ok = true;
        for (const a of avoid) {
            if (Math.hypot(x - a.x, z - a.z) < a.r + Math.max(ow, od) / 2) { ok = false; break; }
        }
        if (ok) {
            for (const o of layout.obstacles) {
                if (Math.abs(x - o.x) < (ow + o.w) / 2 + 0.8 && Math.abs(z - o.z) < (od + o.d) / 2 + 0.8) {
                    ok = false;
                    break;
                }
            }
        }
        if (!ok) continue;

        layout.obstacles.push({ x, z, w: ow, d: od, floorY: rect.floorY });
    }
}

function countTotalOn(layout, floorY) {
    let n = 0;
    for (const o of layout.obstacles) if (o.floorY === floorY) n++;
    return n;
}

// ─── §5  NavMesh build ───────────────────────────────────────────────────────
//
// We assemble two triangle soups:
//   walkable — the platform tops (split into Z strips so the ramp's edge shares
//              vertices with them) and the ramp itself, all facing up.
//   blockers — a downward-facing "ceiling" quad floating just above each
//              obstacle footprint. These are too steep to be walkable, so they
//              are discarded from the floor, but they stay in the source geometry
//              the builder ray-casts against for head clearance — which is what
//              knocks the obstacle footprints out of the navmesh.
//
// NavigationMesh.build then merges shared vertices, erodes every island by the
// agent radius, and hands back a clean walkable topology.

function buildWalkableSoup(L) {
    const t = [];

    // Upper platform A (y = 0), split at the ramp band so strip A2's far edge
    // coincides with the ramp's low edge.
    pushFloorRect(t, L.Ax0, L.Ax1, L.Az0, L.rampZ0, 0);
    pushFloorRect(t, L.Ax0, L.Ax1, L.rampZ0, L.rampZ1, 0);
    pushFloorRect(t, L.Ax0, L.Ax1, L.rampZ1, L.Az1, 0);

    // Lower-or-higher platform B (y = yB), split the same way.
    pushFloorRect(t, L.Bx0, L.Bx1, L.Bz0, L.rampZ0, L.yB);
    pushFloorRect(t, L.Bx0, L.Bx1, L.rampZ0, L.rampZ1, L.yB);
    pushFloorRect(t, L.Bx0, L.Bx1, L.rampZ1, L.Bz1, L.yB);

    // Ramp: low edge at (Ax1, 0) shares vertices with A2; high edge at (Bx0, yB)
    // shares with B2 — so the three islands fuse into one connected mesh.
    pushQuad(t,
        [L.Ax1, 0, L.rampZ0], [L.Bx0, L.yB, L.rampZ0],
        [L.Ax1, 0, L.rampZ1], [L.Bx0, L.yB, L.rampZ1]
    );

    return t;
}

function buildBlockerSoup(L) {
    const t = [];
    for (const o of L.obstacles) {
        const y = o.floorY + BLOCKER_HEIGHT;
        pushFloorRect(t, o.x - o.w / 2, o.x + o.w / 2, o.z - o.d / 2, o.z + o.d / 2, y, /* flip = */ true);
    }
    return t;
}

function buildNavMesh(walkable, blockers) {
    const sourceTris = walkable.concat(blockers);

    const source = new BinaryTopology();
    bt_mesh_from_unindexed_geometry(source, sourceTris);

    const navmesh = new NavigationMesh();
    navmesh.build({
        source,
        agent_radius: AGENT_RADIUS,
        agent_height: AGENT_TOTAL_HEIGHT,
        agent_max_climb_angle: AGENT_CLIMB_ANGLE,
    });

    return navmesh;
}

// ─── §6  NavMesh overlay ─────────────────────────────────────────────────────

// Pull every triangle out of the built navmesh topology as a flat XYZ soup,
// lifted slightly so it doesn't z-fight with the surface it sits on. The fill is
// drawn as ordinary geometry; the wireframe is recorded as gizmo line segments
// (§9), because Shade has no wireframe draw mode — its rasterizer is
// triangle-list only.
function buildNavOverlay(topology, fillLift, wireLift) {
    const faces = topology.faces;
    const faceCount = faces.size;

    const positions = [];
    const segments = [];
    const tri = new Float64Array(9);
    const v = [0, 0, 0];
    let tris = 0;

    for (let faceId = 0; faceId < faceCount; faceId++) {
        if (!faces.is_allocated(faceId)) continue;

        let loop = topology.face_read_loop(faceId);
        for (let i = 0; i < 3; i++) {
            const vertexId = topology.loop_read_vertex(loop);
            topology.vertex_read_coordinate(v, 0, vertexId);

            positions.push(v[0], v[1] + fillLift, v[2]);

            tri[i * 3] = v[0];
            tri[i * 3 + 1] = v[1] + wireLift;
            tri[i * 3 + 2] = v[2];

            loop = topology.loop_read_next(loop);
        }

        // The three edges of this face, as line endpoints. Interior edges get
        // recorded twice, once per adjacent face — invisible, and cheaper than
        // de-duplicating them.
        for (let i = 0; i < 3; i++) {
            const a = i * 3;
            const b = ((i + 1) % 3) * 3;

            segments.push(
                tri[a], tri[a + 1], tri[a + 2],
                tri[b], tri[b + 1], tri[b + 2],
            );
        }

        tris++;
    }

    return {
        geometry: meshlet_geometry_build_from_geometry(geometryFromSoup(positions, "NavMesh overlay")),
        segments: new Float32Array(segments),
        tris,
    };
}

// ─── §7  Tube style for the path display ─────────────────────────────────────

function makeTubeStyle() {
    const style = new TubePathStyle();
    style.material_type = TubeMaterialType.Basic;
    style.material = new BasicMaterialDefinition();
    // The tube is drawn straight into the HDR scene colour, so the swatch's sRGB
    // #4ef0a8 has to be decoded to linear like every other colour here.
    style.color.copy(Color.from_sRGB_to_linear(Color.parse("#4ef0a8")));
    style.width = 0.07;
    style.cap_type = CapType.Round;
    style.path_mask = [0, 1];
    style.cast_shadow = false;
    style.receive_shadow = false;
    return style;
}

// ─── §8  Level lifecycle + navigation ────────────────────────────────────────

let levelEntities = [];   // everything we spawn for a level, for teardown
let agentEntity = -1;
let pathVizEntity = -1;
let navmesh = null;
let navWireSegments = null;   // line endpoints redrawn through Gizmo every frame
let pickSoup = null;          // the walkable surface, used only for click raycasts
let navTriCount = 0;

function clearLevel() {
    if (levelEntities.length > 0) {
        ecd.removeEntities(levelEntities);
        levelEntities = [];
    }
    agentEntity = -1;
    pathVizEntity = -1;
    navmesh = null;
    navWireSegments = null;
    pickSoup = null;
}

function spawnMesh(geometry, material, position, rotation) {
    const sg = ShadedGeometry.from(geometry, material);
    sg.setFlag(ShadedGeometryFlags.CastShadow);
    sg.setFlag(ShadedGeometryFlags.ReceiveShadow);

    const transform = new Transform64();
    transform.setTranslation(position.x, position.y, position.z);

    if (rotation !== undefined) {
        transform.setRotation(rotation.x, rotation.y, rotation.z, rotation.w);
        // a Transform64 does not maintain its matrix; compose it once the pose is set
        transform.updateMatrix();
    }

    const id = new Entity()
        .add(transform)
        .add(sg)
        .build(ecd);

    levelEntities.push(id);
    return id;
}

function spawnOverlay(geometry, material) {
    const sg = ShadedGeometry.from(geometry, material);
    sg.clearFlag(ShadedGeometryFlags.CastShadow);
    sg.clearFlag(ShadedGeometryFlags.ReceiveShadow);

    const id = new Entity()
        .add(new Transform64())
        .add(sg)
        .build(ecd);

    levelEntities.push(id);
    return id;
}

function boxGeometry(width, height, depth) {
    return meshlet_geometry_build_from_geometry(make_box_geometry(width, height, depth));
}

function buildLevel(seed) {
    clearLevel();

    const rng = seededRandom(seed >>> 0);
    const L = generateLayout(rng);

    // --- NavMesh ---
    const walkable = buildWalkableSoup(L);
    const blockers = buildBlockerSoup(L);
    navmesh = buildNavMesh(walkable, blockers);

    // --- Visible platforms ---
    spawnMesh(
        boxGeometry(L.Ax1 - L.Ax0, PLATFORM_THICKNESS, L.Az1 - L.Az0),
        platformMaterial,
        new Vector3((L.Ax0 + L.Ax1) / 2, -PLATFORM_THICKNESS / 2, (L.Az0 + L.Az1) / 2)
    );
    spawnMesh(
        boxGeometry(L.Bx1 - L.Bx0, PLATFORM_THICKNESS, L.Bz1 - L.Bz0),
        platformMaterial,
        new Vector3((L.Bx0 + L.Bx1) / 2, L.yB - PLATFORM_THICKNESS / 2, (L.Bz0 + L.Bz1) / 2)
    );

    // --- Visible ramp (a thin slab rotated to match the slope) ---
    {
        const run = L.Bx0 - L.Ax1;
        const rise = L.yB;
        const len = Math.hypot(run, rise);
        const theta = Math.atan2(rise, run);
        const half = theta / 2;

        const rotation = { x: 0, y: 0, z: Math.sin(half), w: Math.cos(half) };
        // local "up" of the slanted box = (-rise/len, run/len, 0); drop the box
        // by half its thickness along it so the top face lands on the walk surface.
        const center = new Vector3(
            (L.Ax1 + L.Bx0) / 2 + (rise / len) * (RAMP_THICKNESS / 2),
            L.yB / 2 - (run / len) * (RAMP_THICKNESS / 2),
            L.rampZc
        );

        spawnMesh(boxGeometry(len, RAMP_THICKNESS, L.rampW), rampMaterial, center, rotation);
    }

    // --- Visible obstacles ---
    for (const o of L.obstacles) {
        spawnMesh(
            boxGeometry(o.w, PILLAR_HEIGHT, o.d),
            obstacleMaterial,
            new Vector3(o.x, o.floorY + PILLAR_HEIGHT / 2, o.z)
        );
    }

    // --- NavMesh overlay (fill + wireframe) ---
    const overlay = buildNavOverlay(navmesh.topology, NAV_FILL_LIFT, NAV_WIRE_LIFT);
    navTriCount = overlay.tris;
    navWireSegments = overlay.segments;
    spawnOverlay(overlay.geometry, navFillMaterial);

    // --- Pick soup: the full walkable surface, used only for click raycasts ---
    pickSoup = new Float32Array(walkable);

    // --- Agent capsule ---
    const agentSG = ShadedGeometry.from(capsuleGeometry, agentMaterial);
    agentSG.setFlag(ShadedGeometryFlags.CastShadow);
    agentSG.setFlag(ShadedGeometryFlags.ReceiveShadow);

    const agentTransform = new Transform64();
    agentTransform.setTranslation(L.agentStart.x, L.agentStart.y, L.agentStart.z);

    const follower = new PathFollower();
    follower.speed.set(AGENT_SPEED);
    // Keep the capsule upright — let it yaw to face travel, but never pitch/roll.
    follower.clearFlag(PathFollowerFlags.WriteRotationX);
    follower.clearFlag(PathFollowerFlags.WriteRotationZ);
    follower.clearFlag(PathFollowerFlags.Active);   // nothing to follow until the first click

    agentEntity = new Entity()
        .add(agentTransform)
        .add(agentSG)
        .add(new Path())
        .add(follower)
        .build(ecd);
    levelEntities.push(agentEntity);

    // --- Path visualisation: a separate entity carrying a lifted copy of the
    //     route so the tube floats just above the ground instead of being
    //     buried in it (the agent's own Path sits exactly on the surface). ---
    const viz = new PathDisplay();
    viz.specs.push(PathDisplaySpec.from(PathDisplayType.Tube, makeTubeStyle()));

    pathVizEntity = new Entity()
        .add(new Path())
        .add(viz)
        .build(ecd);
    levelEntities.push(pathVizEntity);

    refreshLevelHud(seed);
    setPathHud(0, 0);
}

// Compute a route from the agent to a clicked world point and start walking it.
function navigateTo(x, y, z) {
    if (agentEntity < 0 || navmesh === null) return;

    const xf = ecd.getComponent(agentEntity, Transform64);

    const count = navmesh.find_path(
        pathOut,
        xf.translation_x, xf.translation_y, xf.translation_z,
        x, y, z
    );

    if (count < 2) {
        setPathHud(0, 0);
        return;
    }

    // Drive the capsule along the ground-level route.
    const path = ecd.getComponent(agentEntity, Path);
    path.clear();
    path.setPointCount(count);
    for (let i = 0; i < count; i++) {
        path.setPosition(i, pathOut[i * 3], pathOut[i * 3 + 1], pathOut[i * 3 + 2]);
    }

    const follower = ecd.getComponent(agentEntity, PathFollower);
    follower.position = 0;
    follower.clearFlag(PathFollowerFlags.Finished);
    follower.setFlag(PathFollowerFlags.Active);

    // Feed a lifted copy to the path-display entity and ask it to rebuild.
    const viz = ecd.getComponent(pathVizEntity, Path);
    viz.clear();
    viz.setPointCount(count);
    for (let i = 0; i < count; i++) {
        viz.setPosition(i, pathOut[i * 3], pathOut[i * 3 + 1] + PATH_LIFT, pathOut[i * 3 + 2]);
    }
    ecd.sendEvent(pathVizEntity, PathEvents.Changed, null);

    setPathHud(count, path.length);
}

// ─── Click-to-navigate plumbing ──────────────────────────────────────────────
//
// There is no scene-graph raycaster to ask: the renderer owns what it draws and
// hands out one picking primitive, `viewportProjectionRay`, which turns a point
// on the viewport into a world ray. The walkable soup we fed the navmesh builder
// is right here in memory, so the hit test is a Möller-Trumbore sweep over it —
// exact, and against the surface the navmesh was actually derived from.

const ndc = new Vector2();
const raySource = new Vector3();
const rayDirection = new Vector3();
const hitNormal = new Float64Array(3);

function pickGround(position) {
    if (pickSoup === null) return;

    // Pointer position (viewport pixels) → clip space → world ray.
    engine.graphics.normalizeViewportPoint(position, ndc);
    engine.graphics.viewportProjectionRay(ndc.x, ndc.y, raySource, rayDirection);

    let nearest = Infinity;

    for (let i = 0; i + 8 < pickSoup.length; i += 9) {
        const t = tri3_raycast(
            hitNormal, 0,
            raySource.x, raySource.y, raySource.z,
            rayDirection.x, rayDirection.y, rayDirection.z,
            nearest,
            pickSoup[i], pickSoup[i + 1], pickSoup[i + 2],
            pickSoup[i + 3], pickSoup[i + 4], pickSoup[i + 5],
            pickSoup[i + 6], pickSoup[i + 7], pickSoup[i + 8],
        );

        if (t < nearest) nearest = t;
    }

    if (!Number.isFinite(nearest)) return;

    // `rayDirection` is unit length, so `nearest` is a true distance.
    navigateTo(
        raySource.x + rayDirection.x * nearest,
        raySource.y + rayDirection.y * nearest,
        raySource.z + rayDirection.z * nearest,
    );
}

// `tap` is a press and release that barely moved — the engine's own pointer
// device separates it from the orbit-drag that shares the same button, so the
// camera controller and this handler can both listen without fighting.
engine.devices.pointer.on.tap.add((position) => {
    pickGround(position);
});

// ─── §9  HUD, buttons, frame loop ────────────────────────────────────────────

const fpsEl = document.getElementById("fps");
const seedEl = document.getElementById("seed");
const triCountEl = document.getElementById("tri-count");
const pathPointsEl = document.getElementById("path-points");
const pathLengthEl = document.getElementById("path-length");

function refreshLevelHud(seed) {
    seedEl.textContent = "0x" + (seed >>> 0).toString(16).toUpperCase();
    triCountEl.textContent = navTriCount.toString();
}

function setPathHud(points, length) {
    pathPointsEl.textContent = points > 0 ? points.toString() : "—";
    pathLengthEl.textContent = points > 0 ? length.toFixed(1) : "—";
}

document.getElementById("randomize-btn").addEventListener("click", () => {
    buildLevel((Math.random() * 0xFFFFFF) >>> 0);
});

// First load: always the same seed.
buildLevel(INITIAL_SEED);

let fpsWindow = 0;
let fpsFrames = 0;
let lastFrameMs = performance.now();

const gizmoFrom = [0, 0, 0];
const gizmoTo = [0, 0, 0];

// Gizmo is immediate mode: DebugDrawSystem clears the recording once the frame
// that consumed it has been submitted, so the navmesh edges are re-recorded here
// every frame, on the signal that fires just before the frame is drawn.
engine.graphics.on.preRender.add(() => {
    // PathFollowingSystem writes the agent's Transform64 as it walks, and a
    // Transform64 announces nothing on its own, so the capsule would sit at the
    // spawn while the follower advanced. One announcement per frame, before the
    // frame is drawn, puts the mesh where the follower left the transform.
    if (agentEntity >= 0) {
        t64_announce_change(ecd, agentEntity);
    }

    const segments = navWireSegments;
    if (segments === null) return;

    Gizmo.color = NAV_WIRE_COLOR;

    for (let i = 0; i + 5 < segments.length; i += 6) {
        gizmoFrom[0] = segments[i];
        gizmoFrom[1] = segments[i + 1];
        gizmoFrom[2] = segments[i + 2];

        gizmoTo[0] = segments[i + 3];
        gizmoTo[1] = segments[i + 4];
        gizmoTo[2] = segments[i + 5];

        Gizmo.draw_line(gizmoFrom, gizmoTo);
    }
});

engine.graphics.on.postRender.add(() => {
    const nowMs = performance.now();
    const dt = (nowMs - lastFrameMs) / 1000;
    lastFrameMs = nowMs;

    fpsWindow += dt;
    fpsFrames++;
    if (fpsWindow >= 0.5) {
        fpsEl.textContent = (fpsFrames / fpsWindow).toFixed(0);
        fpsWindow = 0;
        fpsFrames = 0;
    }
});

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>NavMesh navigation · Meep</title>
  <meta name="robots" content="noindex">
  <style>
    *, *::before, *::after { box-sizing: border-box; }
    html, body {
      margin: 0; padding: 0;
      width: 100%; height: 100%;
      overflow: hidden;
      background: #07090c;
      color: #e6edf3;
      font-family: ui-sans-serif, system-ui, -apple-system, "Segoe UI", Roboto, sans-serif;
    }

    .panel {
      position: fixed;
      z-index: 1000;
      background: rgba(7, 9, 12, 0.72);
      border: 1px solid #1f2731;
      border-radius: 10px;
      backdrop-filter: blur(10px);
      -webkit-backdrop-filter: blur(10px);
      box-shadow: 0 12px 32px rgba(0,0,0,0.4);
    }

    .hud {
      top: 1rem; left: 1rem;
      padding: 0.8rem 1rem;
      font-family: ui-monospace, "JetBrains Mono", monospace;
      font-size: 0.82rem;
      line-height: 1.7;
      color: #9aa5b1;
      min-width: 200px;
    }
    .hud .label {
      color: #6b7785;
      text-transform: uppercase;
      letter-spacing: 0.1em;
      font-size: 0.65rem;
      margin-right: 0.5rem;
    }
    .hud .value { color: #4ef0a8; }

    .legend {
      bottom: 1rem; left: 1rem;
      padding: 0.8rem 1rem;
      font-size: 0.82rem;
      line-height: 1.55;
      max-width: 380px;
      color: #9aa5b1;
    }
    .legend strong { color: #e6edf3; }
    .legend .swatch {
      display: inline-block;
      width: 0.8em; height: 0.8em;
      border-radius: 2px;
      vertical-align: -1px;
      margin-right: 0.15em;
    }
    .legend kbd {
      font-family: ui-monospace, monospace;
      font-size: 0.78em;
      color: #e6edf3;
      background: #11161d;
      border: 1px solid #2a3441;
      border-bottom-width: 2px;
      border-radius: 3px;
      padding: 0.05em 0.4em;
    }

    .randomize-btn {
      bottom: 1rem; right: 1rem;
      padding: 0.7rem 1.1rem;
      font-family: ui-sans-serif, system-ui, sans-serif;
      font-size: 0.9rem;
      font-weight: 600;
      letter-spacing: 0.02em;
      color: #03110a;
      background: #4ef0a8;
      border: none;
      border-radius: 8px;
      cursor: pointer;
      box-shadow: 0 12px 32px rgba(0,0,0,0.4);
    }
    .randomize-btn:hover { background: #2dd185; }
    .randomize-btn:active { transform: translateY(1px); }
  </style>
</head>
<body>

  <div class="panel hud">
    <div><span class="label">fps</span>     <span class="value" id="fps">--</span></div>
    <div><span class="label">seed</span>    <span class="value" id="seed">--</span></div>
    <div><span class="label">navmesh tris</span><span class="value" id="tri-count">--</span></div>
    <div><span class="label">path pts</span><span class="value" id="path-points">--</span></div>
    <div><span class="label">path len</span><span class="value" id="path-length">--</span></div>
  </div>

  <div class="panel legend">
    Two platforms joined by a ramp, with obstacles carved out of the
    <span class="swatch" style="background:#2e7bff"></span><strong>navigation mesh</strong>
    (black wireframe). <strong>Click anywhere</strong> on the ground to walk the capsule there
    along a <span class="swatch" style="background:#4ef0a8"></span>routed path —
    the engine's <code>Path</code> + <code>PathFollower</code> do the walking.
    <br>
    <kbd>drag</kbd> orbit · <kbd>scroll</kbd> zoom · <strong>Randomize</strong> reshapes the level from a new seed.
  </div>

  <button class="panel randomize-btn" id="randomize-btn">Randomize</button>

  <script type="module" src="./src/main.js"></script>
</body>
</html>

{
  "title": "NavMesh navigation",
  "description": "Click to walk a capsule across two platforms joined by a ramp, routing around obstacles on a navigation mesh. Randomize to reshape the level.",
  "category": "AI",
  "status": "live",
  "order": 20,
  "tags": [
    "ai",
    "pathfinding",
    "navigation",
    "navmesh",
    "path",
    "ecs"
  ],
  "sourceHint": "examples-src/navmesh/",
  "demoUrl": "/examples/navmesh/demo.html",
  "defaultFile": "src/main.js"
}

{
  "name": "@meep-examples/navmesh",
  "version": "0.1.0",
  "private": true,
  "type": "module",
  "description": "Navigation-mesh path-finding: click to walk a capsule agent across two platforms joined by a ramp, avoiding obstacles. Built from a seeded, randomizable level.",
  "scripts": {
    "dev": "vite",
    "build": "vite build",
    "preview": "vite preview"
  },
  "dependencies": {
    "@woosh/meep-engine": "3.41.0"
  },
  "devDependencies": {
    "@rollup/plugin-strip": "^3.0.4",
    "vite": "^8.0.13"
  }
}

import { defineConfig } from "vite";
import { copyFileSync, existsSync, mkdirSync } from "node:fs";
import { fileURLToPath } from "node:url";
import { resolve, dirname } from "node:path";

import strip from "@rollup/plugin-strip";

const __dirname = dirname(fileURLToPath(import.meta.url));
const outDir = resolve(__dirname, "../../public/examples/navmesh");

// See examples-src/entity-stress-test/vite.config.js for the rationale on
// base: "./" and emptyOutDir: false.
export default defineConfig({
  // Vite's dependency pre-bundling rewrites the engine's own asset imports and
  // loses their URLs, so a dev server ends up serving ".../deps/undefined" for
  // the renderer's data files. The engine is source-only ESM and needs no
  // pre-bundling - but its CommonJS dependencies do, or the import of them from inside
  // the excluded engine finds no default export.
  optimizeDeps: {
    exclude: ["@woosh/meep-engine"],
    include: ["dat.gui", "opentype.js"],
  },
  plugins: [
    {
      // Copy the committed source thumbnail + meta into the generated gallery
      // folder. public/examples/<id>/ is build output (gitignored); these are
      // kept in source here and copied through on every build so the gallery
      // (src/data/examples.ts) can resolve them.
      name: "copy-gallery-assets",
      apply: "build",
      closeBundle() {
        mkdirSync(outDir, { recursive: true });
        for (const name of ["thumbnail.png", "meta.json"]) {
          const src = resolve(__dirname, name);
          if (existsSync(src)) {
            copyFileSync(src, resolve(outDir, name));
          }
        }
      },
    },
  ],
  base: "./",
  build: {
    outDir,
    emptyOutDir: false,
    rollupOptions: {
      input: resolve(__dirname, "demo.html"),
      plugins: [
        {
          // this will remove all assert statements from the production build
          ...strip(),
          apply: 'build'
        }
      ],
    },
    target: "es2022",
  },
});