Flocking behavior

In this article I'll explain how to simulate the movements of birds which is called flocking. The article is based on the wonderful paper of Graig Reynolds whom's name is always used in the same sentence with flocking behavior. Graig did a wonderful job on the research of movement of birds. This behavior can be used in you visualisations, simulations, etc.. A couple of days ago I found a fantastic implementation of flocking behavior in a logo. Have a look at BLPRNT.com (wait untill the logo has loaded).

Keypoints in flocking

Basically to implement flocking behavior you'll need to following things:

1. A good working vector class which openframeworks has.
2. Implementation of: Separation
3. Implementation of: Alignment
4. Implementation of: Cohesion

Flocking video, based on the code described in this article

Flocking with openFrameworks from roxlu on Vimeo.

1. A good working vector class.

Here I mean a vector class which does all the vector operations for you. A vector is something which has a length and a direction. You can find numerous tutorials on vector math but to implement flocking you don't need lots of fancy things. Most of the math is extremely simple, like addition, subtraction, multiplication and averaging. 'All'of the flocking implementations use a vector class, though it can be done without. In this article we do use vectors. Let me quickly explain how this vector class is used.

In our simulation we have a couple of "boids", which represent the birds. A bird has a position and velocity. Multiple forces which influence the velocity and therefore the position are applied on thes boids. Like in most physics implementations we calculate the resulting position based on the current forces, velocity and position. The new position is simply calculated by adding all the forces to the velocity and then adding the velocity to the current position.

velocity += force;
position += velocity;

Note that the above code is not 100% working as we need to limit the force and velocity.

2. Implementation of: Separation

We use separation to avoid that all boids group together at one position. They need to keep a certain distance from eachother. For this implementation we created two classes, Boid and Boids. Boid represents a single bird, and Boids a 'flock'.

The Boids class implements the flocking behaviour. It has a method "flock()" which handles the separation. Roughly the separation works like this (in pseudo code):

Loop through all boids (i)
    Loop through all other boids (j)
          Check if i != j (we don't check the current boid with itself)
          Calculate the distance of the current boid (i) with the other boids (j)
          If the other boid is too close move away 
   End loop
End loop

The implementation of cohesion for our flocking algorithm:
note: I left out the other part like cohesion and alignment for clearity.

void Boids::flock() {
    float too_close_dist = 90.0f;
    float in_sight_dist = 150.0f;
 
    for (int i = 0; i < boids.size(); ++i) {
        for(int j = 0; j < boids.size(); ++j) {
            if (j == i) continue;
            float dist = (boids[i]->getPosition() - boids[j]->getPosition()).length();
 
            // separate
            if (dist <= in_sight_dist ) {
                // This is where we move away. We "Flee" away from the other Boid.
                if (dist <= too_close_dist) {
                        boids[i]->flee(boids[j]->getPosition());
                }
            }
        }
 
    }
}

3. Implementation of: Alignment

As described by Craig Reynolds, alignment is the behavior of birds when they steer towards the average heading of local flockmates. This means we check which birds are in range and remember the velocity of each of these in-range birds. When we've found all birds in range we average this velocity and steer towards it.

Alignment in openFrameworks

void Boids::flock() {
    float too_close_dist = 90.0f;
    float in_sight_dist = 150.0f;
    int insight_count = 0;
    ofxVec3f average_vel, average_pos;
    for (int i = 0; i < boids.size(); ++i) {
        average_vel.set(0,0,0);
        average_pos.set(0,0,0);
        insight_count = 0;
 
        for(int j = 0; j < boids.size(); ++j) {
            if (j == i) continue;
            float dist = (boids[i]->getPosition() - boids[j]->getPosition()).length();
 
            if (dist <= in_sight_dist ) {
                average_vel += boids[j]->getVelocity();
                insight_count++;
            }
        }
        if (insight_count > 0) {
            average_vel /= insight_count;
            boids[i]->addForce(average_vel - boids[i]->getVelocity());
        }
    }
}

4. Implementation of: Cohesion

When we've got a group of birds they tend to fly into a direction as a whole. This is because of cohesion; each bird positions himself to a average direction. A bird looks at the birds which are in sight and adjusts his position to the average position of the birds in sight.

Technically we achieve this (like with separation) for each bird to check the distance to the other birds and when they are in a given range we remember their position. When we've looped through all position for lets say the first bird, we calculate the average position and we let the bird seek this point.

In pseudo code:

Loop through all boids (i)
    Loop through all other boids (j)
          Check if i != j (we don't check the current boid with itself)
          Calculate the distance of the current boid (i) with the other boids (j)
          If the other boid is in range
               Add the position to our average postion vector (ofxVec3f)
               Increase the "insight counter" that is used to average the position
          End if
   End loop
   Average the position
   Let boid "i" seek to the average position
End loop

Implementation of the cohesion for the flocking algorithm.

void Boids::flock() {
    float in_sight_dist = 150.0f;
    int insight_count = 0;
    ofxVec3f average_vel, average_pos;
    for (int i = 0; i < boids.size(); ++i) {
        average_vel.set(0,0,0);
        average_pos.set(0,0,0);
        insight_count = 0;
 
        for(int j = 0; j < boids.size(); ++j) {
            if (j == i) continue;
            float dist = (boids[i]->getPosition() - boids[j]->getPosition()).length();
 
            if (dist <= in_sight_dist ) {
                average_pos += boids[j]->getPosition();
                insight_count++;
            }
        }
        if (insight_count > 0) {
            average_pos /= insight_count;
            boids[i]->seek(average_pos);
        }
    }
}

Additional information about flocking

As you see we use a method "seek" which implements a seeking steering behavior. I've attaced the source code with some other parts that are used to create a simple flock.

Resources

Craig Reynolds Boids
Download the source code of the flocking algorithm