Developer
Boids - Simulating life
Creating a flocking simulation in JavaScript
20 Jun 22

A little over a month ago I was holed up in a hotel in Phnom Penh, Cambodia. I was supposed to be staying somewhere new every other night but the day I arrived in Cambodia I was struck with a toothache so bad I couldn't leave my hotel.

I watched people from my hotel window as they weaved between and around each other, following friends and dodging speeding tuk tuks. It reminded me of boids simulations I had seen online. I decided to take advantage of my downtime and start a new project.

Project page: https://ronandoherty.com/projects/boids

Repository: https://github.com/donanroherty/Boids

NOTE: The demo above has evolved since I wrote this post. Some implementation details have changed, but the principles are the same.

## What is boids?

Boids is an algorithm to simulate the emergent behaviour of flocking animals. Each boid is an independent agent which alters it's own velocity in an attempt to stay close to other boids. A boid is essentially a particle which reacts to forces applied to it.

A boid uses 3 primary forces to control its movement in a group:

• Cohesion guides a boid towards the center of a group, which is the average position of all other agents in visible range of our boid.

• Alignment attempts to match a boids velocity (direction and speed) to its neighbours.

• Separation creates space between boids, reducing collisions and spreading out flockmates over a larger area.

The combination of these 3 forces enable a group of boids to self organise, flying as a group without overlapping. Groups can join other groups or dynamically split apart depending on how these 3 forces are tuned.

To create a more realistic result I have also added a drag force to simulate air or fluid friction.

Additionally there is an enforced minimum and maximum speed to prevent unrealistic behaviour. A bird can not have a speed of zero without falling out of the sky. Max speed can also be a balancing factor to prevent a boid from gaining too much momentum from a force and repeatedly punching through the middle of a flock without finding an equilibrium.

## Code overview

Clone the code at tag v1.0.0 to follow along:

``git clone --depth 1 --branch v1.0.0 https://github.com/donanroherty/Boids.git``

### File structure

``````- /boids/
app.js
boid.js
flock.js
tick.js
vec2.js
index.html
jsconfig.json
package.json
- /gui/
...``````

The `/gui/` folder contains a SolidJS app which wraps the boids code, adds controls to the main parameters and builds to the web component at the top of this page. Have a play with it and then jump into the `/boids/` folder.

The files to pay attention to are:

• `app.js` initializes the canvas, creates a flock and creates a tick routine which updates the simulation and draws the boids every frame.
• `boid.js` implements a single boid with all the forces necessary to create it's emergent behaviour.
• `flock.js` creates and stores boids in a list. Update and draw calls are propogated to the boids through the flock.
• `tick.js` creates a repeating timestep. The timestep is fixed, always producing a deltatime of 1/60th of a second. It will cap out at this framerate but may run slower with more boids to compute.
• `vec2.js` is a collection of useful vector operations.

For this article I will focus on the implementation of a single boid in `boids.js`. Everything else should be easy enough to figure out by reading the code.

### Boid implementation

``````// /src/boid.js
// ...
function createBoid(pos, vel, canvas) {
let position = pos
let velocity = vel

let config = {
size: 5,
detectionRange: 50,
cohesionFactor: 0.2,
alignmentMaxStrength: 0.3,
separationMaxStrength: 10,
separationRange: 30,
dragFactor: 0.01,
minSpeed: 50,
maxSpeed: 150,
}
// ...``````

Lets jump into the boid implementation. A boid has a `position` that is mutated each timestep by a `velocity` vector. Velocity is accumulated by adding forces to it each frame. The primary forces are cohesion, alignment and separation, however I also added a drag factor to simulate air density and a min and max speed to ensure movement remains within realistic limits.

Beneath the position and velocity variables are the boid tuning parameters.

#### Updating the simulation

``````// /src/boid.js
// ...
function update(dt, boids) {
const boidsInRange = boids.filter(
(b) =>
position !== b.getPosition() &&
position.sub(b.getPosition()).lenSq() < config.detectionRange * config.detectionRange
)

if (boidsInRange.length > 0) {
}

velocity = velocity.clampedLen(config.minSpeed, config.maxSpeed)

mirrorOutOfBounds()
}
// ...``````

Each frame, `update(dt, boids)` is called with arguments for deltatime and an array of all boids.

• `dt` is the timestep between frames. This is provided by the tick function and is used to calculate the proportion of the velocity vector to apply to the boids position each frame. As I'm using a fixed timestep of 60 frames per second `dt` will always be 1/60 = .01666 seconds.

• `boids` is a list of all boids in the flock.

The `boids` list is filtered and assigned to `boidsInRange`, which should only contain agents which are not the current boid and within the boids detection range.

`addForce` is now called for each of our forces `cohesion`, `alignment`, `separation` and `drag`. Each call to `addForce` mutates the current velocity vector as `velocity=velocity+force`.

We wrap the `cohesion`, `alignment` and `separation` forces in an if statment checking `boidsInRange.length` as there's no point computing these forces if there is no boids within range.

Speed limits

`velocity`'s length is clamped between `minSpeed` and `maxSpeed`.

Updating the position

A new position for the boid is calculated as `position + (velocity * deltatime` and applied to position.

Handling boids that fly off screen

Finally `mirrorOutOfBounds()` is called to check if a boid has flown out of the canvas. Boids that fly through a border are teleported to the opposite side of the canvas.

## The force functions

### Cohesion

``````  function cohesion(boids) {
const avgPos = boids
.reduce((acc, b) => {
return acc
}, vec2())
.div(vec2(boids.length, boids.length))

const toGroupCenter = avgPos.sub(position)
}``````

Cohesion is a force which a boid uses to move towards the center it's of fellow boids within range. We pass `cohseion(boids)` all the flockmates in range and calculate the average position by getting the sum of all positions and dividing by the number of boids.

`toGroupCenter` is a vector pointing to the average ceter of the nearby flockmates. This can be thought of as the speed and direction the boid must move to reach the flock center. The further a boid is from the center, the longer `toGroupCenter` will be and the faster the boid will try to accelerate towards it's flockmates. We scale `toGroupCenter` by `cohesionFactor` to give us more control of the cohesion force.

### Alignment

``````  function alignment(boids) {
const avgVel = boids
.reduce((acc, b) => {
return acc
}, vec2())
.div(vec2(boids.length, boids.length))

const diff = avgVel.sub(velocity)
return diff.clampedLen(0, config.alignmentMaxStrength)
}``````

Alignment steers a boid to move in the same direction and speed as its flockmates. Similar to cohesion, we get the average velocity (`avgVel`) of each flockmate. We subtract the boids `velocity` from the `avgVel` to get the force necessary to match the groups speed and direction. Again, we want to control the strength of this force using `alignmentMaxStrength`. The resulting force will gradually cause our boid to match the direction and speed of its flockmates.

### Separation

``````  function separation(boids) {
const boidsTooClose = boids.filter(
(b) => position.sub(b.getPosition()).lenSq() < config.separationRange * config.separationRange
)

return boidsTooClose.reduce((acc, other) => {
const ba = getPosition().sub(other.getPosition())
const dist = ba.len()

const perc = 1 - dist / config.separationRange
}, vec2())
}``````

Separation is a force which pushes a boid away from other boids within range to prevent collisions. Try standing too close to one of your friends and you'll see why it's necessary. We want to add a force in the opposite direction, making it stronger when flockmates are very close, and weaker when they are further away.

We filter the flockmates into a new array, `boidsTooClose`, which is all boids closer than `separationRange`.

Now we reduce `boidsTooClose` into a vector force. For every flockmate that is too close for comfort, we get a vector (`ba`) pointing from the flockmate to our boid and distance (`dist`) to the flockmate from this vector.

We calculate `perc` as value between 0 and 1 representing how far the flockmate is encroaching on our personal space. Now we create a force in the direction of `ba` and scale it by `separationMaxStrength` and `perc`. The larger `perc` is, the more seperation strength is applied.

Each iteration of the reduce function accumulates a force which will move our boid away from it's encroaching flockmates.

### Drag

``````  function drag() {
return velocity.scale(-config.dragFactor)
}``````

Drag reduces a boids speed as it passes through the air. Each frame, we add an opposing force to the velocity scaled by the `dragFactor`. This makes our boid tend to move at it's `minSpeed` most of the time rather than sitting at its max speed as if it was flying through space.

## A note about the tick function

``````// ./src/tick.js
function createTick(tickFn) {
const targetFPS = 60
let timeout
let lastRealDelta

doTick_R(performance.now())

function doTick_R(timestamp) {
const now = performance.now()

tickFn(1 / targetFPS)

timeout = setTimeout(() => {
doTick_R(now)
lastRealDelta = now - timestamp
}, 1000 / targetFPS)

return timeout
}

return {
targetFPS,
getTimeout: () => timeout,
getLastRealDelta: () => lastRealDelta,
}
}``````

`app.js` calls `createTick` passing an update function as an argument. Each tick, the update function clears the canvas, updates the simulation and draws the updated scene to the canvas.

I used a simple fixed rate tick function for this project. A fixed rate ensures that each frame will have the exact same delta time which gives consistant behaviour every frame. I originally tried using a variable framerate, however as computation time varies based on the number of boids and how close they are to each other, the simulation becomes very unstable when subjected to vastly different deltatimes.

I settled for a fixed tick rate of 60 updates per second. A frame may take longer but delta time will always be the same.

## Conclusion

That's the meat and potatoes of the boids algorithm. The supporting code in the other files should be self explanatory.

Where to go from here? Well there's a lot of ways to add more dynamism and interesting interactions to these simple rules. I hope to add some of the following features and write about them soon:

• Predators boids
• Multiple flocks interacting
• Obstical avoidence
• Wind and and air turbulance
• Feeding and goals
• Birth and death cycles
• Making the system 3D
• Tune parameters for various agent types (birds, fish, peole, cars, spaceships)
• The list goes on...