Transcript week03 - AI Wisdom

Artificial Intelligence in Games
Class 3
Steve Rabin
[email protected]
www.aiwisdom.com/uw
1
Project 1: State Machines



Assigned week 2, Due week 4
Download sample from webpage
Put USERTYPE.DAT file in directory:


C:\Program Files\Microsoft Visual Studio
8\Common7\IDE
Extra documentation in readme.txt

Worth reading to get familiar with structure
2
Project 1:
State Machines Grading

(80%) Have at least 4 NPCs doing something
interesting


At least 3 state machines, with at least 15 states
among them
Use at least 10 different examples of the following:


Substates, a Global Message Response other than
MSG_Reset or MSG_MouseClick, SendMsgDelayedToState,
ChangeStateDelayed, PopState, ReplaceStateMachine,
PushStateMachine, PopStateMachine, RequeueStateMachine,
data passed in msg, MarkForDeletion, OnCCMsg,
SendMsgBroadcastToList, SetTimer or
OnPeriodicTimeInState, OnTimeInState, or a persistent state
variable such as DeclareStateInt.
(-5% for each missing, list the file and line number of each
that you use to get credit!)
3
Project 1:
State Machines Grading

(20%) Draw UML diagram of state machines you
create




(-5% for each missing: Proper starting state indicator,
all transitions labeled, all states labeled)
(-5% for each missing state, -10% for each missing
state machine)
Turn in hardcopy on paper
Late assignments are penalized 10% per day

If late, turn in UML diagram at the next class
4
Project 1: State Machines:
Extra Credit (1)

(Extra Credit 10% for each one, max 20%)


Implement Formations (not leader
following/queuing), Flocking, or Patrolling using
queued state machines
(Extra Credit 5%)


First to find a particular significant bug in the
State Machine Language engine (not the entire
project) – max 15% per person
E-mail me at [email protected]
5
Project 1: State Machines:
Extra Credit (2)
(Extra Credit 10%) Answer the following questions about persistent state
variables (like DeclareStateInt)
1. What is the C++ language mechanism that allows a persistent state variable to behave
like a first-class type? (For example, how myVar declared with
DeclareStateInt(myVar) can act like an int.)
2. Why does a persistent state variable need a backing store?
3. At what time does the backing store of a persistent state variable get created?
4. Where is the backing store of a persistent state variable?
5. How is a persistent state variable indexed in the backing storage? More specifically,
how is the name of the variable correlated with the index?
6. Within a state, when a persistent variable gets a value assigned to it, where does this
value get stored?
7. At what point does a persistent variable that's been altered store it's value in the
backing store?
8. What happens to the backing storage after a state change? (look in
StateMachine::PerformStateChanges)
9. What is the overhead of using a persistent state variable compared with a class
member variable?
10. What is the passive overhead of supporting persistent state variables in SML (for
example, if persistent state variables are never used)?
11. Describe two (2) reasons to use a persistent state variable instead of a class member
variable.
6
Project 1: State Machines
Turn-In Instructions

Zip up everything and send to [email protected]




Create a readme.txt and write:






All code, resource files, and exe
(-10% if I can't double click exe and run)
(-10% for large unnecessary files: ".ncb" file, hidden subversion
directories/files, no Debug/Release dir)
One paragraph about what you implemented
One paragraph (and/or bullet points) explaining directions
One paragraph about your experience working on this project
(problems, insights, difficulty, number of hours spent)
List the 10 features you chose to implement and which file and line
number I can find each one (-10% for each missing or each missing
listing)
Thoroughly describe any attempted extra credit along with any special
directions to work it or view it
UML diagrams

Hardcopy on paper
7
Recommended Reading

Artificial Intelligence for Games

Chapter 4: Pathfinding
8
Design Patterns and
Programming Languages


http://newbabe.pobox.com/~mjd/blog/2006/09/11/#design-patterns
Peter Norvig's presentation on "Design
Patterns in Dynamic Languages" describes
three "levels of implementation of a pattern":

Invisible


Formal


So much a part of language that you don't notice
Implement pattern itself within the language
Instantiate/call it for each use
(as with macros)
Informal

Design pattern in prose; refer to by name, but must be
reimplemented from scratch for each use
9
Design Patterns and
Programming Languages
Recurring problem: Two or more parts of a machine language
program need to perform the same complex operation.
Duplicating the code to perform the operation wherever it is
needed creates maintenance problems when one copy is
updated and another is not.
Solution: Put the code for the operation at the end of the program.
Reserve some extra memory (a "frame") for its exclusive use.
When other code (the "caller") wants to perform the operation,
it should store the current values of the machine registers,
including the program counter, into the frame, and transfer
control to the operation. The last thing the operation does is to
restore the register values from the values saved in the frame
and jump back to the instruction just after the saved PC value.
This is a "pattern"-style description of the pattern we now know as
"subroutine".
10
Macro Trick for in-sync
Enumerations and Strings
(the file msgnames.h)
REGISTER_MESSAGE_NAME(MSG_CheckTouch)
REGISTER_MESSAGE_NAME(MSG_Tagged)
REGISTER_MESSAGE_NAME(MSG_SetTargetPosition)
REGISTER_MESSAGE_NAME(MSG_Arrived)
REGISTER_MESSAGE_NAME(MSG_Reset)
REGISTER_MESSAGE_NAME(MSG_MouseClick)
11
Macro Trick for in-sync
Enumerations and Strings
//Create enumeration from msgnames.h
#define REGISTER_MESSAGE_NAME(x) x,
typedef enum
{
#include "msgnames.h"
MSG_NUM
} MSG_Name;
#undef REGISTER_MESSAGE_NAME
12
Macro Trick for in-sync
Enumerations and Strings
//Create strings from msgnames.h
#define REGISTER_MESSAGE_NAME(x) #x,
static const char* MessageNameText[] =
{
#include "msgnames.h"
"Invalid"
};
#undef REGISTER_MESSAGE_NAME
13
Reactive Movement
and
Steering Behaviors
14
Movement

Two types


Reactive movement
Planned movement
15
Steering Behaviors:
Physics Model

Simple Vehicle Model



orientation, mass, position, velocity
max_force, max_speed
Forward Euler Integration




steering_force = truncate (steering_dir, max_force)
acceleration = steering_force / mass
velocity = truncate (velocity + acceleration, max_speed)
position = position + velocity
16
Steering Behaviors:
Seek and Flee



Seek – Steer toward goal
Flee – Steer away from goal
Steering force is the difference between current velocity
and desired velocity

Blue is steering force, magenta is velocity
17
Steering Behaviors:
Pursue and Evade



Based on underlying Seek and Flee
Pursue – Predict future interception position of target
and seek that point
Evade – Use future prediction as target to flee from
18
Steering Behaviors:
Wander

Type of random steering with long term order



Steering is related from one frame to another
Maintains state
Red dot is wander direction


Constrained to be on black circle
Randomly moves within white circle each frame
19
Steering Behaviors:
Arrival


Goal to arrive at target with zero velocity
Red circle is maximum distance before
slowing down
20
Steering Behaviors:
Obstacle Avoidance



White box is future path
Steering force strictly left or right
Braking force stronger as collision gets closer
21
Steering Behaviors:
Containment




General obstacle avoidance
Object is contained within the surface
Blue object has a random probe
Green object has three probes


More robust
Three times the work per frame
22
Steering Behaviors:
Wall Following


Move parallel and offset from gray areas
Goal to remain given distance from wall




Predict object’s future position (black dot)
Project future position to wall
Move out from wall set amount from normal
Seek toward new point (red circle)
23
Steering Behaviors:
Path Following


Path is connected line segments with radius
Corrective steering only when varying off of path



Red dot future predicted position
Red circle is closest spot on path
Corrective steering toward white circle farther down path
24
Steering Behaviors:
Flow Field Following



Steer to align motion with local tangent of the flow field
Field could be time-varying
Black circle is predicted future position where sample is
taken
25
Steering Behaviors:
Flow Field Mathematics (AIW3 Ch3.1)

Bilinear interpolation
tx 
ty 
S x  P0 x
P1x  P0 x
S y  P0 y
P2 y  P0 y
R  1  t y   1  t x   P0  t x  P1   t y  1  t x   P2  t x  P3 
26
Steering Behaviors:
Avoidance using Flow Fields (Bloodwake)
27
Steering Behaviors:
Avoidance: T-Bone vs Sweeping w/ Flow Field
28
Steering Behaviors:
Path Smoothing via Flow Fields
29
Combined Steering Behaviors:
Group Path Following

Path following with separation steering


Combined with weighted sum
Path following has 3 times weight as separation
30
Combined Steering Behaviors:
Leader Following (Group)

Combines separation and arrival


Arrival target is a point offset slightly behind the leader
Followers must move out of leader’s future path
31
Combined Steering Behaviors:
Leader Following (Queue)

Combines separation and arrival

Each object has a different leader
32
Combined Steering Behaviors:
Unaligned Collision Avoidance



Objects moving in all directions (unaligned)
Combines containment and avoidance
Future collisions predicted and objects steer away from
collision site, or speed-up / slow-down
33
Combined Steering Behaviors:
Queuing

Seek doorway, Avoid gray walls, Separation from
each other, Braking if others nearby or in front
34
PID Controller for Steering




Proportional-Integral-Derivative
Feedback-based algorithm
50 year old technique
Used in Need for Speed Underground
series to steer cars
35
PID Controller for Steering
1st term is proportional to the current error
2nd term is proportional to the integral of the error
3rd term is proportional to the derivative of the error
error (t )  measured (t )  desired (t )
d
output (t  1)  c p  error (t )  ci   error (t )dt  c d  error (t )
dt
1st is value of current error
2nd is last several values of the error, multiplied by their time-steps,
and all added up
3rd is approximated by taking the current error, subtracting previous
error, and dividing by time-step
36
Flocking
37
Flocking
38
Flocking
39
Flocking

First demonstrated by Craig Reynolds in his 1987
SIGGRAPH paper and movie




Used to give flocks of birds and schools of fish eerily
realistic movement
Won an Oscar in 1997 for his flocking work




(Scientific and Technical Award)
Flocking is an example of emergent behavior (a-life)


“Flocks, Herds, and Schools: A Distributed Behavior Model”
Film (Stanley and Stella in "Breaking the Ice"
Simple individual rules result in complex group behavior
Individual creatures often called “boids”
PS2 technical demo
OpenSteer demo
40
Flocking:
Boids


Term “boids” often used
Three sources for the term boid:
1. “Boid” is an abbreviation of “birdoid” from flocking birds
2. Primitive ellipsoid shapes for modeling were called “soids”
from Tom Duff at the New York Institute of Technology
3. In the Mel Brooks film “The Producers” there was a scene
complaining about pigeons on the roof:
“You used to be able to sit on the stoop like a normal person,
but not any more, ‘cause of da BOIDS. Dirty, lousy, stinkin’
BOIDS.”
41
Flocking:
Three simple rules
Separation
Alignment
Cohesion
42
Flocking:
Other Rules?


What if there
are obstacles?
Where do
these flocks go?



Birds
Fish
Herds
43
Flocking:
Other “Rules”



Obstacle avoidance
Changing goals
Wandering
44
Flocking:
Computational Difficulties



What if the flock is really big?
What if the objects are irregular?
What if there are “U” shaped obstacles?
45
Flocking:
Making it Look Good

Each boid should have random properties
(within a small range)



Speed
Acceleration
Change goal often
46
Flocking:
What about this Flock?
47
Alternative to Flocking:
Simple Swarms



Computationally simpler
Doesn’t enforce separation or
interpenetration
Example

Hundreds of spiders crawling around, up
walls, and dropping from the ceiling
– Tom Scutt, Tomb Raider series
48
Simple Swarms
attacking Player

Outer zone



Inner zone


If heading toward player: waver heading
If heading away: steer toward player
Swirl around player
Flee after random amount of time
49
Swarm Intelligence

Technique based on collective behavior in
decentralized, self-organized systems



Simple agents interact locally
Global behavior emerges




Beni & Wang (1989)
Ant colonies
Bird flocking
Animal herding
Swarm Robotics

Combining swarm intelligence with robotics
50
Swarm Intelligence

The U.S. military is investigating swarm techniques
for controlling unmanned vehicles.

NASA is investigating the use of swarm technology
for planetary mapping.


A 1992 paper by M. Anthony Lewis and George A.
Bekey discusses the possibility of using swarm
intelligence to control nanobots within the body for
the purpose of killing cancer tumors.
Swarm technology is particularly attractive because it
is cheap, robust, and simple.
51
Formations



Mimics military formations
How is it similar to flocking?
How is it different from flocking?
52
Formations

Issues






Is there a leader?
Where do individuals steer towards?
What happens when they turn?
What happens when they change heading
by 180 degrees?
What happens when there is a narrow pass?
Formation splitting and reforming?
53
Intermission
54
General Debugging

Five step process



1. Reproduce problem consistently
2. Collect clues
3. Pinpoint error




Propose hypothesis or
Divide and conquer
4. Repair the problem
5. Test the solution
55
Debugging Tips











Question assumptions
Minimize interactions and interference
Minimize randomness
Break up complex code into steps
Check boundary conditions
Disrupt parallel computations
Exploit tools in the debugger
Check code that has recently changed
Explain the bug to someone else
Debug with a partner
Get outside help
56
Tough Debugging Scenarios

Bug exists in Release but not Debug


Bug exists on final hardware, not dev-kit


Record as much info when it does happen
Unexplainable behavior


Timing or memory overwrite problem
Intermittent problems


Find out how they differ – usually memory size / disk (no seek)
Bug disappears when changing something
innocuous


Uninitialized data or optimization issue (inlining)
Retry, Rebuild, Reboot, Reinstall
Internal compiler errors

Full rebuild, divide and conquer, try other machines, compiler
updates
57
General Diagnostics







Alter variables at run-time
Visual AI diagnostics
Logging capability
Recording and playback ability
Track memory allocation
Print lots of info on crash
Educate entire team (testers, artists,
designers, producers)
58
Prevention of Bugs











Set compiler to highest warning level
Set compiler warnings to be errors
Compiler on multiple compilers
Write your own memory manager
Use asserts to verify assumptions (squeeze more)
Initialize variables when they are declared
Bracket loops and if statements
Use cognitively different variable names
Avoid identical code in multiple places
Avoid magic (hardcoded) numbers
Verify code coverage when testing
59
AI Diagnostics


Debugger is great, but…
Need to:



Monitor changes over time
Visualize spatial relationships
Primitives: Lines, Arrows, Text
60
AI Diagnostics




Identify Unit
Statistics
AI State
View Pathfinding




Process, Result, Final
View Past Visited
View Tactical Info
View Current Target







View Patrols
View Leader
View Sensory
View Anims / Audio
View Player
Commands
Show Fire Arcs
Considered
Show Tracers
61
62
63
64
65
66
67
68
69
AI Diagnostics (CLI)







Destroy
Invulnerable
Stop Movement
Freeze
Blind, Deaf,
Insensate
Duplicate
Forget








Reset
Modify State
Set Target
Change Game Speed
Teleport to Location
Follow
Switch Player Control
Spawn Objects
70
Strategy AI Spectrum
Soren Johnson (GDC2008)
"Good"
"Fun"
71
Strategy AI Spectrum
Soren Johnson (GDC2008)
"Good"
"Fun"
72
Strategy AI Spectrum
Soren Johnson (GDC2008)
"Good"
"Fun"
73
Rules Over Time?
Soren Johnson (GDC2008)
Fixed
Evolving
74
Playing Same Game?
Soren Johnson (GDC2008)
Symmetrical
Asymmetrical
75
Best Environment?
Soren Johnson (GDC2008)
Multi-Player
Single Player
76
Tactics Available?
Soren Johnson (GDC2008)
Everything
Limited
77
Measuring Performace?
Soren Johnson (GDC2008)
Objective
Subjective
78
Turing Test?
Soren Johnson (GDC2008)
Pass!
Irrelevant
79
Cheating?
Soren Johnson (GDC2008)
No
Yes?
Not Applicable
80
Summary Comparison
Soren Johnson (GDC2008)
“Good” AI







Fixed Rules
Symmetrical
Multi-Player
Unlimited Tactics
Objective Testing
Passes Turing
No cheating
Playing to Win...
“Fun” AI







Evolving Design
Asymmetrical
Single Player
Limited Options
Subjective Quality
Ignores Turing
Cheating Irrelevant
Playing to Lose...
81
What About Civ AI?
Soren Johnson (GDC2008)
“Good” AI







“Fun” AI
Fixed Rules

Symmetrical

Multi-Player

Unlimited Tactics

Objective Testing

Passes Turing Fails Turing
No Cheating
Cheats 
Playing to Win...
Evolving Design
Asymmetrical
Single Player
Limited Options
Subjective Quality
Ignores Turing
Cheating Irrelevant
Playing to Lose...
82
Artificial Stupidity:
Tips from Experts

Don’t over-design the AI


Get the AI playing the game and slowly improve it



Football example
Turn-based example
Play the game yourself and find the real problem the
AI must solve


Use cheap tricks when they will suffice
HyperBlade example
Know when and how to cheat

RTS example
83
Artificial Stupidity:
Tips from Experts (Half-Life 2)

Move Before Firing


Be Visible



Lots of gunfire keeps tension high
Use tracers, puffs of dust, and sparks to emphasize missed shots
Miss the First Time


Color or brightness should stand out
Have Horrible Aim


Should never get shot entering a room
Gives player a chance to react
Warn the Player

“Take this!” (helps when player is attacked from behind)
84
Artificial Stupidity:
Tips from Experts (Half-Life 2)

Attack Kung-Fu Style


Tell the Player What You’re Doing



Player gets overwhelmed too easily otherwise
The only way the player knows that your AI is intelligent
“Cover Me!” or “Retreat!”
React to Mistakes

If grenade lands back at AI’s feet




Cover head with arms and yell “Oh no!”
Turns failures into features
Pull Back at Last Minute
Intentional Vulnerabilities

Design them in instead of letting player find unintended ones
85
AI Cheating




Is it ethical?
How can the AI cheat?
Why might it be necessary to cheat?
How will the player feel?
86
AI Cheating
“Cheating can be one of the easier ways to
deal with difficulty levels, but is also
typically obvious to the player.”
– Bob Scott, Empire Earth
87
AI Cheating
“Cheating should be viewed as a tool of last
resort when designing AI within a turn-based
environment.”
– Soren Johnson, Civilization III
“Cheating is for challenge, which is one source of
fun.”
– Soren Johnson, Civilization IV
88