TypeScript: simulating birds flocks

If you’re interested in: simulations 🖥, how the universe works 💫, how an ant colony manages to gather 125 kg of food a day 🐜, how bird flocks emerge 🦅, then natural systems modelling may be the topic for you.

One example of natural systems are bird flocks. Simulating a flock of birds is surprisingly simple. There are 3 basic rules:

• Cohesion: Birds will try to move towards other birds
• Separation: Birds will try to avoid crashing into other birds
• Alignment: Birds will try to move in the same direction as other birds

Using these three simple rules, we can create impressively life like simulations.

The three rules mentioned above is known as the Boids algorithm, which was originally developed by Craig Reynolds in the 80’s and has been implemented countless times. From Wikipedia boid is defined as:

The name “boid” corresponds to a shortened version of “bird-oid object”, which refers to a bird-like object. “boid” is also a New York Metropolitan dialect pronunciation for “bird”.

This article is yet another tutorial on the amazing phenomena of emergent behaviour based on simple rules.

1. Basic structure

I made a lightweight “rendering engine” for TypeScript that allows me to quickly prototype animations using the HTML5 Canvas (View it on Github). This is what I will be using here.

Let’s create our boids class which will hold our rendering engine, and all the birds tracked by the system.

In our constructor, we first define the canvas where the birds will be rendered with the call to “new RenderingLayer()”.

We then add a few hundred birds to simulate. These birds will first start at random locations on the screen.

We can then start the rendering by calling the start method on the engine.

class Boids {
  birds: Array<IBird>;
  engine: IEngine;
  constructor() {
    const birdLayer = new RenderingLayer(LayerIndex.BIRDS, LayerType.DYNAMIC);

    this.birds = [];
    for (let i = 0; i < BIRD_COUNT; i++) {
      // add a bird at a random location in our layer.
      const x = Math.random() * this.birdLayer.getWidth();
      const y = Math.random() * this.birdLayer.getHeight();
      const bird = new Bird(this, x, y, birdLayer.getWidth(), birdLayer.getHeight());

      this.birds.push(bird);
      birdLayer.addEntity(bird);
    }

    this.engine = new Engine();
    this.engine.registerLayer(birdLayer);
    this.engine.start();
  }
}

1.1 Basic Bird Class

Each bird has a position, velocity and acceleration vector. Just as we’ve learnt in physics, position is calculated from velocity, which in turn is calculated by the accelerations. Acceleration is found by the following equation:

Force = MassAcceleration therefore Acceleration= Force/Mass.

In a universe where there is no mass (our simulation), then Acceleration = Force*.

The velocity here is initially given based on a random initial angle. The X component of our velocity vector can be found using the cosine of our angle whilst the Y component can be found using the sine.

However since this is graphics based mathematics, angles are not given in degrees, they are instead in radians.

Therefore, we must convert our random 0–360° into radians.

We then normalize this vector so it is of length one. This is important, because without this, birds going at 45° angles will be displaced further than birds going at a 90° (Hint: a²+b² = c²). However this unit vector means birds will travel 1 pixel, every 16 ms (1000 ms / 60 fps = 16 ms per frame). Let’s change that by multiplying by the bird speed. This will result in a velocity of: 100 px per 1000 ms. Or 100 px/second.

export default class Bird implements IBird {
  boids: Boids;
  position: Vector2D;
  velocity: Vector2D;
  acceleration: Vector2D;

  constructor(boids: Boids, initialX: number, initialY: number, maxX: number, maxY: number) {
    this.boids = boids;

    this.maxX = maxX;
    this.maxY = maxY;

    this.position = new Vector2D(initialX, initialY);
    const randomAngle = fromDegree(Math.random() * 360);
    this.velocity = new Vector2D(Math.cos(randomAngle), Math.sin(randomAngle))
      .normalize()
      .multiply(BIRD_SPEED);
    this.acceleration = Vector2D.ZERO();
  }
}

To render the bird, we can simply attach a render function to our bird.

render(context: CanvasRenderingContext2D) {
      this.rotate(context); // rotate to bird's angle.
      context.strokeStyle = 'red';
      context.beginPath();
      context.moveTo(this.position.x1 + BIRD_WIDTH/2, this.position.x2);
      context.lineTo(this.position.x1 - BIRD_WIDTH/2, this.position.x2 + BIRD_HEIGHT/2);
      context.lineTo(this.position.x1 - BIRD_WIDTH/2, this.position.x2 - BIRD_HEIGHT/2);
      context.closePath();
      context.stroke();
      this.unrotate(context); // restore canvas orientation
  }

  rotate(context: CanvasRenderingContext2D) {
      // Move origin point to the center of the bird
      context.translate(this.position.x1, this.position.x2);
      // Rotate about the bird's center by x degrees
      context.rotate(getAngle(this.velocity));
      // Return to the original origin
      context.translate(-this.position.x1, -this.position.x2);
  }

  unrotate(context: CanvasRenderingContext2D) {
      // Move origin point to the center of the bird
      context.translate(this.position.x1, this.position.x2);
      // Rotate about the bird's center by -x degrees (undoing rotation)
      context.rotate(-getAngle(this.velocity));
      // Move origin back to the origin.
      context.translate(-this.position.x1, -this.position.x2);
  }

Since we want our bird to have an orientation based on their velocity, we must rotate the canvas, then draw the bird, then undo the rotation so that the next bird can be rendered properly.

Here a bird is represented by a simple triangle.

I opt to rotate by the opposite values instead of saving canvas states and restore canvas for performance.

We end up with a decently interesting random mess

already :

1.2 Adding velocity!

By using the engine, we can add velocity with ease. We add an update function (which is an optional method on the IEntity interface) and take into account the time since the last render to get a fluid movement. Using deltaTime is useful for framerates that may not be constant (i.e. going from 30 fps to 60 fps would calculate position badly).

The checkBoundary() function simply wraps the bird around to the opposite side of the screen.

update(deltaTime: number) {
    this.position.add(
        this.velocity
            .clone()
            .multiply(deltaTime)
    );
    this.checkBoundary();
}

Adding velocity to position

To get the position, we use the velocity and multiply by the amount of time this velocity was maintained. In this case, the velocity will be maintained for roughly 16 ms, going at 100 px/s the boid will have moved 1.6px.

And with this, we are now ready to change their behaviour!

2. Implementing boid rules

In my implementation, performance is a big factor, especially because it is ran in JavaScript (we all know it isn’t very performant…).

The pseudo-code for Boids algorithm is originally of O(rN²) where r is the amount of rules, in this case 3. I opted to increase performance by removing consecutive inner loops. This is done with accumulators, they add up the values of each boid, before being calculated. This reduces the complexity to O(N²).

A new function to perform all maneuvers will help separate our code out:

• Each frame the rule accumulators are reset, and recalculated. The acceleration is defined as the sum of all boid rules.
• Birds can only see other birds if they are close by as birds are not omnipotent.
• The velocity is then calculated from the acceleration.
• Setting the magnitude of our velocity to the maximum bird speed will ensure that the birds don’t end up going the speed of light ⚡.

performManeuvers(birds: Array<IBird>) {
    this.resetAccumulators();

    let birdsSeen = 0;
    for(let n = 0; n<birds.length; n++) {
        if(birds[n] !== this) {
            if(birds[n].position.distance(this.position) < BIRD_VISUAL_RANGE) {
                birdsSeen += 1;
                for(let r = 0; r<this.rules.length; r++) {
                    this.rules[r].accumulate(birds[n]);
                }
            }
        }
    }

    for(let r = 0; r<this.rules.length; r++) {
        this.acceleration.add(
            this.rules[r].perform(birdsSeen)
        );
    }

    this.velocity
        .add(this.acceleration)
        .normalize()
        .multiply(BIRD_SPEED);
}

2.1 Cohesion

Cohesion says that birds will try to move towards the centre mass of nearby birds. This can be done by adding the position of nearby birds together and then finding the distance from the current bird’s position.

The position of the nearby birds are accumulated by summing their positions.

accumulate(bird: IBird) {
    this.value.add(bird.position);
}

And then the rule is performed by dividing by the amount of birds seen, and finding the distance between the current bird and the center of mass.

performCohesion(birdCount: number): Vector2D {
      return this.cohesionAccumulator
          .divide(birdCount)
          .sub(this.position)
          .divide(BIRD_COHESION_RESISTANCE);
  }

A constant can be used to resist this cohesion force.

Resulting in a pretty satisfying animation already.

However there is one problem… all the birds just collide and will form a single dot. This is where the second rule comes in…

2.2 Separation

Separation fixes the problem that cohesion brings, it isn’t very natural for birds to just collide and not to drop out of sky 💀. A new rule — separation — is created to keep birds a certain distance away from other birds.

In this case, we accumulate the distance between two birds (if they’re within separation distance).

accumulateSeparation(bird: IBird) {
    const distance = bird.position
        .clone()
        .sub(this.position);

    if (distance.magnitude() < BIRD_SEPARATION_DISTANCE) {
        this.separationAccumulator.sub(distance);
    }
}

We can add this value directly to velocity to get the separation factor.

2.3 Alignment

Although we fixed the problem with cohesion by adding the separation rule, a new problem can be seen… The birds will just coalesce into a ball, and end up cancelling the movement out. To fix this, we can add a new force aligning birds in the average direction of movement.

Alignment is defined as taking the average velocity of the nearby birds, and subtracting our velocity from this average.

performAlignment(birdCount: number): Vector2D {
    return this.nearbySumOfVelocities
        .divide(birdCount) // average velocity by dividing
        .normalize()
        .multiply(BIRD_SPEED)
        .sub(this.velocity)     // subtract our velocity to get the force
        .multiply(BIRD_ALIGNMENT_EAGERNESS);
}

The bird alignment eagerness constant is a meta variable allowing us to change the behaviour of the flock from a constants file.

And there we have it. Add the three rules together… Change values for some meta variables… and we get flock simulation.

3. Extras

• Original research by Craig
• Boids source code on Github
• TypeScript Render Engine on Github

Further improvement ideas:

1. Hunger, exhaustion, maximum velocity change (before death), age;
2. Predators, mating, different rule weights based on behaviour;
3. Genetic algorithm! NEAT?;

If you want to see more of our works, take a look at our blog section on software development.

Finally, I wanted to add a nice background for the birds, so I made one using Perlin noise.