Boids
Background and Update
by Craig Reynolds

[You need to be using an Java-enabled browser to see this demo.]
(more information about this applet (and others) is available)

In 1986 I made a computer model of coordinated animal motion such as bird flocks and fish schools. It was based on three dimensional computational geometry of the sort normally used in computer animation or computer aided design. I called the generic simulated flocking creatures boids. The basic flocking model consists of three simple steering behaviors which describe how an individual boid maneuvers based on the positions and velocities its nearby flockmates:

separation diagram
Separation: steer to avoid crowding local flockmates
alignment diagram
Alignment: steer towards the average heading of local flockmates
cohesion diagram
Cohesion: steer to move toward the average position of local flockmates

Each boid has direct access to the whole scene's geometric description, but flocking requires that it reacts only to flockmates within a certain small neighborhood around itself. The neighborhood is characterized by a distance (measured from the center of the boid) and an angle, measured from the boid's direction of flight. Flockmates outside this local neighborhood are ignored. The neighborhood could be considered a model of limited perception (as by fish in murky water) but it is probably more correct to think of it as defining the region in which flockmates influence a boids steering.

neighborhood diagram
a boid's neighborhood

A slightly more elaborate behavioral model was used in the early experiments. It included predictive obstacle avoidance and goal seeking. Obstacle avoidance allowed the boids to fly through simulated environments while dodging static objects. For applications in computer animation, a low priority goal seeking behavior caused the flock to follow a scripted path.

simulated boid flock avoiding obstacles (1986)
simulated boid flock avoiding cylindrical obstacles (1986)
(early motion tests, 20 second clip, QuickTime, 10 MB)

In cooperation with many coworkers at the Symbolics Graphics Division and Whitney / Demos Productions, we made an animated short featuring the boids model called Stanley and Stella in: Breaking the Ice. This film was first shown at the Electronic Theater at SIGGRAPH '87. There was a technical paper on boids published at the same conference. In the course notes for SIGGRAPH '88 there was an informal paper about obstacle avoidance.

Since 1987 there have been many other applications of the boids model in the realm of behavioral animation. The 1992 Tim Burton film Batman Returns was the first. It contained computer simulated bat swarms and penguin flocks which were created with modified versions of the original boids software developed at Symbolics. Andy Kopra (then at VIFX, which later merged with Rhythm & Hues) produced realistic imagery of bat swarms. Andrea Losch (then at Boss Films) and Paul Ashdown created animation of an "army" of penguins marching through the streets of Gotham City.

scene from Breaking the Ice (1987): flock of boids
from  Stanley and Stella in: Breaking the Ice  (1987)
(40 second clip, QuickTime, 2.8 MB)

As luck would have it, Chris Langton organized the original ground-breaking Artificial Life Workshop a few months after the boids paper was published in 1987. A helpful go-between got word to Chris and he let me give an informal presentation on boids at the Workshop. The boids model has become an oft-cited example of principles of Artificial Life. Flocking is a particularly evocative example of emergence: where complex global behavior can arise from the interaction of simple local rules.

In the boids model (and related systems like the multi-agent steering behavior demos) interaction between simple behaviors of individuals produce complex yet organized group behavior. The component behaviors are inherently nonlinear, so mixing them gives the emergent group dynamics a chaotic aspect. At the same time, the negative feedback provided by the behavioral controllers tends to keep the group dynamics ordered. The result is life-like group behavior.

A significant property of life-like behavior is unpredictability over moderate time scales. For example at one moment, the boids in the applet above might be flying primarily from left to right. It would be all but impossible to predict which direction they will be moving (say) five minutes later. At very short time scales the motion is quite predictable: one second from now a boid will be traveling in approximately the same direction. This property is unique to complex systems and contrasts with both chaotic behavior (which has neither short nor long term predictability) and ordered (static or periodic) behavior. This fits with Langton's 1990 observation that life-like phenomena exist poised at the edge of chaos.

The boids model is an example of an individual-based model, a class of simulation used to capture the global behavior of a large number of interacting autonomous agents. Individual-based models are being used in biology, ecology, economics and other fields of study.

Note that the straightforward implementation of the boids algorithm has an asymptotic complexity of O(n2). Each boid needs to consider each other boid, if only to determine if it is not a nearby flockmate. However it is possible to reduce this cost down to nearly O(n) by the use of a suitable spatial data structure which allows the boids to be kept sorted by their location. Finding the nearby flockmates of a given boid then requires examining only the portion of the flock which is within the general vicinity. Using such algorithmic speed-ups and modern fast hardware, large flocks can be simulated in real time, allowing for interactive applications. [new]

Online resources related to boids

Other computational models of group motion

Natural flocks, herds, and schools

Software

(There is additional source code for Java implementations listed on the boids applet page.)
Boids
This is the original 1986-1988 implementation, written in Symbolics Common Lisp, and based on Symbolics' S-Geometry 3d modeling system and S-Dynamics animation system. (Modern versions of those applications are available from Winged Edge Technologies, see: Mirai Modeling and Mirai Animation. Your browser may not recognize this file as Lisp source code and try to reformat it as filled text. If so use [View / Page Source] or equivalent, or download the file.)
C++ Boids
This platform-independent boids implementation by Christopher Kline includes C++ source code and an Inventor-based binary executable demo for SGI machines. These boids support both flocking and obstacle avoidance.
Buzzz!
An After Dark screen saver module for Macintosh computers by Simon Fraser. This very nice package implements a parameterized version of boids including several species of creatures (wasps, birds, fish, sheep...) based on altering the parameters. There are control panels that allow you to experiment with the parameters. For other sources of this software see Simon's AD page.
boids.exe
by Jürgen Schmitz. Version 1.0 of a Windows application featuring three distinct species of flocking birds and nice control panels for adjusting their parameters. See the readme file for more information.
SchoolView
This is a screen saver for NeXT computers by David Lambert based on the boids model. C code and related files are available for FTP. See the readme file for details.
A-Quarium
A screen saver for Windows by Ric Colasanti. A-Quarium is a fish tank simulator somewhat related to boids. "...a fish will try to swim with a close neighbour if it is of the same species, and will try to swim away if it is of a different species. The behaviour of the fish tank is an emergent property of all the individual fish actions..."
Max Boids
There is an implementation of boids for MAX, an interactive real-time graphic programming environment, from IRCAM and Opcode.
Boppers
This Windows 3.1 software originally accompanied the book Artificial Life Lab by Rudy Rucker, Waite Group Press, 1993, now out of print. It includes an implementation of boids and related ALife models.
Imagine Flock 3D
A commercial "IPAS plug-in" for 3D Studio from CBL Technology.
Stone's Mac Boids
This is an application for a PowerPC Macintosh using QD3D. Other versions exist for 68000 Macs with FPU, and as After Dark modules. See the main page by Stone (Ishihama Yoshiaki) for other alife-related Mac and Java software.
MatFa's Boids 0.1
Mattias Fagerlund wrote this very nice 2D implementation of boids for Windows 95 or WindowsNT and provides both executable and source code. A screen shot on the web page shows the interactive slider controls and a large flock flying around several obstacles.
Boids: DirectX Flocking Sample
A boids implementation by Stephen Coy has been included in the DirectX sample code since version 5. Stephen suggests that better source code is included with DMBoids the DirectMusic demo based on boids.
Boids for Apprentice
A boids demo based on Christopher Kline's implementation (see above) is included in Eric Powers's OpenGL/OpenInventor tool called Apprentice which is free for non-commercial, educational use.
Cool School
By David S. Hooper, Cool School simulates a school of fish and predators using behavioral modeling. The O(n2) cost of the naive boids algorithm is reduced by by subdividing the population into a hierarchy of "subschools". He reports running at interactive rates with 32 subschools each containing 33 fish on a 200MHz Pentium-class machine. Cool School was developed as part of the Virtual Whale project mentioned above.
Simulation of a Flock of Birds
A 1997 class project at Stanford by Chris Quartetti and Eng-Shien Wu, includes a movie file showing flocking and collision avoidance, and C++ source code.
Boids Demos in VRML, Java3D, and C
Anthony Steed (of University College London) developed the first two implementations to compare VRML and Java3D, and the third to test the DIVE multi-user VR system. Source is includes for all three.
Flock This!
A commercial plug-in from Northern Lights Productions for the Electric Image animation system, creates herds and flocks of animated characters. [new]
Gnat Cloud and Mega Flies
Keith Wiley created these Mac applications to simulate extremely large swarm-like populations, using modifications of the basic boid algorithms. See also his Flock With Obstacles applet. [new]
vbBoid
Richard Lowe wrote this boids implementation in Visual Basic and provided the source code at PlanetSourceCode's VB repository. (I have not seen it run but:) It apparently provides for interactive specification of obstacles. [new]
3D Boids
Robert Platt wrote a boids implementation as a Windows application for a Final Year Project in college. The original version used Direct3D and he later rewrote it to use OpenGL. Binaries and source are available for download from his page. [new]
The Birds
Olcay Cirit wrote this 2d shooter game based on boids. It runs under Windows 95, 98, and NT and is available for free download. You can shot at the flocking birds, but watch out, because they can shoot back! And since they are a flock, they can make coordinated group attacks. [new]
Crowd simulation
Bill Powers developed these models of "people moving in relation to other people and things" as part of a suite of (Windows PC based) demonstrations of his Perceptual Control Theory. Powers and his colleagues in the Control Systems Group seek to model and understanding the purposeful behavior of living organisms. [new]
Creature Behaviour Simulator
James Greenbank wrote this ecological simulation of a three species system using individual-based local rules. It is written as a Java application. This page contains links to a paper, the source code and both platform-independent and Windows-specific executables. [new]
CM: Flocking Model
a StarLogoT implementation of flocking from Connected Mathematics ("Making Sense of Complex Phenomena Through Building Object-Based Parallel Models.") Includes links to a movie of the simulation and a page of background. [new]
flock v1.0
John Kundert-Gibbs wrote this flocking plug-in for Maya in its scripting language MEL. It is available at the HIGHEND3D repository. [new]
Greg's boids
Greg Johnson wrote this boids code to use with the Persistence of Vision Raytracer, the page contains links to the code, a movie, and some diagrams of the steering force vectors used in the boids model. [new]

Lexicological note: in addition to common terms like flock, herd, and school, English has a rich history of specific words to describe groups of various animals, sometimes known as collective nouns or venereal terms. These words were used more frequently when hunting wild animals was a major source of food. For an amusing discussion of these words see the book An Exaltation of Larks by James Lipton (Viking Penguin, 1993, ISBN 0140170960). Here are some web pages that provide similar information:

Send comments to Craig Reynolds <cwr@red3d.com>
visitors since June 29, 1995
Last update: September 6, 2001
(fixed the "early motion tests" link December 6, 2006)
(fixed links to Brian J. Mork's work July 30, 2007)