Boids: Flocking Behavior

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Boids

Loading interactive demo…

Boids in a walled field with obstacles, or on a torus, each steering by three local rules read off the neighbours inside its circle: separation pushes away from each of them, alignment steers toward their mean heading, cohesion toward their centre. A fourth rule turns a boid from a wall or obstacle it is close to. Each rule is a capped steering force; the weighted sum of the three is capped, added to the velocity with the avoid push, and the speed capped. Every boid moves at once from the same start-of-tick state, and glides there over the tick. One boid is followed; the rest run the same code untraced.Take the tour, or press and explore. Legend:

The panel beside the stage is the real Flock class from the published library executing in your browser, with the current line highlighted.

The followed boid, ringed, and its summed push once the rules are in.
Each group of neighbours wears its own colour, the largest group this one; every chevron points along its velocity.
A boid flying alone, hollow; the trails of the last ticks; the followed boid's dashed circle is its radius; the walls and the obstacles.
The separation push.
The alignment push.
The cohesion push, and the neighbours' centre it heads for.
The avoid push, away from a wall or obstacle that is close.

neighbours counts the boids inside the followed boid's circle, speed is its speed, polarization the length of the flock's mean unit heading (1 is one shared heading), spread the mean distance to the flock's centre, and groups how many chains of neighbours the flock is in and how many boids fly alone. Tap a boid to follow it.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Three rules, three vectors. A boid at $p$ with velocity $v$ sees the set $N$ of boids within radius $r$ . Separation wants to go away from each neighbour, the nearest hardest: $d_{\text{sep}} = \sum_{j \in N} \frac{p - p_j}{|p - p_j|^2}$ . Alignment wants the neighbours' mean heading, $d_{\text{ali}} = \sum_{j \in N} v_j$ , and cohesion wants their centre, $d_{\text{coh}} = \frac{1}{|N|}\sum_{j \in N} p_j - p$ . Each is only a direction; what turns it into motion is the steering recipe.

Desired minus current, capped. For a desired direction $d$ the steering force is $f = \operatorname{limit}\big(\hat{d}\, v_{\max} - v,\ f_{\max}\big)$ : full speed the desired way, minus the velocity the boid already has, capped at $f_{\max}$ . A boid already flying the desired way gets no push; one flying the wrong way gets the full cap. The weighted sum $w_s f_{\text{sep}} + w_a f_{\text{ali}} + w_c f_{\text{coh}}$ is capped again at $f_{\max}$ , added to $v$ , and $|v|$ is capped at $v_{\max}$ . Two caps: one on how hard a boid can turn, one on how fast it can go. With $f_{\max} = 0.1$ and $v_{\max} = 0.4$ a boid turns about fourteen degrees a tick, so a heading spreads through a neighbourhood in a dozen ticks or so.

Local rules, global order. No boid sees the flock, only its circle, yet the headings line up. Polarization, the length of the mean unit heading $\big|\frac{1}{n}\sum_i \hat{v}_i\big|$ , starts near $0$ for scattered headings and climbs toward $1$ . Alignment is what spreads a heading through a group; separation and cohesion set its spacing, and their balance is the spread readout. Set separation to zero and the flock collapses; set the radius to one and it forms far more slowly, since most boids see nobody.

Why a torus ends in one heading. Alignment is a consensus rule: every meeting averages two headings and nothing ever disagrees, so on a plane that wraps, with nothing to turn for, the only stable end is every boid flying one way. Real flocks keep milling because the world keeps disturbing them. Here that is a fourth rule, avoid: a wall inside a margin or an obstacle inside its reach asks for a turn away, harder the closer it is (the ask grows as the square of how far in the boid is), steered like the other rules but with a budget of its own, $2 f_{\max}$ , so the boid turns in time. A group that meets a wall turns and splits from groups elsewhere; streams part round an obstacle and merge beyond it. The groups readout counts the chains of neighbours the flock is in, and each wears its own colour on the stage. Switch the edges to torus and take the obstacles away to watch the consensus set in.

Cost. Every boid checks every other, $O(n^2)$ a tick: fine for $24$ , hopeless for $10^5$ . Real flocks bin boids into a spatial hash or a grid of cells the radius wide, so each boid checks only the neighbouring cells, near $O(n)$ for a sparse flock.

The edges. On a torus the plane wraps: a boid leaving an edge enters the opposite one, and the offset between two boids is the shorter of the two ways round on each axis, never more than half the world. Between walls the offset is the plain difference, a boid that reaches an edge is held inside, and the avoid rule sees to it that almost none does.

Synchronous update. Every push in a tick is computed from the state the tick began with, then every boid moves. Updating in place would let boid $3$ react to where boid $2$ already moved this tick, and the result would depend on the order the boids were numbered.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

step maps the old state to a new array before assigning it, which is the synchronous update: every steer call reads the start-of-tick state.
Zero forces are still emitted, so a tick always plays seven events and a lonely boid's tick reads "nothing to push away from" rather than skipping ahead.
seek caps once and steer caps again: each rule's force is capped at maxForce, then their weighted sum is, then the speed is capped at maxSpeed. The avoid push is the exception: seek with twice the cap, added after the sum, so it is never crowded out by the three rules.
The wrap is a double modulo, ((x % width) + width) % width, because a negative coordinate's remainder is negative; between walls contain clamps instead, and clear sets a boid that ended inside an obstacle onto its surface.
offset is a static, used for the neighbourhood and by the stage for the same distance, so the circle on the stage and the code agree about who is a neighbour across the seam.
The focus boid is the only one traced; every other boid runs the same private steer with no tracer, which is why the trace stays seven events a tick whatever the count.

Craig Reynolds built the boids model in 1986 while at Symbolics and presented it at SIGGRAPH the next year. Animating a flock by hand, bird by bird, was hopeless; scripting the flock as one object looked wrong. His answer was to give each simulated bird a few local rules about its nearest neighbours and let the flock emerge. The paper's three rules, separation, alignment, and cohesion, are still the ones every flocking system starts from, and the idea that convincing group motion comes from simple individual behaviour became the basis of behavioural animation in film and games.

1986Craig Reynolds - Develops the boids model, an artificial life program in which each bird-like agent steers by separation, alignment, and cohesion toward its local flockmates.source
1987Craig Reynolds - Publishes 'Flocks, Herds, and Schools: A Distributed Behavioral Model' at SIGGRAPH; the short film Stanley and Stella in: Breaking the Ice, the first animation made with the model, premieres at the same conference's Electronic Theater.source
1992Tim Burton's Batman Returns - Brings boids to feature film: computer-generated bat swarms and armies of penguins marching through Gotham City, made with modified versions of Reynolds' software.source
1998Craig Reynolds - Receives the Academy Scientific and Technical Award for his pioneering contributions to the development of three-dimensional computer animation for motion picture production.source
1999Craig Reynolds - Presents 'Steering Behaviors for Autonomous Characters' at the Game Developers Conference, a library of behaviours (seek, flee, wander, arrival, obstacle avoidance, path following) with flocking as the combination of separation, alignment, and cohesion.source

Used today

Film crowds - Behavioural animation grew out of the model: bat swarms, penguin armies, and the wildebeest stampede in The Lion King are flocks of simple agents.
Game AI - Flocking, and the steering behaviours it belongs to, move squads, schools, and swarms in games; Half-Life used boids in 1998.
Swarm robotics - Groups of unmanned ground and aerial vehicles keep formation with the same three local rules.
Optimization - Particle swarm optimization, introduced by Kennedy and Eberhart in 1995, moves a swarm of candidate solutions with the same flock-inspired local pulls.

boids24

radius3.00

separation1.50

alignment1.00

cohesion1.00

max speed0.40

edges

obstacles

ticks

trails

show

neighbours: 1 of 23
speed: 0.13
polarization: 0.65
spread: 9.3
groups: 3 groups, 7 alone

flock.ts

import { Vec2 } from "../linear/vec";import type { Tracer } from "../trace";/** One bird-oid object: where it is and how it is moving, in world units per tick. */export interface Boid {  position: Vec2;  velocity: Vec2;}/** What the edges of the world do: wrap round, or push back. */export type FlockWorld = "torus" | "walls";/** A round obstacle the boids steer round. */export interface Obstacle {  readonly x: number;  readonly y: number;  readonly r: number;}export interface FlockOptions {  /** The world is this wide and this high. */  width: number;  height: number;  /** "torus" (the default): a boid leaving one edge enters the opposite one. "walls": the edges push back. */  world?: FlockWorld;  /** Walls only: how far inside an edge its push begins (default 0, no push). */  margin?: number;  obstacles?: readonly Obstacle[];  /** How far outside an obstacle's surface its push begins (default 0, no push). */  reach?: number;  /** Weight of the avoid push (default 1). */  avoid?: number;  avoidanceForce?: number;  /** A boid sees every other boid within this distance (the short way round, on a torus). */  radius: number;  /** Weights of the three rules in the summed push. */  separation: number;  alignment: number;  cohesion: number;  /** A boid never moves faster than this, in units per tick. */  maxSpeed: number;  /** A tick's summed push, and each rule's push, is capped at this length. */  maxForce: number;}const ZERO = new Vec2(0, 0);/** * Reynolds' boids: every boid steers by three local rules read off its * neighbours within a radius. Separation pushes away from each * neighbour, hardest from the nearest; alignment steers toward the * neighbours' mean heading; cohesion steers toward their centre. Each * rule is a steering force, the desired velocity minus the current one * capped at `maxForce`; the weighted sum is capped again, added to the * velocity, and the speed capped at `maxSpeed`. A fourth rule, avoid, * turns a boid away from a wall it is about to reach and from any * obstacle it is close to; it has a budget of its own, twice the cap, * so a boid turns before the wall instead of sharing the rules' cap * with it. The update is synchronous: every rule in a tick reads the * state the tick began with, and the whole flock moves at once. The * world is a torus or a walled field. * * Time per tick: O(n²) for n boids, since every boid checks every * other; a spatial hash brings it near O(n) for a sparse flock. */export class Flock {  private state: Boid[];  private tick = 0;  private optionsValue: FlockOptions;  constructor(    boids: readonly Boid[],    options: FlockOptions,    private readonly tracer?: Tracer,  ) {    Flock.validate(options);    this.optionsValue = options;    this.state = Flock.copy(boids);  }  /** The rules in force: the world, the radius, the four weights, and the two caps. */  get options(): FlockOptions {    return this.optionsValue;  }  /** The flock as it stands, after the ticks stepped so far. */  get boids(): readonly Boid[] {    return this.state;  }  /** How many ticks have been stepped. */  get ticks(): number {    return this.tick;  }  /**   * Changes the rules without moving anything: the next tick reads the   * new options from the same positions and headings, and the tick count   * carries on. Invalid options throw and leave the old ones in force.   */  retune(options: FlockOptions): void {    Flock.validate(options);    this.optionsValue = options;  }  /** Replaces the boids without touching the rules or the tick count: a flock that grew or shrank mid-run. */  repopulate(boids: readonly Boid[]): void {    this.state = Flock.copy(boids);  }  private static validate(o: FlockOptions): void {    if (!(o.width > 0) || !(o.height > 0)) throw new RangeError(`world ${o.width} by ${o.height} is empty`);    if (!(o.radius > 0)) throw new RangeError(`radius ${o.radius} must be positive`);    if (o.separation < 0 || o.alignment < 0 || o.cohesion < 0 || (o.avoid ?? 1) < 0) throw new RangeError("rule weights must not be negative");    if (o.separation < 0 || o.alignment < 0 || o.cohesion < 0 || (o.avoidanceForce ?? 1) < 0) throw new RangeError("rule weights must not be negative");    if (!(o.maxSpeed > 0) || !(o.maxForce > 0)) throw new RangeError("maxSpeed and maxForce must be positive");    if ((o.margin ?? 0) < 0 || (o.reach ?? 0) < 0) throw new RangeError("margin and reach must not be negative");    for (const ob of o.obstacles ?? []) if (!(ob.r > 0)) throw new RangeError(`obstacle radius ${ob.r} must be positive`);  }  private static copy(boids: readonly Boid[]): Boid[] {    return boids.map((b) => ({ position: b.position, velocity: b.velocity }));  }  /** The displacement from a to b: on a torus the shortest way round, never more than half the world along either axis. */  static offset(a: Vec2, b: Vec2, width: number, height: number, world: FlockWorld = "torus"): Vec2 {    let dx = b.x - a.x;    let dy = b.y - a.y;    if (world === "torus") {      if (dx > width / 2) dx -= width;      else if (dx < -width / 2) dx += width;      if (dy > height / 2) dy -= height;      else if (dy < -height / 2) dy += height;    }    return new Vec2(dx, dy);  }  /** The length of the mean unit heading: 1 when every boid flies the same way, near 0 when headings cancel. */  static polarization(boids: readonly Boid[]): number {    if (boids.length === 0) return 0;    let sum = ZERO;    for (const b of boids) sum = sum.add(b.velocity.normalize());    return sum.length() / boids.length;  }  /**   * One synchronous tick: every boid's push is computed from the state   * the tick began with, then all of them move at once. The focus boid   * is traced; the rest run the same code untraced.   */  step(focus = -1): readonly Boid[] {    this.tick += 1;    this.state = this.state.map((_, i) => this.steer(i, i === focus ? this.tracer : undefined));    return this.state;  }  /** Steps `ticks` times and returns the history, the starting state first. */  run(ticks: number, focus = -1): Boid[][] {    if (!Number.isInteger(ticks) || ticks < 0) throw new RangeError(`ticks ${ticks} must be a whole number`);    const history: Boid[][] = [[...this.state]];    for (let t = 0; t < ticks; t++) history.push([...this.step(focus)]);    return history;  }  private steer(i: number, tracer?: Tracer): Boid {    const { width, height, radius, maxSpeed, maxForce } = this.options;    const world = this.options.world ?? "torus";    const self = this.state[i]!;    const near: number[] = [];    const neighbourIds: number[] = [];    let away = ZERO;    let heading = ZERO;    let centre = ZERO;    for (let j = 0; j < this.state.length; j++) {      if (j === i) continue;      const other = this.state[j]!;      const d = Flock.offset(self.position, other.position, width, height, world);      const dist = d.length();      if (dist > radius) continue;      near.push(j);      neighbourIds.push(j);      // Away from the neighbour, weighted by the inverse square of its distance: the nearest pushes hardest.      if (dist > 0) away = away.sub(d.scale(1 / (dist * dist)));      heading = heading.add(other.velocity);      centre = centre.add(d);    }    // ▸ which boids lie within the radius    tracer?.emit("neighbours", { tick: this.tick, boid: i, count: near.length, ids: [...near] });    tracer?.emit("neighbours", { tick: this.tick, boid: i, count: neighbourIds.length, ids: [...neighbourIds] });    const sep = this.seek(away, self.velocity);    const separationForce = this.seek(away, self.velocity);    // ▸ push away from each neighbour, the nearest hardest    tracer?.emit("separation", { tick: this.tick, fx: sep.x, fy: sep.y, strength: sep.length() });    tracer?.emit("separation", { tick: this.tick, fx: separationForce.x, fy: separationForce.y, strength: separationForce.length() });    const ali = this.seek(heading, self.velocity);    const alignmentForce = this.seek(heading, self.velocity);    // ▸ steer toward the neighbours' mean heading    tracer?.emit("alignment", { tick: this.tick, fx: ali.x, fy: ali.y, strength: ali.length() });    tracer?.emit("alignment", { tick: this.tick, fx: alignmentForce.x, fy: alignmentForce.y, strength: alignmentForce.length() });    const toCentre = near.length > 0 ? centre.scale(1 / near.length) : ZERO;    const toCentre = neighbourIds.length > 0 ? centre.scale(1 / neighbourIds.length) : ZERO;    const coh = this.seek(toCentre, self.velocity);    const cohesionForce = this.seek(toCentre, self.velocity);    const c = this.contain(self.position.add(toCentre));    // ▸ steer toward the neighbours' centre    tracer?.emit("cohesion", { tick: this.tick, fx: coh.x, fy: coh.y, strength: coh.length(), cx: c.x, cy: c.y });    tracer?.emit("cohesion", { tick: this.tick, fx: cohesionForce.x, fy: cohesionForce.y, strength: cohesionForce.length(), cx: c.x, cy: c.y });    const avoid = this.avoidance(self);    const avoidanceForce = this.avoidance(self);    // ▸ turn away from a wall or an obstacle that is close    tracer?.emit("avoid", { tick: this.tick, fx: avoid.x, fy: avoid.y, strength: avoid.length() });    tracer?.emit("avoid", { tick: this.tick, fx: avoidanceForce.x, fy: avoidanceForce.y, strength: avoidanceForce.length() });    const push = sep    const push = separationForce      .scale(this.options.separation)      .add(ali.scale(this.options.alignment))      .add(alignmentForce.scale(this.options.alignment))      .add(coh.scale(this.options.cohesion))      .add(cohesionForce.scale(this.options.cohesion))      .limit(maxForce);    const raw = self.velocity.add(push).add(avoid.scale(this.options.avoid ?? 1));    const raw = self.velocity.add(push).add(avoidanceForce.scale(this.options.avoidanceForce ?? 1));    const velocity = raw.limit(maxSpeed);    // ▸ sum the three pushes, cap the push, add it and the avoid push, cap the speed    tracer?.emit("steer", { tick: this.tick, ax: push.x, ay: push.y, vx: velocity.x, vy: velocity.y, speed: velocity.length(), limited: raw.length() > maxSpeed });    const moved = self.position.add(velocity);    const position = this.clear(this.contain(moved));    // ▸ step along the new velocity; wrap at the edges, or stay inside the walls    tracer?.emit("move", { tick: this.tick, x: position.x, y: position.y, wrapped: world === "torus" && (position.x !== moved.x || position.y !== moved.y) });    return { position, velocity };  }  /**   * The avoid rule's push: away from every wall inside the margin and   * every obstacle inside its reach, each growing with the square of how   * far in the boid is, so a wall a whole margin away asks for nothing   * and one at hand asks for everything. Steered like the other rules   * but with twice the cap, and eased in so a faint ask stays faint.   */  private avoidance(self: Boid): Vec2 {    const { width, height, maxForce } = this.options;    const world = this.options.world ?? "torus";    const margin = this.options.margin ?? 0;    const reach = this.options.reach ?? 0;    const ramp = (t: number): number => (1 - t) * (1 - t);    let want = ZERO;    if (world === "walls" && margin > 0) {      const p = self.position;      if (p.x < margin) want = want.add(new Vec2(ramp(Math.max(0, p.x) / margin), 0));      if (width - p.x < margin) want = want.add(new Vec2(-ramp(Math.max(0, width - p.x) / margin), 0));      if (p.y < margin) want = want.add(new Vec2(0, ramp(Math.max(0, p.y) / margin)));      if (height - p.y < margin) want = want.add(new Vec2(0, -ramp(Math.max(0, height - p.y) / margin)));    }    if (reach > 0) {      for (const ob of this.options.obstacles ?? []) {        const d = Flock.offset(new Vec2(ob.x, ob.y), self.position, width, height, world);        const dist = d.length();        const gap = dist - ob.r;        if (gap < reach && dist > 0) want = want.add(d.scale(1 / dist).scale(ramp(Math.max(0, gap) / reach)));      }    }    const ask = want.length();    if (ask === 0) return ZERO;    return this.seek(want, self.velocity, 2 * maxForce).scale(Math.min(1, 2 * ask));  }  /** A steering force toward a desired direction: full speed that way, minus the current velocity, capped. Nowhere to go is no force. */  private seek(desired: Vec2, velocity: Vec2, cap = this.options.maxForce): Vec2 {    if (desired.length() === 0) return ZERO;    return desired.normalize().scale(this.options.maxSpeed).sub(velocity).limit(cap);  }  /** The same point inside the world: on a torus the equivalent point in the fundamental rectangle, between walls the nearest point inside. */  private contain(p: Vec2): Vec2 {    const { width, height } = this.options;    if ((this.options.world ?? "torus") === "walls") {      const x = Math.min(width, Math.max(0, p.x));      const y = Math.min(height, Math.max(0, p.y));      return x === p.x && y === p.y ? p : new Vec2(x, y);    }    const x = ((p.x % width) + width) % width;    const y = ((p.y % height) + height) % height;    return x === p.x && y === p.y ? p : new Vec2(x, y);  }  /** A point inside an obstacle is set onto its surface: the avoid rule turns boids away, this keeps a cornered one out. */  private clear(p: Vec2): Vec2 {    let out = p;    for (const ob of this.options.obstacles ?? []) {      const centre = new Vec2(ob.x, ob.y);      const d = out.sub(centre);      const dist = d.length();      if (dist < ob.r && dist > 0) out = centre.add(d.scale(ob.r / dist));    }    return out;  }}

ticks =: 48
polarization =: 0.65
mean speed =: 0.23

48 ticks done: polarization 0.65 (1 would be one shared heading), mean speed 0.23.

import { Vec2 } from "../linear/vec";import type { Tracer } from "../trace";/** One bird-oid object: where it is and how it is moving, in world units per tick. */export interface Boid { position: Vec2; velocity: Vec2;}/** What the edges of the world do: wrap round, or push back. */export type FlockWorld = "torus" | "walls";/** A round obstacle the boids steer round. */export interface Obstacle { readonly x: number; readonly y: number; readonly r: number;}export interface FlockOptions { /** The world is this wide and this high. */ width: number; height: number; /** "torus" (the default): a boid leaving one edge enters the opposite one. "walls": the edges push back. */ world?: FlockWorld; /** Walls only: how far inside an edge its push begins (default 0, no push). */ margin?: number; obstacles?: readonly Obstacle[]; /** How far outside an obstacle's surface its push begins (default 0, no push). */ reach?: number; /** Weight of the avoid push (default 1). */ avoid?: number; avoidanceForce?: number; /** A boid sees every other boid within this distance (the short way round, on a torus). */ radius: number; /** Weights of the three rules in the summed push. */ separation: number; alignment: number; cohesion: number; /** A boid never moves faster than this, in units per tick. */ maxSpeed: number; /** A tick's summed push, and each rule's push, is capped at this length. */ maxForce: number;}const ZERO = new Vec2(0, 0);/** * Reynolds' boids: every boid steers by three local rules read off its * neighbours within a radius. Separation pushes away from each * neighbour, hardest from the nearest; alignment steers toward the * neighbours' mean heading; cohesion steers toward their centre. Each * rule is a steering force, the desired velocity minus the current one * capped at `maxForce`; the weighted sum is capped again, added to the * velocity, and the speed capped at `maxSpeed`. A fourth rule, avoid, * turns a boid away from a wall it is about to reach and from any * obstacle it is close to; it has a budget of its own, twice the cap, * so a boid turns before the wall instead of sharing the rules' cap * with it. The update is synchronous: every rule in a tick reads the * state the tick began with, and the whole flock moves at once. The * world is a torus or a walled field. * * Time per tick: O(n²) for n boids, since every boid checks every * other; a spatial hash brings it near O(n) for a sparse flock. */export class Flock { private state: Boid[]; private tick = 0; private optionsValue: FlockOptions; constructor( boids: readonly Boid[], options: FlockOptions, private readonly tracer?: Tracer, ) { Flock.validate(options); this.optionsValue = options; this.state = Flock.copy(boids); } /** The rules in force: the world, the radius, the four weights, and the two caps. */ get options(): FlockOptions { return this.optionsValue; } /** The flock as it stands, after the ticks stepped so far. */ get boids(): readonly Boid[] { return this.state; } /** How many ticks have been stepped. */ get ticks(): number { return this.tick; } /** * Changes the rules without moving anything: the next tick reads the * new options from the same positions and headings, and the tick count * carries on. Invalid options throw and leave the old ones in force. */ retune(options: FlockOptions): void { Flock.validate(options); this.optionsValue = options; } /** Replaces the boids without touching the rules or the tick count: a flock that grew or shrank mid-run. */ repopulate(boids: readonly Boid[]): void { this.state = Flock.copy(boids); } private static validate(o: FlockOptions): void { if (!(o.width > 0) || !(o.height > 0)) throw new RangeError(`world ${o.width} by ${o.height} is empty`); if (!(o.radius > 0)) throw new RangeError(`radius ${o.radius} must be positive`); if (o.separation < 0 || o.alignment < 0 || o.cohesion < 0 || (o.avoid ?? 1) < 0) throw new RangeError("rule weights must not be negative"); if (o.separation < 0 || o.alignment < 0 || o.cohesion < 0 || (o.avoidanceForce ?? 1) < 0) throw new RangeError("rule weights must not be negative"); if (!(o.maxSpeed > 0) || !(o.maxForce > 0)) throw new RangeError("maxSpeed and maxForce must be positive"); if ((o.margin ?? 0) < 0 || (o.reach ?? 0) < 0) throw new RangeError("margin and reach must not be negative"); for (const ob of o.obstacles ?? []) if (!(ob.r > 0)) throw new RangeError(`obstacle radius ${ob.r} must be positive`); } private static copy(boids: readonly Boid[]): Boid[] { return boids.map((b) => ({ position: b.position, velocity: b.velocity })); } /** The displacement from a to b: on a torus the shortest way round, never more than half the world along either axis. */ static offset(a: Vec2, b: Vec2, width: number, height: number, world: FlockWorld = "torus"): Vec2 { let dx = b.x - a.x; let dy = b.y - a.y; if (world === "torus") { if (dx > width / 2) dx -= width; else if (dx < -width / 2) dx += width; if (dy > height / 2) dy -= height; else if (dy < -height / 2) dy += height; } return new Vec2(dx, dy); } /** The length of the mean unit heading: 1 when every boid flies the same way, near 0 when headings cancel. */ static polarization(boids: readonly Boid[]): number { if (boids.length === 0) return 0; let sum = ZERO; for (const b of boids) sum = sum.add(b.velocity.normalize()); return sum.length() / boids.length; } /** * One synchronous tick: every boid's push is computed from the state * the tick began with, then all of them move at once. The focus boid * is traced; the rest run the same code untraced. */ step(focus = -1): readonly Boid[] { this.tick += 1; this.state = this.state.map((_, i) => this.steer(i, i === focus ? this.tracer : undefined)); return this.state; } /** Steps `ticks` times and returns the history, the starting state first. */ run(ticks: number, focus = -1): Boid[][] { if (!Number.isInteger(ticks) || ticks < 0) throw new RangeError(`ticks ${ticks} must be a whole number`); const history: Boid[][] = [[...this.state]]; for (let t = 0; t < ticks; t++) history.push([...this.step(focus)]); return history; } private steer(i: number, tracer?: Tracer): Boid { const { width, height, radius, maxSpeed, maxForce } = this.options; const world = this.options.world ?? "torus"; const self = this.state[i]!; const near: number[] = []; const neighbourIds: number[] = []; let away = ZERO; let heading = ZERO; let centre = ZERO; for (let j = 0; j < this.state.length; j++) { if (j === i) continue; const other = this.state[j]!; const d = Flock.offset(self.position, other.position, width, height, world); const dist = d.length(); if (dist > radius) continue; near.push(j); neighbourIds.push(j); // Away from the neighbour, weighted by the inverse square of its distance: the nearest pushes hardest. if (dist > 0) away = away.sub(d.scale(1 / (dist * dist))); heading = heading.add(other.velocity); centre = centre.add(d); } // ▸ which boids lie within the radius tracer?.emit("neighbours", { tick: this.tick, boid: i, count: near.length, ids: [...near] }); tracer?.emit("neighbours", { tick: this.tick, boid: i, count: neighbourIds.length, ids: [...neighbourIds] }); const sep = this.seek(away, self.velocity); const separationForce = this.seek(away, self.velocity); // ▸ push away from each neighbour, the nearest hardest tracer?.emit("separation", { tick: this.tick, fx: sep.x, fy: sep.y, strength: sep.length() }); tracer?.emit("separation", { tick: this.tick, fx: separationForce.x, fy: separationForce.y, strength: separationForce.length() }); const ali = this.seek(heading, self.velocity); const alignmentForce = this.seek(heading, self.velocity); // ▸ steer toward the neighbours' mean heading tracer?.emit("alignment", { tick: this.tick, fx: ali.x, fy: ali.y, strength: ali.length() }); tracer?.emit("alignment", { tick: this.tick, fx: alignmentForce.x, fy: alignmentForce.y, strength: alignmentForce.length() }); const toCentre = near.length > 0 ? centre.scale(1 / near.length) : ZERO; const toCentre = neighbourIds.length > 0 ? centre.scale(1 / neighbourIds.length) : ZERO; const coh = this.seek(toCentre, self.velocity); const cohesionForce = this.seek(toCentre, self.velocity); const c = this.contain(self.position.add(toCentre)); // ▸ steer toward the neighbours' centre tracer?.emit("cohesion", { tick: this.tick, fx: coh.x, fy: coh.y, strength: coh.length(), cx: c.x, cy: c.y }); tracer?.emit("cohesion", { tick: this.tick, fx: cohesionForce.x, fy: cohesionForce.y, strength: cohesionForce.length(), cx: c.x, cy: c.y }); const avoid = this.avoidance(self); const avoidanceForce = this.avoidance(self); // ▸ turn away from a wall or an obstacle that is close tracer?.emit("avoid", { tick: this.tick, fx: avoid.x, fy: avoid.y, strength: avoid.length() }); tracer?.emit("avoid", { tick: this.tick, fx: avoidanceForce.x, fy: avoidanceForce.y, strength: avoidanceForce.length() }); const push = sep const push = separationForce .scale(this.options.separation) .add(ali.scale(this.options.alignment)) .add(alignmentForce.scale(this.options.alignment)) .add(coh.scale(this.options.cohesion)) .add(cohesionForce.scale(this.options.cohesion)) .limit(maxForce); const raw = self.velocity.add(push).add(avoid.scale(this.options.avoid ?? 1)); const raw = self.velocity.add(push).add(avoidanceForce.scale(this.options.avoidanceForce ?? 1)); const velocity = raw.limit(maxSpeed); // ▸ sum the three pushes, cap the push, add it and the avoid push, cap the speed tracer?.emit("steer", { tick: this.tick, ax: push.x, ay: push.y, vx: velocity.x, vy: velocity.y, speed: velocity.length(), limited: raw.length() > maxSpeed }); const moved = self.position.add(velocity); const position = this.clear(this.contain(moved)); // ▸ step along the new velocity; wrap at the edges, or stay inside the walls tracer?.emit("move", { tick: this.tick, x: position.x, y: position.y, wrapped: world === "torus" && (position.x !== moved.x || position.y !== moved.y) }); return { position, velocity }; } /** * The avoid rule's push: away from every wall inside the margin and * every obstacle inside its reach, each growing with the square of how * far in the boid is, so a wall a whole margin away asks for nothing * and one at hand asks for everything. Steered like the other rules * but with twice the cap, and eased in so a faint ask stays faint. */ private avoidance(self: Boid): Vec2 { const { width, height, maxForce } = this.options; const world = this.options.world ?? "torus"; const margin = this.options.margin ?? 0; const reach = this.options.reach ?? 0; const ramp = (t: number): number => (1 - t) * (1 - t); let want = ZERO; if (world === "walls" && margin > 0) { const p = self.position; if (p.x < margin) want = want.add(new Vec2(ramp(Math.max(0, p.x) / margin), 0)); if (width - p.x < margin) want = want.add(new Vec2(-ramp(Math.max(0, width - p.x) / margin), 0)); if (p.y < margin) want = want.add(new Vec2(0, ramp(Math.max(0, p.y) / margin))); if (height - p.y < margin) want = want.add(new Vec2(0, -ramp(Math.max(0, height - p.y) / margin))); } if (reach > 0) { for (const ob of this.options.obstacles ?? []) { const d = Flock.offset(new Vec2(ob.x, ob.y), self.position, width, height, world); const dist = d.length(); const gap = dist - ob.r; if (gap < reach && dist > 0) want = want.add(d.scale(1 / dist).scale(ramp(Math.max(0, gap) / reach))); } } const ask = want.length(); if (ask === 0) return ZERO; return this.seek(want, self.velocity, 2 * maxForce).scale(Math.min(1, 2 * ask)); } /** A steering force toward a desired direction: full speed that way, minus the current velocity, capped. Nowhere to go is no force. */ private seek(desired: Vec2, velocity: Vec2, cap = this.options.maxForce): Vec2 { if (desired.length() === 0) return ZERO; return desired.normalize().scale(this.options.maxSpeed).sub(velocity).limit(cap); } /** The same point inside the world: on a torus the equivalent point in the fundamental rectangle, between walls the nearest point inside. */ private contain(p: Vec2): Vec2 { const { width, height } = this.options; if ((this.options.world ?? "torus") === "walls") { const x = Math.min(width, Math.max(0, p.x)); const y = Math.min(height, Math.max(0, p.y)); return x === p.x && y === p.y ? p : new Vec2(x, y); } const x = ((p.x % width) + width) % width; const y = ((p.y % height) + height) % height; return x === p.x && y === p.y ? p : new Vec2(x, y); } /** A point inside an obstacle is set onto its surface: the avoid rule turns boids away, this keeps a cornered one out. */ private clear(p: Vec2): Vec2 { let out = p; for (const ob of this.options.obstacles ?? []) { const centre = new Vec2(ob.x, ob.y); const d = out.sub(centre); const dist = d.length(); if (dist < ob.r && dist > 0) out = centre.add(d.scale(ob.r / dist)); } return out; }}