Craig W. Reynolds

Flocks, Herds, and Schools, A Distributed Behavioral Model

Synthesis of Craig W.Reynolds's Publication

Complex patterns emerge from the schooling of fishes.

Reynolds explains in his publication that it is possible to reproduce the behaviour of a pack, herd, swarm or flock by applying a minimum number of rules to the individuals that make up this system. Each individual is called a "Boid", and will behave according to its own perception of the system.

In fact, one could have the illusion that a flock of birds moves as a single unit, with coordination, whereas in reality it is the reaction of each individual towards his neighbours that causes the behaviour we observe to emerge.

Reynolds notes that a flocking simulation is similar to a particle system, which is a graphical technique simulating many natural phenomena such as fire, explosion, smoke, etc. The similarity lies in the fact that the system is composed of a large number of particles, with their own behavior, interacting with neighboring particles. Except that in our simulation, the particles are replaced by individuals with a geometric model. Therefore, these individuals must manage their orientations to cope with the direction in which they are moving.

It is important to consider that the formation of a flock is an asset for the survival of its members. Indeed, there is safety in numbers and it offers multiple advantages in order to escape predators, save energy by taking advantage of group dynamics, find food more quickly and expose themselves to social and reproductive interactions. We can therefore deduce that the flock aspires to be as massive as possible. We also know that the integrity of a flock depends on the interactions of its members, and their ability to respect certain behaviors. We can therefore observe a willingness of individuals to group together while avoiding collisions.

Reynolds's rules

Reynolds therefore sought to identify and simplify as much as possible the rules that, applied to each individual, allow a flock to emerge spontaneously. He identified that these rules are based on two parameters: the distance between two individuals and their velocities. The rules are therefore as follows: "Collision Avoidance", "Velocity Matching" and "Flock Centering" as well as environmental pressures. This collection of rules prevents the members of the flock from touching each other, forces individuals to adapt their speeds to those of their neighbors and encourages the grouping of individuals in a flock. In the next chapter we will provide details on these rules in order to implement them in a simulation.

Each of the three rules will thus produce a suggestion of direction and speed to adopt to take part in the flock. And depending on the situation, these suggestions will be more or less important, for example, if a collision is imminent, it will be necessary to favour an avoidance manoeuvre rather than adapting the speed of movement to those of the surroundings. These subtleties will therefore have to be taken into account when designing a simulation.

Application: Unity simulation

Simulation controls :

You can hold the mouse right click button, to look around.

Also, use the sliders to adjust each rules's influence.

Simulation's Code

A few details on the laws that govern the flock

Reynolds has identified 3 rules applied to each member of a flock: "Separation", "Alignment" and "Cohesion".

Alignment:

To avoid collisions, each Boid should try to move at the same speed as his neighbors to avoid overtaking them, or getting caught up. The speed is represented as a 3-dimensional vector describing the distance travelled each second along the x, y and z axes of the global reference. Thus by collecting the velocity vectors of the neighbors, we can deduce the speed to be adopted but also in which direction.

Alignment rule applied to the Boids

To apply this rule, we will collect the velocity vector of each Boid present in the sphere of perception of the Boid to be steered. Then we will add these vectors (black arrow). We will divide the result by the number of neighbors to obtain an average velocity (red dotted vector). Finally we won’t directly assign this vector to the Boid, otherwise it will behave unnaturally since it will change direction and velocity immediately. To steer our Boid correctly, we subtract its own velocity from the average velocity to obtain a steering vector (in green). This way, the Boid will be subjected to an acceleration that will progressively redirect it towards the direction and general speed of the group.

Separation:

The separation rule will be used to move the Boids away from each other, according to the distance between them. Indeed, a Boid will try to move further away from a close neighbor than from a more distant one.

Referring to the figure, we collect the distance between each neighbor and the Boid to be oriented (A). A repulsive force is applied to (A), inversely proportional to the distance between the Boid and its counterpart (red dotted arrow). The average of these forces (in orange) represents the ideal direction and speed to keep a sufficient distance between the Boids. But applying it directly to the Boid would not be natural, therefore we subtract the speed vector of A (black dotted arrow) from the repulsion vector to form a second steering vector (green). This vector will redirect the Boid to the desired trajectory.

Separation rule applied to the Boids

Cohesion:

Each Boid will seek to place itself at the center of mass of the formation to which it belongs. Indeed, the average position where the individual will be attracted will therefore depend on the number of individuals in its sphere of perception. As Reynolds explains, if a Boid is located deep in the swarm, the density of neighbors will be homogeneous and it will place itself at an equivalent distance from its counterparts: the center of mass. But if an individual is at the edge of the flock, neighboring Boids will be more concentrated on one side. The centre of gravity of the neighboring Boids will therefore be shifted towards the body of the swarm. In this case, the need to get closer to the flock is stronger and the flight path will be slightly deviated towards the center of the overall flock.

Cohesion rule applied to the Boids

In the simulation, we will therefore collect the position of each Boid in the sphere of perception of (A) in order to obtain the center of gravity of the local cluster. Then we create a vector emanating from (A) towards the center of gravity (Red Arrow). Again, this vector is not directly assigned to the Boid (A) for for the sake of a realistic simulation. So we create a third steering vector (in green).

Page updated

Google Sites

Report abuse