Why the AI opponent was the slowest thing in the game

Eight players, one map, everybody fighting everybody. That mode ran at 3 to 15 frames per second. The system that automatically lowers graphics settings when frames get late had already gone to the bottom of its ladder, all eighteen rungs, which means it had turned off everything it was allowed to turn off. There was nothing left to give.

Underneath the graphics, the game's own logic was taking 58.65 milliseconds per tick against a 50 millisecond budget, so it was falling behind on its own before anything was drawn. The plan going in blamed combat. The plan was wrong. Combat came fourth, at roughly 1 millisecond a tick. The computer opponents were 90% of the work, and the specific reason was that every time one of them thought about what to do next, it swept the entire map twenty-one times.

215 milliseconds that nothing owned#

None of that could be found until the measurements were fixed, and the state they were in is the more useful half of this story.

A capture of four hundred units against four hundred reported 4 frames per second, with each frame taking 250 milliseconds. The pieces that were being timed added up to 33.6: six milliseconds of game logic plus 27.6 of drawing. Roughly 215 milliseconds a frame was happening outside everything being measured. The browser's own reporting of blocked-up work confirmed it independently, 213 stalls totalling 39.7 seconds across 102 seconds of play, about 40% of the session. Neither the processor figure of 42 milliseconds nor the graphics figure of 14.9 explained it, and the thing that decides what a frame is limited by, reading only those two numbers, cheerfully declared the game limited by the graphics card.

The tools could not have found the answer, because the tools were reporting almost nothing. The per-part timings came back empty. Nearly nine milliseconds of drawing time was attributed to nothing at all. The current graphics level was absent from the log entirely, so a setting the game had lowered by itself was indistinguishable from one the player had chosen, and had to be worked out backwards from the resolution being exactly 1.5 multiplied by 0.7.

What went in was a meter for the main thread, a classifier that reads every number it is given rather than two of them, and an accountant that checks the timed pieces sum to the frame, so unclaimed time is loud instead of silent.

That accountant is the thing to steal, and it costs one subtraction.

// Every frame: prove your timings add up before you trust their ranking.
function accountForFrame(observedFrameMs, phases) {
  const measured = Object.values(phases).reduce((a, b) => a + b, 0);
  const unaccounted = observedFrameMs - measured;
  if (unaccounted > observedFrameMs * 0.1) {
    console.warn(
      `${unaccounted.toFixed(1)} ms of ${observedFrameMs.toFixed(1)} ms is unmeasured ` +
      `(${(100 * unaccounted / observedFrameMs).toFixed(0)}%) — ranking below is unreliable`,
      phases,
    );
  }
  return unaccounted;
}

Until that remainder is small, every per-part number you have is ranking a subset against itself, and the thing at the top of your profile is only the top of the measured part. Ours was 215 milliseconds of 250.

Six free-for-all stress maps landed alongside it, at two, four and eight players across a ramp of 400, 800 and 1,600 units, because automatic graphics lowering only reacts after frames are already late. Knowing where the cliffs are is the only way to get in front of them.

The map sweep that ran twenty-one times per thought#

With honest numbers, the opponents were unmistakable. Every time one decided what to build next, it asked "which parts of the map can I actually reach from here?" about twenty times over, and eight opponents each did it privately with no sharing between them.

The obvious fix is to make that sweep cheaper, and there was plenty available. It was written the textbook-naive way twice over: it removed items from the front of a growing list, which in JavaScript shuffles everything behind them along by one every single time, and it tracked visited tiles by building a little piece of text like "37,214" for each one, hashing it, comparing it and throwing it away. Both are common enough to be worth naming. Removing from the front of an array is not free the way removing from the end is; walk a read position forwards instead. And any grid already has a natural whole number for each tile, row times width plus column, which indexes a flat array and allocates nothing. On a 512 by 512 grid, those two changes together take the same sweep from 142 milliseconds to 7.

The sweep itself is a flood fill: start on one tile, step to its walkable neighbours, then to theirs, and keep going until nothing new is reachable. It is the same operation as the paint bucket in an image editor, and it answers "what can I get to from here" by visiting all of it.

But making it twenty times cheaper is still the wrong fix. Whether one patch of walkable land connects to another does not depend on which direction you ask from. That makes the answer for any starting point simply "which region is this point in", and regions do not change unless the terrain does.

So the map is divided into connected regions once, in a single pass that gives every walkable tile a region number — the standard name for this is connected-component labelling — and every later question becomes one array lookup. Two tiles are mutually reachable if and only if their numbers match.

The general rule, without any of our nouns: a reachability question you ask repeatedly, over connections that work both ways and change rarely, should be a labelling you compute once, not a search you run again. Label the whole grid in one pass, cache the labels against the map they describe, and throw the cache away when a version number on the terrain changes. Cache keyed on the thing, so it cannot outlive it. Versioned by the thing, so it cannot go stale.

Ownership was the part worth being careful about. The labelling depends only on whether a tile is walkable ground, never on buildings, players, the clock, or which opponent asked. That is what makes one shared answer safe for eight opponents at once, and what keeps two machines in a multiplayer match in agreement. Buildings block units through a separate layer, exactly as they did before.

The replacement also reproduces one quirk deliberately. The old sweep always included the tile you started on, walkable or not, so an opponent whose starting point sat on water still pulled in every walkable neighbour and could treat two regions as joined if they met at that one tile. The new one therefore returns the starting point plus every region touching it. It looks odd until you know it is not a new rule, just the old one written down.

The measurements were lying in three separate ways#

None of what follows is about game AI.

The opponents' own timings under-reported by a factor of eight, because each of the eight had its own private tally and nothing added them up. Asking how fast combat was reset the counter that decides how often combat runs, so measuring it changed it. And the stripped-down rig used to prove improvements was skipping twenty of the pieces the real game runs, and quietly changing the behaviour of others where it did run them: units moved without the layer that tracks flying occupancy, auras ran without the grid that finds nearby targets.

That last one gave the most useful result of the whole exercise. Putting the missing pieces back made the measured average fall rather than rise, because the versions running without the things they depend on were doing more work, not less. A benchmark that is faster than the game is not a cautious benchmark, it is a different program. A check now pins the three lists of what-runs-where against each other so they cannot drift apart again.

The combat figure that started the whole plan was an artefact of the same class. Its 8.5 millisecond reading was a spike carrying about 35% measurement overhead, and the alarming sixteen deaths that suggested combat was broken were an artefact of the window: the armies had not met yet. The measurement that ranked combat first was taken before the thing it measured had started.

The plan going in ranked combat first and the AI fourth. The measurement reversed it exactly.

Two bugs that had been playable for months#

Looking hard at parts of the game that had no business being on the profile is what turned up six other bugs in the same pass, and two of them had shipped long enough to be uncomfortable.

Stuns lasted twenty times as long as they were written to, because a duration counted in ticks was being reduced by an amount measured in seconds. A one second stun ran for twenty. And the Ratmen corruption speed bonus did nothing at all: shipped, documented, playable, inert. Neither was found by a test, because neither one crashes, neither logs anything, and both produce a game that runs perfectly well. They were found by reading code while looking for something else, and both were fixed in the same pass.

That is the real argument for a profiling session that goes wider than its target. The AI cost was the thing being hunted, and the work paid for itself twice over in bugs I was not looking for, because the only way to rank a part of a program honestly is to read what it actually does.

Where the cost went next#

At 5.87 milliseconds a tick the game logic uses roughly 12% of one processor core, which changes which thread is worth arguing about: the one moving the simulation off the main thread would free is no longer the busy one. It also means the next profile has a different shape, because with this gone the largest remaining item is not a subsystem at all. It is one job that two different parts of the game both ask for, and working out routes turned out to be 78.8% of what was left. How often an opponent should think, and what it should think about, is a design question rather than a speed one, and belongs with how the opponent makes decisions.