Navigation

Pathfinding over terrain and around buildings: bake where an agent can stand, then ask for routes around walls, up gentle slopes and over kerbs, the same on the web, the JVM and Native.

module: awake:navigation Desktop · Android · iOS · Web

com.awakekt.awake:navigation bakes where an agent can stand from terrain heights and static colliders, and searches it with A*. It is common Kotlin with no platform code, so a browser client and an authoritative JVM server bake the same bytes and find the same route. The AI behaviours use it to walk.

There are two ways in. A walkable surface reads terrain, obstacles, water and no-walk areas, and answers for any agent radius, with the nearest reachable point when a target cannot be reached. A walkability grid reads terrain slope alone and backs the streamed and hierarchical grids below. Start with the surface.

Bake a walkable surface

Describe the agent, list what is in the way, and bake a region:

Kotlin

val agent = NavAgent(radius = 0.4f, height = 1.8f, stepHeight = 0.3f, maxSlopeDegrees = 40f)
val areas = NavAreas(
    obstacles = listOf(
        // A house: its world bounds, from the ground to the roof.
        NavObstacle(NavFootprint.Rect(20f, 20f, 30f, 32f), minY = 0f, maxY = 6f),
        // A well: an upright cylinder.
        NavObstacle(NavFootprint.Circle(40f, 12f, 1.2f), minY = 0f, maxY = 1f),
    ),
    noWalk = listOf(NavFootprint.Rect(50f, 50f, 60f, 60f)), // a fenced field
    water = NavWater(surfaceY = -1f, maxDepth = 0.5f),
)
val ground = NavGroundHeight(heightmap::heightAtWorld) // NaN off the map reads as blocked
val surface = bakeNavSurface(NavRegion(0f, 0f, 129, 129, 0.5f), ground, agent, areas)

A sample is blocked when the ground has no height there, when the terrain to any neighbour is steeper than maxSlopeDegrees, when the water is deeper than maxDepth, when a no-walk outline touches it, or when an obstacle touches it and is too high to step over (stepHeight) and too low to walk under (height). Obstacles are tested against the ground under each sample, so a crate on a hill is as tall as the crate. Cells are tested rather than centres, so a wall thinner than a sample still blocks.

The bake stores each sample's distance to the nearest blocked one, not a bit. That is what lets the radius wait for the query: one surface serves a narrow and a wide agent of the same height class.

Find a path

Kotlin

val query = NavPathQuery(surface, ground) // keep one per thread and reuse it
val path = NavPath() // the agent owns its path and reuses it too
when (query.findPath(Vec3f(10f, 0f, 26f), Vec3f(40f, 0f, 26f), agent, path)) {
    NavPathStatus.Complete -> Unit // path ends at the target
    NavPathStatus.Partial -> Unit // path ends at the reachable point nearest the target
    NavPathStatus.NoPath, NavPathStatus.None -> Unit // nowhere to stand at the start
}
val next = path.get(1, Vec3f()) // read waypoints without allocating

Status	What the path holds
`Complete`	From the start to exactly the target, through the corners that matter.
`Partial`	To the reachable point nearest the target: the target is walled in, across water, inside a building, or past the node budget.
`NoPath`	Nothing: the start has nowhere to stand within `snapSamples`.

An endpoint inside an obstacle first moves to the nearest standable sample, so an agent pushed into a wall still finds its way out, and a target inside a building is reached at its wall.

Reuse the query and the path

NavPathQuery keeps its search state between queries and NavPath keeps its waypoints in one float array, so a warm query allocates nothing. Keep one query per thread; a server answering many agents keeps one per worker.

A search expands at most maxExpandedNodes samples. The budget counts nodes, not milliseconds: a time budget would make a route depend on the machine, and a server and its clients must agree. A route across a kilometre of town at 1 m expands about 120,000 samples in about 50 ms on a desktop JVM.

Follow a route

NavPathFollower walks one agent along routes from a query. It plans when given a destination, steers toward each corner, and re-plans every repathInterval and whenever the agent makes less than stuckDistance of progress in stuckSeconds, so an agent pushed off its route or held by something the surface does not know about finds its way again from where it is:

Kotlin

val follower = NavPathFollower(agent)
follower.moveTo(Vec3f(40f, 0f, 26f))
// Each frame: ask which way to walk, then move the agent however the game moves it.
while (follower.update(query, position, delta = 1f / 60f, direction) && frames++ < 3_000) {
    position.x += direction.x * 4f / 60f
    position.z += direction.z * 4f / 60f
}

The follower only gives a direction; whatever moves the agent, a character controller, a transform or a network, does the moving. It keeps its route in its own NavPath and borrows the query, so following and re-planning allocate nothing per frame.

Walk an agent in a scene

A navigation_agent component walks its node to a destination over the scene's navigation grid, with nothing wired by the host: runProject runs NavigationAgentSystem for it. With a movement_control whose driver is Agent, the agent walks through the control, so a character_controller carries it over slopes and steps and walls stop it; without one it moves by its transform. Here one agent of each kind walks through the gap in a wall:

Kotlin

        /** A 12 by 12 yard. A wall across z = 5 from x = 0 to 8 leaves a gap at x = 9 to 11. */
        const val YARD_SCENE = """
{ "version": 1, "name": "yard", "nodes": [
  { "name": "Map", "components": [ { "component": "navigation", "cellSize": 1.0, "rows": [
    "............", "............", "............", "............", "............",
    "#########...",
    "............", "............", "............", "............", "............", "............" ] } ] },
  { "name": "Walker", "transform": { "position": { "x": 1.0, "y": 0.0, "z": 1.0 } }, "components": [
    { "component": "navigation_agent", "radius": 0.3, "speed": 4.0, "destinationX": 1.0, "destinationZ": 10.0 } ] },
  { "name": "Steered", "transform": { "position": { "x": 4.0, "y": 0.0, "z": 1.0 } }, "components": [
    { "component": "movement_control", "driver": "Agent" },
    { "component": "navigation_agent", "radius": 0.3, "speed": 4.0, "destinationX": 4.0, "destinationZ": 10.0 } ] }
] }
"""

destinationX and destinationZ give it somewhere to go as the scene starts. Code sends it elsewhere, such as from a click-to-move handler, with world.get<NavigationAgent>(entity)?.moveTo(target), and stops it with stop(). The fields are on the scene document components reference. A scene with a navigation_agent and no navigation does not load.

Outside a played project, add NavigationAgentSystem(grid.surface) to the world yourself, where grid is the scene's NavigationGrid or any NavSurface. It runs one query for every agent on the frame thread, and allocates nothing per frame.

Large regions and caching

Bake a large region as a lattice of tiles, and cache each tile's bytes:

Kotlin

val world = NavTiledSurface(tilesX = 4, tilesZ = 4, tileSamples = 32, sampleSize = 0.5f)
for (tileZ in 0 until 4) {
    for (tileX in 0 until 4) {
        val tile = bakeNavSurface(world.regionOf(tileX, tileZ), ground, agent, maxAgentRadius = 1f)
        val bytes = NavSurfaceCodec.encode(tile) // cache these; decode instead of re-baking
        world.put(tileX, tileZ, NavSurfaceCodec.decode(bytes))
    }
}

Each tile is baked looking maxAgentRadius past its border, so tiles baked separately, or on different machines, join without a seam. A tile not yet put reads as blocked, and a route stops at the edge of what is loaded. NavSurfaceCodec writes a versioned little-endian layout and rejects bytes it does not recognise rather than decoding them into a different surface.

Walkable surface reference

Call or property	Type	Default	What it does
`NavAgent(radius, height, stepHeight, maxSlopeDegrees)`		`0.4`, `1.8`, `0.3`, `45`	The body routed. Height, step and slope are baked; the radius is read by the query.
`NavObstacle(footprint, minY, maxY)`			A static collider: a `NavFootprint.Rect` or `Circle` spanning `minY..maxY`.
`NavAreas(obstacles, noWalk, water)`		none	Everything besides terrain that blocks.
`NavWater(surfaceY, maxDepth)`		depth `0`	Water deeper than `maxDepth` is blocked.
`bakeNavSurface(region, ground, agent, areas, maxAgentRadius)`	`NavSurfaceTile`	`agent.radius`	Bakes one region; `ground` returns `NaN` where there is none.
`NavGridTile.toNavSurface()`	`NavSurfaceTile`		A slope-baked grid tile as a surface, without re-baking.
`NavTiledSurface(tilesX, tilesZ, tileSamples, sampleSize, originX, originZ)`	`NavSurface`	origin `0`	A lattice of tiles searched as one surface.
`NavPathQuery(surface, ground, maxExpandedNodes, snapSamples)`		`FLAT`, `200000`, `8`	The reusable query; `ground` gives waypoint heights.
`NavPathQuery.findPath(from, to, agent, out)`	`NavPathStatus`		Writes the route into `out`.
`NavSurfaceMesh(surface, agent)`	`NavMesh`		The surface for `PathRequestSystem` and the AI behaviours.
`NavPathFollower(agent)`			Plans, steers and re-plans one agent; `arriveDistance` `0.25`, `waypointRadius` `0.35`, `repathInterval` `2`, `stuckSeconds` `0.75`, `stuckDistance` `0.1`.

Find a path on a slope grid

Bake a grid from a Heightmap, search it, then smooth the result:

Kotlin

val tile = heightmap.bakeNavGrid(cellSize = 1f, maxSlopeDegrees = 45f)
val path = tile.findPath(start = Vec3f(-5f, 0f, -5f), goal = Vec3f(5f, 0f, -5f))
val route = tile.smoothPath(path) // drops waypoints the ones around them can see past

A sample is walkable when the ground rises no more than maxSlopeDegrees to each of its four neighbours, cellSize metres away. findPath returns an empty list when no route exists, including when either end is off the grid.

Ask from an entity

Inside the ECS, an entity asks through a PathRequest component and PathRequestSystem answers it:

Kotlin

val navMesh = NavGrid(heightmap.bakeNavGrid())
val paths = PathRequestSystem(navMesh) // pass a CoroutineScope to search off the frame thread

val request = PathRequest()
world.add(agent, request)
request.requestPath(from = Vec3f(-5f, 0f, -5f), to = Vec3f(5f, 0f, -5f))

paths.update(world, 1f / 30f)
if (request.status == PathStatus.Ready) {
    println("walk ${request.waypoints}")
}

PathRequest.status moves Idle → Pending → Ready or Unreachable. cancel() returns it to Idle and drops any answer. The system answers only pending requests, so a route stays put until its owner asks again.

Properties

Call or property	Type	Default	What it does
`bakeNavGrid(cellSize, maxSlopeDegrees)`	on `Heightmap`	`1`, `45`	Bakes a whole heightmap into a `NavGridTile`.
`bakeNavGridCell(samples, sampleSize, maxSlopeDegrees)`	on `Heightmap`	`45`	Bakes exactly `samples × samples`, for one streamed cell.
`NavGridTile.findPath(start, goal)`	`List<Vec3f>`		8-connected A*. Waypoints carry X and Z; Y is `0`.
`NavGridTile.smoothPath(path)`	`List<Vec3f>`		Removes waypoints the neighbours can see past.
`NavGrid(tile)`	`NavMesh`		A single tile as the `NavMesh` that `PathRequestSystem` searches.
`PathRequestSystem(navMesh, searchScope)`	`System`	no scope	Answers requests; with a `CoroutineScope`, searches run off the frame thread and land on the next update.

Large and streamed worlds

Type	What it is
`StreamedNavGrid(samplesPerCell, sampleSize)`	A `NavMesh` over one tile per loaded world cell. Routes stop at the edge of what is loaded.
`NavGridCellStreamer(grid, config, heightmapAt, …)`	An `AsyncWorldCellStreamListener` that bakes each cell's tile off the frame thread as it streams in.
`HierarchicalNavGrid(grid, coarse)`	Plans across unloaded cells with a `CoarseNavGraph` and returns the next loaded leg.

Wire NavGridCellStreamer into a WorldPartitionSystem; see Large worlds.

How the grid works

A NavGridTile stores one bit per sample: walkable or not. It records only terrain shape, so waypoints carry X and Z and leave Y at zero; read the height from Heightmap.heightAtWorld if you need it. Tiles are immutable once baked, which is what lets a search read one off the frame thread.

Only slope blocks a grid path

bakeNavGrid reads terrain height and nothing else. For buildings, props, water and agent width, bake a walkable surface instead. Moving agents are neither's job: that is local avoidance.

Keep searches off the frame

A* over a large grid costs milliseconds. Pass a CoroutineScope to PathRequestSystem so a search does not stall the frame, and repath on an interval rather than every frame.

Debugging

navGridDebugLines returns world-space lines: a cross on every blocked sample, and each agent's route if you pass routes. NavDebugSource draws the same lines through the debug registry, turned on with --debug=nav, and counts walkable and blocked samples on the debug panel; see Debug tools.

Kotlin

val lines = navGridDebugLines(tile, surfaceAt = { x, z -> heightmap.heightAtWorld(x, z) })
// Hand `lines` to the renderer's debug-line pass with any other debug lines you draw.

Navigation

Bake a walkable surface

Find a path

Follow a route

Walk an agent in a scene

Large regions and caching

Walkable surface reference

Find a path on a slope grid

Ask from an entity

Properties

Large and streamed worlds

How the grid works

Debugging

See also