Flocking is a technique for animating groups of creatures, such as flocks of birds, schools of fish, herds of wildebeest, etc.
It is described as a type of artificial life algorithm, or emergent behavior. This means that it uses a set of simple rules to control digital characters, and that the rules lead to more complex behaviors that mimic living things.
Flocking was introduced in 1987 by Craig Reynolds, and used in the classic computer animation "Stanley and Stella: Breaking the Ice". http://www.red3d.com/cwr/boids/ is Reynolds' official web page on flocking.
The generic term boid is often used to refer to artificial creatures that use flocking behavior.
There are three basic rules for flocking behavior.
These rules are applied independently by each boid.
There is no overall, "flock-level" intelligence
guiding them as a group.
Each boid is only aware of the other boids in its immediate vicinity, rather than all boids in the simulated world. The boid applies its rules based on the current positions and velocities of its neighbors.
The rules, in order of precedence, are:
The Separation and Cohesion rules will work together to bring boids into a group, without them all clumping up into the same spot.
The Alignment rule will cause the boids to move as a group.
Separation - keep a certain minimum distance from any neighbors, to avoid colliding |
Alignment - match the direction and speed of neighbors |
Cohesion - move towards the average position of neighbors |
Step 1: Create a class to represent the boids and their motion.
This class has position, velocity, & acceleration vectors, and updates the position and velocity on each frame.
The boid class is primarily going to serve as the intelligence of the creatures. We need to have some way to use the data from this in our 3D scene. I've chosen to make the boid class a type of dms::Object, so that it can be inserted into a libdms scene graph. The class will create & update a transformation, but will have no geometry - the geometry is taken care of by attaching some other object to the boid. This way the intelligence is independent of what the creatures look like.
Step 2: Create a "boid species" class, to store general data about different types of boids, and keep track of all the boids of each type.
The boidSpecies class provides a function to find all the neighbors of a particular boid. It uses the STL vector template for lists of boids.
This program shows the neighbors of one particular boid, by making the neighbor boids larger.
flock1.cpp
boid1.h
boid1.cpp
boidSpecies1.h
boidSpecies1.cpp
Step 3: Apply the flocking rules, as a set of functions in the boid class (called from update()).
One important issue is how to combine the instructions from the different rules. This implementation uses a very simple prioritization scheme. Whichever rule says it has the highest priority is followed.
flock2.cpp
boid2.h
boid2.cpp
boidSpecies2.h
boidSpecies2.cpp