Transcript Modeling of Flocking/Group Behaviors

Flocking and Group Behavior
Luv Kohli
COMP259
March 24, 2003
Outline
• First, birdies!
– Craig Reynolds paper on flocking
• Then, fishies!
– Tu & Terzopoulos paper on artificial
fishes
What is a flock?
• One definition: a group of birds or
mammals assembled or herded
together
Why model flocking?
• It looks cool
• Difficult to animate using traditional
keyframing or other techniques
– Hard to script the path
– Hard to handle motion constraints
– Hard to edit motion
Boids!
• “boids” comes from “bird-oids”
• Similar to particle systems, but have
orientation
• Have a geometric shape used for
rendering
• Behavior-based motion
Boid motion (1)
• Boids have a local coordinate system
Boid motion (2)
• Flight is accomplished using a dynamic,
incremental, and rigid geometrical
transformation
• Flight path not specified in advance
• Forward motion specified as incremental
translations in local +Z direction
Boid motion (3)
• Rotation about X, Y, and Z axes for
pitch, yaw, and roll
• No notion of lift or gravity (except for
banking)
• Limits set for maximum speed and
maximum acceleration
Flocking motion
• Boids must coordinate with flockmates
• Two main desires:
– Stay close to the flock
– Avoid collisions with the flock
• Flocking seems to have evolved due to
protection from predators, higher
chances of finding food, mating, etc.
Flocking – 3 Behaviors (1)
• Collision avoidance: avoid collisions with
nearby flockmates
Flocking – 3 Behaviors (2)
• Velocity matching: attempt to match
velocity with nearby flockmates
Flocking – 3 Behaviors (3)
• Flock centering: attempt to stay close
to nearby flockmates
Arbitrating behaviors
• Behavioral urges produce acceleration
requests: normalized 3D vector with
importance in [0,1]
• Priority acceleration allocation is used
instead of averaging acceleration
requests
• Acceleration requests are prioritized and
the most important ones are used up to
a maximum acceleration
Simulated perception
• Unrealistic for each boid to have
complete knowledge
• Flocking depends upon a localized view
of the world
• Each boid has a spherical neighborhood
of sensitivity, based upon a radius and
an exponent: 1/rn
• Can be exaggerated in forward direction
Scripted flocking
• More control is needed for animation
(e.g., flocks should be near point A at
time t0 and near point B at time t1)
• Flock has a migratory urge towards a
global target
• Global target can be moving and can
vary depending on boids or other
factors
Avoiding obstacles (1)
• Force field approach
– Obstacles have a field of repulsion
– Boids increasingly repulsed as they
approach obstacle
• Drawbacks:
– Approaching a force in exactly the
opposite direction
– Flying alongside a wall
Avoiding obstacles (2)
• Steer-to-avoid approach
– Boid only considers obstacles directly
in front of it
– Finds silhouette edge of obstacle
closest to point of eventual impact
– A vector is computed that will aim the
boid at a point one body length
beyond the silhouette edge
Avoiding obstacles (3)
Algorithmic considerations
• Naïve algorithm is O(N2)
• This can be significantly reduced:
– Localizing each boid’s perception
– Parallelization
– Spatial partitioning can be used to
achieve O(1)
On to fish!
• Want to model schooling and other
behaviors:
– Eating
– Avoiding predators
– Mating
• Modeled with limited memory,
perception of the world, behavior, and
physics
Overview
Physics-based fish model (1)
• Dynamic fish model consisting of 23
nodal point masses and 91 springs
• Spring arrangement maintains
structural stability while allowing
flexibility
• 12 springs run the length of the body to
serve as simple muscles
Physics-based fish model (2)
Mechanics (1)
• Each node has:
– mass mi
– Position xi(t) = [xi(t) yi(t) zi(t)]
– Velocity vi(t) = dxi/dt
– Acceleration ai(t) = d2xi/dt2
Mechanics (2)
• Spring Sij connects node i to node j
– Spring constant cij
– Rest length lij
– Deformation eij = ||rij|| - lij
•rij = xj(t) – xi(t)
– Exerts force fsij = cijeij(t)rij/||rij|| on
node i, and –fsij on node j
Mechanics (3)
• Equations of motion specified by:
mi(d2xi/dt2) + ρi(dxi/dt) – wi = fwi
ρi = damping factor
wi(t) = sum of spring forces
fwi = external (hydrodynamic) forces
• Integrated using numerically stable
implicit Euler method
How to swim fish-style (1)
• Artificial fish moves by contracting
muscles
• Forward motion achieved by swinging
tail, which displaces water
• Displaced water produces a reaction
force normal to the fish’s body and
proportional to the displaced volume
How to swim fish-style (2)
• Instantaneous force
proportional to
∫s(n·v)nds
• s = surface
• v = relative velocity
between surface
and fluid
• n = unit outward normal
function over surface
• Approximated with
f=min(0, -A(n·v)n), where
A is triangle area. (1/3)f is
given to each triangle node
How to swim fish-style (3)
• Tail swinging achieved by contracting
swimming muscles on one side and
relaxing on the other side periodically
• Turning achieved by contracting one
side sharply, relaxing the other side,
then slowly relaxing the contracted side
• Swimming uses back two muscle
groups, turning uses front two muscle
groups
Motor controllers
• Artificial fish has three motor controllers
– Swim-MC(speed)
•Converts speed into contraction
amplitude and frequency
– Left-turn-MC(angle)
– Right-turn-MC(angle)
•Converts angle into parameters for
muscles
Sensory perception (1)
• Vision sensor: vision is cyclopean
• Covers 300 degree spherical angle
extending to some effective radius
based on water translucency
• Vision sensor has access to geometry,
material properties, and illumination
information
• Image is averaged to determine overall
light
Sensory perception (2)
• Temperature sensor
• Samples ambient water temperature at
center of fish’s body
Mental state (1)
• Fish’s mental state specified by:
– Hunger
•H(t) = min[1-ne(t)R(∆tH)/,1]
•ne(t) = amount of food consumed
•R(x) = 1 – p0x, po = digestion rate
•∆tH = time since last meal
• = appetite
– p0 = 0.005 results in ravenous fish
Mental state (2)
• Fish’s mental state specified by:
– Libido
•L(t) = min[s(∆tL)(1-H(t)), 1]
•s(x) = p1x, p1 = libido constant
•H is hunger
•∆tL = time since last mating
– p1 = 0.01 results in sexual mania
Mental state (3)
• Fish’s mental state specified by:
– Fear
•F(t) = min(sum(min[Do/di(t), 1]),1)
•Do = 100 (constant)
•di(t) = distance to visible predator i
Intention generator
Satisfying intentions
• Once an intention is selected, control is passed to a
behavior routine
• Eight behaviors:
– Avoiding-static-obstacle
– Avoiding-fish
– Eating-food
– Mating
– Leaving
– Wandering
– Escaping
– Schooling
• Behaviors can also have subroutines that are called
Schooling
Different fish types
• Predators, prey, pacifists
• Each type has different intentions which
lead to different behavioral patterns
• Pacifists exhibit mating behavior based
upon criteria for being interested in
potential mates
Pacifists
• A male fish selects a mate as follows:
– A female of the same species is
preferred to one of other species
– Closer females are more attractive
than ones further away
• A female fish selects a mate similarly
but shows preference to male fish size
(stronger, more protective) rather than
proximity
References
• Reynolds, C. W., 1987. "Flocks, Herds,
and Schools: A Distributed Behavioral
Model." Computer Graphics, 21(4): 2534.
• Tu, X. and Terzopoulos, D. "Artificial
fishes: Physics, locomotion, perception,
behavior." Proc. ACM SIGGRAPH '94
Conference.