Flocking

This project is done in collaboration with Kelly Cho.

I. Overview

The behaviour of a group of animals, for example schooling fish or flocking birds, is one that can be easily observed in nature, but perhaps not so simple to describe in computer animation. Instead of individually animating or scripting the motion of each agent, a system of agents that react dynamically to their surrounding agents is a much better solution to flocking in computer animation.

An approach involving three steering behaviours (separation, alignment, and cohesion) was first described in Reynolds' 1987 SIGGRAPH paper, Flocks, Herds, and Schools: A Distributed Behavioral Model (Reynolds, 1987). There have been several further papers since, which build upon this model. One of which is Hemelrijk and Hildenbrandt's paper, Self-Organized Shape and Frontal Density of Fish Schools (Hemelrijk and Hildenbrandt, 2007), which describes refined weights and adds other force factors to the original model in order to more accurate represent schooling fish. We used this paper as the basis for our project.

II. Live Demo

III. Implementation

Steering Forces

There are three steering forces that describe the basic movement of an agent. Each of these forces take into account a subset of all the other agents to consider in their calculations.

• Cohesion - toward the average location of its neighbours
• Alignment - toward the average direction of its neighbours
• Separation - away from the average location of its neighbours

The cohesion force allows the agents to be able to find each other and move towards each other. The alignment force gives the agents a sense of cohesive direction. The separation force prevents agents from any collisions and over crowding.

Additional Forces

• Random Noise - a small force in a random direction to account for stochastic influences
• Cruise Speed - a force based on all the other forces that keeps the agent from moving too slow or fast

Weights

Each of these forces are weighted with some scaling parameter that determines the importance of each force. Of course, these weights can be changed to simulate different behaviours.

Radii of Perception

Each steering force has a radius of perception. These radii describe the zones in which each steering force selects the subset of neighbours to act upon.

Blind Angles

Realistically, an agents's behavior should only be impacted by neighbours it can perceive. Since cohesion motivated mainly through visual cues, there is a blind angle in that radius directly behind the agent. Alignment is influenced primarily through the lateral line system (an organ system found in fish that detects movement, pressure, etc. in the surrounding water), so it has blind angles both in the front and the back.

Density Dependent Radii

Likewise, an agent's senses is also impacted by its surroundings. While a static radius leads to fairly accurate flocking or schooling, in actuality an agent's radii of perception are limited by the density of its neighbouring agents. For example, a crowded agent would be able to percieve neighbours in a small radius around it than an agent surrounded by only a few neighbours. Therefore, the radii can be better calculated as a linear interpolation of the previous radii and a newly calculated density dependent radii.

This calculation is done for the cohesion and alignment radii. The separation radius stays constant because an agent's desire to have personal space should not change with the amount of neighbours it has.

s = smoothness * Δt;					// Weight for interpolation
d = max_radius - (influence * num_neighbors(t));	// Density dependent radius
radius(t + Δt) = max(min_radius, ((1 - s) * radius(t)) + (s * d));

The smoothness value determines how quickly the radius is allowed to change per calculation by prioritizing either the current radius or the calculated density dependent radius. The smaller the smoothness value, the smoother the change in radius.

The influence value determines how many neighbours it requires for the radius to constrict. The larger the influence value, the more quickly the radius reduces. If this value is too large, then the agents display a swirling behaviour since it effectively turns off alignment.

Obstacle Avoidance

To make this simulation more interesting, we can make our agents interact with the environment. Obstacles are the most basic form of environment.

Referencing Craig Reynolds’ paper Steering Behaviors for Autonomous Characters (Reynolds, 1999), we also implemented obstacle avoidance. While the basic idea is the same as described in this paper, instead of having a rectangular zone of detection in front of each agent, we chose to instead have the obstacle determine this zone.

Each obstacle has attributes position, radius, and buffer radius. The buffer radius determines how large of a zone around the obstacle our agents should avoid.

To calculate this obstacle avoidance force (to be referred to as avoidance from now on), every existing obstacle is looped through to find relevant obstacles (must in the agent’s direct path) and then from those obstacles, determine the closest, and therefore most relevant obstacle.

To determine whether an obstacle is relevant or not:

1. Check whether or not the obstacle is in front of the agent by calculating the dot product of the forward vector and the vector toward the obstacle.
2. Check whether this agent is going to be within the buffer zone in the next time step by projecting the vector from the agent to the obstacle onto the agent’s speed vector and checking if the length of this vector is greater than the sum of the radius and the buffer radius.

Once the most relevant obstacle is determined, the avoidance force direction is simply the normal out of the obstacle at the possible point of intersection on the obstacle, if the agent continues on the current trajectory. This can be calculated with a simple line sphere intersection algorithm.

IV. Future Work

The next step would be to move this simulation into the 3D realm. All the forces work the same way and should only require changes such as adding pitch and roll forces to keep the agents largely horizontal and right side up.

Some additional features could include obstacles of different shapes, such as rectangle or lines, and multiple types of agents that flock differently (based on body length, radii, etc.) and do not flock with agents that are not of their same type.

Ideally, we should also implement a spatially sorted data structure in order to handle simulations of very large number of agents.