The idea: steer a little, every tick

A game character or a simulated bird should not jump to its goal. It should turn and speed up the way a vehicle does. Craig Reynolds' steering behaviours do this with one rule. Each tick, a behaviour says which velocity the agent would like to have, the desired velocity. The steering force is the difference:

steering = desired − v        (clamped to the max force)
v ← v + steering·dt          (clamped to the max speed)
p ← p + v·dt
A boid with its velocity v = (2, 0) as a grey arrow, a blue arrow for the desired velocity (1.81, −0.85) pointing at the target, and a red dashed arrow from the tip of v to the tip of the desired velocity: desired − v = (−0.19, −0.85). A small circle at the tip of v shows that only a piece up to the max force 0.1 is used.
The steering force is desired − v, but only a small piece (the max force) is used per tick, so the boid turns in a smooth curve.

The max force is what makes the motion look natural. In Demo 1: one seek step up close, the boid flies right with v = (2, 0) and the target is down and to the right. desired − v = (−0.19, −0.85) has length 0.87, but only 0.1 of it is used: steering = (−0.022, −0.098). The boid turns a few degrees per tick.

The page uses a fixed timestep, dt = 1 tick, and seeded start positions. The same start gives the same flight every time, which is why the numbers below can be checked. See The Game Loop: Variable Delta Time vs a Fixed Timestep for why games step physics with a fixed dt, and Projectile Motion for motion under one constant force, gravity.

Seek and arrive

Seek wants full speed straight at the target. It never wants to slow down, so the boid flies past, turns and comes back. (Demo 2: seek overshoots and circles: start (15, 60), target (100, 20), max speed 2, max force 0.1. The boid first comes within 2 units at tick 47; at tick 100 it is 17.00 units away again. It circles the target for ever.)

Arrive is seek with brakes. Inside a slowing radius (20 units here) the desired speed falls in proportion to the distance, so it is 0 at the target.

Desired speed against distance to the target. Seek is a flat line at 2. Arrive rises in a straight line from 0 at distance 0 to 2 at distance 20, the slowing radius, then stays at 2.
Seek always wants speed 2; arrive wants 2 × distance / 20 inside the slowing radius, so it wants to stop exactly at the target.

(Demo 3: arrive slows down and stops: the same start; at tick 100 the boid is 0.00 from the target at speed 0.00.)

Flee and adding behaviours together

Flee is seek turned around: the desired velocity points straight away from a threat. Here it only acts inside a panic radius of 15. Behaviours combine as a weighted sum of their steering forces, each clamped first. In Demo 4: arrive + flee steers around a threat, the threat sits next to the straight path and flee has weight 3. The boid swerves and comes no closer than 7.12 units (plain arrive would pass 2.43 from it). Once it is out of the panic radius, arrive takes it to the target: 0.02 units away at tick 120.

A weighted sum has a known weakness. If the threat sat exactly on the path, the two forces would point in opposite directions and could cancel, leaving the boid stuck in front of the threat.

Boids: three local rules

In 1987 Reynolds made a flock of boids ("bird-oids") from three steering behaviours. Each boid only sees its neighbours, the boids within a radius R (15 units here). Nobody leads and nobody knows the whole flock.

Three panels with the same kind of picture: a red boid in the middle of a dashed circle of radius R with orange neighbours. Separation: a red arrow away from the two boids inside a small red circle. Alignment: a blue arrow towards the neighbours' mean heading. Cohesion: a green arrow towards a plus sign at the neighbours' centre.
Every rule looks only inside the neighbour radius: separation pushes off close boids, alignment matches their heading, cohesion moves to their centre.
RuleDesired velocityWeight here
Separationaway from neighbours closer than 6, each weighted by 1/distance1.5
Alignmentthe neighbours' mean velocity1
Cohesionseek the neighbours' centre1

Each rule's steering is desired − v at full speed 2, clamped to 0.05, then multiplied by its weight. All 24 boids work out their forces from the old positions, then all move at once. The world wraps around its edges. (Demo 5: one flocking step up close: the red boid has 6 neighbours, 2 of them closer than 6. Separation (−0.069, −0.030), alignment (−0.036, −0.035) and cohesion (0.013, −0.048) add up to (−0.092, −0.113).)

Measuring a flock

  • The alignment order parameter φ = |mean of the unit velocities|. It is 1 when every boid flies the same way and near 0 when the headings are random.
  • The closest pair: the smallest distance between two boids. Near 0 means boids sit on top of each other.
  • Groups: link every two boids closer than R and count the connected parts.

(Demo 6: all three rules make a flock: φ goes from 0.26 to 0.94 in 100 ticks, the 13 starting groups merge into 2, and the closest pair stays 2.81 apart.)

What each weight does

Switch one rule off and the flock breaks in its own way. Same seed, 100 ticks:

Weights (sep, ali, coh)φclosest pairgroupswhat you see
1.5, 1, 10.942.812a flock (Demo 6)
0, 1, 10.990.132boids pile on top of each other (Demo 7)
1.5, 0, 10.221.534clusters that mill about, no common heading (Demo 8)
1.5, 1, 00.985.563aligned but loose; groups never join
1.5, 0, 00.196.2814boids only keep apart

Boids look a little like particle swarm optimization, but the goal is different. PSO particles all listen to one shared best point to search a function. Boids have no goal and no shared memory; the flock comes only from what each boid sees nearby.

What the page leaves out

Real games and films use more behaviours (wander, pursue and evade a moving target, path following, obstacle avoidance with look-ahead, leader following) and pick between them by priority, not only a weighted sum. Boids there usually have a field of view, so they ignore boids behind them, and they work in 3D. With thousands of boids the neighbour search uses a grid or a tree instead of checking every pair. The page also skips mass (force = mass × acceleration) and orientation smoothing.

On the mind map

This page on the AI: Search, Games & Reasoning mind map · 23 pages in 7 branches · open it to see the whole map and test yourself in recall mode.