Agents that each steer by their nearest neighbors can come to share one direction. Measured as a transition, the change turns out to be sharp, to need the agents to move, and to depend on how each picks its neighbors.
The cells of the previous essay stay on a fixed grid; the agents here move through open space and steer by their neighbors. In 1987 Craig Reynolds simulated flocking with "boids", agents that each follow three steering rules based only on nearby agents. Watching the animation, it is hard to say when a scattered crowd has become a flock.
Each boid steers by the others within its vision radius: separation pushes it away from neighbors that are too close, alignment turns it toward their average heading, and cohesion pulls it toward their average position. The readout gives the polarization φ, the length of the boids' average heading: 1 when all point the same way, near 0 when headings are random.
Figure 1. 150 boids with separation, alignment and cohesion. Boids are colored by group: two boids share a group if a chain of neighbors, each within the vision radius of the next, connects them. φ is computed over all boids; within-group φ is the size-weighted average of each group's own polarization, over groups of two or more (gray boids are loners).
Only alignment gives the boids a common direction: in three background runs of 1,500 steps, φ averaged … over the second half with the default weights and … with alignment at zero. At these weights it also gathers them; without it they stay about as spread out as a random scatter. Cohesion alone gathers them only when strong (cohesion 2, radius 100, the other two at zero): nearly all 150 pile into one swarm that churns in place, φ below 0.1.
Restore alignment, set the radius to its smallest values and press Scatter. Many small groups form, each aligned inside, so within-group φ runs well above the global φ until groups that cross paths merge.
In 1995 Tamás Vicsek and colleagues kept only alignment. Every particle moves at speed v0. Each step it adopts the average heading of all particles within distance 1 (itself included), then adds a random angle drawn uniformly from [−η/2, η/2]. The noise η plays the role of temperature: at η = 2π the new heading is completely random.
Figure 2. The Vicsek model: 400 particles in a 20 × 20 periodic box (density 1, interaction radius 1), each drawn as a short stroke colored by its heading. The trace plots φ at every step; the dashed line marks the random-heading level for 400 particles.
At low noise the colors merge into one hue and the trace climbs toward 1. At high noise it lies along the dashed line at about 1/√N, … for 400 particles. In between, ordered stretches break up and re-form.
In Figure 3 the moving particles' φ crosses 0.5 at η ≈ …, and the flicker peaks near there, where Figure 2's trace swung hardest: a phase transition in a finite system.
Figure 3. Figure 2's code at 16 noise levels, each from a fresh random start, for moving particles (v0 = 0.3) and frozen ones (v0 = 0): φ averaged over 600 steps after discarding 400, with error bars showing how much it flickers within the run (one standard deviation). The vertical line is Figure 2's current noise; click the chart to move it there.
Vicsek's group reported a continuous transition. Grégoire and Chaté (2004), with much larger systems, found it discontinuous: near threshold the ordered phase is dense bands travelling through a sparse disordered gas, and φ is bimodal. With Vicsek's noise that needs big boxes, about 128 interaction radii at density 2 by the estimate of Chaté and colleagues (2008). Adding the noise to the summed neighbor headings as a random vector, which Grégoire and Chaté also tried, brings the bands into a box a browser can run.
Figure 4. 2,048 particles in a 64 × 64 periodic box (density 1/2, v0 = 0.5). Right: density in 64 strips measured along the flock's direction of travel, one row every 3 steps, newest at the bottom, shaded from empty to four times the mean density. A band moving with the flock draws a diagonal stripe. With vector noise, η weights a random unit vector against the neighbors' summed headings; with angle noise, η is the width of the random turn, as in Figure 2.
With vector noise a band forms within a few hundred steps, its densest strip 5 to 7 times the mean density. Raise η to 0.6 and within a few hundred more steps it dissolves and φ drops to about 0.1. Under angle noise the stripes stay broad and blurred, near 3 times the mean: Chaté and colleagues see sharp bands with it only in boxes wider than a band.
Figure 3's second curve holds everything fixed except speed. Frozen particles still align, but their best φ on the sweep was …, against … for moving ones. A particle has … neighbors on average, yet the network they form is in pieces.
Figure 5. Particle 0 (circled) and everyone whose heading can depend on its heading at step 0 (violet). After each step a particle within distance 1 of a reached one is reached, because it has averaged in that heading. Same box and density as Figure 2, η = 1. Thin curves: means of 10 runs at each speed; thick violet: the run on the left.
Frozen, particle 0's influence stops at the edge of its cluster: on average … of the box, 2 to 76 particles over the ten starts. Moving at v0 = 0.3, it reaches … within 40 steps, because particles leave their clusters and carry headings to strangers.
Motion matters even when the network is connected. In two dimensions a static system cannot hold true long-range order against noise (the Mermin-Wagner theorem); Toner and Tu (1995) showed that a flock can, because motion carries heading information along. A 400-particle box cannot test that limit.
Our particles count everything within a fixed distance as a neighbor. Ballerini and colleagues reconstructed starling flocks in three dimensions and found each bird interacting with six or seven nearest neighbors, however far away. They argued that a fixed count holds a flock together through the density swings a predator causes, and tested it in a two-dimensional alignment model; Figure 6 repeats that test.
Figure 6. 200 birds start aligned in a disc of radius 5 and only align (with turning noise of width 0.1); a repulsive predator (red) flies the other way 4 units off the flock's center. The view follows the largest piece; a piece is a chain of birds with gaps of at most 3, the paper's definition. The histogram counts pieces after 500 steps over the same 40 starts for both rules, rerun when the strength changes.
At the default strength the metric flock came through whole in none of the 40 trials and the topological flock in 29. Most extra pieces are stragglers (the largest piece averaged 183 and 194 birds). A metric bird pushed beyond distance 1 has no neighbors left to turn it back; a topological bird always has seven. Noise does some of this: at strength zero the metric flock still split in 19 of 40 trials, the topological in 2.
The drivers of the next essay also respond only to what is near them, the car ahead, and a jam can form among them with no obstacle on the road.