Behavioral Animation - Computer Animation: Algorithms and Techniques - page 340

Aggregate behavior
Managing complexity is one of the most important uses of the computer in animation, and nothing
exemplifies that better than particle systems. A particle system is a large collection of individual ele-
ments, which, taken together, represent a conglomerate fuzzy object. Both the behavior and the appear-
ance of each individual particle are very simple. The individual particles typically behave according to
simple physical principles with respect to their environment but not with respect to other particles of the
system. When viewed together, the particles create the impression of a single, dynamic complex object.
This illusion of a greater whole is referred to as emergent behavior and is an identifying characteristic
of particle systems, flocking, and, to a lesser extent, crowds.
Often behavioral animation is concerned with a large number of characters. The primitive behaviors
of flocking and prey-predator activity, as well as crowd modeling, are common examples. One of the
problems when dealing with a large group of behavioral characters is that knowledge about nearby
characters is often required. Particle systems do not exhibit this complexity because there is (typically)
no particle-particle interaction. There is only simple physical interaction with the environment. But
when knowledge of nearby characters is required, the processing complexity is n -squared where n
is the number of characters. Even when interactions are limited to some k nearest neighbors, it is still
necessary to find those k nearest neighbors out of the total population of n .
One way to find the nearest neighbors efficiently is to performa three-dimensional bucket sort and then
check adjacent buckets for neighbors. Such a bucket sort can be updated incrementally by adjusting bucket
positions of anymembers that deviate toomuch fromthe bucket center as the buckets are transformedalong
with the flock. There is, of course, a time-space trade-off involved in bucket size—the smaller the buckets,
themore buckets needed but the fewermembers per bucket on average. This does not completely eliminate
the n -squared problem because of worst-case distributions, but it is effective in practice.
The members of a flock, typically fewer in number than particles in a particle system, usually
behave according to more sophisticated physics (e.g., flight) and a bit of intelligence (e.g., collision
avoidance). Simple cognitive processes that control the movement of a member are modeled and might
include such behavior as goal-directed motion and the steering to maintain separation from neighbors.
Adding more intelligence to the members in a group results in more interesting individual behaviors,
which is sometimes referred to as autonomous behavior . Modeling autonomous behavior tends
to involve fewer participants, less physics, and more intelligence. Particle systems, flocking, and crowd
behavior are examples of independently behaving members of groups with varying levels of autonomy,
physical characteristics, and simulated motions ( Table 11.1 ). If a larger number of autonomous
agents are modeled, crowds are created that share some of the same emergent qualities as flocks and
particle systems.

Table 11.1 Aggregate Behavior

Number of
Elements Type Incorporated Physics Intelligence

2
-10

4

Particles 10 Much—with environment None

1
-10

3

Flocks 10 Some—with environment and other elements Limited

1
-10

2

Crowds 10 Usually little physics, but depends on interaction with

environment

Varies from little
to much