Flocks, Herds, and Schools

Reference: Craig W. Reynolds, "Flocks, Herds, and Schools: A Distributed Behavior Model", Computer Graphics 21:4, pp. 25-34, (SIGGRAPH 87).

Definitions:

A flock consists of a group of discrete objects (boids) moving in a visually complex fashion. There appears to be some central control, but evidence indicates that the motion is just the aggregate result of individual object motions.

Problem: How do we simulate the motions of a flock in computer animation?

Possible solutions: keyframe or script each individual object path. But this would be very tedious and error prone. Also, it would be almost impossible to do without collisions.

This paper discusses another approach. It assumes the flock is the result of interactions between the behaviors of different boids. So, we must simulate the behavior of an individual boid (the flock associated behavior). This requires also simulating perceptual mechanisms and some aspects of aerodynamic flight. If this is done correctly, then to create a flock we just create multiple instances of the boids.

Flocks are a generalization of particle systems, which are used to simulate dynamic fuzzy objects, such as fire, clouds, etc. In a flock, the particles (which are dot-like, e.g., maybe small spheres) are replaced by full geometric entities with an orientation. The behavior of boid particles is more complex, plus they interact with each other whereas simple particles don't.

Each boid has an internal state and a set of behaviors. It is easiest to encapsulate these into an object, in the sense of object oriented programming. Then each new boid is an instance. The author read the literature of the behavior of flocks, etc., and determined certain behaviors that were used in the simulation. The behaviors were expressed in rules of descending precedence:

  1. Collision avoidance: avoid collisions with neighbors or obstacles
  2. Velocity Matching: attempt to match velocity (speed and direction) with neighbors
  3. Flock centering: attempt to stay close to neighbors

If a boid does velocity matching with its neighbors, then it will probably avoid collisions. So static collision avoidance tends to establish minimum distances between boids and velocity matching tends to maintain it.

Flock centering means moving to the center of the nearby neighbors, i.e., it is a localized model, not global. If a boid is close to the center of the flock this will have little effect (since the boid density will be uniform), but if it is on the edges then it will have a greater effect. Since each boid is looking primarily at its neighbors, the flock can split to go around an obstacle. That is, if a large part of the flock splits off, most of the boids in the two flocks are unperturbed since their surroundings remain homogeneous. This is actually a better model of herds or schools of fish, who have a limited vision of the entire school or herd, since it assumes that the boids can only detect other boids a limited distance away.

Each of the three behavioral urges is expressed as an acceleration request or vector. The requests are weighted according to priority and then averaged to give a final acceleration vector. There are potential problems in critical situations. For example, if a wall were directly ahead and the requests were in opposite and therefore canceling directions, the boid might make only a small turn and would hit the wall.

This paper uses a priority ordering and each request is placed into an accumulator, weighted with its priority. This continues until the maximum acceleration is reached and then no more requests are taken. For example, flock centering could be ignored if there were a strong collision avoidance request.

Simulated Perception

In this model, the boids do not take into account all of the other boids but only their neighbors. This corresponds to a limited perception of the outside world. This is actually more accurate than assuming total perception. For herds and schools of fish, especially in murky waters, there is a limited perceptual range. Even for birds, some of the birds will be occluded by others. An earlier model used a central force for the flock centering. This resulted in the entire flock trying to converge on one spot. These simulations showed that the real world flocking behavior actually depended upon a limited perception.

The sensitivity of a boid to its neighbors is governed by two parameters: it is only sensitive to neighbors within a sphere of a certain radius (centered on the boid itself), and the degree of sensitivity is an inverse exponential of distance, so it is dependent upon the value of the exponent. An improved model would increase the sensitivity in the forward direction, and by an amount proportional to the boids speed. In the current model, boids in the front are overly distracted by boids behind them.

The magnitude of attraction or repulsion was found to be best weighted by an inverse square relationship (similar to gravity). This gave a more realistic behavior than a linear relationship, i.e., the boids are much more influenced by close neighbors. Fish sense their neighbors both visually, which tends to be an inverse square relationship, and by pressure waves, which is an inverse cube of the distance, so their behavior would be a combination of the two.

Global Direction

In computer animation we frequently want to be able to control the flock's general direction, i.e., we might want the flock to enter the scene from the left, circle once, and then exit right. We can do this by establishing a global direction for each frame. This global direction vector would be added into the acceleration vector accumulator. We might just add it in to the front boids, who would then be followed by the rest of the flock.

Avoiding Environmental Obstacles

Boids in an empty environment quickly settle down to a steady state, i.e. all at a close distance and with matched velocities. Introducing environmental obstacles makes the motion much more complex. The author found that a "steer-to-avoid" model worked best. In this model, a boid is only affected by objects directly in front of it. Once it detects an object, it finds the silhouette edge closest to its intersection point. It then computes a vector that will aim it at a point one body length away from the edge. The actual obstacles encountered in an animation might be very complex geometric entities, e.g., a tree, bridge, etc., so the author takes the approach of independently modeling the "shape for rendering" and the "shape for collision avoidance." So a complex entity might be represented as a simple shape for collision avoidance. At the time of this paper, the author had developed algorithms to handle spheres, cylinders, planes, and boxes, and was working on convex polyhedral obstacles.

The obstacles do not have to be static, they might be other moving entities, e.g. a herd of elephants. They could also be predators, which would necessitate the addition of a higher priority avoidance algorithm.

Algorithm analysis

This is an O(N^2) algorithm, since the boids must consider all the others to determine if they are close or not. This is not realistic since schools of fish seventeen miles long have been observed, as well as huge flocks of birds, and a century ago, huge herds of buffalo. So in real life there must be a limit, or a constant time algorithm. The author was investigating different ways to achieve this.

Future Work

One aspect of boid behavior not considered in this paper is drafting, i.e., one boid following another boid to lessen wind resistance. In real life, birds draft behind each other, just as bicyclists do in a race. Birds that are in front, or on the outside, eventually move to the rear, or the inside, of the flock so that the wind-breaking is shared equally. This leads to an oval shaped flock (or bicycle pack).

Craig Reynolds has a Java applet demonstrating the algorithm and information about boids and other related subjects on his home page.

Here is an animation that was shown at the SIGGRAPH 97 course on Artificial Life.


Main Artificial Life Page
HyperGraph Home page.

Last changed February 16, 1999, G. Scott Owen, owen@siggraph.org