How complex a flocking system has to be to look convincing ?

Abstract

Flocking Systems have been used since their introduction in 1987 by Craig W. Reynolds. Flocking systems were used in several computer graphics industries and not only for research and simulation purposes. The entertainment and film industry have made an intensive use of flocking systems in films (eg: flock of bats in Batman Returns, 1992) and commercials. It helps to rapidly create the complex animations of numerous actors: flocking of birds, schools of fishes, Herds, crowds, traffics and so forth.
Basically, as described by C.W.Reynolds, a flocking system is an elaborated particle system where each particle is an actor. Each actor has basic rules that control its behaviour within the aggregate motion of flocking actors.
The three basic rules implemented for each actor or Behaviour Routine are: Cohesion and Alignment and Separation. With these two routines, one can implement a basic flocking system from a particle system. One can hence simulate natural motion of flock or any kind of synchronized motion such as flocking of birds or schools of fishes. That is of course only two examples of use that can be applied to other kind of actors.
Indeed, depending on the purpose, the complexity of a flocking system can reach such a level where is can become difficult to distinguish it from a Life Simulation System.
A flocking system can be set up in many different ways but generally setting up some very basic rules is enough to bring life to actors in a flock, schools, and even a crowd.

Introduction

Today, the use of flocking systems is a common and well understood technique in the visual effect industry. Most popular 3d packages support the use of particles systems. Depending on which package you use, you can create more or less basic flocking system using already implemented tools such as in Side Effects Software Houdini®, where flocking behaviours are already implemented and can be use directly without any need of scripting. Some packages require knowledge of scripting (usually the embedded scripting language that come with the software) to be able to create a simple flocking system. It is the case with Alias® Maya® (version 6.5 at the time of writing) you need to use the MEL (Maya Embedded Language).
As these two packages are commonly used in the visual effects industry, most of the flocking systems you see in commercial or films have probably been generated from one of both.
Recently, some package go further and implement more complex behaviour using fuzzy logic and decision making for your flocking system using artificial intelligence. It is the case of Massive™ from Massive Software®.
Artificial Life software fulfils the need of more complex behaviours such as crowd simulation. Indeed, flocking systems can successfully be used for synchronized motion of actor such as birds, fishes, ants and so forth using the two behaviours described above where actors have very little decisions. Such flocking systems aren’t sufficient to simulate realistic motion of aggregated actor in the case of a crowd or any kind of simulation where actors have to have more than three basic behaviours.
In one hand, basic flocking systems aren't sufficient to create complexity within an aggregation of actors but can be very quickly setup using common 3D package in use in the visual effect industry. In the other hand software such as Massive™ are very good to create very complex behaviours and hence, they are very suitable for crowd simulation. But in many cases an elaborated flocking system can fulfil the need of complexity within a flocking system.
Creating convincing motion of a crowd can be solved using a flocking system. How complex a flocking system has to be to look convincing? Is the subject of this research webpage.

Basic flocking system

Flocking systems may seem complex when we watch them but they are actually very simple. According to Craig W.Reynold in the case of a flocking of birds "a flock is simply the result of the interaction of behaviour of individual birds".
Interaction is the key of simulating any sort of flocks, schools, crowd and so forth. Actors can interact between themselves or with the environment (avoiding other actors and obstacles). Some very complex flocking systems go further where the environment itself can react to the flocking actors such as behavioural L-Systems.

The underlying of most flocking system and the model described by Craig W. Reynold is a particle system.  A simple example of a flocking system is made of a leader and a follower, both are particles. The leader needs only one behaviour: the Avoidance capability. The follower needs at least two: the target to follow (derived from the Cohesion behaviour) and the Separation.

This is the first step to create a Flocking System. Is it enough to create a realistic flock of birds, a school of fishes? Not really. One more routine is needed to simulate that: Alignment

This one more routine constraint the followers to point a specific direction. In the case of the Leader-Follower model, the follower point toward the leader as they are following it.

Once these three behaviours have been implemented, they can already be used to create herds but not a realistic flock of birds yet. To simulate a flock of birds or of fish and any flying group of actor one more attribute is needed: the Banking.

To recapitulate, with one or more Leader and few or numerous followers and with few attributes: target follow, collision avoidance, alignment and banking in the case of flying actors, one can create very realistic motion of Herds, Flocks and Schools.
It can be enough but we are still far from the complexity of what an A.I system can create. But with a simple approach and an efficient use of flocking system capabilities, more complex result can be achieved. And hence a flocking system can be used to simulate systems as complex as crowd.

Approach to a more complex flocking system

Flocking Systems not A.I Systems

In a basic flocking systemthe few routines are in fact the foundation of a useful flocking system. With such flocking systems, an animator gets rapidly limited by the lack of control that (s)he has on it.
In fact, these rules are global in a way that they only "sculpt" the general motion of the flock. The routines introduced above can be seen as global routines. The limitations are the fact that every actor in the simulation is the same and have the same behaviours. To get further realism, we need to get further into "trait".

"Trait" means that every actor in the flocking system is different and hence behaving differently within the group. It might not be useful for a school of fish, but it certainly improves the realism of Herd and Crowd simulations. Indeed, that is what defines the nature. Every member of any given species is different. Human beings are the extreme example of traits.
We can differentiate two level of trait within a group: the conduct (individual behaviour) and the appearance (colour, size ...).

It seems tedious to create these traits with a flocking system. One approach to solve this problem is the use of Artificial Life system.
From a visual effects point of view, using such a system is expensive and complex. For a visual effects shot the most important thing is that the simulation look as realistic as possible for a very short amount of time. Also, A.I system doesn't give the maximum of control to the animator and hence not being subject to any unexpected behaviour.
Finally, A.I systems attempt to simulate senses by creating intelligent actors that are really able to make decisions. Flocking Systems attempt to simulate intelligence but only visually (actors has to look as they had a brain). When a flocking system simulation is running, it is has to look like the actors are intelligent. But, how to increase the realism by making actors behaving as they where taking decisions on there own?

Per-particles attributes and probability

Instead of considering each actor to be able to make decisions and then behave according the situation we can take another approach. In A.I Systems, even if it can take decision the actor has to choose between routines to face a situation. In some very advanced A.I systems the actor can even evolve trough time but we don't consider these particular systems. What we want to recreate with a flocking system is something that looks like a decision happening within the flock, herd or crowd.
We can look at decision making from another angle. We can consider that decision making by actors within a group implying an alteration of their behaviour as a probability of an event to occur. The probability of an alteration of an actor's behaviour to occur is what we want to achieve using a flocking system and neither a decision making nor fuzzy logic.

In an aggregate of actors, very basic behaviours can be setup for every actor by assigning a set attributes to every particle or per-particle attribute (as flocking systems I am stating here are based on a particle system). These attribute can be of any kind: speed, mass, size, sex, libido etc. 

By using probabilities and mathematical functions we can than randomly or specifically distribute variations of the attributes to each particle. For example:

• 30% of the actors a female (leaders)
• 2% of  immobile actors
• Random distribution of the size,libido using random function, IF statement, loops, link to other attributes.
• link to particles attributes (AGE,LIFE, ID ...)
• ...and so forth

From here, with very few attributes we have created variations for each actor. The probability of getting two actors to have the exact same characteristics decreases rapidly as the number of attributes increase. 

And by linking attributes accordingly we can set up behaviours of our actors, e.g.:

• The speed diminishing as the size or the mass increase
• As the libido attributes variable increase the radius of the field of separation diminish.
• ...and so forth

Finally, using these simple parameters and applying variation on them, the flocking system would look very complex and very controllable though. The possibilities to extend such flocking systems are endless and the flocking system keeps being simple and flexible.

Conclusion

Theoretically one can create very complex looking flocking system using very few attributes. By linking attributes together, creating new attribute very easily, and creating variation using simple probabilities and mathematical expression.
Flocking systems can fulfill 99.9 % of the need to create complex motion of actors by faking decision making and  fuzzy logic what A.I systems are made for. It doesn't really make sense to use A.I for short simulations as used in films and commercials. A.I is more suitable for games, research on robotics, crowd management, driving simulator.
Another area to look at for flocking systems is the ability to manage hundreds of thousands or millions of actors with as less computing power need as possible. This is one reason of the success of >Massive™ the A.I system from >Massive Software®.

References

1. Craig. W. Reynolds, Flocks,Herds and Schools: A Distributed behavioral model,Computer Graphics, Volume 21 #4, July 87, (acm SIGGRAPH '87 Proceedings), pp 25-34.
2. H.Noser, D. Thalmann,The Animation of Autonomous actors based on Production rules,IEEE Computer Society Press, June 96, (Computer Animation '96).
3. Xiaoyuan Tu, Artificial Animals for computer Animation,Springer,1999.
4. D.M.Bourg, G.Seeman, AI for Game Developers,O'Reilly, July 2004.
5. C.Loscos, D.Marchal,A.Meyer,Intuitive Crowd Behaviour in Dense Urban Environments using local laws,2003.
6. POP Flocking, Houdini Training 4.0, Side Effect Software, 1999
7. Flocking birds in MGS, http://mgs.lami.univ-evry.fr/ImageGallery/EXEMPLES/FlockingBird/index.html
8. Flock Demo Software, http://www.riversoftavg.com/flocking.htm