Navigation and AI

Navigation meshes, path queries, crowd steering, behaviour trees and utility AI are commands on the same surface as the rest of the engine: nav.* and ai.* (commands in crates/sparklight-control/src/commands/nav/, the algorithms in crates/sparklight-nav, the scene glue and the state in crates/sparklight-scene3d/src/nav.rs). Every command has a JSON Schema and coded errors (schemas/commands/, system.commands), and every command is an MCP tool (nav_bake, nav_path, ai_step, …). General rules of the surface: docs/agent/commands.md. The 3D scene they work with: docs/agent/space3d.md. Verification: docs/agent/testing.md.

Quick start

{"command": "space3d.load", "params": {"path": "samples/space3d/ragdoll-wall.space3d.json"}}
{"command": "nav.bake", "params": {"name": "arena", "agent_radius": 0.4, "agent_height": 1.8}}
{"command": "nav.path", "params": {"from": [-8, 0, 3], "to": [8, 0, 3]}}
{"command": "nav.obstacle.add", "params": {"shape": {"type": "circle", "radius": 1.0}, "position": [0, 0, 3]}}
{"command": "nav.debug.capture", "params": {"path": "arena.png"}}

A guard that patrols, sees the player and chases (the whole thing is samples/navigation/scenarios/guard-patrol-chase.ai-scenario.json):

spark call ai.scenario.run '{"path": "samples/navigation/scenarios/guard-patrol-chase.ai-scenario.json"}' --project . --json
spark test samples/navigation/guard.test.json --project .

The navmesh

A NavMesh is a set of convex polygons (at most 6 vertices when baked, positive winding in the ground plane) with portal links between them. Links are found by edge overlap, not by shared vertex ids, so the mesh stays connected across T-junctions between regions and after carving. Walls are the polygon edge stretches no link covers.

3D bake (nav.bake, source space3d)

Recast-style, written from scratch (no navmesh crate; see “Choices”):

1. Voxelise the triangles of the static colliders on a grid of cell_size x cell_height. The colliders are the Fixed Body shapes (box, sphere, capsule; ConvexHull and TriMesh with the model’s real triangles, FromMesh with its bounding box), plus anchored, non-dynamic Destructible objects at their initial shape. Sensors and dynamic bodies are left out unless asked for (include_sensors, include_kinds).
2. Filter: spans steeper than max_slope_deg are not walkable; obstacles lower than step_height do not stop an agent; ledges (a drop of more than step_height beside the span) and spans with less than agent_height head room are dropped.
3. Erode by agent_radius (chamfer distance transform from every border).
4. Regions: a monotone partition (no holes, no overlaps).
5. Contours of each region are traced, simplified (Douglas-Peucker, max_simplification_error cells) and cut to max_edge_len.
6. Polygons: ear clipping, then greedy merging into convex polygons of up to 6 vertices. A region whose contour cannot be triangulated falls back to row runs (stats.fallback_regions counts them), so a bake never leaves a hole.

The polygon heights come from the contour corners (the highest of the four surfaces around the corner); a polygon over a ramp is a planar approximation. There is no detail mesh; physics keeps characters on the real floor.

Default settings: agent_radius 0.4, agent_height 1.8, max_slope_deg 45, step_height 0.4, cell_size 0.2, cell_height 0.1. Limits: 4096 x 4096 cells (E_NAV_LIMIT). Re-baking under an existing name keeps its obstacles and agents.

2D bake (source: scene2d or polygons)

The tile layers (solid tiles) and static boxes of the 2D scene, or the shapes you pass (bounds, obstacles polygons, walkable polygons, solid_rects, areas), are rasterised on a grid aligned with the tile size; cells nearer than agent_radius to a blocked cell or the border are removed; the free cells are covered by maximal rectangles. 2D points are [x, y] and are stored as (x, 0, y) internally; every nav.* command takes and returns [x, y] for a 2D mesh.

Areas and costs

Polygons carry an area id 0..15 (2D: areas rectangles at bake time). nav.path takes area_costs ({"1": 3.0} makes area 1 three times as costly) and excluded_areas.

Queries

Command	What it answers
nav.nearest	the nearest point of the mesh to a point, within extents
nav.path	A* over polygons (costs from the entry points of the portals), then string pulling (funnel) to the corner points; a goal on another island gives the closest reachable path with complete: false
nav.raycast	walk a line along the mesh and stop at the first wall: fraction, hit point, wall normal
nav.random_point	uniform by area, seeded

Dynamic obstacles (carving)

nav.obstacle.add takes a circle, box or convex polygon footprint (grown by the agent radius, because the mesh already keeps agent centres away from walls). The footprint is cut out of the polygons it covers; the pieces are convex again and re-linked, so paths change at once and agents re-plan on their next step. follow: "<object>" makes the obstacle track a 3D object on every ai.step. nav.obstacle.move and nav.obstacle.remove carve again; removing the obstacle gives back the baked mesh bit for bit (nav.info.base_hash equals hash).

Off-mesh links (jump, drop)

nav.offmesh.add {start, end, kind, radius, bidirectional, cost, speed, arc_height} joins two places the walkable mesh does not: the ends snap to the nearest polygons within radius (resolved says whether both did). A* treats the link as an extra edge (walk to the start, then cost times the leap’s length), the funnel splits the corridor at it, and nav.path returns the take-off point and the landing as consecutive points with links: [{point, link}]. Agents walk to the take-off (within 0.3 m), then leap:

• jump: a CharacterController gets a jump press once and a velocity toward the landing; an agent the crowd moves itself follows an arc of arc_height over the straight line at speed.
• drop: no jump, the body just walks off (physics falls) or the crowd lowers the agent.

On landing the agent finds its polygon and plans again. A link survives a re-bake of its mesh; nav.debug.capture draws it as a dashed magenta line (take-off magenta, landing cyan). Links are not in nav.export documents (re-add them after nav.import).

Agents and crowds

nav.agent.add creates a steering agent on a mesh, optionally bound to a 3D object (entity). A CharacterController object is driven by feeding it the crowd’s velocity (space3d.character.move); any other object has its transform written; an agent without an object (position) is moved by the crowd itself. Steering: path following along the corners, arrive (linear slow-down within slow_radius, stop within stop_distance), and ORCA (optimal reciprocal collision avoidance, written from the published algorithm) against up to max_neighbors neighbours plus half-planes from the walls near the agent. Targets that move more than repath_distance are re-planned; a changed mesh re-plans at once.

States (nav.agent.get.state): idle, moving, arrived, no_path, off_mesh.

• The AI is part of the 3D simulation: space3d.step runs it (Space3D::step, step 1c of docs/agent/space3d.md), in a fixed order inside every physics step, right after the scripts: AiAgent components become agents, obstacles that follow objects move, agents are told where their objects really are, brains tick (agent-name order, every period steps), crowds steer (mesh-name order), characters get their velocity (and a jump press when a jump link starts) or plain objects their transform. ai.step {frames} is the same as space3d.step {frames} with the AI numbers in its answer.
• nav.step {frames} advances only the crowds, without a scene: agents without objects move. Use it for 2D and pure navigation tests.
• ai.until {that, max_frames} steps until an ai.assert condition holds: robust scenarios use it instead of frame counts.

The AiAgent component

{"command": "space3d.spawn", "params": {"name": "Guard", "components": {
  "Transform3D": {"position": [-14, 0.95, 8]}, "CharacterController": {"height": 1.8, "radius": 0.4},
  "AiAgent": {"mesh": "arena", "tree": "guard", "max_speed": 4.5, "blackboard": {"target": "Player"}}}}}

The component is saved in the scene file. The agent and its brain are created the first time the mesh and the tree it names exist (so the component can be in the scene before the mesh is baked), keyed by the object’s name; removing the component or the object removes them. Fields: mesh, tree or utility, period, blackboard, radius/height (default: the controller’s, else the mesh’s), max_speed, max_accel, stop_distance, eye_height, drive (auto, character, transform). nav.agent.add and ai.brain.attach still create agents by hand. A brain whose tick fails (unknown tree, bad leaf parameters at run time) stops thinking, records an error AI event and a scene event ai_error; ai.brain.get shows enabled: false and the error.

Behaviour trees (JSON)

ai.tree.load {doc | path}; the schema is ai.schema {kind: "behavior_tree"} (also schemas/ai/behavior-tree.schema.json).

{"version": 1, "name": "guard",
 "root": {"type": "selector", "reactive": true, "children": [
   {"type": "sequence", "children": [
     {"type": "condition", "name": "can_see", "params": {"target": "Player"}},
     {"type": "action", "name": "move_to", "params": {"target": "Player", "stop_distance": 1.3}}]},
   {"type": "action", "name": "patrol", "params": {"points": [[-12, 0, 6], [12, 0, 6]]}}]}}

Nodes: sequence, selector (children; reactive: true re-checks from the first child every tick and aborts what no longer applies), parallel (success/failure: one | all), decorators inverter, succeeder, failer, repeat / retry (count), timeout / cooldown (seconds), leaves wait, check (blackboard key op value), set, condition, action, subtree (inlined from subtrees), utility (score a utility document and run its choice). A parameter may be {"bb": "key"} to read the blackboard when the action runs.

Built-in leaves (ai.leaves): actions move_to, patrol, stop, face, set_speed, log, emit; conditions can_see (range, view cone, line of sight through the physics colliders), within, arrived, has_path, chance.

Validation is exhaustive: ai.validate (and ai.tree.load) report every problem as {code, message, path, hint}:

Code	Meaning
E_AI_SCHEMA	the document does not match the schema (wrong type, missing field, unknown property, out of range)
E_AI_UNKNOWN_NODE	unknown node type
E_AI_UNKNOWN_SUBTREE	subtree names a subtree that is not defined
E_AI_CYCLE	subtrees contain each other
E_AI_UNKNOWN_LEAF	no such action or condition
E_AI_PARAMS	unknown, missing or mistyped parameter of a leaf
E_AI_BAD_CURVE	invalid utility curve
E_AI_LIMIT	more than 2048 nodes (after inlining) or deeper than 48 levels
E_AI_UNKNOWN	no tree, utility document or brain by that name

Utility AI (JSON)

ai.utility.load, schema ai.schema {kind: "utility"}. Each action has considerations: an input (blackboard number, or a sensor: speed, pos_x/y/z, time, distance_to_target from blackboard.target), a range mapped to 0..1, a response curve (linear, power, logistic, step, smoothstep, inverse, constant) and a weight. Score = product (with the usual compensation) times the action weight; 0 vetoes. inertia favours the last choice, cooldown blocks an action after it was chosen, selection is best or weighted_random (seeded). ai.utility.evaluate returns every score with the evidence of each consideration. An action’s run is one of the leaves above.

Brains, blackboards, events

ai.brain.attach {agent, tree | utility, period, blackboard} gives an agent a mind; ai.brain.get shows its status, blackboard, the running nodes (id, label, path in the document) and memory. ai.blackboard.set/get. The AI event log (ai.events) records spotted, lost_sight, waypoint, arrived, tree_status, utility and whatever trees emit. ai.assert checks blackboards, events (counts), tree status, agent state and distances and fails with E_ASSERT_FAILED (data: expected, actual).

Scenarios, debug pictures, goldens

ai.scenario.run runs a scenario file {version: 1, name, steps: [{do: "<command id>", ...params}]} over any commands (space3d.*, nav.*, ai.*); a step that reports equal: false / passed: false fails the run, expect_error expects a code, update_goldens: true regenerates nav.golden.check goldens.

nav.debug.capture draws the navmesh from above with a deterministic software rasteriser (no GPU): polygons shaded by height and cost class, polygon edges, walls (white), obstacles (red), agent paths (yellow with white corners), agents (disc with a heading line). nav.golden.update / nav.golden.check store and compare goldens/nav/<name>.png (tolerance 2/255 on at most 0.1 % of the pixels; equal state gives equal pixels on any machine). The guard scenario’s golden is goldens/nav/guard-chase.png.

Determinism, snapshots and the state hash

Everything is deterministic: no hash-map iteration, no clocks, no threads; avoidance and planning use fixed iteration orders and total orders for ties. nav.bake reports hash (the mesh), nav.hash / ai.hash the whole navigation and AI state, ai.step returns the 3D state hash and the ai_hash.

The navigation and AI state belongs to the scene (Space3D::nav): meshes with obstacles, off-mesh links and crowds, trees, utility documents, brains with blackboards and running nodes, the AI event log. So space3d.snapshot.take / restore copy it and bring it back (the state hash and ai.hash after a restore equal those at the snapshot, and stepping on repeats bit for bit), space3d.hash covers it (an untouched scene hashes as before), space3d.determinism.check covers it, and snapshot.save / snapshot.load rebuild it by replaying the logged nav.* / ai.* commands. Replacing the scene (space3d.new, space3d.load) drops it. Without a 3D scene the commands use a detached per-session state (2D meshes, nav.step); it is not in snapshots.

Choices

• Algorithms written for this engine, no navmesh crate: recast-style crates and Bevy navigation plugins bring ECS coupling, floating-point choices we cannot pin for bit-equal results, and their own data models; the pipeline here is about 1500 lines, uses only glam, and every step is covered by tests. ORCA follows the published algorithm (van den Berg et al.); no code was copied.
• Monotone region partition instead of watershed: simpler, no holes, linear; the polygons are less round than watershed’s.
• Linking by edge overlap instead of shared vertices: robust for carving and for regions simplified independently.

Known limits

• A ConvexHull or TriMesh collider bakes with the model’s real triangles (nav.bake loads the models first; FromMesh is the model’s bounding box, like the physics). A model that cannot be loaded, and a Destructible from an asset file, bake as boxes; nav.bake.stats.approximated_colliders counts them (0 for the samples). The physics hull of a concave model is filled where the bake uses the exact mesh.
• No height detail mesh (polygons over a ramp are planar), no per-tile partial re-bake: a changed static scene is baked again.
• The can_see condition uses the heading of the agent (set by movement, face or nav.agent.set), not the object’s skeleton.
• Off-mesh links are not saved in nav.export documents and are resolved against the carved mesh (a link whose end is inside an obstacle’s footprint joins nothing until the obstacle moves).
• A trigger of the 2D runtime is not wired to the AI: 2D agents are read with nav.agent.get and moved by nav.step.

Commands

All commands are listed with their schemas in schemas/commands/ and by spark commands --prefix nav. / --prefix ai.; the table is in docs/agent/commands.md. Error codes: E_NAV_* (config, no geometry, bake failed, no mesh, off mesh, format, unknown obstacle or agent, entity, limit) and E_AI_* above.