Scene Creation

Chapter 22. Flocking Boids

Flocking is a computer model for the coordinated motion of groups (or flocks) of entities called boids. Flocking represents group movementas seen in bird flocks and fish schoolsas combinations of steering behaviors for individual boids, based on the position and velocities of nearby flockmates. Though individual flocking behaviors (sometimes called rules) are quite simple, they combine to give boids and flocks interesting overall behaviors, which would be complicated to program explicitly.

Flocking is often grouped with Artificial Life algorithms because of its use of emergence: complex global behaviors arise from the interaction of simple local rules. A crucial part of this complexity is its unpredictability over time; a boid flying in a particular direction may do something different a few moments later. Flocking is useful for games where groups of things, such as soldiers, monsters, or crowds move in complex, coordinated ways.

Flocking appears in games such as Unreal (Epic), Half-Life (Sierra), and Enemy Nations (Windward Studios).

Flocking was first proposed by Craig Reynolds in his paper "Flocks, Herd, and Schools: A Distributed Behavioral Model," published in Computer Graphics, 21(4), SIGGRAPH'87, pp. 25-34.

The basic flocking model consists of three simple steering behaviors (or rules):

Separation

Steer to avoid crowding local flockmates.

Alignment

Steer toward the average heading of local flockmates.

Cohesion

Steer to move toward the average position of local flockmates.

These rules are illustrated in Figure 22-1.

Figure 22-1. Reynolds' steering rules

The circles in Figure 22-1 surround the center boid's local flockmates. Any boids beyond a certain distance of the central boid don't figure in the rule-based calculations.

A more elaborate notion of neighborhood only considers flockmates surrounding the boid's current forward direction (see Figure 22-2). The extent of neighborhood is governed by an arc on either side of the forward vector. This reduced space more closely reflects how real-world flock members interact.

Figure 22-2. Boid neighborhood based on distance and angle

Many other rules have been proposed over the years, including ones for obstacle avoidance and goal seeking. Reynold's web site (http://www.red3d.com/cwr/boids/) contains hundreds of links to relevant information, including flocking in games, virtual reality, computer graphics, robotics, art, and artificial life. The plethora of links at Reynold's site can be a tad daunting. A good starting point is Conrad Parker's web page explaining boid algorithms with pseudocode examples (http://www.vergenet.net/~conrad/boids/pseudocode.html). He describes Reynolds' steering rules, and additional techniques for goal setting, speed limiting, keeping the flock inside a bounded volume, perching, and flock scattering. His pseudocode was a major influence on the design of my boids' steering rules.

Two other good starting points are Steven Woodcock's articles "Flocking: A Simple Technique for Simulating Group Behavior" in Game Programming Gems and "Flocking with Teeth: Predators and Prey" in Game Programming Gems II. The first paper describes Reynolds' basic steering rules, and the second introduces predators and prey, and static obstacles. Both articles come with C++ source code.