Transcript grovesnorFlocks

Flocks, Herds, and Schools: A
Distributed Behavioral Model
By: Craig Reynolds
Presented by:
Stephanie Grosvenor
Flocks and Boids
• Flock is a group of objects that exhibit
the general class of polarized (aligned),
non-colliding, aggregate motion
• To simulate flock, simulate the behavior of
individual bird
– Perception
– Flight dynamics
• Boid is a simulated bird-like object
How do we simulate a flock in
computer animation?
– Scripting is bad
– Particle system too simple
– Make particle systems more complex
• Local perception
• Simulated physics
• Flocking behaviors
– Result of dense interaction of relatively simple
behaviors of individually simulated birds
Behavioral Animation
• Animator as a theatrical director
• Character's performance is the indirect result of the
•
•
director's instructions to the actor.
Not know how a simulation is going to proceed from the
specified behaviors and initial conditions - many
unexpected, pleasant surprises.
Problem getting uncooperative flocks to move as
intended ("these darn boids seem to have a mind of
their own!").
Boids and Turtles
• Logo turtle
– Movement forward,
back, left, right
• 3D turtles and their
•
paths are equivalent
to boid objects and
their flight paths
Simple rules for
complex behavior
Geometric Flight
• Flight - Dynamic, incremental, rigid motion
•
•
along a path
Geometrical transformation of an object,
moving along and tangent to a 3D curve
Motion rigid - Underlying geometric model
free to change shape within flying
coordinate system
Geometric Flight
• Conservation of momentum
• Simple model of viscous speed damping –
not exceed maximum speed
• Minimum speed can be specified
• Maximum acceleration used to provide
smooth changes of speed and heading
Geometric Flight
• Gravity modeled but only defines banking
behavior
• Many physical forces not supported
Banking
• Magnitude of turning acceleration directly
•
•
varies with object’s velocity and with the
curvature of its path
Correct banking – object’s local space
remains aligned with the perceptual or
accelerational coordinate system
Makes boid fit viewer’s expectation of how
flying objects should move and orient
themselves
Natural Flocks, Herds, and Schools
• Bird in flock must have behavior that allows it to
•
coordinate movement with flockmates
Two balanced, opposing behaviors
– Desire to stay close to flock
– Desire to avoid collisions within flock
• Individuals don’t pay much attention to each
and every bird in flock
– Bird’s perception of the rest of flock is localized and
filtered
• Itself
• Two or 3 nearest neighbors
• Rest of flock
Simulated Flocks
• Collision Avoidance
– Avoid collisions with nearby
flockmates
• Velocity Matching
– Attempt to match velocity with
nearby flockmates
• Flock Centering
– Attempt to stay close to nearby
flockmates
Collision Avoidance
• Urge to steer away from imminent impact
• Static collision avoidance based on relative
position of flockmates
• Ignores velocity
Velocity Matching
• Looks only at velocity
– Ignores position
• Predictive version of collision avoidance
– If boid does a good job of matching velocity
with neighbors – collision in near future
unlikely
• Static collision avoidance and dynamic
velocity matching are complementary
• Static collision avoidance serves to
establish minimum required separation
distance – velocity matching maintains it
Flock Centering
• Boid localized perception of world center of flock
•
•
•
actually means center of nearby flockmates
Causes boid to fly in a direction that moves it
closer to centroid of nearby boids
If a boid is close to the center of the flock this
will have little effect (since the boid density will
be uniform), but if it is on the edges then it will
have a greater effect.
Correctly allows simulated flocks to split
Arbitrating Independent Behaviors
• three behavioral urges associated with flocking
•
•
•
•
each expressed as acceleration requests
Behavior has several parameters – including
strength, further accentuate the acceleration
request
Navigation module of boid brain to collect
relevant acceleration requests and then
determine single behaviorally desired
acceleration
Weighted average according to priority
Not good for collision with obstacles - Weighted
average may cancel (opposite directions)
Arbitrating Independent Behaviors
• Acceleration requests considered in
priority order and added to accumulator
• Magnitude added to another accumulator
• Continue until sum of accumulated
magnitudes larger than maximum
acceleration value
• Emergency acceleration allocated to
satisfy pressing needs first
• Example: Centering ignored in order to
maneuver around obstacles
Simulated Perception
• Perception model tries to model real bird
• Filtering out surplus information that
•
implements boid’s behavior
Real bird imperfect senses – nearby
flockmates hide those farther away
– Strongly localized information available
• Aggregate motion of flocking depends on
limited localized view of world
Each boid has direct access to the whole scene‘s
geometric description, but flocking requires that it
reacts only to flockmates within a certain small
neighborhood around itself.
The neighborhood is characterized by a distance
(measured from the center of the boid) and an angle,
measured from the boid's direction of flight.
Flockmates outside this local neighborhood are ignored.
The neighborhood defining the region in which flockmates
influence a boids steering.
Scripted Flocking
• Happy aimless flocking is good – direction better
• Direct motion at specific times
• Simulations under control of general-purpose animation
•
•
•
•
scripting system
Interactive motion control facilities – provides ability to
schedule invocation of user-supplied software on a frame
by frame basis
Describe Timing of flock actions
Flexible Control over time varying values of parameters
Set up and animate all nonbehavioral aspects of scene
background/lighting/camera motion/ visible objects
Scripted Flocking
• Migratory urge – global target (global direction)
• Global position – a target point toward which
•
•
•
birds fly (going z for the winter)
Bounded acceleration, incrementally turns boid
toward migratory target
Animate dynamic parameter – global position
vector, global direction vector
Animate goal point along desired path
Avoiding Environmental Obstacles
• Two types of shapes of environmental collision avoidance
– Force field
– Steer-to-avoid
• Force Field
– Field of repulsion force emanating from obstacle out into space
– Boid increasingly repulsed as it gets closer to obstacle
• Problem
– approach obstacle surrounded by a force field at angle such that
exactly opposite to direction of force field
– Worst case scenario – fail to turn
– Problem with peripheral vision
– Too strong up close/ too weak far away
• Want long-range planning to avoid obstacles, not
•
panicky correction
Steer-to-avoid more robust - natural
Avoiding Environmental Obstacles
• Steer-to-avoid
• Obstacles that are directly in
front of boid (where local z and
obstacle intersect)
• Silhouette edge of obstacle is
•
closest to point of eventual
impact
Radial vector computed – aim
boid at point 1 body length
beyond silhouette edge
Other Applications of the Flock Model
Polarized, noncolliding aggregate motion
• Traffic patterns, fish, locomotion, crowds
• Scientific investigation
Questions?