Last Time
• Terrain Generation
• We’re pretty much done with the graphics part of the course
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Today
• AI
– Overview
– State Machines
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
What is AI?
• AI is the control of every non-human entity in a game
– The other cars in a car game
– The opponents and monsters in a shooter
– Your units, your enemy’s units and your enemy in a RTS game
• But, typically does not refer to passive things that just react
to the player and never initiate action
– That’s physics or game logic
– For example, the blocks in Tetris are not AI, nor is a flag blowing in
the wind
– It’s a somewhat arbitrary distinction
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
AI in the Game Loop
• AI is updated as part of the game loop, after user input, and
before rendering
• There are issues here:
– Which AI goes first?
– Does the AI run on every frame?
– Is the AI synchronized?
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
AI and Animation
• AI determines what to do and the animation does it
– AI drives animation, deciding what action the animation system
should be animating
– Scenario 1: The AI issues orders like “move from A to B”, and it’s
up to the animation system to do the rest
– Scenario 2: The AI controls everything down to the animation clip
to play
• Which scenario is best depends on the nature of the AI
system and the nature of the animation system
– Is the animation system based on move trees (motion capture), or
physics, or something else
– Does the AI look after collision avoidance? Does it do detailed
planning?
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
AI Update Step
• The sensing phase determines the state of
the world AI Module
– May be very simple - state changes all
come by message
– Or complex - figure out what is visible,
Sensing
where your team is, etc
• The thinking phase decides what to do
given the world Game
– The core of AI Thinking
Engine
• The acting phase tells the animation what
to do
– Generally not interesting
Acting
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
AI by Polling
• The AI gets called at a fixed rate
• Senses: It looks to see what has changed in the world. For
instance:
– Queries what it can see
– Checks to see if its animation has finished running
• And then acts on it
• Why is this generally inefficient?
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Event Driven AI
• Event driven AI does everything in response to events in the
world
– Events sent by message (basically, a function gets called when a
message arrives, just like a user interface)
• Example messages:
– A certain amount of time has passed, so update yourself
– You have heard a sound
– Someone has entered your field of view
• Note that messages can completely replace sensing, but
typically do not. Why not?
– Real system are a mix - something changes, so you do some sensing
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
AI Techniques in Games
• Basic problem: Given the state of the world, what should I
do?
• A wide range of solutions in games:
– Finite state machines, Decision trees, Rule based systems, Neural
networks, Fuzzy logic
• A wider range of solutions in the academic world:
– Complex planning systems, logic programming, genetic algorithms,
Bayes-nets
– Typically, too slow for games
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Goals of Game AI
• Several goals:
– Goal driven - the AI decides what it should do, and then figures out
how to do it
– Reactive - the AI responds immediately to changes in the world
– Knowledge intensive - the AI knows a lot about the world and how
it behaves, and embodies knowledge in its own behavior
– Characteristic - Embodies a believable, consistent character
– Fast and easy development
– Low CPU and memory usage
• These conflict in almost every way
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Two Measures of Complexity
• Complexity of Execution
– How fast does it run as more knowledge is added?
– How much memory is required as more knowledge is added?
– Determines the run-time cost of the AI
• Complexity of Specification
– How hard is it to write the code?
– As more “knowledge” is added, how much more code needs to be
added?
– Determines the development cost, and risk
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Expressiveness
• What behaviors can easily be defined, or defined at all?
• Propositional logic:
– Statements about specific objects in the world – no variables
– Jim is in room7, Jim has the rocket launcher, the rocket launcher
does splash damage
– Go to room8 if you are in room7 through door14
• Predicate Logic:
– Allows general statement – using variables
– All rooms have doors
– All splash damage weapons can be used around corners
– All rocket launchers do splash damage
– Go to a room connected to the current room
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
General References
• As recommended by John Laird, academic game AI leader
and source of many of these slides
• AI
– Russell and Norvig: Artificial Intelligence: A Modern Approach,
Prentice Hall, 1995
– Nilsson, Artificial Intelligence: A New Synthesis, Morgan
Kaufmann, 1998
• AI and Computer Games
– LaMothe: Tricks of the Windows Game Programming Gurus,
SAMS, 1999, Chapter 12, pp. 713-796
– www.gameai.com
– www.gamedev.net
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Finite State Machines (FSMs)
• A set of states that the agent can be in
• Connected by transitions that are triggered by a change in
the world
• Normally represented as a directed graph, with the edges
labeled with the transition event
• Ubiquitous in computer game AI
• You might have seen them, a long time ago, in formal
language theory (or compilers)
– What type of languages can be represented by finite state machines?
– How might this impact a character’s AI?
– How does it impact the size of the machine?
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Quake Bot Example
• Types of behavior to capture:
– Wander randomly if don’t see or hear an enemy
– When see enemy, attack
– When hear an enemy, chase enemy
– When die, respawn
– When health is low and see an enemy, retreat
• Extensions:
– When see power-ups during wandering, collect them
• Borrowed from John Laird and Mike van Lent’s GDC
tutorial
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Example FSM
• States:
Attack – E: enemy in sight
~E E,~D – S: sound audible
E – D: dead
D • Events:
E
S – E: see an enemy
Wander Chase – S: hear a sound
~E,~S,~D E ~S S,~E,~D – D: die
D
~E • Action performed:
– On each transition
Spawn S
D – On each update in some
D states (e.g. attack)
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Example FSM Problem
• States:
Attack – E: enemy in sight
~E E,~D – S: sound audible
D E – D: dead
E • Events:
Wander S
Chase – E: see an enemy
~E,~S,~D E ~S S,~E,~D – S: hear a sound
D
~E – D: die
Spawn S
D
D
Problem: Can’t go directly
from attack to chase. Why not?
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Better Example FSM
~S • States:
Attack-S
Attack – E: enemy in sight
E,S,~D
~E E,~S,~D S – S: sound audible
– D: dead
D D ~E E
E • Events:
Wander S – E: see an enemy
Chase – S: hear a sound
~E,~S,~D E ~S S,~E,~D
D – D: die
~E • Extra state to recall
S whether or not heard a
D Spawn sound while attacking
D
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Example FSM with Retreat
S Attack-ES
Retreat-S
Attack-E E,-D,S,-L
-E,-D,S,L
• States:
-S L
E,-D,-S,-L – E: enemy in sight
L -L E
-E
– S: sound audible
E E -L – D: dead
-L Retreat-ES
Wander-L – L: Low health
-E,-D,-S,L E L E,-D,S,L
-S
• Worst case: Each
L
-L
S extra state
Retreat-E variable can add
Wander -E -E E E,-D,-S,L 2n extra states
-E,-D,-S,-L
• n = number of
D D
Chase existing states
D D
Spawn -E,-D,S,-L
D S
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
(-E,-S,-L)
Hierarchical FSMs
• What if there is no simple action for a state?
• Expand a state into its own FSM, which explains what to do
if in that state
• Some events move you around the same level in the
hierarchy, some move you up a level
• When entering a state, have to choose a state for it’s child in
the hierarchy
– Set a default, and always go to that
– Or, random choice
– Depends on the nature of the behavior
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Hierarchical FSM Example
Wander ~E Attack
E
Pick-up ~S
Chase
Powerup
S
Start
D Spawn
Turn Right
~E
• Note: This is not a complete FSM
– All links between top level states
Go-through still exist
Door – Need more states for wander
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Non-Deterministic Hierarchical
FSM (Markov Model)
• Adds variety to actions
Attack
• Have multiple transitions for the
same event
• Label each with a probability
Approach
that it will be taken
.3
Aim & • Randomly choose a transition at
Slide Right
.3 run-time
& Shoot .3 Start
.4 .3 • Markov Model: New state only
depends on the previous state
Aim &
.4
Slide Left
Aim &
& Shoot
Jump &
Shoot
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Efficient Implementation
event
• Compile into an array of state-name, event
• state-namei+1 := array[state-namei, event] state
• Switch on state-name to call execution logic
• Hierarchical
– Create array for every FSM
– Have stack of states
• Classify events according to stack
• Update state which is sensitive to current
event
• Markov: Have array of possible transitions
for every (state-name,event) pair, and choose
one at random
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
FSM Advantages
• Very fast – one array access
• Expressive enough for simple behaviors or characters that
are intended to be “dumb”
• Can be compiled into compact data structure
– Dynamic memory: current state
– Static memory: state diagram – array implementation
• Can create tools so non-programmer can build behavior
• Non-deterministic FSM can make behavior unpredictable
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
FSM Disadvantages
• Number of states can grow very fast
– Exponentially with number of events: s=2e
• Number of arcs can grow even faster: a=s2
• Propositional representation
– Difficult to put in “pick up the better powerup”, “attack the closest
enemy”
– Expensive to count: Wait until the third time I see enemy, then
attack
• Need extra events: First time seen, second time seen, and extra states to
take care of counting
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
References
• Web references:
– www.gamasutra.com/features/19970601/build_brains_into_games.h
tm
– csr.uvic.ca/~mmania/machines/intro.htm
– www.erlang/se/documentation/doc-4.7.3/doc/design_principles/fsm.
html
– www.microconsultants.com/tips/fsm/fsmartcl.htm
• Game Programming Gems Sections 3.0 & 3.1
– It’s very very detailed, but also some cute programming
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Todo
• By Monday, Nov 3, Stage 3 demo
• Thurs Nov 6, Midterm
– Everything up to and including lecture 15
10/23/03 CS679 - Fall 2003 - Copyright Univ. of Wisconsin
