Transcript Autonomous Game Agents

Autonomous Game Agents
CIS 479/579
Bruce R. Maxim
UM-Dearborn
3/21/2017
1
Agent Movement Layers
• Action Selection
– Agent chooses goals and decides which plan to
follow (e.g. do A, B, and then C)
• Steering
– Calculating desired trajectories needed to satisfy
the goals and plans from action layer
• Locomotion
– Mechanical (how) aspects of the agent’s
movement (allows body type customization)
3/21/2017
2
Problems
• Implementing steering behaviors brings new
challenges to game programmers
• Some behaviors requires lots of manual
tweaking to look right
• Need to avoid using lots of CPU time
• When combining behaviors, it is possible that
they may accidentally cancel each other out
3/21/2017
3
The code examples come from
the Buckland text
3/21/2017
4
Vehicle Model - 1
• This class handles the location layer
• All moving game agents are derived from the
MovingEntity class which is itself derived from
the BaseGameEntity class the critical data
attributes include
–
–
–
–
–
3/21/2017
ID
type
position
bounding radius
scale
5
Vehicle Model - 2
• The vehicle’s heading and side vectors are
used to define a local coordinate system and
will be updated by the steering algorithms
every frame
• The vehicle’s heading will always be aligned
with its velocity
• The Vehicle class is derived from the class
MovingGameEntity and inherits its own
instance of the SteeringBehavior class
3/21/2017
6
Vehicle Model - 3
• The Vehicle class contains a pointer to a
GameWorld class instance to enable access
to all pertinent obstacle, path, or agent data
• Physics updating is handled by the
Vehicle::Update method
• The display area is assumed to wrap around
itself (left to right and top to bottom)
3/21/2017
7
Update - 1
// Updates the vehicle's position from a series of steering behaviors
void Vehicle::Update(double time_elapsed)
{
//update the time elapsed
m_dTimeElapsed = time_elapsed;
//keep a record of its old position to allow later update
Vector2D OldPos = Pos();
Vector2D SteeringForce;
//calculate combined force from steering behaviors in vehicle's list
SteeringForce = m_pSteering->Calculate();
//Acceleration = Force/Mass
Vector2D acceleration = SteeringForce / m_dMass;
//update velocity
m_vVelocity += acceleration * time_elapsed;
//make sure vehicle does not exceed maximum velocity
m_vVelocity.Truncate(m_dMaxSpeed);
//update the position
m_vPos += m_vVelocity * time_elapsed;
3/21/2017
8
Update - 2
//update the heading if the vehicle has a non zero velocity
if (m_vVelocity.LengthSq() > 0.00000001)
{
m_vHeading = Vec2DNormalize(m_vVelocity);
m_vSide = m_vHeading.Perp();
}
//Enforce NonPenetration constraint, treat screen as a toroid
WrapAround(m_vPos, m_pWorld->cxClient(), m_pWorld->cyClient());
//update vehicle's current cell if space partitioning is turned on
if (Steering()->isSpacePartitioningOn())
{
World()->CellSpace()->UpdateEntity(this, OldPos);
}
if (isSmoothingOn())
{
m_vSmoothedHeading = m_pHeadingSmoother->Update(Heading());
}
}
3/21/2017
9
Seek
// Given a target, this behavior returns a steering force which will
// direct the agent towards the target
Vector2D SteeringBehavior::Seek(Vector2D TargetPos)
{
Vector2D DesiredVelocity =
Vec2DNormalize(TargetPos - m_pVehicle->Pos())
* m_pVehicle->MaxSpeed();
return (DesiredVelocity - m_pVehicle->Velocity());
}
// Left mouse button controls the target position
// Overshoot is determined by values of MaxSpeed (use Ins/Del keys)
// and MaxForce (use Home/End keys)
3/21/2017
10
Flee
// Given a target, this behavior returns a steering force which will
// direct the agent away from the target
Vector2D SteeringBehavior::Flee(Vector2D TargetPos)
{
//only flee if the target is within 'panic distance'. Work in distance
//squared space (to avoid needing to call the sqrt function
const double PanicDistanceSq = 100.0f * 100.0;
if (Vec2DDistanceSq(m_pVehicle->Pos(), target) > PanicDistanceSq)
{
return Vector2D(0,0);
}
Vector2D DesiredVelocity = Vec2DNormalize(m_pVehicle->Pos() - TargetPos)
* m_pVehicle->MaxSpeed();
return (DesiredVelocity - m_pVehicle->Velocity());
}
// Left mouse button controls the target position
// Overshoot is determined by values of MaxSpeed (use Ins/Del keys)
// and MaxForce (use Home/End keys)
3/21/2017
11
Arrive - 1
// Similar to seek but it tries to arrive at target with a zero velocity
Vector2D SteeringBehavior::Arrive(Vector2D TargetPos,
Deceleration deceleration)
{
Vector2D ToTarget = TargetPos - m_pVehicle->Pos();
//calculate the distance to the target
double dist = ToTarget.Length();
if (dist > 0)
{
//value is required to provide fine tweaking of the deceleration.
const double DecelerationTweaker = 0.3;
//calculate speed required to reach target given desired deceleration
double speed = dist / ((double)deceleration * DecelerationTweaker);
3/21/2017
12
Arrive - 2
//make sure the velocity does not exceed the max
speed = min(speed, m_pVehicle->MaxSpeed());
//similar to Seek don't need to normalize the ToTarget vector
//because we have calculated its length: dist.
Vector2D DesiredVelocity = ToTarget * speed / dist;
return (DesiredVelocity - m_pVehicle->Velocity());
}
return Vector2D(0,0);
}
3/21/2017
13
Illusion of Pursuit
• Don’t simply seek old enemy position
• Need to run toward enemy’s new position
based on observed movement
• The trick is trying to figure out how far in the
future to predict movement
• Might also add to the realism of the behavior
if some time were added to slow down, turn,
and accelerate back to speed
3/21/2017
14
Pursuit
// Creates a force that steers the agent towards the evader
Vector2D SteeringBehavior::Pursuit(const Vehicle* evader)
{
//if evader ahead and facing agent then seek evader's current position.
Vector2D ToEvader = evader->Pos() - m_pVehicle->Pos();
double RelativeHeading = m_pVehicle->Heading().Dot(evader->Heading());
if ( (ToEvader.Dot(m_pVehicle->Heading()) > 0) &&
(RelativeHeading < -0.95)) //acos(0.95)=18 degs
{
return Seek(evader->Pos());
}
//Not considered ahead so we predict where the evader will be.
//lookahead time is proportional to the distance between evader and
//pursuer; and inversely proportional to sum of agent's velocities
double LookAheadTime = ToEvader.Length() /
(m_pVehicle->MaxSpeed() + evader->Speed());
//now seek to the predicted future position of the evader
return Seek(evader->Pos() + evader->Velocity() * LookAheadTime);
}
3/21/2017
15
Evade
// agent Flees from the estimated future position of the pursuer
Vector2D SteeringBehavior::Evade(const Vehicle* pursuer)
{
// no need check for facing direction (unlike pursuit)
Vector2D ToPursuer = pursuer->Pos() - m_pVehicle->Pos();
//Evade only considers pursuers within a 'threat range'
const double ThreatRange = 100.0;
if (ToPursuer.LengthSq() > ThreatRange * ThreatRange)
return Vector2D();
// lookahead time is propotional to distance between evader and
// pursuer; and inversely proportional to sum of agents' velocities
double LookAheadTime = ToPursuer.Length() /
(m_pVehicle->MaxSpeed() + pursuer->Speed());
//now flee away from predicted future position of the pursuer
return Flee(pursuer->Pos() + pursuer->Velocity() * LookAheadTime);
}
3/21/2017
16
Illusion of Wandering
• Make agent appear to follow a random walk
through game environment
• Do not calculate a random steering force
each step or you will get spastic agent
behavior and no persistent focused motion
• One technique to avoid the jitters is to project
an imaginary target moving on a circular path
having a fixed wander radius (but moving
center) in front of the agent and let the agent
seek
3/21/2017
17
Wander - 1
// This behavior makes the agent wander about randomly
Vector2D SteeringBehavior::Wander()
{
//this behavior is dependent on the update rate, so this line must
//be included when using time independent framerate.
double JitterThisTimeSlice =
m_dWanderJitter * m_pVehicle->TimeElapsed();
//first, add a small random vector to the target's position
m_vWanderTarget += Vector2D(RandomClamped() * JitterThisTimeSlice,
RandomClamped() * JitterThisTimeSlice);
//reproject this new vector back on to a unit circle
m_vWanderTarget.Normalize();
//increase length of vector to be same as radius of wander circle
m_vWanderTarget *= m_dWanderRadius;
3/21/2017
18
Wander - 2
//move the target into a position WanderDist in front of the agent
Vector2D target = m_vWanderTarget + Vector2D(m_dWanderDistance, 0);
//project the target into world space
Vector2D Target = PointToWorldSpace(target,
m_pVehicle->Heading(),
m_pVehicle->Side(),
m_pVehicle->Pos());
//and steer towards it
return Target - m_pVehicle->Pos();
}
// Green circle is “Wander Circle” and the dot is the target
// Can control radius, distance, and jitter using keyboard
3/21/2017
19
Obstacle Avoidance
• Obstacles are any game objects that can be
approximated using circle in 2D or a sphere
in 3D
• The goal is to apply an appropriate steering
force to keep a bounding box (2D)
surrounding the agent (or bounding
parallelepiped in 3D) from intersecting any
obstacles
• The box width matches bounding radius and
length is proportional to agent speed
3/21/2017
20
Find Closest Intersection Point
• Vehicle only needs to consider the obstacles within
range of its detection box (needs to iterate though list
and tag obstacles in range)
• Tagged obstacles positions transformed to vehicle
local space (allows negative coordinates to be
discarded)
• Check for detection box and bounding circle overlap
(reject any with y values smaller than half the width of
the detection box)
• Apply appropriate steering force to prevent collision
with nearest obstacle
3/21/2017
21
Steering Force
• Two parts: lateral force and braking force
• To adjust the lateral force simply subtract the
obstacle’s local position form its radius (can
be scaled by the distance from obstacle)
• The braking force is directed horizontally
backward from the obstacle (its strength
should be proportional to the distance)
• Let’s look at the code
3/21/2017
22
Wall Avoidance
• Wall is line segment (2D) with normal pointing
in the direction it faces (polygon in 3D)
• Steering is accomplished using 3 feelers
projected in front of agent and testing for wall
intersections
• Once closest intersection wall is found a
steering force is calculated (scaled by
penetration depth of feeler into the wall)
• Let’s look at the code
3/21/2017
23
Interpose - 1
// returns force that attempts to position vehicle between 2 others
// demo shows red vehicle trying to come between two blue wanderers
Vector2D SteeringBehavior::Interpose(const Vehicle* AgentA,
const Vehicle* AgentB)
{
//first we need to figure out where the agents are going to be at
//time T in the future. Approximate by determining the time taken to
//reach the midway point at the current time at at max speed.
Vector2D MidPoint = (AgentA->Pos() + AgentB->Pos()) / 2.0;
double TimeToReachMidPoint =
Vec2DDistance(m_pVehicle->Pos(),MidPoint) / m_pVehicle->MaxSpeed();
3/21/2017
24
Interpose - 2
//assume that agent A and agent B will continue on a straight
//trajectory and extrapolate to get their future positions
Vector2D APos = AgentA->Pos() +
AgentA->Velocity() * TimeToReachMidPoint;
Vector2D BPos = AgentB->Pos() +
AgentB->Velocity() * TimeToReachMidPoint;
//calculate the mid point of these predicted positions
MidPoint = (APos + BPos) / 2.0;
//then steer to Arrive at it
return Arrive(MidPoint, fast);
}
3/21/2017
25
Hide
• Goal is to position vehicle so that obstacle is
between itself and the hunter
– Determine a hiding spot behind each obstacle
using GetHidingPosition
– The Arrive method is used to steer to the closest
hiding point
– If no obstacles are available the Evade method is
used to avoid hunter
• Let’s look at the code
3/21/2017
26
Path Following
• Creates a steering force that moves a vehicle
along a series of waypoints
• Paths may be open or closed
• Can be used for agent patrol routes or
racecar path around a track
• Helpful to have a path class that stores
waypoint list and indicates “open” or “closed”
• Then Seek or Arrive can be used to get the
desired path following behavior
3/21/2017
27
FollowPath - 1
// Given a series of Vector2Ds, this method produces a force that will
// move the agent along the waypoints in order. The agent uses the
// 'Seek' behavior to move to the next waypoint - unless it is the last
// waypoint, in which case it 'Arrives'
Vector2D SteeringBehavior::FollowPath()
{
//move to next target if close enough to current target (working in
//distance squared space)
if(Vec2DDistanceSq(m_pPath->CurrentWaypoint(), m_pVehicle->Pos())
< m_dWaypointSeekDistSq)
{
m_pPath->SetNextWaypoint();
}
3/21/2017
28
FollowPath - 2
if (!m_pPath->Finished())
{
return Seek(m_pPath->CurrentWaypoint());
}
else
{
return Arrive(m_pPath->CurrentWaypoint(), normal);
}
}
3/21/2017
29
Offset Pursuit
• Calculates a steering force to keep an agent
at a specified distance from a target agent
–
–
–
–
Marking opponents in sports
Docking spaceships
Shadowing aircraft
Implementing battle formations
• Always defined in leader space coordinates
• Arrive provides smoother behavior than Seek
3/21/2017
30
OffsetPursuit
// Keeps a vehicle at a specified offset from a leader vehicle
Vector2D SteeringBehavior::OffsetPursuit(const Vehicle* leader,
const Vector2D offset)
{
//calculate the offset's position in world space
Vector2D WorldOffsetPos =
PointToWorldSpace(offset, leader->Heading(),
leader->Side(),leader->Pos());
Vector2D ToOffset = WorldOffsetPos - m_pVehicle->Pos();
//lookahead time is propotional to distance between leader and
//pursuer; inversely proportional to sum of both agent velocities
double LookAheadTime = ToOffset.Length() /
(m_pVehicle->MaxSpeed() + leader->Speed());
//now Arrive at the predicted future position of the offset
return Arrive(WorldOffsetPos +
leader->Velocity() * LookAheadTime, fast);
}
3/21/2017
31
Flocking
• Emergent behavior that appears complex and
purposeful, but is really derived from simple rules
followed blindly by the agents
• Composed out of three group behaviors
– Cohesion (steering toward neighbors’ center of mass)
– Separation (creates force that steers away from neighbors)
– Alignment (keeps agent heading in the same direction as
neighbors)
• Flocking demo allows us to examine the effects of
each and experiment
• The code for each function is defined separately
3/21/2017
32
Combining Steering Behavior
• In an FPS you might want a bot that
combines path following, separation, and
wall avoidance
• In an RTS you might want a group of bots to
flock together while wandering, avoiding
obstacles, and evading enemies
• The steering class used in Buckland allows
you to turn on the behaviors you want for
each class instance and combine them when
computing the appropriate steering force
3/21/2017
33
Remaining slides are incomplete
3/21/2017
34
Combination Strategies
• Weighted truncated sum
• Weighted truncated sum with pioritization
• Prioritized dithering
3/21/2017
35
Ensuring Zero Overlap
• Add non-penetrating constraint
3/21/2017
36
Spatial Partitioning
• If you have lot of agents and you need to check all for
neighbors this requires O(n2)
• The cell space partitioning method can reduce the
checks to O(n)
– Check agents bounding radius to see which cells it intersects
in the world grid
– These cells are checked of presence of agents
– All nearby agents in range are added to the neighbor list
• You can observe the effects of turning cell
partitioning on and off in Another_Big_Shoal.exe
3/21/2017
37
Smoothing
• Judders can be caused by two conflicting
behaviors obstacle avoidance (turn away
from enemy) and seek (no threat turn back to
original direction of travel)
• You could decouple the heading form the
velocity vector and base the heading on the
average of several recent steps
3/21/2017
38