Subscribe
Subscribe
MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
Logo IMG
HOME > PAST ISSUE > Article Detail

COMPUTING SCIENCE

Flights of Fancy

How birds (and bird-watchers) compute the behavior of a flock on the wing

Brian Hayes

Boidland

In retrospect, neither democracy nor dictatorship was a very good point of reference for understanding bird society. Both theories were swept aside dramatically in the 1980s.

The key insight came not from an ornithologist but from an expert on computer graphics and animation. Craig W. Reynolds, now of Sony Computer Entertainment, wrote a program in which simulated birds—he called them “boids”—gave a convincing imitation of flocking behavior. And the boids did it without any need for leaders or thought transference. Each boid attends to a few near neighbors, ignoring the rest of the flock, and obeys three simple rules:

1. Collision avoidance: Try not to run into neighboring boids.
2. Velocity matching: Try to fly at the same speed and in the same direction as neighboring boids.
3. Cohesion: Try to stay close to neighboring boids.

The rules are to be applied in the order given. That is, collision avoidance gets the highest priority; if no collisions are imminent, then the boid adjusts its speed and direction to match the average of its neighbors’ velocities; if the velocities are already in good agreement, the boid moves a little closer to its flockmates. (Note that the third imperative is in mild conflict with the other two.)

When I first read about the boid model, I was astonished that it worked. A stable state in which all the boids fly on parallel trajectories seemed like a possible outcome of the rules, but just barely so. A far more likely result, I thought, was a fragmented collection of many small flocks, each roughly the size of a boid neighborhood.

I changed my mind when I saw the boids in action and got a chance to play with implementations of the model. The flocking of boids is not a perfect simulation of bird behavior, but the resemblance is unmistakable. And the flocks are not only stable but robust. If you start the simulation with boids moving randomly, they spontaneously assemble into a flock. If an obstacle causes the flock to split, the factions eventually rejoin.

What accounts for the balletic coordination of a boid flock? Although a boid interacts directly only with its immediate neighbors, those neighbors interact with their own neighbors, and thus a network of indirect connections binds the whole flock together. The surprise is that these tenuous links are enough to do the job. When a boid at the north end of the flock starts turning, a boid at the south end gets the signal only through several intermediaries. Admittedly, many such chains of intermediaries connect the two boids. Even so, it’s unexpected that distant events can exert such a powerful influence. It’s almost like thought-transference.








comments powered by Disqus
 

EMAIL TO A FRIEND :

Subscribe to American Scientist