From Wikipedia, the free encyclopedia

Flocking is a common demonstration of emergence and emergent behavior, first simulated in 1986 by Craig Reynolds with his simulation program, Boids. It is a simulation of simple agents which are allowed to move, with basic rules governing their movement. The result is alike to a flock of birds, a school of fish, or a swarm of insects.

Two flocks of Common Cranes

Basic flocking is controlled by three simple rules:

1. Separation - avoid crowding neighbours
2. Alignment - steer towards average heading of neighbours
3. Cohesion - steer towards average position of neighbours

With these three simple rules, the flock moves in an extremely realistic way, creating complex motion and interaction that would be extremely hard to create otherwise.

Flocking is a common technology in screensavers, and has found its use in animation. Flocking has been used in many films (Gabbai 2005) to generate crowds which move more realistically. Tim Burton's Batman Returns (1992) featured flocking penguins, and Disney's The Lion King (1994) included a wildebeest stampede.

From a practical perspective, flocking has been considered as a means to control the behavior of Unmanned Air Vehicles (UAVs) (Gabbai 2005).

In flocking simulations, there is no central control; each bird behaves autonomously. The three simple rules described above are applied not to the entire flock, but only to local flockmates; each bird has to decide for itself which flocks fall into its environment (typically defined as a circle (in 2D flocks) or orb (in 3D flocks) with a certain radius).

A basic implementation of a flocking algorithm therefore has complexity O(n²) because every bird has to calculate its distance from every other bird in the entire flock in order to decide whether or not it falls into its environment.

An accepted solution to this complexity problem is bin-lattice spatial subdivision. By using this technique the entire area the flock can move in is divided into a large number of bins. This would be a 2D grid in a 2D flocking simulation, or a 3D grid in a 3D flocking simulation. In the simulation, there is a global register which stores which bins contain which bird. Each time a bird moves from one bin to another, it updates its location in this global register.

This decreases the complexity of the flocking algorithm enormously, since bird do not need to check their position against all other birds. They only have to look in the register to see which birds are close enough to possibly be in their local environment.

The complexity of the flocking algorithm is then reduced from O(n²) to O(n * k), which resolves into O(n) when k is a constant.

Lee Spector, Jon Klein, Chris Perry and Mark Feinstein studied the emergence of collective behavior in evolutionary computation systems.^[1]

• Craig Reynolds' Boids page
• Iztok Lebar Bajec's fuzzy logic based flocking publications
• Flocking Simulator - A flocking behavior simulator in Java. Run online or free download. Includes multiple flocks, predators, obstacles and food.
• NetLogo, a free software for multi-agent modeling, simulation, and the like, including a flocking simulation.
• VisualBots - Freeware multi-agent simulator in Microsoft Excel - Visual Basic syntax
• 3D Java Boids demonstrating bird flocking (Paul Richmond)