Boids Flocking Simulator

Nobody is in charge of a flock. No lead bird calls the turn. Yet the cloud wheels and folds as if of one mind, which is how one group of physicists who tracked starlings put it.

The plainest demonstration that no leader is needed came from computer animation. In 1986 Craig Reynolds built a program of coordinated animal motion and called its generic creatures boids. The paper, “Flocks, Herds, and Schools: A Distributed Behavioral Model”, appeared the next year, in the 1987 SIGGRAPH proceedings. Its abstract states the wager directly: instead of scripting the path of each bird by hand, simulate every bird as an independent actor that steers by its own local view of the scene, and let the group motion come out of their dense interaction.

That choice was practical before it was philosophical. An animator who draws three hundred paths by hand has to redraw them all when one bird moves. A program in which each bird picks its own course has nothing to redraw.

Three rules, stated plainly

Reynolds’s own summary lists three steering behaviors. Separation: steer to avoid crowding local flockmates. Alignment: steer toward the average heading of local flockmates. Cohesion: steer to move toward the average position of local flockmates. Every one of them is about the neighbors and nothing else.

“Local” has a precise meaning. A boid reacts only to flockmates inside a neighborhood set by a distance from itself and an angle measured from its direction of flight; everything outside is ignored. Reynolds notes that this could be read as limited perception, as for fish in murky water, but that it is better thought of as the region in which flockmates influence a boid’s steering.

Rules alone do not move anything. In a later paper on steering, written for the 1999 Game Developers Conference, Reynolds gives the simple vehicle underneath: a point with a position and a velocity, a steering force limited by a maximum force, and a velocity cut off at a maximum speed before it is added to the position. The three behaviors each produce a steering request; the requests are scaled by weights and summed. He counts nine parameters in all, a weight, a distance and an angle for each behavior, and he is frank that his choice for how repulsion falls with distance is only a setting that worked well, with nothing fundamental about it.

That candor matters for anyone reading a boids demo, this one included. The simulator on this page follows the same order of operations with a fixed time step of one sixtieth of a second. Its weights, radii and presets were found by running it. None of them is a measurement of an animal.

What emergence means here

Emergence is an overused word, so it helps to pin it down. Reynolds calls flocking an evocative example of it: complex global behavior arising from the interaction of simple local rules. Nothing in the three rules says “form a flock”, “turn left together” or “stay as one group”. Those are descriptions of what happens, and they appear only when many boids run the rules at once.

Here is a run anyone can repeat. Choose the Polarized flock setup: 300 boids, seed 19, scattered over a wrapped plane with random headings. At the start the polarization, defined below, reads 0.03 and the boids fall into 15 separate groups. After 5 seconds it reads 0.71 with 3 groups. After 10 seconds, 0.88 with 2 groups. After 15 seconds it reads 0.96 and there is one group. So the measure runs from 0.03 to 0.96 with no rule ever mentioning the whole. Now drag Alignment to zero and the order drains away. In a test that did so at the 30 second mark, the flock had frayed into 31 groups 20 seconds later, with polarization down to 0.45.

Reynolds adds a subtler point. The flock is predictable for a second or so, since a boid will still be going roughly the same way, and all but impossible to predict over minutes. He sets that against both chaos, which has neither kind of predictability, and static or periodic order.

Physicists reached the same phenomenon from the other side. In 1995 Tamas Vicsek and colleagues published a deliberately bare version: particles driven at a constant speed that, at each step, take the average direction of the particles around them with some random perturbation added. They reported a transition from no net transport to collective motion as the noise is turned down. Alignment alone, in other words, is enough for order to appear, and the change behaves like a change of phase.

Telling a flock from a swarm

Looking is not measuring. A study of schooling fish led by Kolbjorn Tunstrom used two numbers, and this page uses the same two. Polarization is the length of the average of every animal’s unit heading: 0 when headings cancel, 1 when all agree. Rotation takes, for each animal, the direction from the group’s center to it and the direction it is heading, and averages the turning those imply; it is also 0 to 1, and it is high when the group circles its own center.

With those two numbers the fish, golden shiners in groups of 30 to 300, showed three states: a swarm with both low, a polarized school, and a milling state in which the school turns as a ring. The authors drew bands at 0.35 and 0.65 to separate them, and the labels on this page use those bands. Group size mattered. The share of time spent polarized fell from 0.57 for 30 fish to 0.05 for 300, while milling rose from 0.03 to 0.45.

A number near zero is not exactly zero, and the reason is arithmetic. Add up N unit arrows pointing at random and the sum does not vanish; its typical length is the square root of N, so random headings give a polarization of about one over the square root of N. For 300 boids that is close to 0.06, and the worked run started at 0.03, the same order of size. The plot marks that level so a flock is never credited with order it does not have.

The Milling ring setup shows the third state. Two hundred boids start on a band around a goal point, with weak alignment and a short perception radius, and rotation holds above 0.9 while polarization stays under 0.35. It is fragile in an instructive way. Raise Alignment to 2 and Perception radius to 16, and within 20 seconds rotation collapses to about zero as the ring jams into a knot.

Two further measures cover what those miss. The group count links any two boids closer than the perception radius and counts the connected clusters, which is how a predator’s effect shows up as a number. The mean distance to the nearest neighbor tracks how tightly the flock packs.

Where real birds differ

Boids is a sketch of a flock, and the field data say where the sketch is wrong. A team of physicists reconstructed the three-dimensional positions of individual starlings in flocks of a few thousand birds. Their finding cuts against the neighborhood described above. A starling does not respond to everyone within a fixed distance. It interacts with a fixed number of neighbors, on average 6 to 7 neighbors, however near or far they happen to be.

The authors call that a topological rule, against the metric rule of most models, and they argue it is what keeps a flock whole when a predator’s attack makes its density change abruptly. The Neighbors control switches this simulator between the two, so the difference can be watched: in the Nearest seven setup polarization keeps dipping toward 0.5 and recovering instead of settling near 1.

Later measurements widened the gap. Members of the same group found that velocity fluctuations in starling flocks are correlated over a range that grows with the size of the flock, which they describe as scale-free. And in turning flocks the decision to turn was found to spread across the group linearly in time with negligible attenuation, in contrast with theories of collective motion that predict a slower, dissipative spread.

So this simulator cannot tell anyone how starlings fly. It has no wings, no air, no bodies that collide, no eyes with blind spots beyond one angle, and no noise. Its predators chase the nearest boid and never catch one. What it can do is show which group behaviors follow from local steering alone.

Where boids went

The first uses were in film. Reynolds and colleagues made the short Stanley and Stella in: Breaking the Ice, shown at SIGGRAPH in 1987, and he records the 1992 film Batman Returns as the first feature to use the approach, for swarms of bats and flocks of penguins made with modified versions of the original software. Games followed; the 1998 game Half-Life used the method for its flying creatures.

Robots are the hardest test, because nothing is ideal. One research group wrote a flocking algorithm for autonomous flying robots and tried it on real quadcopters. Their account stresses time delay, communication that only reaches nearby robots and inaccurate sensors, and reports that a friction-like term aligning the velocities of neighbors can be essential for taming the instabilities those bring.

Speed is the other practical matter. Checking every boid against every other costs work that grows with the square of the flock. Reynolds’s remedy is to sort the creatures into a lattice of bins, so a boid examines only the bins its neighborhood touches; on a flock of 1,000 simulated birds he measured that as about 16 times faster than the naive search. This page does the same with a grid whose cells are one perception radius wide.

A last detail makes experiments repeatable. The starting positions come from a seeded generator of the xorshift kind that George Marsaglia described, with a period of two to the 32nd power minus one. The same seed and settings give the same flock, step for step, so a surprising run can be shown to someone else. Three sliders carry the argument: turn one rule off and see which part of the flock goes with it.