Transcript AI for Games

Artificial Intelligence for Games
Finite State Machines
Patrick Olivier
[email protected]
“Intelligent” Behaviours
• Restrict “behaviour” to “intelligent behaviours”
• For example:
– trajectory of a car is not “intelligent” 
– decision to fight and what to fight 
– decision to flee and what to flee from 
• Complex behaviours implement more intelligent
opponents
– define a kind a “personality” for NPCs or opponents
– formalising behaviours makes gameplay explicit
Finite state machines: theory
• Simple theoretical
construct:
a
– Set of states (S)
– Input vocabulary (I)
– Transition function T(s,i)
• A way of denoting how
an object can change its
state over time
1
2
b
f
e
5
c
3
4
d
g
Finite state machines: practice
• Character AI modeled as a
sequence of mental states
• World events can force a
state change
• Easy to grasp, even for
non-programmers
• Input to the FSM continues
as long as the game
continues
Monster In Sight
Gather
Treasure
Flee
No Monster
Monster Dead
Fight
Cornered
Finite state machines: example
• States
–
–
–
–
Atttack
Inspect
Spawn
Patrol
• Events
– E: see an enemy
– S: hear a sound
– D: die
• Action performed
– On each transition
– On each update in some
states (e.g. attack)
Attack
E,~D
~E
E
D
E
~S
Inspect
E
Patrol
S
D
~E
D
Spawn
D
S
Pac-man: Blinky (the red ghost)
FSMs: advantages & disadvantages
• Advantages:
– Easy to understand
– Easy to implement
– Flexible: suitable for a range of problems
• Disadvantages:
– Scalability: can be cumbersome
– State oscillation
FSMs: implementation issues
• Polling
– Simple and easy to debug
– Inefficient since FSM’s are always evaluated
• Event Driven Model
– FSM registers which events it is interested in
– Requires Observer model in engine
• Multithreaded
–
–
–
–
Each FSM assigned its own thread
Requires thread-safe communication
Conceptually elegant
Difficult to debug
Class exercise
•
•
•
•
•
•
10 minutes exercise
work in pairs or threes
pick a game scenario
agree on percepts for the scenario
each develop an FSM for a different NPCs
aim for interesting interactions:
– between player and NPCs
– between NPCs
• hand in a “final” sheet (with names on it)
Extensions: Hierarchical FSMs
• expand a state into its own sub-FSM
• some events move you around the same level in
the hierarchy, some move you up a level
• when entering a state, choose a sub-state:
– set a default, and always go to that
– random choice
– depends on the nature of the behaviour
Extensions: Hierarchical FSMs
Wander
Attack
~E
E
S
Start
Turn Right
Chase
~S
Pick-up
Powerup
D
Spawn
~E
Go-through
Door
Extensions: stack-based FSMs
• Gives the AI a (limited)
form of ‘memory’
• Switch states, then return
to a previous state
• Permits temporary
interruption
• More realistic behaviour
• Not all states stack-able
• Replacement behaviours
Extensions: inertial FSMs
• Need to address the oscillation problem
• For example – basketball:
– LOS=FALSE  stand-state
– LOS=TRUE  basket-drive-state
• Introduce inertia to dampen state changes
• State inertia (e.g. minimum running times)
• Perceptual inertia (e.g. multiple firings)
Other extensions of FSMs…
• Inter-character concurrent FSM
– Coordinating multiple characters
• Intra-character concurrent FSM
– Coordinating multiple behaviours (in one NPC)
• Levels of detail (LODs)
– Analogous to LOD in graphics
– e.g. crowd simulation
• Proximal NPCs use fully elaborated FSM
• Distal characters use fixed paths or worse
Nondeterministic FSMs
• Probabilistic FSMs
– multiple transitions for same
event
– each transition has
probability that it will be
taken
– probabilistically choose a
transition at run-time
Attack
.3
Slide
& Shoot
Approach
.3
.3
.1
Start
.4
.2
Aim
& Shoot
.4
Jump &
Shoot
Questions?