Boids

1Three rules, one neighbourhood

A boid's neighbours are the flockmates within radius r. Separation pushes away from the ones that are too close, weighted by 1 / distance so the nearest push hardest. Alignment turns towards their average heading. Cohesion steers towards their centre. Three sliders weight them against each other.

The ringed boid has … neighbours within r = …, and … of them inside the separation ring.

s = Σ_|d|<rs (xᵢ − xⱼ) / |xᵢ − xⱼ|²separation: away from crowding, r_s = 0.45 rs = …

a = (1/k) Σ vⱼalignment: the neighbours' mean velocitya = …

c = (1/k) Σ xⱼ − xᵢcohesion: towards the neighbours' centrec = …

2Steering, not teleporting

Each rule gives a desired velocity at full speed in its direction. The steering force is the difference between that and the current velocity, capped at a small maximum, so boids turn smoothly instead of snapping. The weighted forces add up, the velocity changes by their sum, and speed stays between a minimum and a maximum so the flock never stalls. Every boid updates from the same snapshot, then all move together.

F = w_s steer(s) + w_a steer(a) + w_c steer(c)steer(u) = clamp(v_max û − v, F_max)w = …, |F| = …

v ← clamp(v + F, v_min, v_max)
x ← x + vone step per framev = …, speed …

3The spatial hash: only ask the neighbours

Checking every boid against every other is n(n − 1) distance tests a step, which grows with the square of the flock. Instead the stage is cut into square cells as wide as r, and each step the boids are bucketed into cells with a counting sort. Anyone within r must be in your own cell or one of the eight around it, so a boid only checks those nine buckets: the work grows like n, not n².

Switch the search to brute force to watch the n² cost; past a couple of thousand boids the step is spread over several frames so the page stays responsive, and the flock visibly stutters. N-body gravity faces the same n² problem with long-range forces and solves it with a tree instead.

cell = ⌊x / r⌋ + ⌊y / r⌋ × columnsbucket index; cells r wideringed boid: ⌊…⌋ + ⌊…⌋ × … = cell …

checks ≈ n × 9 r² ρ, not n(n − 1)ρ = boids per square pixel… instead of … (…)

4The quadtree: cut space where the birds are

A grid cuts space evenly, so a dense knot of birds lands in a few crowded cells while empty sky gets cells too. A quadtree adapts instead: start with one square round the whole stage, and split any square holding more than … boids into four, again and again. Dense flocks get small squares and empty sky stays one big one.

To find a boid's neighbours, walk down from the top and only open squares that overlap the box round its circle of radius r. It is the same tree N-body's Barnes-Hut mode builds every step for gravity; there it lumps far squares into one heavy star, here it just skips them. Pick quadtree in the search menu, tick show cells, and compare the checks with the grid's. For uniform boids at one radius the flat grid usually wins: it is simpler and every lookup is nine cells. Trees shine when density varies wildly or the search radius does.

split a square when it holds > … boidsdepth ≈ log₄ (n / leaf size) for an even spread…

visit leaves where [x ± r] × [y ± r] meets the squareabout log n steps down, then the boids in a few leaveschecks this step: …

5The predator

A fourth rule outranks the others: anything within the fear radius of the predator steers straight away from it, with a stronger force and a short burst of speed. Because neighbours copy each other's heading, the panic spreads through the flock faster than the predator can see, which is what makes real murmurations ripple and split. The hunting hawk chases the nearest boid it can see; your pointer is a hawk you steer.

f = steer(xᵢ − x_p) × 3, if |xᵢ − x_p| < r_fearflee; r_fear = 3 r, speed cap raised 30%fleeing now: …, caught so far: …

6Measuring order

Polarisation φ is the length of the average heading: 1 when every boid flies the same way, near 0 when they point every which way, like gas molecules. It is the order parameter physicists use for flocks (the Vicsek model), and the chart shows it climbing as the rules take hold. Set alignment to zero and order melts.

φ = | (1/n) Σ vᵢ / |vᵢ| |0 is disorder, 1 is a perfect flockφ = …