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

may not have a group membership. Qualities of an individual relevant to group membership include the
following:
￿ A changeable belief system: From experiences, senses (e.g., vision) understanding the nature of
things as a result of learning, and causes and effects (from seeing or experiencing a sequence of
events)
￿ Time-varying biases, propensities, disposition, inclination, tendency, and emotional state: Things
that will be satisfied if possible and if there are enough extra DOFs in attaining a goal or desire to
satisfy secondary desires
￿ Goals, desires: Definite objectives that the agent is trying to satisfy
11.4.3 Crowd control
Similar to flocking behavior, individual crowd members are typically represented as being aware of
nearby crowd members and must be managed to avoid collisions. As opposed to flocking behavior,
there is less concern about the effect of physics on the crowd members, because crowds are often
land-based animals (e.g., humans) where collisions are avoided rather than detected and movement
occurs in two-dimensional space. However, because of the large number of members typically found
in a crowd, strategies for controlling the motion of each member must be very efficient for many appli-
cations. Three main strategies have been used to control crowds: rules, forces, and flows. Rules have
been discussed under the topic of intelligent behavior. For crowds, usually simple rules are used in
order to keep the computation cost low. Forces can be used that are similar to those found in particle
systems but must be organized so as to prevent collisions. The work by Helbing (e.g., [ 45 ] ) concerning
what he calls social forces is basically an extension of Reynolds' work on flocking behavior that is
applied to social interactions in crowds. In the third approach to crowd control, the movement of crowd
members has been compared to flow fields. This is usually effective for crowds that are massive in the
number of members and only positional information of an individual is needed.
11.4.4 Managing n-squared complexity
Because of the typically large number of members in a crowd, the task of comparing each crowd mem-
ber to every other crowd member for discovering the spatial proximity relationship is a major concern.
As a consequence, some type of spatial decomposition approach has often been used in cases where the
domain of interest is known ahead of time, for example, in building evacuation simulations. In such
cases, a spatial sort can be used to sort the crowd members into a data structure conducive for iden-
tifying neighbors within a certain distance. For example, a grid-based approach can be used in which all
of the interesting space is broken down into a rectangular matrix of cells. With a small enough cell size,
each cell holds one group member so that movement into a cell is restricted to empty cells. This can be
useful in maintaining the “personal space” of a crowd member, for example. Of course this also results
in a large number of cells, so updating the occupancy of each cell can start to incur an undesirable
overhead. Increasing the cell size reduces the number of cells, but requires maintaining a list of crowd
members inside of each cell and increases the complexity of finding the nearest neighbor in a given
direction. Other structures can also be used such as binary space partitioning, a hierarchical quadtree,
or dynamic Voronoi diagrams, but these require modification as the crowd members change location
over time.