Flocking Boids and Emergent Behavior

In 1986 Craig Reynolds developed a simulation of flocking behavior of creatures that he called boids.  As is typical of good ideas, this one is simple to describe: even when many individuals each behave according to a small set of very simple rules, the resulting collective behavior of the group can be very interesting and complex.  For example, consider a flock of birds, or a school of fish, or an army of orcs (that’s right, orcs), or cars on a freeway.

In the case of boids, Reynolds originally used just three simple rules: separation, alignment, and cohesion.  Separation means don’t run into any other boids.  Alignment means head where everyone else is heading.  And cohesion means stick with the group.  Just these three rules can yield interesting and realistic flocking behavior among a large number of boids that all follow those same rules.

I have VPython to blame for spending enough time on this to warrant posting about the subject.  In the process of experimenting with VPython and putting together a few example programs for students, I wrote the following boids simulation.  It’s a little quick and dirty, but I think it provides pretty convincing evidence for Python’s advertisement as “pseudo-code that runs.”  Cool flocking behavior in less than a page of code.  Each rule determines a small change in velocity of a boid as a function of its neighbors.  Note that I added a fourth rule, bounding, so that the boids tend to stay within a fixed volume of space, so that they don’t fly “off camera.”  Here is the code:

#!/usr/bin/env python

from visual import *
seterr(all='ignore')

num_boids = 30
fps = 24
dt = 1.0 / fps

boids = [arrow(pos=20 * (v - 0.5), axis=norm(v - 0.5))
         for v in random.rand(num_boids,3)]

def separation(boid):
    center = mean([b.pos for b in boids if b != boid and
                   abs(b.pos - boid.pos) < 5], 0)
    if isscalar(center):
        center = boid.pos
    return norm(boid.pos - center) * 0.05

def alignment(boid):
    heading = mean([b.axis for b in boids if b != boid and
                    abs(b.pos - boid.pos) < 10], 0)
    if isscalar(heading):
        heading = boid.axis
    return (norm(heading) - boid.axis) * 0.1

def cohesion(boid):
    center = mean([b.pos for b in boids if b != boid and
                   abs(b.pos - boid.pos) < 10], 0)
    if isscalar(center):
        center = boid.pos
    return norm(center - boid.pos) * 0.01

def bounding(boid):
    if abs(boid.pos) > 30:
        return -norm(boid.pos) * 0.25
    else:
        return vector(0, 0, 0)

rules = [separation, alignment, cohesion, bounding]

while True:
    rate(fps)
    for boid in boids:
        boid.axis = norm(boid.axis + sum([dv(boid) for dv in rules], 0))
        boid.pos = boid.pos + boid.axis * 10 * dt

The filtered list comprehensions and vectorized mathematical operations provided by Numpy (included with VPython) certainly contribute to the readability.

This sort of simulated “emergent” complexity of behavior has several interesting applications.  Hollywood has put it to good use: computer-generated bats and penguins simulated using algorithms similar to boids were first used in the movie Batman Returns.  (Okay, so maybe that’s not very good use.)  And the idea has taken off from there; Massive Software has a pretty cool gallery on their site showing, among other things, the many movies and games where similar technology has been used.

This entry was posted in Uncategorized. Bookmark the permalink.

3 Responses to Flocking Boids and Emergent Behavior

  1. azaroma says:

    Hi, i find very interesting this topic and i think your program is very didactic. I am researching about cellular automata and emergent behavior because i want to follow de AI branch in my college. I pretend to emulate flocking for a project i’m doing but i would like to know if there’s some site where i can find information that helps me understand your code, since it’s not commented i don’t quite comprehend some of the things you’re doing here. Thanks for your example.

    • If you are unfamiliar with Python, then their beginners’ guide is probably a good place to start. Beyond that, the Visual Python site has pretty good documentation on the use of their 3D graphics primitives (the arrow is the only one used here).

      • azaroma says:

        Thank you for your recommendations, i surely am going to check that begginers’ guide. Last night i figured a lot of the code out, at first was overwhelming the amount of different things that can be done in python. In the next days i hope to solve the boids array creation mystery. Again, this is an excellent and simple example, keep up the good work.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s