Byte Engine Docs

Find paths around obstacles

Declare where characters can walk and what blocks them, find each character a path to its target around the obstacles, and steer characters around each other.

Give characters such as NPCs a way to reach a target without walking through walls. You mark the floors as walkable and the walls as obstacles, and the navigation system builds a navigation mesh from them. Each tick, a character asks the mesh for a path to its target and walks toward the path's next corner, steering around the other characters on its own.

Create the navigation system

Create a Navigation system on the world scope before you create the areas. It builds only from the areas published after it exists:

let navigation = Navigation::new(app.world(), app.parameters().scope("navigation"));

Keep it where your gameplay can reach it, such as the state your tasks share.

Mark floors and obstacles

Create a navigation area beside each floor and wall, with a transform that places it. An area is a rectangle given by its half extents along local X and local Z:

app.world()
	.create(NavigationArea::walkable(100.0, 100.0))
	.with(Transform::identity());

app.world()
	.create(RenderableMesh::generated(wall_mesh))
	.with(NavigationArea::obstacle(0.25 + CHARACTER_RADIUS, 6.0 + CHARACTER_RADIUS))
	.with(Transform::from_position(Point::new(6.0, 1.5, 12.0)));

Paths are for a point, so make each obstacle larger than its wall by the character's radius, plus however far your characters cut corners: aiming a little way along the path, as the next section does, cuts a corner by about a third of that distance. Characters then pass the wall with their body clear of it.

Update the mesh each tick

Call update at the start of the tick, before anything searches the mesh, with the time since the last tick. It rebuilds the mesh only when an area was created, moved, or deleted:

if let Err(error) = navigation.update(time.delta()) {
	eprintln!("{error}");
}

Follow a path

Search from where the character stands to its target, and head for the second corner of the path: the first corner is the start. The search moves both ends onto the mesh first, because a character that cuts a corner, or a target that stands against a wall, can be just off it:

let corners = navigation.find_path(character, target, &mut path).ok()?;
let next_corner = corners.get(1).copied();

Keep path between searches to reuse its storage. Search again when the target moves or the route needs updating. The route accounts for walls and walkable surfaces; steering handles moving characters separately. Add up the distances between route corners to choose the gait and decide when to stop near the target.

Steer around other characters

Make every character that others should avoid a navigation agent, including the player's. Give it the character's radius:

app.world()
	.create(RenderableMesh::resource(MODEL))
	.with(NavigationAgent::new(CHARACTER_RADIUS))
	.with(transform);

Each tick, pass the velocity the character means to move at: toward the path's next corner at its gait's speed, or zero to stand. Steering returns a direction around other characters and a speed ceiling for following a slower character ahead or approaching the mesh boundary:

let steering = navigation.steer(character, toward_corner * WALK_SPEED);
let velocity = steering.velocity;

Aim the character a little way along its path, such as 0.8 m, rather than at the next corner, so each turn starts before the corner. Turn its heading toward the result at a rate bounded by how hard it can lean into a turn, such as 10 m/s² divided by its speed, up to 150° per second: a walk then turns on half a meter and a sprint on about 4 m. Choose the desired gait from route distance, then reduce it when steering reports a lower speed ceiling. Steering retains the side of a pass while the blocking character remains ahead. A character following another in the same direction yields speed instead of trying to overtake it. With root-motion clips, choose a gait at or below the returned speed ceiling and allow room for the stopping animation. Before a stopped follower sets off, check steering.following_speed: this ceiling isn't limited to the requested gait speed, so you can require room for a complete start and stop. A character that means to stand gets a velocity only when others press on it; move it when that velocity is more than a brush, such as above 0.5 m/s.

Give precedence to whoever should hold their ground when two characters meet: a character steps aside only for others of equal or greater precedence. Rank the player highest, a settled character by how early it settled, and a moving one lowest. With root motion, wait for the stopping clip to reach a standing state before giving settled precedence or requesting another start. Publish the agent again under its handle as the character settles or sets off. A late arrival that lands on a settled character then moves itself out, and the settled one keeps its spot:

world.channel::<CreateMessage<NavigationAgent>>().send(CreateMessage::new(
	character,
	NavigationAgent::new(CHARACTER_RADIUS).with_precedence(-settled_at),
));

See the paths

Register the debug mesh render pass after tone mapping, and create the navigation system with its parameters so navigation.debug reaches it:

byte_engine::application::graphics::setup_debug_mesh_render_pass(&mut app);
let navigation = Navigation::new(app.world(), app.parameters().scope("navigation"));

Then run with --navigation.debug=true. The mesh's boundary draws in cyan, each character's radius in purple on the floor, and its latest path in amber.

Rust API

On this page