artificial life
Chapter 3: Cellular Automata
3.7 Flocking
A graphical artist, Craig Reynolds, took the “bottom-up” method of programming Cellular Automata to create a system that mimicked a natural phenomena that is easily recognizable at a glance, flocking. People had already tried to model flocking, using techniques such as “follow the leader” or just brute force choreography, but none were very successful in giving visually believable results.
Reynolds observed that one single bird does not lead the birds; rather the motion of the flock is a result of the independent decisions of each individual bird. Reynolds guessed at the criteria used by a bird during flight and applied those criteria to create a model.
The model Reynolds used for flight is incredibly simple. After each frame the bird-oid (“boid”) re-orients itself using some given rules and moves forward along its local z-axis by a distance proportional to its speed. The bird accelerates slightly if pitched forward (pointed down) and decelerates if pitched back.
The most important part of the simulation is the set of rules that determine how the bird reacts to other birds.
1. Obstacle Avoidance: the bird doesn't want to crash into any trees, bridges, trucks or arbitrarily placed floating spheres. If a bird is headed towards an object, it should steer to avoid it.
2. Avoid other birds: Although the bird wants to stay with the flock, it doesn't want to actually crash into one of its neighbors. If a bird is going to crash into another bird, it should steer to avoid it also.
3. Velocity Matching: The bird desires to stay with its group; it provides a number of advantages. It's easier to find a mate, it provides protection from predators, and there are more eyes searching the ground below for the next meal. Velocity indicates both speed and direction.
4. Flock Centering: If the flock is attacked by a predator the individuals on the outside are at a disadvantage, so each bird attempts to fly towards the center of the group. It's also less likely that a bird is left behind if they're in the center of the flock.
5. Migratory Interests: The birds do have an ultimate destination in mind, so if there are no other pressing issues they tend towards that direction.
These rules are listed by priority, if a bird must choose between avoiding a bridge and flying towards its ultimate destination it is better that the bird worry about avoiding the bridge first [Reynolds, 1987]
As with the cells in regular cellular automata these birds cannot see their entire environment, they each have a radius of sight and must determine their path based upon the obstacles they can see within that radius of sight.
Reynolds was very pleased with the results of his model. The model yielded a flock that moved with convincing complexity, far more believable than the choreographed work done before this time. The simulation was so good that it has been used in feature films such as Batman Returns, Cliffhanger, The Lion King and countless others.