Flocking

Flocking

Flocking (sometimes known as swarming or Herding) is a technique created by Craig Reynolds in his 1987 paper for SIGGRAPH called “Flocks, Herds and Schools: A Distributed Behavioural Model”.

Five Steering Behaviours

Separation -> Steer to avoid crowding local flock mates.

Alignment -> Steer toward average heading of local flock mates.

Cohesion -> Steer to move toward average position of local flock mates.

Avoidance -> Steer to avoid running into local obstacles or enemies.

Survival->Steer to eat as needed, or to avoid being eaten if a predator is seen.

What’s interesting about these five simple behavioural rules is how life like the resulting behaviour of the boids can be.

Separation

Gives an agent the ability to try to maintain a certain separation distance from other agents in the immediate vicinity. This prevents crowding together while ensuring a “natural-looking” closeness that emulates groups in the real world.

Alignment

Provides an agent that has the ability to align itself with other agents in its immediate vicinity, (i.e. Head in the same direction and/or speed as other agents). As with separation, this accounts for alignment through each member of a flock looking at nearby flock mates and then adjusting its heading and speed to match the average of the flock.

Cohesion

Gives an agent the ability to “group” with nearby agents, emulating similar behaviour seen in nature.

Avoidance

Provides an agent with the ability to steer away from obstacles and avoid collisions. This behaviour is accomplished by giving each agent the ability to “look forward” some distance and determine whether a collision with something is likely and adjust to avoid.

Every boid is a bit different

To make each boid a bit different we would have to individualise all the boids with various parameters – range of sight, maximum speed of flight etc. We would have to allow a randomised component apon boid creation. A newly created boid would now have some “personality” making each one a little different from its fellows – some wont see well, others will see very well, some want to maintain more distance from their fellows than the norm. Some will be hungrier than the others.

Why Do This?

A couple of reasons for doing this. Both of which add to the life like behaviour of the creatures in our little world.

First, providing each boid with slightly different capabilities is simply more realistic than an endless army of clones.

Secondly, the differences will combine to provide some forms of novel emergent behaviour as out boids interact, again providing what in the end is a more realistic representation of a group of creatures moving “en masse”. The tug and pull of tow boids in the same flock, one of which wants to maintain a cohesion much tighter than it’s fellow, will make for some interesting group dynamics, as will a boid that can see an oncoming predator just a bit farther than any of his flock mates.

All of this adds overhead, but not much though.

Feeding the Flock

If follows that if were going to have classes of boids that feed on one another, we will need something to control that hunger. To represent this, each class of boids that have the ability to eat will have a hunger rating that decrements a little each update cycle. When it reaches zero, our boid will become hungry and will actively seek out prey to satisfy that hunger. Each time a boid eats, a random test will determine if it is still hungry by comparing its current hunger rating to its starting hunger rating. E.g. if a boid starts with 10 hunger points and eats 4 of those points away, theres a 40% chance it will be satisfied and stop eating.

No Memory

Note that the steering behaviours say nothing about state information or about a given agent maintaining knowledge of the flock, it’s environment, it’s heading etc. Flocking is therefore a stateless algorithm in that no information is maintained between updates, each boid re-evaluates it’s environment every update. This reduces memory requirements which might otherwise be needed for similar behaviour using other approaches/ techniques, but also allows the flock to react in real time to changing environmental conditions. The result of this is that the flocks exhibit elements of emergent behaviour. No individual boid knows about where it is going, the flock moves as a single mass, avoiding obstacles and enemies and keeps pace with each flock mate in a fluid, dynamic fashion.

How This is Useful for Computer Games

Flocking provides a powerful tool for unit motion and making more realistic environments that the player can explore. It has been used with great success in a variety of commercial titles e.g. Unreal(Epic) and HalfLife(Sierra) use flocking for many of their monsters. Enemy Nations (Windward Studios) used modified flocking to control unit formations and movement across 3D environments. Groups of animals can wander terrain in real time strategy games or RPG’s more realistically than simple scripting. Groups of archers or swordsmen can be made to realistically move across bridges or around boulders or other obstacles. Monsters in an FPS can wander the dungeon halls in a more believable fashion, avoiding players where possible but perhaps launching an attack when the flock grows large enough.

The possibilities are practically endless.

Constraints

Several constraints on the boids restrict how they move and react. Possibly the most influential is the boids perception range, which restricts how far a flock mate can “look” about its environment to detect other flock mates, potential obstacles ro enemies. The larger this range, the more organised and coherent the flocks and the better they are at avoiding enemies and obstacles. Making it smaller results in more erratic flocks, groups of boids splitting off more often when confronted by onstacles or enemies and so on.

Another constraint on how the agents can move is their velocity and max velocity change. In the real world, animals in flocks are restricted in their ability to keep up with their flock mates by how fast they can move, how fast they can turn and the like. We can simplify this problem by ignoring acceleration and focus entirely on velocity. Changes in velocity can be restricted to some proportion of the overall maximum velocity – this would prevent ridiculous bursts of speed when boids try to catch up with each other. This also provides a governing restraint on how quickly they can slow down or alter course to avoid an obstacle.