Have an Android phone?

Try our new game!

flock

Flocking behavior was first simulated on a computer by computer animator Craig Reynolds[1]. Reynold simulated the flight of fictional creatures (called boids) that move according to a set of basic rules[2]. The result is akin to a flock of birds, a swarm of insects or a school of fish.

Boids. Hold left mouse button to scare the flock, right button to make boids uncooperative

Reynold algorithms, described in [3], demonstrate a possibility of the coordinated behaviour (flocking) without having any leader (all boids run the same algorithm inside). The basic rules that make boids to fly in a flock are:

  • Boids try to fly towards the centre of mass of neighbouring boids (boid does not count its own mass when computing this centre). This center is easy to compute just by averaging x, y and z coordinates of all boids involved:

The formula above states that the acceleration of the boid b (as vector) is proportional (not equal to, also depends on other factors) to the difference between boid location and mass centre location, and directed so that the boid accelerates towards the centre. It works in both 2D and 3D worlds. The mass centre rule can be easily converted into the rule to scatter the existing flock. For that, the computed velocity vector just needs to be inverted.

  • Boids try to keep some distance from the other boids. This is necessary as otherwise the first rule forces boids to collapse into single point.

This formula states that once the distance between the boid b and some other boid (boid k) is less than the critical distance Rcrit, the boid accelerates away (hence minus sign) from that another boid. The similar rule can prevent boids from bouncing into walls and other objects.

  • Boids try to match velocity with near boids. This is also very easy to compute just by averaging x, y and z speed components of all boids involved.

This formula is really an interesting notice: where one would expect complex vector arithmetic (to compute both direction and magnitude of the acceleration vector), as trivial averaging of the speed vectors of other boids can do the job even without involving any trigonometric!

  • Boids slow down or accelerate toward they preferred speed that at the end becomes a speed of the flock.

The rules above may result boids either stalling in place or accelerating above the reasonable speed. This is not nice to watch, so the extra rule has been introduced that causes slow acceleration or deceleration toward the "optimal" velocity Vopt:

Speed can also be limited between the fixed minimum and maximum.

There are also more rules that make the flock behavior to look more realistic:

  • A boid may land and stay fixed for some time (perching).
  • An arbitrary point may become point of attraction or avoidance, permanently or for some fixed time.
  • A blow of wind may be simulated by adding the same value to the velocity vector of all boids.

The final acceleration of the boid is proportional to the sum of impacts that come from the all rules defined above:

here is a weight constant that must be individually tuned for every rule r.

Practical implementation also usually required to implement some way to keep boids inside the visible area of the simulation, like bats in the cave. Old-style animations with moving objects frequently implemented either "infinite space" (when objects go to the top they appear at the bottom) or balls - like bouncing (by negating the speed vector component that has been liable for hitting the wall). However real animals seldom to hit the wall at full speed and bounce. Instead, they slow down and turn around. For boids, slowing down is implemented by gradually decrementing the velocity component directed toward the wall. When it reaches zero, the boid is at its closes distance to the wall, and further decrementing forces it to turn around and fly away. When flying away, the boid accelerates until the distance to the wall becomes no longer critical.

Interestingly, it is possible to find parallels between neighbor sensing model and mathematical models of flock. Neigbour sensing model also contains both components of the positive and negative attraction to the neighbor (responsible for the forming of mycelia that has stable density) and desire to grow in same direction as other hyphal tips are growing (forming chords). The main difference is that flock equations rely on the "mass center" of the flock, assuming than boids can easily determine it. Neighbour sensing model instead assumes capability to sense the closest neighbours only that rapidly declines with the distance.

References

  1. 1 Conrad Parker boids project page, includes boid implementations in many programming languages
  2. 2 Craig Rainolds page, includes rich bibliography on flock behavior
  3. 3 Boids pseudocode