Boids: Simulating large flocks

ORIGINAL: DeCarpentier

April 20, 2011

Boids are bird-like virtual robots capable of flying together in flocks. Inspired by the paper “Flocks, Herds, and Schools: A Distributed Behavioral Model” by Craig Reynolds, I implemented a fast boid simulator in 2006, simulating and rendering more than a thousand boids at real-time frame rates.

Boid interaction

Each boid's behaviour is governed by simple local rules. These are local in the sense that they control the speed and direction of each boid solely based on other boids in their local vicinity, without the help of some central leader or control system. The rules basically work together to get the boid to mimic the velocity and direction of nearby boids, while flying away from boids or other blocking objects that are too close by. In this implementation, each rule simply adds its own 3D acceleration vector as its desire to steer towards to or away from an influence. The following accelerations are calculated and summed for a number of closeby boids:

acc_avoid_boid = -direction_towards_boid / boid_distance

acc_prefer_boid_distance = direction_towards_boid * (1 – preferred_distance / boid_distance)

acc_match_boid_velocity = (other_boid_velocity – own_velocity) / sqrt(boid_distance)

A weighed average of these three acceleration is used to update the current velocity of each boid per frame. Varying the weights and the preferred_distance results in different tradeoffs between conflicting desires and thus different behaviour. Also note that weights for vertical components of any acceleration can be tweaked differently from their horizontal components to describe a preference for more horizontal or vertical flock.

These accelerations somewhat differ from the usual boid implementation. For example, acc_avoid_boidand acc_prefer_boid_distance both prefer to fly away from other boids that are too close. However, acc_avoid_boid is meant and tweaked to prevent accidental collisions, while the less weightyacc_prefer_boid_distance moves the boid to an ideal distance from other boids in a slower, more gentle way.

Furthermore, the acc_match_boid_velocity acceleration also contains an unusual relation to distance. This relation helps to prevent the closest boids to steer into each other, decreasing the chances accidental collisions will happen. Less obvious is the fact that it also helps to prevent recurrent oscillations in flock density and size. This is the result of the formula’s non-linearity and asymmetry, causing any oscillatory spring-like energy to dissipate quickly.

In a typical boid implementation, the rules (and their resulting accelerations) are applied for the N closest boids, N being a small fixed number typically between 3 and 10. In contrast, this simulation applies them for the closest and second closest boid, and for the closest boid farther away than the distance of the (first) closest boid times x, x being a tweakable parameter typically between 2.0 and 10.0. By considering the behaviour of this relatively distant third boid, seperate flocks are more likely to merge, creating larger and more stable flocks.

Other influences

In addition to the boid - boid interactions, Other influences

other influences are easily incorporated as additional accelerations:

acc_avoid_object = -direction_towards_object / object_distance

acc_avoid_predator = -direction_towards_predator / predator_distance

acc_prefer_horizontal_flight = -vertical_velocity

acc_prefer_height = [0 1 0] * (preferred_height - current_height)

Again, these accelerations can be weighed and added to the final acceleration.

Updating positions

The final acceleration is split into the three local axes: forward, sideward and upward. Each component is then clamped to its own specific range, which can be different in each of the three direction as can be expected for any non-omnidirectionally configured creature.

The clamped acceleration is integrated using simple forward Euler integration into the velocity vector. To support fast turning of the boids but prevent too sudden changes in speed, the new speed is smoothed by mixing in the speed from the previous frame, without affecting the new direction. Furthermore, the new velocity is scaled depending on its vertical component, simulating the approximate effect of gravity. Consequently, a boid will simply accelerate when doing down, and decelerate when going up. Lastly, the new velocity is clamped to a predefined range. The clamped velocity is then integrated into the new position.

Simulator details

The boid animation is driven by the current turning speed and vertical velocity, influencing the flapping frequency and tail direction. Updating the boid position and velocity, progressing the animation, and rendering the models is done every frame. But for efficiency reasons, each boid is only allowed to update its AI accelerations 10 times per second. This amortizes the cost of the boid AI over multiple frames while rendering smoothly animated models at higher rates.

To add variety to the flocks, three different types of boids are available in the simulator: sparrow-like boids (in green), gull-like boids (in red), and predator-like boids (in yellow). The sparrows manoeuvre quickly and prefer to stay very close to each other. The gulls fly more elegantly and more synchronized. The predators stalk nearby sparrows and gulls, dispersing their flocks. Together, the variety between species and their interactions result in mesmerizing flocks of ever changing sizes and formations. For further details, see the freely available source code for Windows, distributed under the GPL license.

Downloads

Boids application for Windows.

GPL-licensed C++ Boids source code for Windows