One of the most beautiful examples of emergence in nature is the graceful but disciplined flocking of birds. This behavior can be simulated in an artificial life system. Boids (online implementation), short for bird-oids, simulates flocking, schooling, and herding behaviors in birds, fish, and other animals. This distributed behavior program was independently discovered by Aoki , for the purposes of investigating fish schooling for fishing, and Reynolds , with the intent to use it for procedural animation. These models stand out because of the distributed computation of the agents, unlike similar previous models such as Amkraut’s force-based one .
Rules
Each boid in the simulation is an agent with a direction and velocity. Each agent has procedures that calculate its acceleration based on the following three influences:
- Avoidance: steer away from boids and static objects within an avoidance radius
- Velocity matching: steer in the direction that nearby boids are travelling
- Cohesion: steer towards the centroid of boids within a cohesion radius .
Boids only have a small radius in which they can perceive other boids; they can only process a few individual neighbor boids instead of the whole flock, and they cannot communicate directly. Despite these limitations, believable and biologically plausible flocking behaviour emerges. For example, flocks of boids can split apart to avoid obstacles and remain at a constant density regardless of the number of agents . Additionally, all of these rules are necessary to enforce the non-colliding movement and whole-flock unified, directed motion exhibited in real life .
Implementation
The steering of boids can be implemented in several ways. Aoki implemented a stochastic probability function for direction based on the headings of nearby boids. Reynolds gave different priorities to each steering rule based on the contextual urgentness, and applied the acceleration from the most important rules first. This allows flocks to split apart from static obstacles in realistic, intelligent ways. For large numbers of boids, a spatial partitioning data structure helps reduce the time complexity .
Applications
The simplicity of the boids system has allowed it to be extended in several interesting ways. To have more control over the flock, such as for animation, a fourth rule can be added that influences the boids to navigate to a specific point , a technique that has been used in films like Batman Returns . To allow the flock to split up, another rule can influence boids to occasionally take over as leader and diverge from the flock . Researchers have simulated more complex fish agents whose navigation, still adhering to the rules above, is learned through practice and simulated muscular locomotion . Boids continues to be an influential, foundational, and visually striking artificial life program to the present day.