Transcript Complex Movement

Flocking and more

NPC groups can move in cohesive groups not
just independently
◦ Meadow of sheep grazing?
◦ Hunting flock of birds?
◦ Ants? Bees? Creatures?

Other types of computer controlled NPCs
◦
◦
◦
◦
Humans, Orcs, Catapults?
Squadrons of aircraft?
Friendly soldier squads?
Simulate crowds of people loitering?

Coordinated group movement, the idea:
◦ To have the NPCs move with the illusion of having
purpose and coordination

One of the earliest, most successful group
behavior  Flocking
◦ “Flocks, Herds, and Schools: A Distributed
Behavioral Model”, Craig Reynolds, SIGGRAPH 1987
◦ Originally intended for birds, fish and other
creatures, but it can be modified for other types of
NPCs



Term used by Craig Reynolds to refer to this
simulated flocks
Leaderless flock – able to stick in a group
3 simple rules
◦ Cohesion
◦ Alignment
◦ Separation

Neighborhood: Defines the area where these
rules will come to effect


Have each unit steer towards the average
position of its neighbors
Units are attracted to one another as long as
they are within range


Have each unit steer so as to align itself to
the average heading of its neighbors.
Match direction of units around it that it can
detect


Have each unit steer to avoid hitting its
neighbors.
Units are repelled by non-member units or
obstacles. Repel effect is inversely prop. to
distance from unit

Flocking neighborhood creates a range that
units can detect for other same-group units,
other-group units

Some implementations use two
neighborhoods – one for detection of units,
one for separation to avoid other units



Typically, a visibility arc or field-of-view
(FOV) is used to define the neighborhood
Is this practical?
To what extend is each unit aware of its
neighbors?


Each unit is aware of its local surroundings
Each unit does not necessarily know what the
entire group is doing at any given time


Visibility arc defined by 2 parameters – arc
radius r and angle θ
How do these parameters affect flocking
motion?


Large radius? Small radius?
Wide FOV? Narrow FOV?


Narrow FOV: Squadron of jets, Sneaking up
behavior
Wide FOV: Group of birds, Military army



Steering forces to be applied on the units
Treat each unit as a rigid body that is able to
turn and apply net steering force
accumulated from each flocking rule
2 important techniques when implementing
flocking
◦ Tuning is required so that no single rule
dominates
◦ Modulation of steering forces so that contribution
is not constant for all units

In each game loop
◦ Cycle thru all units in the flock to acquire data
(direction, speed, etc.) from unit’s neighbors
◦ For each unit, update with net steering force from
the three rules


Each unit must update its view of the world
each game loop (cycle thru all units in the
flock)
Refer to textbook for more details on the
implementation code snippet
void DoUnitAI(int i)
{ int j; int N; // Number of neighbors
Vector Pave; // Average position vector
Vector Vave; // Average velocity vector
Vector Fs; // Net steering force
Vector Pfs; // Point of application of Fs
Vector d, u, v, w;
double m; // multiplier, +1 or -1
bool InView;
bool DoFlock = WideView||LimitedView||NarrowView;
int RadiusFactor;
...
}



Calculate average position – vector sum of
their respective positions divided by total
number of neighbors
Determine direction to turn and angle to steer
towards
Steering force effected = Direction multiplier
* Max steering force * angle of steering /
scale factor



Normalize each unit’s velocity vector to get
heading unit vectors
Calculate average heading of all units – sum
of heading unit vectors divided by total
number of neighbors
Effected steering force is calculated same way
as cohesion



Separation is enforced by steering away from
any neighbor that is within view AND within
prescribed minimum separation distance
Because this steering force is corrective,
direction multiplier goes the opposite way
Effected steering force
= Direction multiplier * Max steering force *
(Unit length * separation factor) / separation
distance

http://www.lalena.com/ai/flock/




Flocking would be much more realistic if
units also avoid running into objects in the
game world
To detect whether an obstacle is in the unit’s
path ahead, imagine that each unit has
“feelers” like those on insects!
Well, if one feeler is not enough, maybe you
might need a few feelers?
Let’s see how a single “feeler” works…






v : “feeler”
Calculate vector a
Project a onto v by dot product
to obtain p
Subtract p from a to get vector b
Test conditions:
1. Magnitude (p) < Magnitude (v)
2. Magnitude(b) < Radius (r)
If both tests pass, corrective
steering required, otherwise unit can continue on
its current heading


Corrective force can be calculated
as inversely prop. to distance
from unit to the center of obstacle
or Magnitude (a)
Effected steering force
= Direction multiplier *
Max steering force * (Collision
Visibility Factor * Unit length
for Magnitude(v) / Magnitude(a) )


This obstacle avoidance algo will not
necessarily guarantee zero collisions between
units and obstacles. What are some likely
problems?
What we have seen so far only applies to
circular obstacles. What about block
(rectangular) obstacles or other free forms
shapes?




So far, flocking behaviors are leaderless
By combining classic flocking with leaderbased AI, many new possibilities are
available!
Flocks may have greater purpose if follow a
leader
Question: How to designate leader? Should
we “appoint” a unit as leader? Or should we
let them sort out themselves who should be a
leader?



Let’s focus on this particular method
Advantage: Any unit can become a leader at
any given time, flock will not be leaderless if
leader gets destroyed or separated from flock
Once a leader is established, we can
implement any number of rules to have the
leader do something meaningful
◦ Execute pattern movement or patrolling
◦ Chase or evade or intercept something

Can you figure out an algorithm to do this?

A possible solution:
◦ Determine the number of units directly in front of
or within view of current unit being processed
(velocity directions are available for use)
◦ If no other units are directly in front of the unit, it
becomes the leader. The rest follows flocking rules

Any more ideas?



Follow the Leader AI adds an interesting
dimension into flocking and group
coordinated behavior
More than one leader (of different purposes)
can also be implemented
You can also implement flocking behavior for
player-friendly/assisting NPCs where the
“leader” is simply the player