Michi (道, the way) builds navigation meshes from triangle soup and answers path queries against them. You hand it triangles, it hands you a mesh and a path.

Status: early. The code has been running in a shipping game engine and is heavily tested, but this standalone packaging is new and the API will move. Pin a commit rather than tracking main. Working with an AI agent on this repo? Point it at Agents.md.

---

What it is based on

Michi's pipeline is Recast's — voxelise the input, filter what an agent can stand on, grow regions, trace contours, simplify them, polygonise, and fit a detail mesh for height accuracy. That shape is Mikko Mononen's, from recastnavigation, and this project owes it the obvious debt. String-pulling is his Simple Stupid Funnel, here reimplemented in exact integers; it descends from the classic funnel algorithm for shortest paths in simple polygons (Chazelle; Lee & Preparata; Hershberger & Snoeyink). Contours are simplified with Douglas–Peucker, regions grown by watershed partitioning, and paths found with A* over the polygon graph.

What is ours is a constraint the original does not make: a bake must be bit-identical on every machine, every compiler, and every run. That single requirement rewrote most of the interesting decisions, and it is why several textbook choices were evaluated and turned down:

Considered	Rejected because
Shewchuk adaptive-precision predicates	Unnecessary here. Coordinates live in a bounded fixed-point frame, so the range bound is the proof of exactness — checkable by reading two type declarations, and impossible for a caller to invalidate. Three multiplies, branch-free. An adaptive predicate would be slower and weaker.
Delaunay detail-mesh triangulation	Its in-circle test is the sign of a 4×4 determinant needing more than 64 bits (the bound works out under 2⁶⁶), and MSVC has no __int128. Michi uses a greedy error-driven fan instead.
Hertel–Mehlhorn polygonisation	Produces fewer polygons, but the diagonal-removal order decides the output and is not canonical without inventing an order — exactly the kind of hidden tie-break that makes two machines disagree.
Visvalingam contour simplification	Also integer-exact, but it drops vertices on an area threshold, which has no relationship to how far the boundary actually moves — and boundary movement is what cross-chunk portal matching depends on.

If you only remember one thing about the design: the determinism requirement is upstream of everything else. Fixed-point coordinates, exact predicates, canonical iteration order, and the refusal of hash-ordered containers in the polygon pipeline all fall out of it.

Quick start

#include <michi/nav_chunk_build.hpp>
#include <michi/nav_chunk_data.hpp>

// 1. describe the agent and the lattice
michi::nav::NavChunkBuildParams params;
params.cellSize = 0.30f;
params.cellHeight = 0.20f;
params.agent = { .radius = 0.6f, .height = 2.0f,
                 .maxSlopeDegrees = 45.0f, .maxStepHeight = 0.4f };

// 2. check the settings can express what you asked for (see "Gotchas")
auto warnings = michi::nav::navCheckBakeSettings(/* ... */);

// 3. bake, serialize, load, finalize
auto built = michi::nav::navBuildChunk(tris, {}, {}, params);
set.loadChunk(michi::nav::navEncodeChunkPayload(viewAsChunk(built)));
set.finalize();                       // required before any query

// 4. query — scratch is caller-owned and reusable, which is why this allocates nothing
michi::nav::NavPathScratch scratch;
michi::nav::NavQueryResult out;
set.findPath({ .start = a, .goal = b }, scratch, out);

examples/pathfind.cpp is the complete version. Its actual output:

scene: 30 triangles, 2 solids
settings: slope ceiling 38.7 deg, 0 warning(s)
bake:  330 polygons, 1341 vertices
blob:  39458 bytes

query: (2.0, 0.0, 2.0) -> (13.5, 2.5, 8.0)
status: Success   7 waypoints, 20 polygons, 40 nodes expanded

path length 20.28 m (the blocked straight line would be 13.21 m)

Performance vs Recast

Michi is not faster or smaller than Recast. Three optimisation passes narrowed the gap substantially and did not reverse it. Path cost is 1.88×–2.54× Recast's on the fixtures where nearly every sampled pair is reachable; resident size is larger on all six, 1.49×–2.69× the bytes and 1.66×–2.99× the polygons.

What Michi has that Recast does not is agent radius as a query parameter that actually works — one bake serving several agent sizes, where Recast needs a bake per size, because it erodes at bake time and deletes the fringe. That fringe is what our extra polygons and bytes buy. It is a capability trade, not a performance one, and it is the honest reason to choose this library.

	Michi vs Recast	verdict
Path cost (reachable-pair fixtures)	1.88×–2.54×	loses
Resident size	1.49×–2.69× bytes	loses all 6
Bake (own defaults)	1.33×–2.08×	loses 5 of 6
Bake (matched detail stride)	1.2×–49× faster	wins 5 of 6
Peak memory vs untiled Recast	−38% to −92%	wins all
Peak memory vs tiled Recast	mixed; higher by process working set	loses
Incremental rebuild	~1.2× per dirtied polygon	loses 5 of 6
Determinism across /O2 /Od /AVX2	bit-identical — and so is Recast	no advantage

Caveats we found in our own harness rather than being caught out on:

• The coverage gate was biased in our favour and has been corrected — it eroded on a lattice whose pitch equalled the agent radius, so it eroded nothing on diagonals. Every fixture moved against us; dungeon now passes by 0.59 points.
• Turning the radius filter on costs query time, it does not save it: expansions drop on every fixture but µs/path rises on three of four (+6.0% to +9.3%). Only dungeon gets faster.
• The radius filter's chord deficit is unbounded, not the bounded 8% first claimed. On a hairpin the walked line clears only 0.58× the planned radius. Waypoints are guaranteed; the straight line between them is not.
• Determinism is not a differentiator. Recast's bakes are bit-identical across the same three profiles. A fixed-point frame should pay across compilers, which one machine cannot test.

Full methodology, per-fixture numbers and variance: benchmarks/RESULTS.md · table only: benchmarks/README-TABLE.md · capability comparison: benchmarks/LEDGER.md

What is different

• Deterministic bakes. Bit-identical output for a given build configuration (requires /fp:precise).
• Per-chunk rebuilds. Each chunk is keyed by a hash of what it was baked from; move one crate and one chunk re-cooks. Re-stitching is scoped to chunks whose inputs actually moved.
• Dynamic obstacles at query time. A temporary blocker is composed in when a query runs, so dropping one costs no rebake at all — and costs nothing when absent.
• Agent radius is a query parameter, not a bake parameter. Michi stores a clearance field rather than eroding at bake time, so one mesh serves several agent sizes. This is also why its output is larger: it keeps a near-wall fringe Recast deletes.
• Solid-interior culling. No navmesh inside closed convex geometry, so a floor passing through a crate does not leave a sealed pocket an agent can be sent to and never reach.
• Island measurement, with streaming-safe culling: an island continuing into a chunk that is not loaded is never removed on the strength of the part you can see.
• A bake-time settings validator that tells you, in your own numbers, when the parameters cannot represent the geometry you have.

Gotchas

• cellSize and maxStepHeight cap the steepest representable slope at atan(step / 2·cellSize). Exceed it and ramps are silently cut apart and whatever they led to becomes an unreachable island. Raising maxStepHeight does not fix it; a smaller cell does. navCheckBakeSettings detects this and its message contains the numbers.
• finalize() is required before querying, and after every chunk change.
• NavPathScratch is caller-owned — reuse it, or you reintroduce the per-query allocation.
• Units are lattice cells; nav_tuning.hpp converts from metres and the rounding direction of each conversion is deliberate.

What it does not do

• No off-mesh / jump links. The serialised struct exists; nothing authors or stitches them.
• No crowd simulation. Detour has DetourCrowd; Michi has no equivalent and does not plan to.
• No tile-cache obstacle carving in Recast's sense.
• Bounded world extent. The headline is ±2,097 km at 0.98 mm, but the binding limit is ±16.8 km, because dynamic obstacles use a separate 2²⁴-mm frame. Beyond that, baking and pathfinding still work while obstacles silently stop.
• Freshness keying is mechanism, not policy — the library keys and splices chunks, but deciding what changed is the integrator's job.
• MSVC only in practice. GCC/Clang flags are wired but the library has never been compiled with them.
• Known defects, counted and listed in Agents.md: ear-clipping failures leave a small number of holes in the floor, and some contours are truncated at a vertex cap.
• Far less battle-testing than Recast, which has fifteen years and a great many shipped games behind it. Michi has one engine.

Licence

MIT — see LICENSE. recastnavigation is zlib licensed and no Recast code is included here; the lineage is acknowledged above and its test meshes are used as benchmark fixtures.