Multi-size agents in Godot: clearance maps without the headaches

The problem: your pathfinder thinks every unit is one cell

Grid pathfinding in Godot, including AStarGrid2D, reasons about a single moving point. It asks whether a cell is walkable and how much it costs to enter, and it returns a sequence of cells. That model is correct for a 1×1 unit and quietly wrong for anything bigger.

The symptom is familiar to anyone who has shipped a game with mixed unit sizes. A 3×3 vehicle gets a perfectly valid one-cell path straight through a doorway it physically cannot enter. It either clips through the wall, jams in the gap, or wanders off while the navigation system insists everything is fine. The pathfinder did its job. Its job just did not include the agent's footprint.

The question this post answers: how do you make one grid serve a 1×1 scout, a 2×2 tank, and a 3×3 hauler, without three separate maps and without checking the whole footprint on every step of every search.

Why this is harder than it looks

The naive instinct is to check, at each step of the search, whether the agent's full footprint fits at the candidate cell. For a 3×3 agent that is nine cell lookups per neighbour, per expansion, per query. Multiply by agents and by frequency and you have rebuilt the frame-spike problem from a different direction.

It is also not just about size. Real games change the grid: doors open and close, buildings go up, a destroyed wall opens a new route. Whatever structure you use to answer can a unit this big stand here has to survive those changes without a full rebuild each time. And it has to handle several sizes at once, because precomputing a separate walkability grid per size multiplies both memory and the bookkeeping you have to keep in sync.

So the real constraints are three: answer the footprint question in roughly constant time during the search, share one structure across all agent sizes, and update cheaply when the world changes.

The naive fixes, and where they hurt

Inflate the obstacles. Grow every blocked region by the agent radius and run normal pathfinding on the inflated grid. This works for exactly one size. With mixed sizes you would need one inflated grid per size, and inflating for the largest unit closes narrow routes that smaller units could legitimately use.

One grid per size. Precompute a separate walkability grid for 1×1, 2×2, 3×3, and so on. It answers fast, but memory grows with the number of sizes and every dynamic change has to be applied to every grid. The synchronisation cost is where this one quietly rots.

Footprint check during the search. Keep one grid and test the full footprint at each candidate cell. Correct, no extra memory, and the most common thing people ship first. It is also the slowest, because it redoes the same footprint math constantly and turns a cheap A* into an expensive one right where the frame budget is tightest.

Each of these is a reasonable first move. The version that scales keeps the single-grid memory profile of the third option and the constant-time query of the second.

Clearance maps: precompute the fit once

A clearance map stores, for every open cell, the side length of the largest open square that fits with its corner at that cell. A cell next to a wall has clearance 1; an open cell with enough room around it has clearance 3 or more; a blocked cell has clearance 0.

The point is that this collapses the footprint question into a single number. An agent of size N may stand on a cell only if that cell's clearance is at least N. One 3×3 lookup becomes one integer comparison, and the same map answers for every size: a 1×1 needs clearance ≥ 1, a 3×3 needs clearance ≥ 3.

Building it is one pass over the grid, computed bottom-right to top-left so each cell can reuse three neighbours it has already seen:

# clearance[i] = side of the largest open square whose top-left corner is cell i.
# Filled bottom-right to top-left so each cell reuses three computed neighbours.
func build_clearance(blocked: PackedByteArray, w: int, h: int) -> PackedInt32Array:
    var clr := PackedInt32Array()
    clr.resize(w * h)
    for y in range(h - 1, -1, -1):
        for x in range(w - 1, -1, -1):
            var i := y * w + x
            if blocked[i] == 1:
                clr[i] = 0
            elif x == w - 1 or y == h - 1:
                clr[i] = 1
            else:
                clr[i] = 1 + mini(clr[i + 1], mini(clr[i + w], clr[i + w + 1]))
    return clr

Querying clearance during the search

With the map built, the search barely changes. Wherever the A* expansion considers a neighbour, it first checks that the agent fits, and skips the cell otherwise. The footprint never has to be re-tested cell by cell; the clearance value already encoded it.

This is the property that matters: the expensive geometry was paid once, at build time, and every path query for every size now reads a single number per cell.

func fits(clr: PackedInt32Array, w: int, cell: Vector2i, size: int) -> bool:
    return clr[cell.y * w + cell.x] >= size

# Inside the search, only expand neighbours the agent actually fits on:
for n in neighbours(current):
    if not fits(clr, w, n, agent_size):
        continue
    # ... normal A* cost relaxation from here ...

Dynamic obstacles without rebuilding the world

A clearance map would be useless for real games if every door toggle forced a full rebuild. It does not. When a single cell changes between blocked and open, only cells above and to the left of it can have their clearance affected, and only within a window the size of the largest clearance value nearby. Recompute that small box, not the grid.

In practice you mark a dirty region around the change and recompute just those cells with the same rule used at build time. The cost is proportional to what changed, which is exactly the property that keeps it inside a frame budget when a building drops or a wall opens mid-battle.

# A cell that flips blocked/open only changes clearance for cells above-and-left
# of it, within the largest clearance in that window. Recompute that box only.
func update_region(clr, blocked, w, h, cx, cy, radius) -> void:
    for y in range(cy, maxi(cy - radius, -1), -1):
        for x in range(cx, maxi(cx - radius, -1), -1):
            recompute_cell(clr, blocked, w, h, x, y)

The tradeoffs

Clearance maps assume a square footprint. A 3×3 approximation is fine for most tanks, vehicles, and large monsters; genuinely rectangular or L-shaped units need a richer structure, and that is a real cost worth naming rather than hiding. The map also costs one integer per cell of memory, which is cheap, and a build pass, which is not free but is paid once.

The clearance value is also conservative by design: it guarantees a square of that size fits, which can occasionally refuse a tight diagonal squeeze a more expensive check would allow. For real-time games that trade is almost always correct — a unit that takes a slightly wider route is invisible; a unit wedged in a doorway is a bug report.

The deeper point is the same one that runs through production navigation: move the expensive work to where it is paid least often. Footprint geometry belongs at build and update time, encoded into the grid, not recomputed inside every path query while the frame clock is running.