In his paper "Flocks, Herds, and Schools: A Distributed Behavioural Model", Reynolds successfully developed the first decentralised model of a flocking system by using simple mathematical rules to add behaviour to what was in essence a particle system. The rules were executed on the information provided by each agent’s perception model, i.e. each individual’s local awareness of its immediate environment. The following three rules were used to control each artificial bird (crowned ‘bird-oid’ or ‘boid’) in the simulation:
| Rule | Representation | Description |
|---|---|---|
| Collision avoidance | Acts to repel agents from colliding with other members of the flock and with obstacles in the virtual environment. This force increases exponentially the nearer an agent comes to a collision. | |
| Velocity matching | Can also be thought as alignment whereby an agent steers towards the average heading of its local neighbours. Velocity matching is a side effect of this alignment desire | |
| Flock centering | Recreates an agent's desire to occupy a centroid position relative to its local neighbours |
Reynolds's excellent Boid website provides clear illustration of these rules together with an excellent demonstration of a 3D flocking system.
Each rule is used to calculate a force vector by selectively averaging together navigational detail of neighbouring agents provided by the perception model. The applet shown on this page provides a visualisation of the direction and magnitude of the rule-based force vectors acting on a single agent (shown in green) as it traverses through a group of particles. Neighbouring agents being considered by the perception model are highlighted in red.
Velocity matching and flock centering vectors can be found by taking mean averages of neighbouring agents’ direction and position respectively. Collision avoidance requires a more complicated computation as the magnitude of the force depends on the proximity of the neighbouring agents and obstacles. Neighbours far away from an agent should contribute very little to the collision avoidance vector, whereas neighbours within a few ‘pixels’ of an agent should provide a collision vector component with enough strength to out weigh any conflicting vectors from other rules. Collision free movement is of highest priority to any group of flocking agents – a dolphin swooping through a school of fish is likely to cut the group in half momentarily as a fish’s desire to avoid the jaws of the dolphin far outweighs its urge to remain in the centre of its local neighbourhood. Predator-prey interactions of this type will require further adjustment to the flocking model but for the time being I shall concentrate on building a simulation of flocking agents without the distraction of predators or obstacles.
The collision avoidance vector is calculated using a weighted mean average of component agent avoidance vectors based on the distance from the current agent to neighbouring agents. This distance between agent and neighbour is divided into the radius of the perception area (i.e. the maximum distance two agents can be separated whilst still being able to see each other) and then squared. This gives a number >= 1 which increases exponentially as the distance between agent and neighbour decreases. It is this number which is used to weight the avoidance vectors when the mean vector is calculated. By squaring the weighting and making the relationship between weighting and proximity exponential, neighbours that lie towards the edge of the perception area contribute very little to the mean avoidance vector whereas neighbours closest to the central agent contribute almost entirely to the total value of the mean vector.