Skip to content
Computational Lab.

Boids

Flocking from three steering forces.

Intermediate / particles / steering / emergence

Each boid follows three local rules: separate from neighbors that are too close, align with their average heading, and cohere toward their center of mass. No bird sees the flock, yet the flock appears. Tuning the three weights moves the system between gas, swarm, and vortex.

Tagged: emergence, steering, flocking, spatial hashing

Live simulation

Hold the pointer in the field to scatter the flock.

Speed

Hold the pointer in the field to scatter the flock.

Mathematics

Each boid steers by three local rules weighted and summed into one acceleration: separation from crowding, alignment with local heading, and cohesion toward the local center of mass.

a_i = w_s·s_i + w_a·a_i + w_c·c_i

order: φ = | Σ v_i | / (N · v_max), 0 ≤ φ ≤ 1

neighbor query: all j with |r_j − r_i| ≤ r_vision

The order parameter φ is the standard flocking metric: 1 means every boid flies in the same direction, near 0 means a milling swarm. Raising separation above alignment and cohesion breaks the flock into gas; the transition between regimes is sharp, which is why boids are studied as a phase transition.

How it works

Positions and velocities live in Float32Arrays. A uniform spatial hash with cell size equal to the vision radius reduces the naive O(N²) neighbor query to roughly O(N): each boid inspects only the 9 cells around it. Previous positions are stored each tick so the renderer can interpolate between fixed simulation steps at any refresh rate.

The pointer acts as a predator: while held, a short-range repulsion is added to nearby boids' steering. Drag through a flock and watch it reform from the same three rules.

Implementation

src/engine/experiments/boids.ts · 256 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import { clamp, lerp } from "../core/theme";
3import type { ParameterDef, PointerState, ThemeColors } from "../core/types";
4
5const CAPACITY = 400;
6
7/**
8 * Reynolds boids with a spatial hash for neighbor queries. State lives in
9 * typed arrays; previous positions are kept so render can interpolate
10 * between fixed ticks at any display refresh rate.
11 */
12export class BoidsExperiment extends BaseExperiment {
13 readonly id = "boids";
14
15 private count = 0;
16 private x = new Float32Array(CAPACITY);
17 private y = new Float32Array(CAPACITY);
18 private vx = new Float32Array(CAPACITY);
19 private vy = new Float32Array(CAPACITY);
20 private px = new Float32Array(CAPACITY);
21 private py = new Float32Array(CAPACITY);
22 private orderSum = 0;
23 private neighborSum = 0;
24 private pointer = { x: 0, y: 0, down: false, inside: false };
25
26 private head = new Int32Array(0);
27 private next = new Int32Array(CAPACITY);
28 private gridW = 0;
29 private gridH = 0;
30
31 protected params(): ParameterDef[] {
32 return [
33 { key: "population", label: "Population", min: 40, max: 400, step: 20, defaultValue: 220 },
34 { key: "vision", label: "Vision radius", min: 20, max: 80, step: 2, defaultValue: 44, unit: "px" },
35 { key: "separation", label: "Separation weight", min: 0, max: 3, step: 0.1, defaultValue: 1.6 },
36 { key: "alignment", label: "Alignment weight", min: 0, max: 3, step: 0.1, defaultValue: 1 },
37 { key: "cohesion", label: "Cohesion weight", min: 0, max: 3, step: 0.1, defaultValue: 0.9 },
38 { key: "speed", label: "Cruise speed", min: 40, max: 240, step: 10, defaultValue: 110, unit: "px/s" },
39 ];
40 }
41
42 protected onReset(): void {
43 this.count = this.num("population");
44 for (let i = 0; i < this.count; i++) {
45 this.x[i] = this.rng() * this.width;
46 this.y[i] = this.rng() * this.height;
47 const angle = this.rng() * Math.PI * 2;
48 this.vx[i] = Math.cos(angle) * this.num("speed");
49 this.vy[i] = Math.sin(angle) * this.num("speed");
50 this.px[i] = this.x[i];
51 this.py[i] = this.y[i];
52 }
53 this.orderSum = 0;
54 this.neighborSum = 0;
55 }
56
57 protected onParameterChange(key: string): void {
58 if (key === "population") this.reset();
59 }
60
61 resize(width: number, height: number): void {
62 this.width = width;
63 this.height = height;
64 this.reset();
65 }
66
67 onPointer(state: PointerState): void {
68 this.pointer = state;
69 }
70
71 private rebuildHash(): void {
72 const cell = Math.max(8, this.num("vision"));
73 this.gridW = Math.max(1, Math.ceil(this.width / cell));
74 this.gridH = Math.max(1, Math.ceil(this.height / cell));
75 const cells = this.gridW * this.gridH;
76 if (this.head.length !== cells) this.head = new Int32Array(cells);
77 this.head.fill(-1);
78 for (let i = 0; i < this.count; i++) {
79 const gx = Math.min(this.gridW - 1, Math.max(0, (this.x[i] / cell) | 0));
80 const gy = Math.min(this.gridH - 1, Math.max(0, (this.y[i] / cell) | 0));
81 const c = gy * this.gridW + gx;
82 this.next[i] = this.head[c];
83 this.head[c] = i;
84 }
85 }
86
87 protected onUpdate(dt: number): void {
88 const vision = this.num("vision");
89 const vision2 = vision * vision;
90 const sepRadius = vision * 0.45;
91 const sep2 = sepRadius * sepRadius;
92 const maxSpeed = this.num("speed");
93 const maxForce = maxSpeed * 2.4; // px/s^2
94 const cell = Math.max(8, vision);
95 this.rebuildHash();
96
97 const sepW = this.num("separation");
98 const aliW = this.num("alignment");
99 const cohW = this.num("cohesion");
100 let orderX = 0;
101 let orderY = 0;
102 let neighborTotal = 0;
103
104 for (let i = 0; i < this.count; i++) {
105 const gx = Math.min(this.gridW - 1, Math.max(0, (this.x[i] / cell) | 0));
106 const gy = Math.min(this.gridH - 1, Math.max(0, (this.y[i] / cell) | 0));
107 let sepX = 0;
108 let sepY = 0;
109 let aliX = 0;
110 let aliY = 0;
111 let cohX = 0;
112 let cohY = 0;
113 let neighbors = 0;
114
115 for (let oy = -1; oy <= 1; oy++) {
116 const ny = gy + oy;
117 if (ny < 0 || ny >= this.gridH) continue;
118 for (let ox = -1; ox <= 1; ox++) {
119 const nx = gx + ox;
120 if (nx < 0 || nx >= this.gridW) continue;
121 for (let j = this.head[ny * this.gridW + nx]; j !== -1; j = this.next[j]) {
122 if (j === i) continue;
123 const dx = this.x[j] - this.x[i];
124 const dy = this.y[j] - this.y[i];
125 const d2 = dx * dx + dy * dy;
126 if (d2 > vision2) continue;
127 neighbors += 1;
128 aliX += this.vx[j];
129 aliY += this.vy[j];
130 cohX += dx;
131 cohY += dy;
132 if (d2 < sep2 && d2 > 1e-6) {
133 const inv = 1 / d2;
134 sepX -= dx * inv;
135 sepY -= dy * inv;
136 }
137 }
138 }
139 }
140
141 let ax = 0;
142 let ay = 0;
143 if (neighbors > 0) {
144 // Reynolds steering: desired direction minus current velocity.
145 const invN = 1 / neighbors;
146 if (aliW > 0) {
147 const scale = maxSpeed / (Math.hypot(aliX, aliY) || 1);
148 ax += aliW * (aliX * scale * invN - this.vx[i]);
149 ay += aliW * (aliY * scale * invN - this.vy[i]);
150 }
151 if (cohW > 0) {
152 const cx = this.x[i] + cohX * invN;
153 const cy = this.y[i] + cohY * invN;
154 const toX = cx - this.x[i];
155 const toY = cy - this.y[i];
156 const scale = maxSpeed / (Math.hypot(toX, toY) || 1);
157 ax += cohW * (toX * scale - this.vx[i]);
158 ay += cohW * (toY * scale - this.vy[i]);
159 }
160 if (sepW > 0) {
161 const scale = maxSpeed / (Math.hypot(sepX, sepY) || 1);
162 ax += sepW * (sepX * scale - this.vx[i]) * 1.5;
163 ay += sepW * (sepY * scale - this.vy[i]) * 1.5;
164 }
165 neighborTotal += neighbors;
166 }
167
168 // Pointer acts as a predator: strong short-range repulsion.
169 if (this.pointer.inside) {
170 const dx = this.x[i] - this.pointer.x;
171 const dy = this.y[i] - this.pointer.y;
172 const d2 = dx * dx + dy * dy;
173 const radius = 120;
174 if (d2 < radius * radius && d2 > 1e-6) {
175 const falloff = 1 - d2 / (radius * radius);
176 const inv = (maxSpeed * 6 * falloff) / Math.sqrt(d2);
177 ax += dx * inv;
178 ay += dy * inv;
179 }
180 }
181
182 const mag = Math.hypot(ax, ay);
183 if (mag > maxForce) {
184 ax = (ax / mag) * maxForce;
185 ay = (ay / mag) * maxForce;
186 }
187
188 this.px[i] = this.x[i];
189 this.py[i] = this.y[i];
190 let nvx = this.vx[i] + ax * dt;
191 let nvy = this.vy[i] + ay * dt;
192 const speed = Math.hypot(nvx, nvy);
193 if (speed > maxSpeed) {
194 nvx = (nvx / speed) * maxSpeed;
195 nvy = (nvy / speed) * maxSpeed;
196 } else if (speed < maxSpeed * 0.35 && speed > 1e-6) {
197 const boost = (maxSpeed * 0.35) / speed;
198 nvx *= boost;
199 nvy *= boost;
200 }
201 this.vx[i] = nvx;
202 this.vy[i] = nvy;
203 this.x[i] = (this.x[i] + nvx * dt + this.width) % this.width;
204 this.y[i] = (this.y[i] + nvy * dt + this.height) % this.height;
205 orderX += nvx;
206 orderY += nvy;
207 }
208
209 this.orderSum = this.count > 0 ? Math.hypot(orderX, orderY) / (this.count * maxSpeed) : 0;
210 this.neighborSum = this.count > 0 ? neighborTotal / this.count : 0;
211 }
212
213 render(ctx: CanvasRenderingContext2D, theme: ThemeColors, alpha: number): void {
214 ctx.fillStyle = theme.bg;
215 ctx.fillRect(0, 0, this.width, this.height);
216 const trail = Math.max(2, this.num("speed") / 60);
217 for (let i = 0; i < this.count; i++) {
218 let ix = lerp(this.px[i], this.x[i], alpha);
219 let iy = lerp(this.py[i], this.y[i], alpha);
220 // Skip interpolation across a wrap seam.
221 if (Math.abs(ix - this.x[i]) > this.width / 2) ix = this.x[i];
222 if (Math.abs(iy - this.y[i]) > this.height / 2) iy = this.y[i];
223 const speed = Math.hypot(this.vx[i], this.vy[i]);
224 const dirX = speed > 0 ? this.vx[i] / speed : 1;
225 const dirY = speed > 0 ? this.vy[i] / speed : 0;
226 ctx.strokeStyle = i % 25 === 0 ? theme.accent : theme.fgSecondary;
227 ctx.lineWidth = i % 25 === 0 ? 1.5 : 1;
228 ctx.beginPath();
229 ctx.moveTo(clamp(ix - dirX * trail, 0, this.width), clamp(iy - dirY * trail, 0, this.height));
230 ctx.lineTo(clamp(ix + dirX * trail, 0, this.width), clamp(iy + dirY * trail, 0, this.height));
231 ctx.stroke();
232 }
233 }
234
235 getMetrics() {
236 let speedSum = 0;
237 for (let i = 0; i < this.count; i++) speedSum += Math.hypot(this.vx[i], this.vy[i]);
238 return {
239 population: this.count,
240 meanSpeed: `${(speedSum / Math.max(1, this.count)).toFixed(0)} px/s`,
241 neighbors: this.neighborSum.toFixed(1),
242 order: this.orderSum.toFixed(3),
243 };
244 }
245
246 describe(): string {
247 const flock =
248 this.orderSum > 0.7 ? "a tightly aligned flock" : this.orderSum > 0.35 ? "a loose flock" : "a dispersed swarm";
249 return `${this.count} boids form ${flock}; order parameter ${this.orderSum.toFixed(2)}.`;
250 }
251
252 entities(): number {
253 return this.count;
254 }
255}
256

Performance

Time per tick
≈ O(N) per tick with the spatial hash (O(N²) naive)
Space
Typed arrays: 6 floats per boid plus hash links
Notes
At the default 220 boids the whole update runs in well under a millisecond; the performance overlay shows the real number.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.