Flocking Boids And Emergent Complexity

While out on a stroll with a good friend, she mentioned a screensaver she had seen that simulated a flock of birds. It made me think of the boids algorithm, and the natural and mesmerizing flocking phenomena called murmuration. I couldn’t help but think about it for the rest of the day. So, I decided to try to implement a boids simulation in webgl so that I could stop thinking about it. Its easier to express myself in code than in words, so I figured I’d just write a blog post about it.

Mesmerizing Patterns : A Brief History

The Boid Algorithm was created by Craig Reynolds in 1986, the term “boid” stands for “bird-oid object”. I always think of a new yorker saying “bird” when I see the word “boid” and I prefer to pronounce it that way 💜. I think the only better option would be “birb”. The algorithm is a simple yet elegant model for simulating the coordinated motion of a flock of birds. However, its applications extend beyond bird flocking patterns, encompassing schools of fish, human crowds, and others!

Craig Reynolds introduced boids in the 1980s as a computer model for simulating the coordinated motion of flocks. Rather than controlling the entire flock’s movement, Reynolds’s model focused on the individual, allowing complex patterns to emerge naturally from the interaction of simpler agents following basic rules.

The Essence of a Birb (Boid)

Each boid has a tiny brain, that maintains a state that includes its position, velocity, and acceleration. Based on this state and the state of its nearby neighbors (which is controlled by a perception distance), every boid makes decisions on where to move next. These decisions arise from three simple rules: cohesion, alignment, and separation.

Diving Deeper into the Flocking Rules

1. Cohesion

Cohesion is the behavior that encourages boids to steer towards the average position of their local flockmates. This causes them to form groups and stay together.

Pseudocode for Cohesion:

function cohesion(boid, boids):
    perception_radius = SOME_DISTANCE_VALUE // :) Usually larger than separation
    steering_force = Vector(0,0,0)
    total_in_perception = 0

    for each other_boid in boids:
        if distance(boid.position, other_boid.position) < perception_radius:
            steering_force += other_boid.position
            total_in_perception += 1

    if total_in_perception > 0:
        steering_force = steering_force / total_in_perception  // average position
        steering_force = steering_force - boid.position  // direction towards average position

    return steering_force
end function

2. Alignment

Alignment makes a boid steer in the direction that matches the average heading of its local flockmates. This creates a uniform direction for a group of boids.

Pseudocode for Alignment:

function alignment(boid, boids):
    perception_radius = SOME_DISTANCE_VALUE // :) Usually larger than cohesion
    average_velocity = Vector(0,0,0)
    total_in_perception = 0

    for each other_boid in boids:
        if distance(boid.position, other_boid.position) < perception_radius:
            average_velocity += other_boid.velocity
            total_in_perception += 1

    if total_in_perception > 0:
        average_velocity = average_velocity / total_in_perception  // average velocity
        average_velocity = average_velocity.normalized()  // desired direction

    return average_velocity - boid.velocity  // the steering force to align with others
end function

3. Separation

Separation ensures that boids don’t get too close to one another. It calculates a force that steers each boid away from its close neighbors.

Pseudocode for Separation:

def separation(current_boid, all_boids):
    perception_radius = SOME_DISTANCE_VALUE

    steering_force = Vector(0,0,0)

    total_in_perception = 0

    for other_boid in all_boids:
        distance_to_other = distance(current_boid.position, other_boid.position)

        if 0 < distance_to_other < perception_radius:
            # Calculate the difference vector pointing from
            # the other boid to this current_boid
            difference = current_boid.position - other_boid.position

            # Normalize the difference vector by the distance,
            # so that farther boids have less influence
            difference = difference / distance_to_other

            # Add the difference vector to the steering force of
            steering_force += difference

            total_in_perception += 1

    # If there were any boids within the perception radius
    if total_in_perception > 0:
        # Average the steering force by the number of boids within the perception radius
        steering_force = steering_force / total_in_perception

    # Return the steering force, which will be used to update the current_boid's velocity
    return steering_force

The example separation function above calculates the steering force for a single boid, current_boid, based on its interactions with all other boids in the simulation, all_boids. The function begins by setting a perception radius, which is the distance within which other boids will influence the current boid’s behavior.

If there were any boids within the perception radius, the steering force is averaged by the number of these boids. If there were no boids within the perception radius, the steering force remains zero, meaning the current boid’s velocity will not be adjusted based on separation behavior.

Finally, the function returns the steering force. This steering force is then added to the current boid’s velocity, influencing its direction and speed in the next time step of the simulation.

Wrapping Up

By combining the forces from these three rules, each boid determines its movement direction in the flock. This elegant trio of rules gives rise to the intricate and lifelike patterns that we witness when running a boid simulation. The magic is in the simplicity: while each individual follows basic logic, the collective exhibits complex, emergent behavior that mirrors natural phenomena. It’s beautiful, even in WebGL.

I’ve create an implementation on glitch that you can fork and modify, or just play with. I’ve also embedded it below.