Flow fields in Godot: pathfinding for crowds that share a destination

Asking the same question a hundred times

A* is a question about one agent: given this start and this goal, what is the cheapest route? Ask it for a single unit and it is fast and exact. Ask it for two hundred units all heading to the same rally point, every time the goal moves, and you are recomputing almost the same search two hundred times a frame.

That is where pathfinding stops showing up in the average frame and starts showing up as a spike when everything repaths at once. The work is not just large; it is redundant. Most of those two hundred searches rediscover the same corridors and the same way around the same wall.

For the measured version of this idea, see the Godot 10,000-agent pathfinding benchmark: per-agent AStarGrid2D queries that collapse at 500 agents, replaced by one scheduled shared field that scales to 10,000.

When many agents share a destination, the per-agent question is the wrong question. There is a better one.

Invert the problem

Instead of asking, for each agent, how do I get from here to the goal, ask once, for every cell on the map: if I were standing here, which way is the goal? Answer that for the whole grid and an agent no longer searches at all — it looks up the cell it is standing on and reads a direction.

That precomputed answer is a flow field: a grid where each cell stores a direction vector pointing along the cheapest route to the goal. One computation produces guidance for every position at once, so a thousand agents cost barely more than one — they all read from the same field.

The trade is explicit and worth naming: you pay once, up front, per goal, instead of once per agent. The maths below is the price; the crowd is what you buy.

How a flow field is built

It is two passes. First the integration field: an expansion outward from the goal that records each cell's cheapest accumulated cost to reach it. The goal is 0; its neighbours cost a step more; blocked cells are skipped; a cell's cost is relaxed whenever a cheaper route to it is found. This is the same relaxation A* does, run once from the goal across the whole grid instead of from each agent toward it.

Then the flow pass: for every open cell, look at its neighbours and point toward the one with the lowest integration cost. Store that direction. That is the field. The compact example below uses queue-based relaxation; for a large weighted grid, use a real priority queue so the cheapest frontier cell is expanded first.

# Integration field: cheapest cost from every open cell to the goal.
# Queue-based relaxation keeps this example compact. For a large weighted grid,
# use a priority queue so the cheapest frontier cell is expanded first.
func build_integration(goal: Vector2i, w: int, h: int, blocked: PackedByteArray) -> PackedFloat32Array:
    var cost := PackedFloat32Array()
    cost.resize(w * h)
    cost.fill(INF)
    cost[goal.y * w + goal.x] = 0.0
    var frontier: Array[Vector2i] = [goal]
    var next := 0
    while next < frontier.size():
        var c := frontier[next]
        next += 1
        var base := cost[c.y * w + c.x]
        for n in neighbours(c, w, h):
            if blocked[n.y * w + n.x] == 1:
                continue
            var step := base + move_cost(c, n)  # ~1.0 orthogonal, ~1.4 diagonal
            if step < cost[n.y * w + n.x]:
                cost[n.y * w + n.x] = step
                frontier.push_back(n)
    return cost

# Flow field: each open cell points at its lowest-cost neighbour.
func build_flow(cost: PackedFloat32Array, w: int, h: int) -> PackedVector2Array:
    var flow := PackedVector2Array()
    flow.resize(w * h)
    for y in range(h):
        for x in range(w):
            var best := cost[y * w + x]
            var dir := Vector2.ZERO
            for n in neighbours(Vector2i(x, y), w, h):
                if cost[n.y * w + n.x] < best:
                    best = cost[n.y * w + n.x]
                    dir = Vector2(n.x - x, n.y - y).normalized()
            flow[y * w + x] = dir
    return flow

# Per agent, per frame: no search — read the cell, move along the vector.
func steer(agent: Agent, flow: PackedVector2Array, w: int) -> void:
    agent.velocity = flow[agent.cell.y * w + agent.cell.x] * agent.speed

When flow fields win — and when they don't

The deciding factor is the ratio of agents to distinct goals. Many agents, one or few shared goals — an RTS attack-move, a tower-defense lane, a crowd fleeing one exit — is the flow field's home ground: a single field amortised across the whole crowd. The more units share the destination, the more lopsided the win.

The opposite case is where A* still belongs: a handful of agents each heading somewhere different. Building a full-grid integration field so one unit can walk to one spot is wasted work — you computed directions for thousands of cells nobody will stand on. Few agents, many distinct goals: per-agent A*.

Real games are usually both, and the answer is to use both — flow fields for the shared-goal crowds, A* for the lone movers, on the same grid.

Dynamic goals and a changing map

A flow field is only valid for the goal and grid it was built from. Move the goal and the integration field is stale; open a door or drop a building and the costs around it are wrong. The naive fix — rebuild the whole field every frame — hands back the cost you just saved.

The same discipline that fixes per-agent repathing applies here: rebuild on change, not on a timer, and budget it. Recompute when the goal actually moves or the grid actually changes, cap how often a full rebuild can happen, and for localized edits repair only the affected region of the integration field rather than the entire map.

For a target that wanders constantly, a coarser field updated a few times a second usually looks better than a perfect field that stutters the frame to stay exact.

Where this sits in a real game

Flow fields are one layer in a navigation stack, not the whole thing. They pair naturally with the rest: influence maps bias the integration cost so the crowd flows around danger, not just around walls; clearance data keeps the field honest for agents that do not fit in a single cell; and where the built-in tools stop, you are past what AStarGrid2D was built to answer.

That combination — grids, tactical maps, flow fields, multi-size movement, and the diagnostics to see why a route is what it is — is the layer PathForge is being built to provide for Godot 4, for games where movement is the gameplay rather than a detail.