Where it came from
There was a Flash aquarium game I used to play, the kind where you feed fish and watch them swim, and I wanted something like it to fidget with at work. A virtual snow globe. Around the same time I'd watched Sebastian Lague's Coding Adventures episode on boids and had been looking for an excuse to build them, so the two ideas met: flocking fish, over sand physics you can reach into.
It turned into a performance exercise almost immediately. Boids done the obvious way are O(n²), because every fish asks every other fish where it is, and they fall over somewhere around a few hundred agents. I wanted to know exactly what has to change to run thousands instead, and I wanted the answer visible on screen rather than in a paragraph like this one. So it ships with a telemetry panel: frame time, fish count, how much sand is currently moving, and the number of neighbor checks the grid actually performed this frame. Turn the fish count up and watch which number grows.
Three systems over one pile of arrays
Physics, steering and rendering never call into each other. They read and write the same typed arrays, and that's the entire interface between them.
- Physics is a falling-sand automaton over a
Uint8Arraygrid. - Steering is a fish pool laid out as parallel arrays, driven by a spatial hash.
- Rendering draws water, then light, then sand, then fish, then overlays.
The fish pool
Position, velocity, tail phase, wiggle rate, color index and an active flag each get their own typed array of length 4,000, allocated once at startup. Spawning pops an index off a free-list stack and killing pushes it back, so there are no objects to collect and nothing gets allocated while you're playing. Spawning four thousand fish allocates nothing at all; the memory was already sitting there from the first frame. Color is a single byte pointing into a small registry that holds the hex string, the RGB triple and a pre-lightened highlight, which keeps the pool tight and means the renderer never parses a color.
The spatial hash
Every frame the fish get bucketed into a uniform grid whose cell size is the perception radius,
using a pair of integer arrays called heads and next. It's an
intrusive linked list per bucket, rebuilt by overwriting rather than by allocating. A fish then
only looks at the nine buckets around it. The same structure answers the two interaction
queries for free: nearest fish to the cursor when you click one to remove it, and every fish
inside a rectangle when you drag a box. Switch on "show spatial grid" in the demo and you can
see the buckets it's using.
The sand
A grain falls if the cell below it is empty, otherwise it tries the two diagonals, and the scan runs bottom-up. The direction of the scan alternates by row and by frame, because sweeping left-to-right every time makes every pile lean the same way. You don't notice that until you've watched a few thousand grains settle, and then you can't stop noticing it. Drawing happens in horizontal runs rather than cell by cell, with a second pass that puts a bright edge on the top grain of each column, which is what makes a grid of ones and zeroes read as a lit surface.
Where the two meet
The fish have to avoid terrain that the player is reshaping while they swim through it, and terrain avoidance is usually where this kind of demo starts doing something expensive. Here it's three grid lookups per fish: one probe ahead along the heading, and two off to the sides to work out which way is clearer. The fish steers toward the open side and brakes into the wall. Anything that ends up buried gets a hard shove upward, so burying the whole flock with the Add brush is recoverable rather than fatal.
Boids demos almost always run in empty space. Making them share a world with an automaton the player can rewrite is what forced the sand grid to be cheap to sample, since the steering code hits it hundreds of times a frame.
Rendering
- Each fish is drawn with one
setTransform(cos, sin, -sin, cos, x, y)built straight from its normalized velocity. No save and restore, and noatan2anywhere in the draw loop. - Gradients are cached per color in local coordinates and reused by every fish of that color, instead of building a fresh gradient per fish per frame.
- Detail drops by population. Past 700 fish the glow goes; past 1,000 the eyes and the dorsal highlight go. The frame rate degrades by losing decoration rather than by turning into a slideshow.
- Light rays and caustics are drawn with
lightercompositing over a vertical gradient. Cheap, and it sells the depth better than anything per-pixel would have.
Try this
Spawn a few hundred fish, then use the sand brush to wall off the side of the tank they're heading for. Watching a flock hit a wall that didn't exist a second ago is the whole reason the terrain probes had to be cheap. Then set separation to zero and watch the flock collapse into a single point.
What I'd do next
- Water as a second automaton layer, so digging a trench actually drags the fish along with the current.
- Predators, and a fear term in the steering. The interesting part of flocking is the panic.
- Move the flock update onto the GPU with a ping-pong texture and find out how far past 4,000 it goes.
- Touch input, so it works properly on a phone.