Flocking (behavior)
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.
Basic flocking is controlled by three simple rules:
- Separation - avoid crowding neighbours
- Alignment - steer towards average heading of neighbours
- 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).
Contents |
[edit] Algorithmical complexity
In flocking simulations, there is no central control; each boid behaves autonomously. The three simple rules described above are applied not to the entire flock, but only to local flockmates; each boid 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(n2) because every boid has to calculate its distance from every other boid 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 boids. Each time a boid moves from one bin to another, it updates its location in this global register.
This decreases the complexity of the flocking algorithm enormously, since boids do not need to check their position against all other boids. They only have to look in the register to see which boids are close enough to possibly be in their local environment.
The complexity of the flocking algorithm is then reduced from O(n2) 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. In their paper Emergence of Collective Behavior in Evolving Populations of Flying Agents they describe such systems in detail.
[edit] Live demo
10 boids, not flocking (live demo in Flash 8)
10 boids, flocking (only alignment rule implemented) (live demo in Flash 8)
[edit] References
- Gabbai, J. M. E. (2005), Complexity and the Aerospace Industry: Understanding Emergence by Relating Structure to Performance using Multi-Agent Systems, Manchester: University of Manchester Doctoral Thesis link
[edit] External links
- Craig Reynolds' Boids page
- 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
