Craig Reynolds (Siggraph 87)
Jane’s notes: 4/7/01
Basic
Idea:
The
simulated flock is an elaboration of a particle system, with the simulated
birds (or fish) being the particles.
The individual birds act as single actors, and choose their own course
according by a set of rules dictating its flocking behavior.
Previous
Flocking Work:
-
force-field
animation systems: the birds trace path along a force field, rejection fields
around each bird prevents collision
Modified
Particle System:
- normal particle systems are collections of large number of individual particles, each having own behavior. Particles are created, age, and die off. Behavior includes color, opacity, location and velocity\
-
For
our birds, particles are replaced by geometric shapes, complete with local
coordinate system and thus have one more attribute: orientation.
-
Each
bird is thus an actor: the set of
internal state as an object (in the object-oriented programming sense), adding
a computational process to apply behavioral rules to its internal data
- motion along a path: a dynamic, incremental, rigid geometrical transformation of an object, movng along and tangent to a 3D curve. Does NOT contrain roll
-
Forward
is +z direction
-
Makes
use of local coordinates as the birds’s EYE view, measuring surroundings
relative to its own coordinates. The
local unit is usually a body length.
-
Conservation
of momentum, with defined maximum speed (despite acceleration) , minimum speed
and maximum acceleration
-
Gravity
is only modeled in banking behavior, and not in normal flight. (for otherwise one would need another
parameter, buoyancy or life)
-
In
the current model, steering is done by directing the available thrust in the
appropriate direction; however it would be more realistic if separated into
lateral and tangential components, since they are normally different.
-
Rolling
(rotation about z axis) is used for banking: rolling the object to align the
local Y axis (up/down) with the acceleration acting upon it. Think flight simulator
-
With
correct banking, the object’s local space remains aligned with the “perceptual”
or “accelerational” coordinate system-> simplifies the bird’s orientation
Flocking
-
natural
flocks seem to consist of two opposing behaviors: a desire to stay close, and a
desire to avoid collisions
-
an
evolutionary device for protection against predators perhaps
-
an
individual bird is aware of 3 things:
-
itself
-
its
two or three neighbors
-
the
rest of the flock
-
there
is no upper bound on how many birds can be in a flock.
Simulated
flocks
-
work
required is the square of a flock’s population: O(N2)
-
start
with a model that supports geometric fight, add rules:
1.
collision
avoidance: avoid collisions with nearby flockmates
2.
velocity
matching: attempt to match velocity
with nearby flockmates (heading and speed)
3.
flock
centering: attempt to stay close to nearby flockmates (bird wants to be near
center of flock)
-
with
velocity matching, the spacing between individual birds should remain somewhat
invariant
-
in
a bird’s localized perception, center of flock means center of nearby
neighbors. Therefore, if a bird is in
center of flock, this urge is minimal.
The birds on the edges will try not to stay closer
-
-real
flocks sometimes split apart to go around an obstacle. Flock centering allows this as long as an
individual bird can stay close to some neighbors. The designated leader model, however, does NOT allow this
behavior.
-
the
3 behavorial urges all produce an isolated acceleration request “if I
were in charge, I would accelerate in that direction”.
-
Each
behavior has several parameters that control its function, strength (0 – 1),
which serve as weights
- It is up to navigation module of each bird to prioritize (or just average them all) and determine a final acceleration vector, the pilot module then passes it to the flight module which flies the bird to that direction.
-
averages
however, lead to problems: imagine a
bird trying to make a decision of whether flying N or E in a city block
intersection
-
Prioritized
acceleraton allocation should be used instead
o
Requests
are considered in priority orders and added into accumular
o
Process
continues til max acceleration value is reached
o
The
navigation model then parcel little portions of acceleration out to satisfy
acceleration request in order of priority
-
neighborhood
around each bird is defined as a spherical zone of sensitivity, with magnitude
defined as inverse exponential of distance.
-
Is
exaggerated in forward direction and somewhat proportional to bird’s speed
-
In
an early version, the attraction and repulsion of birds were weighted linearly
with distance, created a very cartoonly spring-like behavior, not realistic
-
birds
released close to each other will naturally flock together in this model
-
small
flocks also join into bigger flocks, and flocks split to avoid obstacles
-
so
far, the model provides happy aimless flocking, what about some controlled
direction?
-
Migratory
urge: specified in global
parameters. A goal point, for example
-
force field or steer-to-avoid
-
force field method will describe repulsive forces around obstacles. It’s bad in
the case if a bird is flying directly into an obstacle. The repulsive force only slow the bird but
will not provide a lateral direction for it to steer away
-
steer-to-avoid: birds will only consider obstacles directly ahead (if its z-axis
intersects with anything). Working in
local perspective space, finds the silhouette edge of obstacle, find a radial
vector which will aim bird at one body length beyond silhouette edge
-
ideally
algorithm should not be sensitive to flock size, a constant time algorithm
is one that is insensitive to the total population
-
haha:
80 birds, using naïve O(N2) algorithm, on a single Lisp Machine
without any special hardware accelerators, the simulation ran for about 95 secs
per frame. A ten-second motion test
took 8 hours to produce.
-
This
model ignores internal animation of birds