Flocking

by Drew Cutchins — on  , and  

Have you ever watched a school of fish, a flock of birds, or even a crowd of people and watched how they move?

Moving together, yet without a leader, they are exhibiting a behavior known as flocking.

Programmer Craig Reynolds defined this behavior according to three rules:

  1. Separation - Members will steer to maintain a defined distance from one another
  2. Alignment - Members will steer to face in a similar direction as members around them
  3. Cohesion - Members will steer to remain close to the flock

We can create flocking behavior in code by using these same rules.

First we need a way to represent a single member of the flock. These are called boids. Boids will have a position, velocity and acceleration. During every frame of the simulation, they will use their acceleration and velocity values to update their position.

//  Defining the model for a boid
class Boid{

    // They will be initialized with a starting x and y position
    constructor(xPos, yPos){
        //  The mass of the boid will dictate how responsive it is to flocking forces
        this.mass = 1;
        this.position = {x: xPos, y: yPos};
        this.velocity = {x: 0, y: 0};
        this.acceleration = {x: 0, y: 0};
    }

    //  Heading is represented by a decimal value indicating the radians
    get heading{
        return Math.atan2(this.velocity.x, this.velocity.y);
    }

    //  This function will be called to guide the boid while flocking
    applyForce(force){
        //  Acceleration is force devided by mass
        this.acceleration.x += force.x / this.mass;
        this.acceleration.y += force.y / this.mass;
    }

    update(){
        //  We will later add code to change the velocity of the boid given its suroundings
        updatePosition();
    }

    updatePosition(){
        //  Acceleration is change in velocity
        this.velocity.x += this.acceleration.x;
        this.velocity.y += this.acceleration.y;

        //  Veloity is change in position
        this.position.x += this.velocity.x;
        this.position.y += this.velocity.y;

        //  Acceleration is reset each frame
        this.acceleration = {x: 0, y: 0};
    }
}

Next, lets create a model for an entire flock.

// Defining the model for a flock
class Flock{
    constructor(flockSize){
        this.boids = [];
        this.size = flockSize;
        this.populateFlock();
    }

    populateFlock(){
        for(var n = 0; n < this.size; n++){

            //  The boids will be created at the center of the graph.
            this.boids.push(new Boid(0,0));

            //  The angle of the boids are evenly distributed in a circle
            var angle = (n / this.size) * 2 * Math.PI;

            //  The velocity is set based on the calculated angle
            this.boids[n].velocity = {x: Math.cos(angle), y: Math.sin(angle)};
        }
    }

    updateFlock(){
        for(var i = 0; i < this.size; i++){
            this.boids[i].update();
        }
    }
}

And finally, we can create a function to render our flock. I have created a few functions such as "drawTriangle" that are irrelevent to the flocking algorithm and therefore not included in this article.

function renderFlock(flock){
    for(var i = 0; i < flock.size; i++){
        renderBoid(flock.boids[i]);
    }
}

function renderBoid(boid){
    //  The drawTriangle function takes a position and a rotation as parameters
    drawTriangle(boid.position.x, boid.position.y, boid.heading);
}

Alright, now lets test our flock update

var flock = new Flock(10);

function loop(){
    // The loop will run every 10 milliseconds
    setTimeout(loop, 10);
    flock.update();
    renderFlock(flock);
}

Wait! All of the boids are gone as soon as they leave the canvas, I'll add a bit of code to make the sides of the screen wrap to one another. If a boid leaves on the left side of the canvas it will reappear on the right side.

Now that we have our flock management and rendering code set up, we can start applying our three rules of flocking.

However, in order to do this, our boids need to have information of other boids nearby. We need to change the boid update function to take an array of neighboring boids as a parameter. We also need to allow our updateFlock function to provide each boid update with its neighbors.

class Flock{
    constructor(flockSize){
        // ...

        //  The proximity boids have to be, to be considered neighbors.
        this.neighborDistance = 10;

        //  The neighborDistanceSquared is compared to the square distance between neighbors.
        //  This avoids the performance costly square root operation.
        this.neighborDistanceSquared = Math.pow(this.neighborDistance, 2);
    }

    // ...

    updateFlock(){
        for(var i = 0; i < this.size; i++){
            var neighbors = [];
            //  Iterates through all other boids to find neighbors.
            for(var j = 0; j < this.size; j++){
                if(j != i){
                    var squareDistance = Math.pow(this.boids[j].position.x - this.boids[i].position.x, 2) 
                        + Math.pow(this.boids[j].position.y - this.boids[i].position.y, 2);

                    if(squareDistance < this.neighborDistanceSquared){
                        neighbors.push(this.boids[j]);
                    }
                }
            }
            this.boids[i].update(neighbors);
        }
    }
}

Separation

Finally we can begin with applying separation to our boids. This force is calculated as a sum of vectors pointing away from nearby boids.

class Boid{

    constructor(xPos, yPos){
        //  ...
        //  We define an ideal distance for our boids to keep from one another
        this.separationDistance = 5;

        //  The strength with which the boid will avoid others
        this.separationStrength = 1;
    }

    //  ...

    update(neighbors){
        var separationForce = calculateSeparation(neighbors);
        this.applyForce(separationForce);
        updatePosition()
    }

    calculateSeparation(neighbors){
        //  This vector is the force we want to apply to our boid to keep it away from neighbors
        var separationForce = {x: 0, y: 0}

        for(var i = 0; i < neighbors.length; i++){
            //  Distance = sqrt((x1 - x2)^2 + (y1 - y2)^2)
            var distance = distance(this.position.x - neighbors[i].position.x,
                                    this.position.y - neighbors[i].position.y);
            if(distance < this.separationDistance){
                //  The offset between the two boids
                var offset = {
                    x: this.position.x - neighbors[i].position.x,
                    y: this.position.y - neighbors[i].position.y,
                }

                //  Note the use of a normalize function,
                //  It scales the vector so that its magnitude is 1.
                //  This value is used to indicate direction rather than distance.
                //  This function is not included in javascript so I had to implement it myself.
                var normalizedOffset = normalize(offset)

                //  The normalized offset is divided by the distance between the boids.
                //  A further boid requires less force to avoid
                var force = {x:normalizedOffset.x /= distance, y:normalizedOffset.y /= distance};

                //  The calculated force is added to the total separation force
                separationForce.x += force.x;
                separationForce.y += force.y
            }
        }

        return separationForce;
    }
    //  ...
}

Separation Strength

Separation Distance

As you watch how the boids avoid one another, try playing with the avoidance strength and seperation distance values. Note that the seperation distance cannot be greater than the neighbor distance value.

Cohesion

Next, we will implement cohesion, forcing boids toward the average position of all of its neighbors. Cohesion is essentially the opposite of separation. If boids are too close they will repel one another, if they are too far, they will atract one another. These two forces will work together to maintain a specified distance between boids.

class Boid{
    //  ...

    calculateCohesion(neighbors){

        //  This is the average position of all neighbors
        var averagePosition = {x: 0, y: 0};

        //  Tracks the number of boids within the cohesion distance
        var count = 0;

        for(var i = 0; i < neighbors.length; i++){
            var distance = distance(this.position.x - neighbors[i].position.x,
                                    this.position.y - neighbors[i].position.y);
            if(distance < this.cohesionDistance){
                averagePosition.x += neighbors[i].position.x;
                averagePosition.y += neighbors[i].position.y;
                count++;
            }
        }

        averagePosition /= count;

        var displacement = {x: averagePosition.x - this.position.x,
                            y: averagePosition.y - this.position.y};

        //  This vector is the force we want to apply to our boid to keep it away from neighbors
        var cohesionForce = {x: displacement.x * this.cohesionStrength, 
                             y: displacement.y * this.cohesionStrength};

        return cohesionForce
    }
}

Cohesion Strength

Cohesion Distance

Note how the boids stick near one another. However these boids now resemble clumps rather than a flock. By combining separation and cohesion, we can create much more realistic behavior.

Separation Strength

Separation Distance

Cohesion Strength

Cohesion Distance

Heading

Last but not least, we need to implement "heading". This final rule forces boids in a similar direction that their neighbors are travelling.

class Boid{

    //  ...

    calculateAlignment(neighbors){
        //  This is the average velocity of all neighbors
        var averageVelocity = {x: 0, y: 0};

        //  Tracks the number of boids within the cohesion distance
        var count = 0;

        for(var i = 0; i < neighbors.length; i++){
            var distance = distance(this.position.x - neighbors[i].position.x, 
                                    this.position.y - neighbors[i].position.y);

            if(distance < this.alignmentDistance){
                averageVelocity.x += neighbors[i].velocity.x;
                averageVelocity.y += neighbors[i].velocity.y;
                count++;
            }
        }

        //  Average = sum/count
        averageVelocity /= count;

        var alignmentForce = {x: averageVelocity.x * this.alignmentStrength, 
                              y: averageVelocity.y * this.alignmentStrength};

        return alignmentForce
    }
} 

Separation Strength

Separation Distance

Cohesion Strength

Cohesion Distance

Alignment Strength

Alignment Distance

When combined, these three simple rules have created complex emergent behavior. I hope you've enjoyed reading about flocking and that you've learned something new! Please provide any feedback or suggestions in the comments.


Related Posts:


Want to support this blog?

I would love to keep this blog ad-free! If you would like to support me, I would really appreciate if you could visit my patreon and make a contribution!


Blog Comments powered by Disqus.