03. Flocking Simulation - Making a Flock of... Boids

 

Introduction

It is common to see how birds and bees flock in intricate ways to travel in nature. This is both fascinating and intricate at the same time. They don't seem to follow a fixed set of rules, yet they follow one another in an orderly manner that order seems to come from chaos. However, in 1986 Craig Reynolds developed a mathematical model that can simulate this kind of behaviour using a mathematical model. He describes a collection of entities called 'Boids' that move in cooperation; or as we say a 'Flock', in space.

The Rules

Each boid moves in space according to three basic rules as Craig lays out:

1. Separation - Steer to avoid crowding local flockmates
2. Alignment - Steer towards the average heading of local flockmates
3. Cohesion - Steer to move toward the average position of local flockmates For each Boid, we must implement these rules so that they behave in a way that ultimately results in the whole flock simulating the behavioural patterns of a flock of birds.

Implementation

Setting Up

We'll start by creating a canvas. In it, we'll create the boids as a class. A boid has several properties: 01. Position, 02. Velocity and 03. Acceleration. We'll create each boid with random position and velocity.

PVector position = new PVector(width/2 + random(-50, 50), height/2 + random(-50, 50));
PVector velocity = new PVector(random(-1, 1), random(-1, 1));
PVector acceleration = new PVector(random(-0.1, 0.1), random(-0.1, 0.1));

Programming the Behaviour

We need three behaviours for boids as well: 01. draw(), 02. update() and 03. flock(). The draw function will draw the boid on-screen, the update function will update all parameters and the flock function will implement the rules. We'll discuss about edgeFix() later.

 void update() {
    this.position.add(this.velocity);
    this.velocity.add(this.acceleration);
    edgeFix();
}

 Flock Function

We will have a separate function that works on the rules: flock(). This will call three functions that individually work on the three rules and return the results to this function.

01. Separation

Essentially, 'Separation' means that an individual boid always avoids crowding. If there are too many boids closer to each other, it tries to move away so that there is much less crowding. In order to implement this in code, we first get the distance between each boid within its neighbourhood and this boid. Then we calculate the ratio between the separation of the two boids on each axis. This is used in the average calculation.

PVector average = new PVector();
int total = 0;
for (int i = 0; i < myFlock.length; i++) {
    if (i != this.ID) {
        float distance = this.position.dist(myFlock[i].position);
            if (distance < neighbourhoodRadius) {
            PVector separation = PVector.sub(this.position, myFlock[i].position);
            separation.div(distance);
            average.add(separation);
            total++;
        }
    }
}
if (total > 0) {
    average.div(total);
    average.setMag(maxSpeed);
    average.sub(this.velocity);
}

02. Alignment

Alignment means that the boids try to move towards the average direction that the rest of the boids are moving. To implement this in code, we must take the velocities of each boid in the vision radius: the radius within which the boid is perceived to see and take the average direction. Something to notice is that we only need the direction, not the speed. Therefore we replace the speed with a fixed speed by using average.setMag(maxSpeed).

PVector average = new PVector();
int total = 0;
for (int i = 0; i < myFlock.length; i++) {
    if (i != this.ID) {
        float distance = this.position.dist(myFlock[i].position);
        if (distance < visionRadius) {
            average.add(myFlock[i].velocity);
            total++;
        }
    }
}
if (total > 0) {
    average.div(total);
    average.setMag(maxSpeed);
    average.sub(this.velocity);
}

03. Cohesion

Cohesion means that the boid tries to move towards the average position of the neighbouring boids. In order to achieve this in code we take the average position of the boids in the neighbourhood and try to move towards it.

PVector average = new PVector();
int total = 0;
for (int i = 0; i < myFlock.length; i++) {
    if (i != this.ID) {
    float distance = this.position.dist(myFlock[i].position);
        if (distance < neighbourhoodRadius) {
            average.add(myFlock[i].position);
            total++;
        }
    }
}
if (total > 0) {
    average.div(total);
    average.sub(this.position);
    average.setMag(maxSpeed);
    average.sub(this.velocity);
}

We will treat the average we get from this as a force. Thus to limit the amount of force we apply to change the direction, we will set a maximum force that each function can apply.

average.limit(maxForce);

Once we receive each force, in the flock() function, we will add them together and set them as the new acceleration. In this case, we consider the mass to be one, thus we can equal force to acceleration.

void flock(boid[] myFlock) {
    PVector alignment = this.align(myFlock);
    PVector cohesion = this.cohesion(myFlock);
    PVector separation = this.separation(myFlock);

    acceleration = new PVector();
    this.acceleration.add(alignment);
    this.acceleration.add(cohesion);
    this.acceleration.add(separation);
}

Finally we will use the draw() function to draw the boids on screen.

Since the boids can move away from the screen, we will use a function called edgeFix() to bring back the boids from the opposite side of the screen.

void edgeFix() {
    if (position.x < 0 || position.x > width) {
        position = new PVector(abs(position.x - width), position.y);
    }
    if (position.y < 0 || position.y > height) {
        position = new PVector(position.x, abs(position.y - height));
    }
}

Finishing Up

In the draw() loop, we will work on each boid.

for(int i = 0; i < Flock.length; i++)
{
    Flock[i].flock(Flock);
    Flock[i].update();
    Flock[i].draw();
}

Cleaning Up the Design

To make the code a bit more interesting, we'll make the first boid behave according to the mouse pointer and ignore the rules, yet others will treat this boid as a usual boid. Thus the flock will end up following the mouse pointer.

if (i != 0) {
    Flock[i].flock(Flock);
    Flock[i].update();
} else {
    Flock[i].position = new PVector(mouseX, mouseY);
}

We will also draw the boids as triangles. One point will face the direction to which it is trying to move.

void drawBoid(PVector position, PVector velocity) {
    PVector p1 = velocity.copy();
    p1.setMag(boidSize);

    PVector p2 = p1.copy();
    p2.rotate(HALF_PI);

    PVector p3 = p1.copy();
    p3.rotate(-HALF_PI);

    triangle(position.x + p1.x, position.y + p1.y, position.x + p2.x/2, position.y + p2.y/2, position.x + p3.x/2, position.y + p3.y/2);
}

 

With that, we can end this adventure. We have a flock of boids that fly! As usual, you can find the code in the Github Repository.

External Links:

• Github Repository with the Processing Code: Github Repository
• Wikipedia article on boids: wikipedia.org
• Craigs original research article: Article
• A Wikipedia article on swarm intelligence: wikipedia.org
• Craigs outline on the flocking simulation: red3d.com
• Coding challenge on flocking simulation by The Coding Train: thecodingtrain.com