Conrad Parker

Boids

I have been interested in the field known as Artificial Life for a number of years. One of the most beautiful findings of this field is a very simple algorithm known as boids, which models flocking behaviour in nature. This algorithm was invented by computer animator Craig Reynolds.

In 1996 I wrote an example of this algorithm as a Java applet, which continues to be quite popular.

In July 1998, this appeared as a video projection in Preston Foerder's theater piece Interesting Times, commissioned by the Contemporary American Theater Festival.
In late 2001 it was exhibited at the Festival Internacional de Linguagem Eletrônica (FILE-2001) at the Museum of Image and Sound in Sao Paulo and in Curitiba city, Brazil.
In May 2005, O'Reilly published Killer Game Programming in Java by Andrew Davison. A sample chapter Flocking Boids [PDF] is available online, and references these pages. It adds some interesting predator/prey behaviour and obstacle avoidance.

The algorithm models the behaviour of flocking animals (eg. birds) by simple rules which describe only the behaviour of individuals. For a full explanation and an informative history of this algorithm see Craig Reynolds' boids page.

Briefly, the rules are:

Boids try to fly towards the centre of mass of neighbouring boids.
Boids try to keep a small distance away from other objects (including other boids).
Boids try to match velocity with near boids.

If you would like to learn more about how these rules are implemented, I have written a programming explanation with accompanying pseudocode.

Here is my Java based example of the model:

Boids background image: Java is required to view boids in their natural
environment.

A nicely laid out version of this is here , and for your viewing pleasure, a larger version is also available. Oh, and now one set at Coogee Beach.

xboids

I have released C source for this program under the GNU General Public License (GNU GPL). This code works exactly as the applet does, and under the X Window System:

download

Download the Java classes

You can also download the Java classes and a sample html file: Boids.tar.gz or Boids.zip

Other implementations

Todd Warner has made an implementation in Python based on the above pseudocode. It is available (under the GNU GPL) at http://www.dma.org/~tw/pyboids/.

Jonathon Crane has written a javascript/DHTML version of this, and I've adapted it here with flocking yellow triangles. Jonathon's code implements ants crawling around; you can see and play with at: http://feastofbeats.co.uk/boids/index.html

Jeff Foster implement this flocking behaviour in Clojure. Yay functional programming!

An interesting parallel to this theory is that proposed by Richard Dawkins in The Selfish Gene. His theory, which he describes in the context of accounting for the evolution of pack behaviour, is as follows:

A simple strategy for a predator animal is to chase the closest prey animal in its vicinity. This is reasonable because it expends the least amount of effort for the predator.

Then a strategy for a prey individual is to try to keep as far away from predators as possible: if predators only attack the closest prey individuals, then all the others should be safe. You can consider each prey individual as having a "domain of danger" surrounding it. This is the area around it comprising the points around it to which it is the closest prey. For example, a lone individual would have a "domain of danger" which is a large circle around it, whereas each individual in a pack would have a small "domain of danger" around it. Then the strategy is to reduce the "domain of danger" as much as possible. This is achieved in the pack formation, where all the prey individuals try to stay together, each one of them selfishly trying to reduce its own "domain of danger". However, the individuals on the edges of the pack have a much greater "domain of danger" than those in the interior. Thus, the individuals on the edge of the pack try to move towards the interior of the pack, which moves other individuals to the edges.

This strategy correlates well with the boids rules. Each individual boid tries to move towards the centre of mass of the pack, which very simply implements the reduction of the "domain of danger". Of course, they cannot all move to the very centre: there is a limit to the closeness of individuals, such that they all have enough room to move. This is also implemented as a rule for Boids.