Pathfinding with flow fields

When thousands of units head for the same place (a rally point, the player, the nearest food), searching a path for each of them is wasteful. A flow field does one search from the goal outward and stores, for every cell of the map, which way to step. Each unit then just looks up the cell it stands on: one array read, the same cost for 10 units as for a million.

Two types do this:

• NavGrid: the map. A cost per cell: 1 is normal ground, up to 255 is slower (mud, shallow water), NavGrid::WALL (0) can’t be entered.
• FlowField: the answer. compute(&nav, &goals) fills it; then direction_at(pos) gives a unit vector toward the nearest goal and distance_at(pos) how far away it is.

The map

#![allow(unused)]
fn main() {
let mut nav = NavGrid::new(100, 80, 4.0); // 100 × 80 cells, 4 world units each
for y in 0..60 {
    nav.set_cost(40, y, NavGrid::WALL);
}
for x in 50..70 {
    for y in 20..40 {
        nav.set_cost(x, y, 6); // mud: six times slower
    }
}
let mut flow = FlowField::new();
flow.compute(&nav, &[vec2(390.0, 10.0)]); // or several goals: the nearest wins
}

static void make_walls(crabby::nav_grid& nav) {
    // 1 is normal ground, higher is slower (mud), nav_grid::wall blocks.
    for (std::uint32_t y = 0; y < 60; ++y) nav.set_cost(40, y, crabby::nav_grid::wall);
    for (std::uint32_t x = 50; x < 70; ++x)
        for (std::uint32_t y = 20; y < 40; ++y) nav.set_cost(x, y, 6);
}

    crabby::nav_grid nav(100, 80, 4.0f);   // 100 x 80 cells, 4 world units each
    make_walls(nav);
    crabby::flow_field flow;
    flow.compute(nav, crabby::vec2{390, 10});   // or several goals: the nearest wins

nav.origin (C++: set_origin) moves the grid: it is where cell (0, 0)’s top-left corner is in the world. nav.cell_at(pos), nav.center_of(cell) and nav.walkable(pos) convert between world points and cells. To fill a whole map at once (from a tilemap, an image, a level file), write nav.costs_mut() (C++: nav.costs()), one byte per cell, row by row.

Paths move in 8 directions. Diagonal steps cost √2 times a straight one, and never squeeze between two walls that touch at a corner. Slow ground counts as longer: a unit walks around a mud pit when the way around is shorter than wading through.

Steering

direction_at only reads, so any number of threads can use one field at once. Look it up from a parallel query:

#![allow(unused)]
fn main() {
/// Every agent steers along the field; mud slows it down, walls stop it.
fn steer(ctx: &mut Ctx) {
    let dt = ctx.dt();
    let random = ctx.random();
    // Taken out for the query, which borrows the world, then put back.
    let paths = ctx.world.remove_resource::<Paths>().expect("paths");
    ctx.world
        .query::<(Entity, &mut Transform2D, &mut Agent)>()
        .par_for_each(|(e, t, a)| {
            let mut rng = random.of(e);
            let cell = paths.nav.cell_at(t.position);
            let slow = cell.and_then(|c| paths.nav.cost(c.x, c.y)).unwrap_or(1).max(1) as f32;
            let want = paths.flow.direction_at(t.position) * (SPEED / slow);
            a.vel = a.vel.lerp(want, 0.15) + rng.unit_vec2() * 3.0;
            // Slide along walls instead of walking into them.
            let next = t.position + a.vel * dt;
            if paths.nav.walkable(next) {
                t.position = next;
            } else if paths.nav.walkable(vec2(next.x, t.position.y)) {
                t.position.x = next.x;
            } else if paths.nav.walkable(vec2(t.position.x, next.y)) {
                t.position.y = next.y;
            }
        });
    ctx.world.insert_resource(paths);
}
}

static void steer(crabby::ctx& ctx, const crabby::flow_field& flow) {
    const float step = 40 * ctx.dt();
    const crabby::flow_view view = flow.view();   // inline lookups, safe from every thread
    ctx.world().each_par([&](crabby::transform2d& t) {
        t.position += view.direction_at(t.position) * step;
    });
}

In C++, flow.view() gives a flow_view whose direction_at is inline, with no call into the engine per lookup. Take a new view after every compute.

The direction is zero at a goal, on a wall, outside the grid and where no goal can be reached; distance_at returns nothing (None, C++ std::nullopt) in the last case. Moving a unit straight along the direction can clip a wall corner, so the example slides along walls with nav.walkable instead of stepping onto them.

When the goal moves

Call compute again: the field reuses its memory, so recomputing every time the player clicks or a target moves is fine. For many different destinations (each squad to its own target), keep one FlowField per destination, not one per unit.

Measured in release on a MacBook Pro (M4 Max) (cargo run --release -p ponko_bench -- flow):

The flow example (cargo run --release --example flow) has 20 000 units finding their way around walls and through mud to wherever you click; H shows the distance field. Headless with a million units (HEADLESS=1 AGENTS=1000000 cargo run --release --example flow) a tick takes 3.2 ms, steering and all.

For a whole game built on flow fields, see the battle example: two armies, one field each, rerouted when you click a new rally point (cargo run --release --example battle).