Transcript Movement for Gaming

Movement for
Gaming
Artificial Intelligence
Spring 2008
Basics

Characters in games usually move
 Movement
calculation often needs to interact with the
“Physics” engine

Avoid characters walking through each other or through
obstacles
 Traditional: kinematic movement
 Characters simply move (often at fixed speed) without regard
to how physical objects accelerate or brake
 Newer approach: Steering behavior or dynamic
movement

Characters accelerate and turn based on physics
Assumptions

Game character behavior needs to be computed
very fast
 Often
not necessary to provide sophisticated
algorithms to give impression of intelligent behavior

Example: Attribution of thought to Pacman’s blinky character
 Character
position can be modeled as a point with
orientation
 3-d movement is usually not necessary


2D suffices for most surface based games
2½D (3-d position and 2-d orientation) suffices for many
others
Statics

Character position is a point
 Traditionally
in gaming given as a vector in
(x,z) coordinates

Orientation is a 2d vector of length 1,
given as  = (sin , cos )
z

x
Kinematics

We describe a moving character by
 Position
 2-dimensional vector
 Orientation
 2-dimensional unit vector given by an angle, a single real
value between 0 and 2
 Velocity
 2-dimensional vecto
 Rotation
 2-dimensional unit vector given by an angle, a single real
value between 0 and 2
Kinematics

Update calculation


Assume frame rate is high enough
Steering is given as

Steering.Linear – a 2D vector


Steering.Angular – a real value


Represents changes in velocity
Represents changes in orientation
Update at each frame




Position += Velocity * Time
Orientation += Rotation * Time modulo (2 )
Velocity += Steering.Linear * Time
Rotation += Steering.Angular * Time
Kinematic Movement

Uses following static data to output a desired
velocity
 Position
 Orientation


Can lead to abrupt changes of velocity that need
to be smoothed over several frames
Many games simplify further and force the
orientation of the character to be in the direction
of the velocity
Kinematic Movement

Seek algorithm
 Character
is given a target position
 Calculate desired direction

velocity = target.position – character.position
 Normalize
velocity to maximum velocity
Kinematic Movement

Flee: Reverse the seek velocity vector
Calculate desired direction

velocity = character.position– target.position
 Normalize
velocity to maximum velocity
Kinematic Movement

Seek with full velocity leads to
overshooting
 Arrival
modification
Determine arrival target radius
 Lower velocity within target for arrival

steering.velocity = target.position – character.position;
if(steering.velocity.length() < radius)
{
steering.velocity /= timeToTarget;
if(steering.velocity.length() > MAXIMUMSPEED)
steering.velocity /= steering.velocity.length();
}
else
steering.velocity /= steering.velocity.length();
Arrival Circle:
Slow down if
you get here
Kinematic Movement

Wandering
 Always
at maximum speed
 Direction changes

e.g. by small random changes
Dynamic Movement

Steering extends kinematic movement by
adding acceleration and rotation
 Remember:
p(t) – position at time t
 v(t) = p’(t) – velocity at time t
 a(t) = v’(t) – acceleration at time t

 Hence:
p  v
 v  a

Dynamic Movement

Dynamic movement update
 Acceleration

in polar coordinates
Size of acceleration (vector length) is limited
In dynamic movement model, we assume that there is a
strict upper bound
 In the Newtonian model, acceleration is the result of an
application of force.


Rotational component is also limited

Can be often disregarded
Dynamic Movement

Dynamic movement update
 Accelerate
in direction of target until maximum
velocity is reached
 If target is close, lower velocity (Braking)

 If

Negative acceleration is also limited
target is very close, stop moving
Dynamic movement update with Physics engine
 Acceleration is achieved by a force
 Vehicles etc. suffer drag, a force opposite
that increases with the size of velocity

Limits velocity naturally
to velocity
Dynamic Movement

Position Update:
class Position
{
protected: Vector2D position;
Vector2D velocity[2];
double orientation, rotation;
friend class Steering;
public: ...
}
Dynamic Movement

Position Update:
class Steering
{
private:
Vector2D linear; // Acceleration Vector
double angular; // describes changes in orientation
public:
...
}
Dynamic Movement

Position Update:
INPUT: steering data structure
OUTPUT: position, orientation
void Position::update(Steering& str)
{
this.position += this.velocity * time;
// this.orientation += steering.angular * time MOD 2;
this.orienatation = velocity.GetOrientation();
this.velocity += steering.linear*time;
if(this.velocity.length()) > MAXVELOCITY)
this.velocity *= MAXVELOCITY/velocity.length();
}
Dynamic Movement

Seek Algorithm
INPUT: target and character position
OUTPUT: steering update
void steering.update(Target & tar, Character & ch)
{
this.linear = tar.position – ch.position;
if(this.linear.length() > MAXACCELERATION)
this.linear *= MAXACCELERATION/this.linear.length();
}
Dynamic Movement

Seek Algorithm
 Seek
will approach target at maximum speed
 Will probably miss it by a little bit

Use a target radius to stop when close enough
 Need
an approach algorithm
Used when close to target
 Triggered when within approach radius of target
 Calculates desired speed based on time to target
and distance to target

Dynamic Movement
Dynamic Movement

Arrival algorithm
 Define
radius within which character slows
down
Calculate optimal speed to target
 If current speed is slower, accelerate towards
target
 If current speed is faster, accelerate away from the
target

 Many
algorithms used do not have a target
radius
INPUT: target and character position
OUTPUT: steering update
void Steering::update(Target & tar, Character & ch, double&
radius, double& timeToTarget)
{
Vector2D dir = tar.position – ch.position;
double distance = dir.Length();
if (distance < Epsilon)
Zero(); // close enough, stop steering
double targetSpeed;
if (distance > radius) targetSpeed = maxSpeed;
else targetSpeed = maxSpeed * distance / radius;
Vector2D targetVelocity = dir*targetSpeed/distance;
this.linear = targetVelocity – ch.velocity;
this.linear /= timeToTarget;
if(this.linear.Length()>MAXACCELERATION)
this.linear /= MAXACCELERATION/linear.Length();
this.angular = 0;
}
Dynamic Movement
Dynamic Movement

Seeking a moving target
 Current
Seek / Arrive algorithm will follow a
dog’s curve
 More realistic behavior
Calculate position of target some time in the future
based on current position and velocity
 This fits the intelligent agent model since it used
information that can be perceived

Dynamic Movement

Aligning
 Match
orientation of character to that of another
character
 Careful because orientation is a value modulo 2, so
difference is misleading
 Subtract character orientation from target orientation
and change to be between - and +
Target
Character 1
orientation 0.95 radians
orientation 0.8 radians
Character 2
orientation 0.4 radians
Dynamic Movement

Velocity Matching
 Change
velocity of character to target velocity
 Check for acceleration limits
Dynamic Movement

Flee
 Opposite
arriving
from Seek but no need to take of
Dynamic Movement

Delegated Behavior
 Built
from simpler
movement components

Based on target and
character position
 Pursue

Seek, but aiming for future
position of target
Dynamic Movement

Delegated Behavior
 Facing
 Makes character look at a target


Calculates target orientation
Calls align
 Wandering
 Steering in random directions gives jerky behavior
 Instead:



Define a target on a (wide) circle around character or far away
Move target slowly
Call seek
Dynamic Movement

Path Following
 Steering
behavior not towards a point, but to a
path
 Implemented as delegated behavior:
Define (moving) target on path
 Use seek

Dynamic Movement

Path Following Implementation I
 Define

(moving) target on path
Find nearest point on path to character

(Already difficult)
Place target ahead of nearest point on path
 Seek

Dynamic Movement

Path Following Implementation II
 Define
(moving) target on path
Find near-future position of character
 Find nearest point on path to near-future position


(Already difficult)
Place target ahead of nearest point on path
 Seek

Dynamic Movement

Path Following
 These
methods lead to corner cutting
behavior
nearest point
on path
future position
target on path
path
Dynamic Movement

Path Following
 Coherence
problem if path crosses itself
previous
point
Two candidates for
closest points
path
Dynamic Movement

Separation
 Common
in crowd simulations where many
characters head into the same direction
 Identify close characters
 Move away from them
Linear separation: Force of separation acceleration
is proportional to distance
 Inverse square law separation: Force of separation
acceleration is inverse square of distance

Dynamic Movement

Collision Avoidance
 Can
use variation of evade or separation
behavior
 Typically only include characters that are
within a cone of orientation of character
Collision avoidance is
not triggered
Collision avoidance is
triggered
Dynamic Movement

Collision Avoidance
 Evasion
behavior triggered within a cone does not
work for large crowds of characters
 “Panic” reaction even though collision is not imminent

Algorithm ignores velocity and speed of other character
Collision avoidance is
triggered
Dynamic Movement

Collision Avoidance
 Calculate
closest approach between
characters
 Determine whether distance at this point is
less than a threshold distance before
triggering evasive behavior
Collision avoidance is
triggered?
Dynamic Movement

Collision Avoidance
 Out-of-cone
characters can collide
Dynamic Movement

Collision Avoidance
 Avoiding
colliding with coordinated groups of
characters
Average velocity / position does not work well
 Instead: Calculate character in group with whom
collision is most likely

Dynamic Movement

Obstacle and Wall Avoidance
 Simple
obstacles are represented by
bounding spheres
 More complicated objects such as walls,
houses, cliffs, etc cannot be represented by
bounding spheres
 Characters use a different obstacle avoidance
algorithm
Dynamic Movement

Obstacle and Wall Avoidance
 Character
casts out a single limited distance
ray
Collision Point
Dynamic Movement

Obstacle and Wall Avoidance
 Calculate
Collision Point
Collision Point
Dynamic Movement

Obstacle and Wall Avoidance
 Calculate
normal of obstacle at collision point
Collision Point
Dynamic Movement

Obstacle and Wall Avoidance
 Set
target on normal at avoidance distance
 Go to Seek
Collision Point
Target
Dynamic Movement

Obstacle and Wall Avoidance
 Ray
casting can be very expensive
 Single ray might not detect collision

Use three rays instead
Dynamic Movement

Obstacle and Wall Avoidance
 Several
configurations tried for rays
Parallel side rays
 Central ray with short whiskers
 Whiskers only
 Single ray only

Dynamic Movement

Obstacle and Wall Avoidance
 Several
configurations tried for rays
Parallel side rays
 Central ray with short whiskers
 Whiskers only
 Single ray only

Dynamic Movement

Obstacle and Wall Avoidance
 Several
configurations tried for rays
Parallel side rays
 Central ray with short whiskers
 Whiskers only
 Single ray only

Dynamic Movement

Obstacle and Wall Avoidance
 Corner
Trap
Left ray detects collision
Right ray detects no collision
Whisker based algorithm sets
target to the right
Dynamic Movement

Obstacle and Wall Avoidance
 Corner
Trap
 Algorithm steers character straight towards
the corner
Now right ray detects collision
Left ray detects no collision
Algorithm sets target to the
right
Dynamic Movement

Obstacle and Wall Avoidance: Corner Trap
 Wide enough fan angle can avoid the problem
 But, wide enough fan angle does not allow characters to
walk through a door
 Solutions:


Get level designers to make doors wide enough for AI
characters
Use adaptive fan angles:
 Increase fan angles if collisions are detected
 Decrease fan angles if collisions are not detected
 Run corner trap avoidance
 If character moves erratically (left/right ray detect
alternatively collisions), declare one ray to be the winner
Combining Steering Behavior

Blending
 Execute
all steering behaviors
 Combine results by calculating a compromise
based on weights


Example: Flocking based on separation and
cohesion
Arbitration
 Selects
one proposed steering
Combining Steering Behavior

Blending
 Example: A group
of rioting characters that need to
act as a unified mob


Characters need to stay by the other
Characters need to keep a safe distance from each other in
order not to bump into each other
 For
each character, calculate accelerations based on
separation and cohesion



For the moment, define cohesion as a force towards the
projected center of the group
Add both accelerations
Ensure that acceleration is within potential of character,
otherwise crop acceleration
Combining Steering Behavior

Blending Weights
 Blending
weights do not need to add up to
one
 Blending weights can evolve

Learning algorithms
 Trial
and Error fixed parameters
Combining Steering Behavior

Flocking and Swarming

Craig Reynold’s “boids”


Simulated birds
Blends three steering mechanisms
1.
2.
3.

Separation
 Move away from other birds that are too close
Cohesion
 Move to center of gravity of flock
Alignment
 Match orientation and velocity
Equal Weights for simple flocking behavior
Combining Steering Behavior

Flocking and Swarming
 Separation
is only calculated for very close birds
 Cohesion and Alignment only consider birds within a
certain neighborhood

Original proposal: Define neighborhood of a boid as a cone.
Boid neighborhood
Combining Steering Behavior

Blending Problems
 Characters


can get stuck
Unstable equilibrium between “seek target” and “flee enemy”
steering if enemy is between character and target
If enemy and target are stationary, small rounding errors
usually let character flip laterally with increasing amplitude
until character finally makes dash for target
Enemy
Target
Combining Steering Behavior

Blending Problems
 Characters

can get stuck
Stable equilibrium between “seek target” and “flee enemy”
steering if enemies are between character and target
Enemies Target
Combining Steering Behavior

Blending Problems
 Constrained Environments
 Tendency to return pathological behavior:
 Conflict between obstacle and chase
Result
Pursue
Wall Avoidance
Target
Combining Steering Behavior

Blending Problems
 Constrained

Environments
Missing a narrow doorway
Result
Collision Ray
Combining Steering Behavior

Blending Problems
 Constrained

Environments
Long distance failure
Collision Ray
Combining Steering Behavior

Blending Problems
 Judder
Obstacle
Avoidance
Collision Ray
t=1
Combining Steering Behavior

Blending Problems
 Judder
No Obstacle
Avoidance
Collision Ray
t=5
Combining Steering Behavior

Blending Problems
 Judder
Obstacle
Avoidance
Collision Ray
t = 10
Combining Steering Behavior

Blending Problems
 Judder
t = 15
Combining Steering Behavior

Blending Problems
 Judder
t = 20
Combining Steering Behavior

Priority Behavior



Seek or Evade will always generate an acceleration
Collision avoidance, Separation, Arrive, ... will often not generate
an acceleration
When blending, give priority to latter components if they propose
an action


Example: Seek will almost always give maximum acceleration, but if
collision avoidance gives an acceleration, it should not be ignored.
Weighting might limit collision avoidance to 50% influence
Can deal with stable equilibria


At equilibrium, all accelerations are about balanced and total
acceleration is near-zero
Add a single behavior at lowest priority such as wandering
Combining Steering Behavior

Priority Behavior
 Can
use a fixed order
 Can use dynamic order

Different components return also a priority value


Collision avoidance might return square inverse of
distance to obstacle
Select behavior based on priority value
Collision avoidance has no influence if collision is long
away
 But becomes hugely important just before a collision
threatens

Combining Steering Behavior

Uncooperative Arbitration Methods
 Blending
 Priorities
Fixed priorities
 Flexible priorities


Cooperative Arbitration Methods
 Use
more complex decision making
processes
Physics Based Trajectory
Prediction
3D-movement
 Most common example:

 Shooting
or throwing objects
Characters should be able to shoot or throw
accurately
 Often, characters should be able to avoid incoming
fire

Physics Based Trajectory
Prediction

Projectile Trajectory
 Absent
air resistance, follows a parabola
t
p(t )  p(0)  sm ut  g
2
– position at time t
 u – firing position (normalized vector)
 g – force of gravity
 sm – muzzle speed
p
Physics Based Trajectory
Prediction

Predicting a landing spot
 Calculate height (solve for y-component)
 No solution: Projectile never reaches that height
 One solution: Projectile reaches height at its vertex
 Two solutions: Pick greater value


Greater value is for projectile descending.
If this value is negative, projectile has already passed the
height and will not reach it again
 Obtain

x-z positions of this point
Note: When a character wants to catch a ball,
height should be at chest
Physics Based Trajectory
Prediction

Firing solution

Consists of muzzle speed




Usually limited to one (guns) or a few values
And firing direction
Set d vector from start to end point
Find times when height is zero
g  d  sm  (g  d  s m ) 2  g d
2
timpact  2


2
2g
2
2
2
Select long or short time trajectory
Calculate firing trajectory
u
2
2d  gtimpact
2 sm timpact
Physics Based Trajectory
Prediction

Projectiles with Drag
 Physical reality is quite complex
 Drag gives a second order non-linear differential equations
 Rotation (such as a spinning golf ball) can create a lift
 Wind

Create a simplified Physics (a.k.a. cheat) or use
a numeric solution for trajetory calculation
 Calculate
trajectory in simplified model
 Adjust firing solution to create a new trajectory that fits
better
Jumping
Shooter games need jumping
 Jumping is not part of steering
mechanisms
 Jumps can be failures

 Character
tries to jump from one platform to
another but fails
 Cost of error larger than for steering

Slight errors when pursuing are corrected
Jumping

Character must set up for jump on the right, but
not on the left:
Jumping

Character uses velocity matching steering mechanism to
make the jump:

Character decides to take the jump

Pathfinding decides that character needs to jump,

this gives also type of jump
OR
 Simple steering mechanism drives character over edge,



this needs look ahead to determine type of jump
New steering behavior to do velocity matching to do jump
When character reaches jump point, new jump action is required
Jumping

Jumps are difficult to make
 if

good landing area is small
Create jump points for characters in level design
 Player
characters can try to make difficult jumps, but
AI characters cannot
 Minimize number of occasions where this limitation
becomes obvious

Level design needs to hide weaknesses in the AI
Jumping

Alternative uses pairs of jump points and
landing pads
 When
character decides to make the jump,
add additional step:

Use trajectory prediction code to calculate velocity
required to reach landing area


This allows characters to take their own physics (weight,
load, strength) into account
Use velocity matching steering algorithm
Jumping

Hole Fillers


Create an invisible jumpable gap as part of certain obstacles
Change obstacle avoidance behavior:




When detecting collision with a jumpable gap, character runs towards gap at
full speed.
Just before the gap, character leaps into air
Works well if landing area is large
Fails for small landing areas

In this case, ensure that level design does not have small landing areas.
Chasm
jumpable gap object
Coordinated Movement
Done by groups of characters
 Coordinated movement

 can
result from individual decisions
 can result from decisions made by group as a
whole
Coordinated Movement

Fixed formations
 Usually
with a designated leader
 Leader moves as an individual, everybody else
moves based on leaders position
 Actual position depends on number of characters
Line
Defensive circle
V or Finger
Four
Two abreast
in cover
Coordinated Movement

Emergent Formations
 Each

character has its own steering system
Arrive Behavior
 Characters
select their target based on other
characters in group
Allows characters to avoid obstacles individually
 Difficult to get rules that do not lead to pathological
formations

Coordinated Movement

Two-Level Formation Steering
 Have
pseudo-character that serves as
formation leader: anchor point
 Individual characters steer individually

Use arrival, avoidance, and separation behavior to
reach target slot
 Has
difficulties when characters run into
obstacles and cannot keep up with group
Coordinated Movement


Two-Level Formation Steering
Prevent problems for characters keeping up by


Slow the formation down (about half of character speed)
Moderate movement of formation based on current positions of
characters in slot

Reset kinematics of anchor point



Base position, orientation, velocity of anchor points on the average of
characters in the slot
 Choosing exactly the average means that characters are almost in
position, so that they move slowly towards their slot position.
 Anchor point moves even slower
 etc.
Move anchor point ahead of the average for moving formations
Set anchor point to average for stationary formations
 Ensure that anchor point orientation is average orientation of slots,
or formation will spin around
Coordinated Movement

Extension of coordination to more than two
levels
 Needed

for military simulation games with lots of units
Consult public military manuals how to organize a platoon in
different squads
 Slot
positions now distinguish between roles of
characters:

E.g. Fire teams, squad leader, communication, platoon
leader, heavy weapons team, …
Coordinated Movement

Dynamic slots and playbooks
 Not
all games can use constant formations
 Slots can be dynamic
E.g. Fielders in a textbook baseball double play
 E.g. Corner kick strategies in soccer

Coordinated Movement

Tactical Movement
 Squads
in dangerous terrain collaborate with
other squads
One squad moves
 Other squad(s) provide lookout and fire cover

Motor Control
Interpret output from steering behavior as
movement requests
 Character (such as a car) might not be
able to satisfy this request by laws of
physics

Movement
request
Motor Control

Output Filtering
 Filter
movement request components to suppress
impossible ones


Divide component in lateral and forward component
Filter out much of lateral component
Filter out much of
lateral component
Movement
request
Motor Control

Output Filtering
 Filter
movement request components to
suppress impossible ones
 Resulting acceleration can be very small

In our example, this does not look to bad, because
car needs to start moving slowly
Resulting
Acceleration
Motor Control

Output Filtering
 Occasionally

leads to desirable behavior
Example: J-turn

Pursuing
Car
Police car backs up and then rushes forward after the
speeding German tourists
Target
Motor Control

Output Filtering
 Can

be pathological
Example: Filtering leads to zero acceleration.

Tourists speed away
Pursuing
Car
movement request
Target
Motor Control

Output filtering
 Tends

to work unless:
small margin of error in steering requests
Driving at high speed
 Maneuvering through tight spaces
 Matching motion to jumping

 Filtering
problems such as zero acceleration
can be solved by heuristics

“Speed forward”
Motor Control

Capability sensitive steering
 AI
now takes capabilities of characters into
account
E.g.: Pursuing character chooses among a set of
feasible maneuvers
 Tends to work if there are few alternatives

Motor Control

Capability sensitive steering
 AI
now takes capabilities of characters into
account
skidding
car
Target
Motor Control

Capability sensitive steering
 Avoidance
algorithm creates unrealistic
steering
skidding
car
Target
Motor Control

Capability sensitive steering
 Creates

more realistic solution
Car accelerates to avoid obstacle
skidding
car
Target
Motor Control

Capability-sensitive steering
 Is
difficult when several steering behaviors
need to be combined
 Best practice:

Leave actuation to the last step
Motor Control

Common actuation properties:
 Humans
 Can turn fast at low speed
 Can sidestep or turn on the spot if stationary or slowly
moving
 Cars and Motorbikes
 Cannot turn while stationary
 Turning radius more extended with increased speed
 Can brake faster than accelerate when traveling in a straight
line
 Cannot travel quickly backward (motorbikes not at all)
 Tracked vehicles
 Can completely turn at low speeds
 Turning capabilities limited by grip at high speeds.
Pathfinding for
Gaming
Artificial Intelligence
Graph Generation

For many situations, approximating a
layout with a graph is sufficient
A* Heuristics




A good heuristics is crucial for performance
Optimal path results from a heuristics that
always under-estimates the actual path length
The closer a heuristics is to true distance, the
faster the algorithm performs
Sometimes performance is more importance
than optimality:
 Pick
a good heuristics that sometimes underestimates distance and gives a non-optimal path
A* Heuristics

Euclidean distance can be misleading
A* Heuristics

Cluster Heuristics
 Agglomerate
related vertices into clusters
H
C
G
F
B
A
A* Heuristics

B
C
B
0
C
9
A
F
G
H
9
2
2
5
0
2
8
15
within cluster
is estimated to zero
 Distances between
clusters is in a look-up
table
H
0
F
2
2
0
6
9
G
2
8
6
0
2
H
5
15
9
2
0
I
0
C
G
F
B
I
0
E
 Distance
E
0
D
Cluster Heuristics
D
World Representation

Pathfinding uses a reduction of game level to a graph

Graph can be designed by level designer,


By automatic tools,





Dirichlet Domains
Tile graphs
Points of visibility
Polygonal meshes
Or by augmenting tools with manual supervision
Criteria for world representation

Validity


Paths need to be doable
Usefulness


Real Time Strategy (RTS) game with hundreds of thousands of tiles cannot
use them for pathfinding
Pathfinding results might appear blocky and irregular
World Representation

Dirichlet Domains a.k.a.
Voronoi polygon
 Given
a finite set of source
points, a Dirichlet domain is
the set of all points closest to
a given source point
 Metric might be nonstandard
 Connections are placed
between neighboring
domains
World Representation

Dirichlet Domain
 Often
specified by artist for level design
because automatic generation is slow
 Pathfinding solution might not be feasible
Traveling to two adjacent Dirichlet domains might
in actuality lead through a third domain that is
impassable
 In practice, seems to work very well

 Pathfinding
itself is fast
World Representation

Points of Visibility

Place nodes (aka waypoints) at important locations


Form graph from these nodes:




Place edges whenever two nodes can see each other
Precompute optimal travel between waypoints
Or rerun algorithm on waypoint graph
Simple navigation from A to B




Such as the center points of Dirichlet domains
Move to nearest waypoint to A.
Move along path between waypoints
Move from nearest waypoint to B to B itself
Can use path smoothing to make walk look more realistic
World Representation

Points of Visibility
 Optimal
paths in 2D run
along inflection points

Inflection points are those
where path curves
 Inflection
points located at
convex corners of
obstacles
 Create nodes there
 Move them away for
characters with thickness
B
optimal path
A
World Representation

Polygonal Meshes
 Created
by level designer as a mesh
World Representation

Non-translation
 Nodes
do not have to reflect position but can
embody more information

Example: Slow moving ship
Nodes reflect position and direction
 Pathfinding find a way for the ship to be in the correct
position and be correctly oriented

Hierarchical Pathfinding

Higher level of hierarchy has nodes that
represent a cluster of nodes of the lower
hierarchy
Hierarchical Pathfinding

Connection costs at higher level
 At

the lowest level:
Depends on where you leave and enter a given node group
 Minimum
Distance between two nodes in group A and
B
 Maximin Distance:


Determine the minimum distance for each node in A to B
Then return the maximum
 Average
Minimum Distance
Hierarchical Pathfinding

Strange Effects:
 Circuitous
Paths
High Level Plan
Hierarchical Pathfinding

Strange Effects:
 Circuitous
Paths
Better Plan Missed
Hierarchical Pathfinding

Strange Effects
 Minimum

Tends to visit to many higher level nodes
 Maximin

distance
distance
Tends to go for the most direct path at the higher
level
Continuous Time Pathfinding

Pathfinding has difficulties with dynamic
scenarios
 Police
car chasing a suspect on an LA
freeway
Path now has a time component
 Create nodes that abstract both time and
location

 Leads
to very dense, populated graphs
Movement Planning

Animations
 Modeling
the character as a point can look
bad
Going up stairs
 Stepping over stepping stones

Movement Planning

Animations
 Create
different velocity ranges based on
current position of character
running
 walking
 creeping
 turning
 sidestepping

Movement Planning

Create Planning Graph
 Nodes
incorporate different location and
different stances
 Edges represent various transitions
“Get up”
 Walk
 Run

Movement Planning

Footfalls
 Determine
where character will plant feet