Navigation

world.nav builds a walkable heightfield from scene geometry and provides point lookup and A* pathfinding. It supports multiple height layers, slopes, steps, headroom checks, incremental scene updates, and optional path smoothing.

Navigation is cell-based, not a polygon navmesh. It does not account for agent radius.

Setup

Mark each mesh that should contribute to navigation before building:

floor.nav = true
// Alternatively:
floor.userData.nav = true

world.nav.build()

Only visible, non-skinned meshes with position geometry are included. A mesh is excluded if it or an ancestor has visible === false. Upward-facing triangles within agentMaxSlope produce walkable cells; all included geometry is also used to remove cells without sufficient headroom.

Configure navigation before calling build():

world.nav.configure({
	cellSize: 0.75,
	agentMaxHeight: 1.75,
	agentMaxClimb: 0.4,
	agentMaxSlope: 45,
	minFaceSize: 0.2,
	objectID: true,
})
world.nav.build()

Changing configuration after the initial build schedules a full rebuild during the next navigation update.

Points

Navigation queries return decoded point objects:

{
	x, y, z,              // cell center; y is the walkable surface height
	minHeight, maxHeight, // surface height range within the cell
	cellX, cellY, cellZ,
	id,                   // packed numeric point ID
	objectID              // optional source object ._id
}

objectID is present only when the build option is enabled. It is null when the contributing object has no supported numeric ._id. When geometry from multiple objects merges into the same cell layer, the object that supplies the strictly highest maxHeight owns the cell; an exact tie keeps the first owner. The option adds one Uint32 (4 bytes) to each allocated packed point slot.

Decoded points belong to the current world.nav.version. Resolve them again after the version changes.

getPointAt(position, options?)

Returns the closest height layer in the position's exact XZ cell, or null. maxVerticalDistance defaults to one cellSize. This method does not search neighboring XZ cells. An infinite vertical distance scans only the height layers stored in that XZ column.

const point = world.nav.getPointAt(feetPosition, {
	maxVerticalDistance: 0.5,
})

getNearestPoint(position, options?)

Returns the nearest point within the supplied horizontal and vertical limits, or null. Both limits default to cellSize * 4 and may be Infinity. With a finite horizontal limit and an infinite vertical limit, columns are visited outwards from the query and the search stops once unvisited columns cannot contain a closer point.

const point = world.nav.getNearestPoint(position, {
	maxDistance: 3,
	maxVerticalDistance: 2,
})

Other point queries

world.nav.getPoint(pointId)          // decoded point or null
world.nav.getPoints(object, includeBelow) // includeBelow defaults to false
world.nav.getNeighbors(pointOrId)    // directly reachable adjacent points
world.nav.getColumn(cellX, cellZ)    // indexed height layers sorted by cellY

getPoints(object, includeBelow = false) returns existing navigation points overlapped by the world-space bounding boxes of the object's supported visible meshes. Groups are traversed and duplicate points are removed. By default, a point matches when its XZ cell overlaps the object and its surface height intersects the object's vertical bounds. Pass true to also include points below the object when the standing volume from the point through agentMaxHeight intersects it. It returns [] when the map is empty or the object has no supported geometry.

The query does not create navigation cells. Its results are decoded current-map points, so their IDs can be used directly as dynamic blockers:

const occupied = world.nav.getPoints(object)
for (const point of occupied) world.nav.dynamic.add(point.id)

const occupiedIncludingBelow = world.nav.getPoints(object, true)

getPoints() assumes the object's world matrices are already up to date. It uses the current matrixWorld without recomputing it. Call object.sync() after transform changes and query after the engine has processed that update. Re-query after either the object moves or world.nav.version changes.

getRandomPoint(options?)

Returns a uniformly selected walkable point, or null when no point matches. Pass a seeded random function for deterministic placement, a filter for game-specific clearance rules, and dynamic: true to exclude point IDs in world.nav.dynamic.

const point = world.nav.getRandomPoint({
	random: seededRandom,
	dynamic: true,
	filter: point => point.y < 2,
})

The first query after a navigation change lazily builds a compact four-byte slot index for each walkable point. maxAttempts defaults to 64; queries use that dense index for O(1) rejection samples without probing empty hash slots. If those attempts do not find a match, the query scans only the occupied index with reservoir sampling so sparse filters still receive an unbiased result.

Neighbor lookup checks the eight surrounding XZ cells and cellY - 1 through cellY + 1. Diagonal moves require both intervening cardinal cells, so paths cannot cut across missing corners.

Pathfinding

findPath(start, end, options?)

start and end may be world positions, current decoded points, or point IDs. World positions are projected with getNearestPoint().

const result = world.nav.findPath(agentFeetPosition, destination, {
	maxDistance: 2,
	maxVerticalDistance: 2,
	maxVisited: 10000,
	allowPartial: true,
	smooth: true,
	maxSmoothingChecks: 2048,
	dynamic: false,
	constraints: [worldSpaceBox, worldSpaceSphere],
})

if (result.status === 'complete') {
	agent.path = result.points
}

result.status is one of complete, partial, unreachable, invalid-start, invalid-end, or empty. result.reason, when present, is max-visited, unreachable, dynamic-end-blocked, or constraint-end-blocked.

Successful and partial results include:

result.points          // movement waypoints, smoothed by default
result.rawPoints       // unsmoothed A* cells
result.startPoint
result.endPoint
result.reachedPoint
result.visited
result.cost
result.durationMs
result.version         // map version used by this query
result.smoothed
result.smoothingChecks

Discard or recompute a path when result.version !== world.nav.version.

smoothPath(points, options?)

Smooths an array of current decoded navigation points. Returns [] for stale or invalid points.

const smoothed = world.nav.smoothPath(rawPoints, {
	maxChecks: 2048,
	dynamic: true,
	constraints: [worldSpaceBox, worldSpaceSphere],
})

constraints accepts an array (or one value) containing world-space Box3 and Sphere instances. Plain { min, max } and { center, radius } objects with finite coordinates are also accepted. Each shape is tested against the full XZ extent and the walkable surface-height span of every navigation cell it covers. Invalid or empty shapes are ignored. Constraints are query-local: they do not mutate world.nav.dynamic or increment world.nav.version.

As with dynamic blockers, a blocked start cell remains usable. With allowPartial: false, a constrained destination returns unreachable with reason: 'constraint-end-blocked'. Smoothing uses the same constraints, so a smoothed segment cannot shortcut through them.

Dynamic blockers

world.nav.dynamic is a game-managed Set of point IDs. Add occupied or temporarily blocked cells, then pass dynamic: true to findPath() or smoothPath().

world.nav.dynamic.add(point.id)
world.nav.dynamic.delete(point.id)
world.nav.dynamic.clear()

The resolved start point remains usable if its ID is blocked. Dynamic blockers do not modify the navigation map or its version. For A* queries, blocker IDs are resolved into reusable packed-point slot stamps once at the start of the synchronous query. Neighbor and diagonal checks then use typed-array lookups; world.nav.dynamic remains the public mutation API.

Runtime updates

After build(), added, removed, transformed, replaced, and visibility-changed navigation meshes are updated automatically in 32-by-32-cell tiles at the end of the frame. Large or unbounded changes fall back to a full rebuild. The runtime column index is rebuilt only for affected tiles. If incremental insertion grows and rehashes packed point storage, that update rebuilds the complete column index so its stored point slots remain valid.

Call object.sync() after transform changes as usual. If position data was mutated in place, explicitly invalidate the mesh:

world.nav.invalidate(mesh) // rebuild affected tiles
world.nav.invalidate()     // schedule a full rebuild

clear() removes all navigation data, dynamic blockers, and debug rendering.

Debugging and state

world.nav.debug(true)  // show walkable points
world.nav.debug(false) // hide them without clearing the map

world.nav.config
world.nav.points       // packed runtime point map
world.nav.stats        // build, update, column-index, storage, and pathfinding metrics
world.nav.version
world.nav.debugEnabled

world.nav.sourcePoints currently aliases world.nav.points because clearance prunes the build map in place. world.nav.stats.sourcePoints records the count before clearance; stats.points records the retained count.

For engine development, window.testNavMesh(options?) automatically marks supported meshes whose direct nav property is undefined, builds the map, and enables debug rendering. window.testNavMesh(false) clears it. Normal game code should explicitly mark meshes and use world.nav.build().

Limitations

• No agent-radius erosion or per-query agent dimensions.
• Vertical walls conservatively block every cell touched by their XZ projection.
• Neighbor lookup only checks the three nearest Y layers.
• A getNearestPoint() query with an infinite horizontal limit scans the entire map; infinite vertical limits remain column-indexed when horizontal distance is finite.
• Debug rendering reuploads the complete point map after an incremental update.