The Swarm

This is chapter three of an interactive book about data-oriented design. Chapter 1 was two tanks on a grid of walls; chapter 2 grew the world to a 8×8 toroidal grid of screens and gave the tanks self-routing. Chapter 3 adds an enemy faction: a thousand mites that wander, copy the last place they saw a tank on contact, and converge on it. As before, every structure below is live — it reads and pokes the running game's memory directly.

The chapter's lesson is scale. One entity is easy; a thousand is a data layout. The volume forces the structures volume needs — a fixed pool with no allocation, a per-cell index rebuilt every tick, a deterministic integer PRNG, a piece of shared knowledge that is just timestamped data copied on contact with no central manager, and — the payoff — a handful of shared route fields standing in for a thousand per-unit routes. The four tanks keep routing exactly as before: 4 routed units beside 4096 that share a few routes — the algorithm matched to the need.

The world & the tanks (recap)

The world is chapter 2's single 160×120 toroidal grid, organised as 8×8 screens; the viewport shows one screen and follows the selected tank. The tanks still route themselves along precomputed path tables. New here is everything swarming around them. The minimap shows the whole world — walls, tanks, routes, and the entire swarm as downsampled dots — so you can watch the mites pool and stream while the viewport stays on one screen:

The viewport is presentation only: following, sliding, the picker, and which mites are drawn never change the simulation. The swarm is the same whether or not you are watching its screen.

A thousand mites in a fixed pool

A mite is a quarter-cell body on the same grid as the tanks. There are exactly N_MITES = 4096, spawned at init and alive for the whole chapter — a fixed pool: flat structure-of-arrays, statically sized, no allocation. Where there's one, there's many: a mite is never updated alone; each transform is one batch over the whole pool. A mite shares the tanks' turn and move transforms — the size is just a parameter (MITE_R instead of TANK_R) threaded into the collision, not a second copy of the movement code. It collides only with walls; crowding is handled by a rule, not by physics.

The grid you already have is the index

A swarm needs to know, cheaply, which mites are near a given mite and how many are in each cell. Scanning 4096×4096 pairs every tick is the naive answer. The data-oriented one: the uniform grid is the acceleration structure. Once a tick we bin every mite into a per-cell count and a short list of the (≤4) occupants — O(N) — and then “who is within one cell of me” is just reading the occupants of a 3×3 neighbourhood. This is the opposite end of the frequency-of-change spectrum from the path tables: the tanks' route tables rebuild only when you edit a wall (rare); the mite index rebuilds every tick (constant), because the mites move every tick. Toggle a wall on the left and watch the per-cell occupancy on the right shift as the swarm flows:

The crowding cap: a sub-segment rule, not a collision

Mites do not physically collide with each other. Instead each cell is quartered into a 2×2 grid of sub-segments, and a mite is assigned to one by index ((index >> 2) & 3 — deliberately not the same bits as the nest, so a nest's mites use all four segments and revive in parallel) and parks at that sub-segment's centre — a quarter-cell off the cell centre. The rule is at most one mite per (cell, sub-segment): a mite steps into a cell only if its own sub-segment there is free (so still at most 4 per cell), else it picks another open neighbour, or holds. This spreads the swarm out inside cells instead of stacking it on the centre — and lets mites a sub-segment off a bolt's line dodge it. It is enforced deterministically by processing mites in index order against a per-cell bitmask of reserved sub-segments — current occupants plus the moves already committed this tick — so the n-th mite sees the earlier ones' reservations (chapter 1's “test only the leading edge” again). The occupancy panel above tops out at 4, always.

The shared knowledge: one cell + one timestamp

Here is the heart of the chapter. What is the minimal data the swarm's behaviour depends on? Not a map, not a plan — just the last known tank position: one world cell plus the frame it was recorded (a timestamp). Each mite carries exactly that one small record. There is no shared blackboard and no manager; the swarm's behaviour emerges entirely from copying this record on contact:

• Sense. A tank within one cell → record its cell, stamped now, and hunt it.
• Read a peer. Otherwise adopt the newest record among the mites in your 3×3 (including an empty one) — last-write-wins — then roll the role die: P(hunt) hunt the cell, else carry it home to your nest. It defaults to 100% hunt (no couriers; lower it to split some home) — a newer record interrupts and re-rolls; either way you keep relaying it.
• Arrive & check. Reach the recorded cell: if the tank is there, refresh it (stamp now); if not, erase it (empty, stamped now) — and “it's gone” propagates back through the swarm by the same rule, because empty-stamped-now is the newest record.

The gossip is made order-independent by double-buffering: every mite reads last tick's records and writes this tick's, then the buffers swap, so propagation never depends on iteration order (ties break on lowest index). Drive a tank into the swarm and watch the belief field below: a sighting diffuses outward from where it happened and dissolves when the position goes stale.

A thousand movers, a handful of shared routes

A hunting or homing mite has a destination — its recorded tank cell, or its nest — and it navigates with the very same path tables the tanks built. But it does not own a route. What is the minimal routing data the swarm depends on? Across 4096 mites the distinct destinations in flight are few — the sixty-three nests plus the handful of recent sighting cells the gossip is converging on — so we keep a small fixed table of shared route fields (N_FIELDS), each a remaining-distance vector keyed by a destination cell, and many mites read the same field. The sixty-three nest fields stay resident; a sighting field is folded the first tick it is wanted and freed when no mite wants it. Turning a destination into the input byte is exactly the tanks' path-follow — one movement model, two input sources — through the shared agent_turn/agent_move.

Every mite belongs to one of sixty-three nests (by index, i % 63), drawn on the map and used to tint the homing mites. How big is the table? Not a guess: instrumenting the distinct active-destination count puts the high-water mark at ~81 — the sixty-three resident nests plus the few sighting cells the gossip has converged on — so N_FIELDS = 128 holds it with headroom, the same prove/measure/detect discipline the Level-1 byte got, applied to a runtime peak. If the live count ever exceeds the table, those mites steer greedily that tick — a safety net, never a crash. The counters above show the live active / 128 routes and the running peak: a thousand movers served by a handful of routes is the chapter's payoff. Beside them the four tanks each compute their own exact route — same world, the cost matched to the need.

The step itself asks one question: is the mite cleanly pathing? If it is hunting or homing and the route field's preferred next sub-segment is open, it takes it — the field step. In any other case — that sub-segment blocked, or the mite wandering — it flocks: it samples the mites in its 3×3 (the same per-cell index) and votes a cardinal from the three classic rules — cohesion toward them, separation off the close ones, alignment to their heading — then takes the best cap-free one. It is the same data (the index) read one more way, and it costs no new state. With alignment weighted highest the swarm flows in streams rather than clumping; and because a blocked hunter now flows with the crowd around a jam instead of stalling against it, the swarm presses tanks harder (measured: kills up ~20%, the average nest less crowded) while the cap still holds every tick.

The tanks shoot back: one transform, the same index

Combat is its own small transform (tanks_fire.c), and it reuses the structures already here rather than adding new ones. Each tank's turret aims independently of its body and turns at its own rate (it can't snap instantly), so it targets the mite most likely to be hit — the one closest to the turret's current direction, needing the least rotation, not the spatially nearest. It scans the per-cell mite index over its search box, takes one line-of-sight test per cell (an integer Bresenham walk over the wall grid), and tracks the smallest bearing change. The turret swings onto that target and, once exactly on it (and the cooldown elapsed), fires at a fixed rate (default 2 shots/sec). The shot is a travelling, piercing bolt — not a hitscan beam: launched from the muzzle, it marches a tunable number of cells per tick (a slow 1 by default), destroying mites whose position lies within a narrow band of its path and piercing on through them — again just reading the per-cell index — until it meets a wall. Because mites sit in sub-segments off the cell centre, the ones on the line die and the ones off it dodge (the bolt carries the mite it was aimed at, so the locked turret still reliably drops its target). Firing no longer pins the turret — the instant the bolt is away the barrel can swing onto the next target while the shot is still travelling — and each destroyed mite leaves a small expanding burst. Tanks won't fire through each other — a turret re-targets if its best mite's shot would pass through a friendly — a bolt that meets a wall throws a hot impact spark and jolts the wall, and a moving tank simply runs over any mite under it — a cell-wide crush that triggers the same burst and death cry. A destroyed mite revives — its memory wiped — at its nest after a timeout (default 5 s), respecting the same crowding cap as spawning (a full nest just waits a tick), so no rule the swarm obeys is broken by combat. There is one nest per screen except the tanks' start screen (0,0) — sixty-three homes — so revived mites never pop up under a barrel, and the spawn load is spread across sixty-three screens' worth of exits rather than piling out through one screen's two or three border openings (which knotted the swarm at the few nests). Spreading the homes is what lets the revival stay dead simple — revive, wander, re-acquire from the live gossip — with no jam to dissolve.

The payoff is the feedback loop. Every kill is a death cry: each mite within 2× sensing range of the dead one has its record overwritten with the firing tank's cell, stamped now, and is flipped to hunt — so a bolt that mows a line doesn't thin the swarm quietly, it broadcasts the shooter's position into the very same gossip that spreads any sighting, and the survivors converge on the attacker. It writes through the ordinary record buffer and the ordinary route fields; the belief field above lights up around a tank that is firing. And it is deterministic — firing draws no randomness — so same seed plus same inputs still replays exactly. The stats above report the per-tick update cost (the whole CPU step: index, gossip, fields, movement, combat) beside the frame, and the live alive / dead split of the pool.

Determinism & the seed

All the randomness — every wander direction and every hunt/home roll — comes from a single integer PRNG (xorshift32) seeded in the world and advanced as mites are processed in index order. So the whole swarm is a pure function of the seed and the inputs: same seed ⇒ identical play, pinned by a state-hash test. Edit the seed to re-scatter the swarm and tune the rest live (the sixty-three nests are fixed, one per screen):

What this bought us

A thousand autonomous units in a few kilobytes of WebAssembly: a flat pool sized to its real domain, a uniform-grid index rebuilt each tick (O(N), the swarm's acceleration structure), a crowding cap that is one deterministic reservation pass, shared knowledge that is one cell and one timestamp copied on contact, and a handful of shared route fields — sized from a measured peak — standing in for a thousand routes. No central state. Integer fixed point throughout, no dynamic allocation, the simulation separated from rendering and wasm so the swarm, the gossip, the cap, and the route table are all tested natively with no browser or GPU. The render scales with what's visible, not with the population. And when the tanks shoot back, combat leans on what's already here — aiming and the bolt both just walk the per-cell index, the death cry writes the existing record buffer, respawn obeys the existing cap; the only addition is a small fixed ring of cosmetic destruction bursts — the proof that the layout, not the feature list, is what the volume bought.

Source for this chapter: mites.c · tanks_fire.c · agent_move.c · agent_turn.c · sim.c · render.c · wasm.c · test.c · README · CONTRACT