Ductane v1.4.0
Contents

Docs / Characters

Finding a way

NavigationGrid answers the question steering cannot: how does this character get there? It lays standing places over the ground and every floor in a CollisionMesh — decks, stairs, ramps, roads — joins the ones a body could walk between, and searches them for a path. Use it for anything that chases or patrols: an enemy round a long wall, up the stairs to a walkway, down off a ledge.

What it is

A grid of 0.4 meter columns. Each column holds as many standing places as it has floors a body fits on, so the ground under a raised deck and the deck itself are two places in one column. A place is found with the same questions a CharacterController asks the same mesh:

Two neighboring places are joined when the rise between them is a step (Body.stepHeight), an even slope — a ramp, not the side of a crate — or a drop a body would walk off but never climb (Body.drop). A diagonal is joined only when both of its sides are, so a path never cuts a corner through a wall.

It is a layered grid rather than a mesh of polygons on purpose: built from the controller's own questions, it agrees with the controller about where a body can stand, and needs no voxelizing, contours or triangulation.

Building one

Build it off the main thread, round the player, over the same reach you built the collision mesh in — a 200 meter square is a quarter of a million columns. Hand it to whatever does the chasing when it is done, and keep using the old one until then.

let body = NavigationGrid.Body(enemyTuning)          // height and step from a controller's tuning
let grid = await Task.detached(priority: .utility) {
    NavigationGrid(mesh: mesh, ground: { p in (height(p), isDry(p)) },
                   around: playerPosition, reach: 100, body: body)
}.value

ground answers two things at a point across the ground: its height, and whether a body can stand there. Say no in water too deep to wade, and paths go round it. headroom limits how far above the ground floors are looked for (16 meters by default).

Body(_:clearance:drop:) takes the standing height and step from a CharacterController.Tuning. The clearance, 0.25 meters by default, is deliberately less than a body's radius: the controller slides along a wall it brushes, and at a full radius a narrow doorway falls between the grid's centers half the time.

Asking for a path

if let points = grid.path(from: enemy.feet, to: player.feet) {
    // walk toward points[0]; when you are over it and on its floor, the next
}

The answer is the points to walk through in turn. The search walks the grid's places, then cuts a straight line through every run of them it can, so a path round a wall is its corners, not a staircase of cells. It ends at the goal's standing place — or, if nothing reaches the goal, at the reachable place nearest it, so a character comes as close as it can and waits there. nil means one end is off the grid; an empty path means the start is the goal.

place(near:within:) finds the standing place under a body, preferring the floor it stands on over the one above it, and looking a little way round when the body leans on a wall. contains(_:) says whether a point is inside the grid.

Following one

Count a point as reached only when the body is over it and on its floor — within a few tenths of a meter across and of height. A looser test lets a character at the foot of a ramp count the point at its top edge as reached, turn for the next one, and walk into the ramp's side.

Search again every half second or so while the target moves. A search that ends short — a target nobody can reach — costs the whole of searchLimit, so search again less often after one of those, unless the target moves.

Costs

An engine runs unoptimized in a game's Debug build, so plan for that build. A search that reaches its goal takes a few milliseconds there, one that cannot reach about ten; an optimized build is many times faster. Building the grid is dominated by the collision mesh's own queries: a fraction of a second optimized, several seconds in Debug, which is why it belongs off the main thread.

What it does not do

It moves nothing: following the path, keeping characters apart and stepping round each other is the game's. It does not climb ladders or jump gaps, and it is not rebuilt when something moves — build it again when the scene changes. It knows nothing of Surroundings.solids; it reads the collision mesh and the ground.