Making pathfinding fast enough for hundreds of units

The game ran fine right up to the moment the armies met. Described the way a player experiences it: everything went syrupy on contact, worst on maps with a bridge or a mountain pass where both sides funnel into the same few tiles, and then it loosened again once the fight thinned out.

Sticky-on-contact is a useful complaint, because it rules things out. Nothing about drawing the scene changes when two armies touch. What changes is that several hundred units all start asking the same question at the same time: where do I put my next step?

Answering that is called pathfinding, and the standard way to do it is an algorithm called A*, said "A star". The map is a grid of tiles, most of which you can walk on. A* fans out from where the unit is standing, keeping a queue of partial routes and always extending whichever one looks cheapest so far, where "cheapest" means the distance already walked plus a guess at the distance remaining. That guess is what separates it from brute force: it pulls the search towards the destination instead of spreading evenly in all directions, so it usually reaches the answer having looked at a fraction of the map.

It is fast for one unit. Nothing about it had ever been measured for four hundred units that are all being shoved around by each other.

One cost with two invoices#

Every measurement I had taken stopped before the armies met, which is the one moment that matters. So the first job was a breakdown that attributes time to individual pieces of work rather than to whole subsystems, run out to tick 3000 on an eight player stress map where the armies collide at about tick 1450.

Pathfinding came back at 78.8% of all simulation time.

That single number turned a two-item work list into a one-item one. The profile I had been working from read combat at 15.8 milliseconds per tick and movement at 10.9, and I had been treating those as two separate problems. They were one problem, roughly 27 milliseconds a tick, arriving as two invoices.

In the worst window, combat measured 16.37 milliseconds a tick and 14.69 of that was units re-planning their route towards a target that keeps moving. Movement measured 25 to 31 milliseconds a tick, and its route in was a unit finding the tile it wanted already occupied by a friend and asking for a fresh path.

Both callers are reasonable on their own. A unit chasing a moving enemy does have to re-plan. A unit that walks into a wall of its own allies does have to do something. Neither one knew what the thing it was calling actually cost, and because the cost was billed to the caller, pathfinding never appeared at the top of any table. It has no line of its own to appear on.

Measuring it was harder than fixing it#

Two facts about the measurement have to come first, because without them none of the results are evidence.

A stopwatch was useless. On the machine doing this work, two identical runs of the same unchanged build varied by a factor of four. The improvement being chased was 13%, which is invisible under that. So the two versions were compared by processor time rather than elapsed time, with exactly one version built into each run, alternated, taking the best of five. Best rather than average, because noise on a shared machine only ever adds time, never removes it.

Timing both versions in one program is invalid. The obvious rig is to keep the old and new implementations in memory, swap a variable between them, and time each. It cannot work. A JavaScript engine speeds up a frequently used call by remembering which function ends up there and pasting that function's body directly into the caller. Point the same call at a second function and the engine throws that work away, permanently, for every version including the ones already measured. A benchmark shaped that way is measuring its own instrumentation, and it fails by returning a clean, repeatable "no difference", which is the most dangerous wrong answer there is, because it looks exactly like a finding.

The rule that falls out is short: one implementation per program, compared across programs. Anything that leaves both versions reachable from the same place is not comparing them.

What changed inside the search#

Every change is confined to the search itself, and every one is designed to produce identical routes.

The cliff rule was folded in. Height is a per-edge rule rather than a per-tile one: the top of a plateau is perfectly walkable, it just cannot be entered from the tile at its foot. Asking that question went through four layers of helper, twice, for every neighbouring tile considered. It now reads the height data directly and answers on the spot. Its share of time fell from 11.7% to 0.2%.

Three small helper functions became plain branches. They were being called around two hundred thousand times a tick. The worst was the test for what kind of movement a unit has (walking, swimming, flying), which was a chain of text comparisons, up to four of them before reaching the common case of a unit that walks. It is now a numeric switch, which compiles down to a jump.

The bookkeeping became flat arrays with a generation counter. This was the single largest cost in the whole simulation. A route across land may consider three thousand tiles with eight neighbours each, and every one of those did a lookup to ask "have I already been here?" against a freshly allocated set that was thrown away at the end of the search.

The replacement is a trick worth stealing, because it applies anywhere you allocate a fresh "visited" set per query, run many small queries, and the thing you are visiting is a fixed finite set you can number: flood fills, dirty-region marking, reachability, per-frame de-duplication.

// A generation counter instead of clearing a visited set.
const CELLS = 256 * 256;
const stamp = new Int32Array(CELLS);   // allocated once, never cleared
let generation = 0;
 
function search(start) {
  generation++;                        // this is the clear, and it is constant time
  let cell = start;
  for (let i = 0; i < 40; i++) {
    cell = (cell + 1) % CELLS;
    if (stamp[cell] === generation) continue;   // already visited this search
    stamp[cell] = generation;                   // mark visited
  }
}

Bumping a number is the whole of the reset, so a cheap search that touches forty tiles pays for forty tiles instead of clearing sixty five thousand entries it never looked at. On the machine described above, twenty thousand small searches take 24 milliseconds with a fresh set each time and 2 milliseconds with the stamp.

Two details decide whether it is safe in your own code. The counter must never wrap round into a value still sitting in the array, so use a 32-bit integer array and reset the buffer if you are ever approaching two billion searches. And the array is shared mutable state, so two searches cannot run over it at once. That is fine inside a single-threaded loop and a bug waiting to happen anywhere else.

Below that, the per-tile records became flat arrays too. The old form allocated tens of thousands of six-field objects per search and several million per tick, then chased a pointer into each one in a deliberately cache-hostile order. Sorting the candidate list, which is nothing but comparing numbers, was 9% of the whole simulation by itself, and now reads one number from one array per comparison.

Two things were deliberately left alone. The running costs stay at full precision, because a route's cost is a sum of diagonal steps and speed-adjusted fractions, and rounding it would reorder ties between equally good routes. And the candidate list still keeps stale entries rather than removing them, because removing them changes which of two equally good tiles surfaces first. That is a route change wearing a data-structure costume.

Playing the same match twice was not enough to check it#

Running the same scenario twice and comparing the results proves that a build agrees with itself. It is the right check for the question it answers and the wrong check here, because a rewrite that returns a different but consistently different route passes it every time.

So the rewrite was compared against the version it replaced, directly:

The first set covers walking, swimming, being carried, flying, moving through forest and hopping, at both unit sizes, with and without other units in the way. The second is every request the game actually made during a run, answered by both versions and compared. The match itself came out identical on both: 728 deaths and 4,854 attacks begun.

One check was kept permanently. Folding the cliff rule into the search created a second copy of a rule that is supposed to exist once, so a test now drives the real search across a real height map with a plateau and a single carved ramp, and asserts that every step of every route it returns is legal under the original rule, and that it refuses exactly the steps the rule refuses. When that goes red, the search is wrong, not the rule.

The result of all of it: 13.1% less processor time.

The bigger win was asking less often#

The same pass also recorded what did not work, and that half turned out to be more useful. Target selection, kiting and the fortress scan together came to about 1.1 milliseconds of a 16 millisecond bill, so earlier work had already taken everything available there. And pathfinding's share only moved from 80% to 77%, which means the work had mostly relocated rather than vanished. Cost per search was now the wrong lever. The next win would have to come from searching less often.

That turned out to be exactly right, and it took one more day. On the eight player stress map, 75 units were sitting permanently stuck, pinned by their own allies with nowhere to go, and re-running a full search at the fastest rate the cooldown allowed, eighty attempts each per four hundred ticks. Of those attempts, 97.4% found nothing, and 100% left the unit standing exactly where it was. Not one unit ever benefited. That was 15.17 of the 65.33 searches per tick, 23% of every search in the game, plus 3,737 slots in the per-tick search budget taken from units that would have used them.

Remembering that a search failed is only safe when the failure is provable, and it is not always. Other units are a soft cost inside the search rather than a hard wall, so "I ran out of places to look" is a pure function of the start, the goal, the terrain and the unit's size, while "I hit my iteration limit" might have succeeded under different conditions. The fix has two tiers accordingly. The provable tier skipped 9,126 searches and suppressed nothing a unit would have acted on. The cautious tier skipped 3,766 and delayed 24 by at most one retry.

Total processor saving across the whole simulation: 26%.

The trade that leaves is written into the code as a number rather than buried in a changelog. Setting the retry delay to zero turns the cautious tier off and makes the game bit-for-bit identical to the version before the change, verified over five paired runs, at the cost of nearly all the saving. The shipped default is not the exact one, and anyone who wants the exact one can have it by changing that number. If you want to know why bit-exactness gets defended this hard even in a single player match, it is the same constraint that shaped the move to eight players and that the determinism check exists to police.

What a flat profile means for the next pass#

With this and the AI's cost both gone, nothing owns the simulation any more. That is the goal, and it is also the point where this kind of work gets expensive: a flat profile has no top item to attack, so the next gain has to come from removing work rather than making work cheaper: asking less often, rather than answering faster.