Section 9.3 Finite-State Machines
749
speCial interest page
fsMs Behind the Game
Everyone is familiar with the use of storyboards in designing a movie. Storyboards are sequences of illustrated panels that set the scene, sketch the action, and
outline the dialogue. Thumbing rapidly through pages of
such panels creates a “flipbook,” a primitive animation
of the movie. So these panels, laid end-to-end, are a onedimensional layout of the movie.
What differentiates a video game from a movie? A
movie (a film) is static in the sense that it always comes
out the same way; there are no variations in the scenes or
changes in the ending. A video game incorporates user
interaction, and based on user input, different outcomes
can occur at various points throughout the game. Design
of a video game requires a two-dimensional approach.
If you freeze the video game at some point where
it is waiting for user input, there is a certain scene on
the screen with particular characters in place, and these
characters may have certain attributes at this point in
time. We can consider this to be the “state” of the game
at the moment. User input is provided, and based on that
input and the current state, something happens to move
the game to a predefined new state. Sound familiar? Yes,
this is essentially a finite-state machine. “Finite state machines are the nuts and bolts of game AI.”
1
Here’s an outline, written as an English paragraph,
of a simple video game: The user starts the game by
C h a p t e r
9 9
1 AI for Game Development, David M Bourg and Glenn Seemann, O’Reilly Media, Inc., 2004, ISBN-13: 978-0-596-00555-9
Start
Level 1
Choose
level 1
Choose
level 2
Lantern
room
Lantern
Book
Find
codeword
Open treasure
chest
Slay
dragon
Plant
tree
Sword
roon
Sword
Book
room
Garden
Door 2
Door 1
Games
ends
Level 2
choosing to play at level 1 or level 2. In this simple
game, the only entity is the user’s avatar, call it object
A. A user who chooses level 1 sends A into a room
where A must pick up one of three objects: a book, a
sword, or a lantern. If the book is chosen, A enters a
room where the book can be searched for a secret code
word. When the code word is found, A moves on to the
opening screen for level 2. If the sword is chosen, A enters a room with a fearsome dragon. When A slays the
dragon, A receives the book and enters the book room
to search for the code word. If the lantern is chosen,
A enters a room to search for a treasure chest. When
the treasure chest is opened, it contains a sword and
A moves on to the room with the fearsome dragon. At
level 2, A chooses between door 1 and door 2. Choosing door 1 ends the game. Choosing door 2 moves A
into a garden, where A must find and plant a lilac tree.
Upon planting the tree, the game ends.
A state graph for a finite-state machine to model the
game behavior described above looks something like the
diagram shown.
Ultimately this design has to be translated into
computer code. Details will vary with the programming language used, of course, but in any event there
must be a way to make multiple choices from a given
state depending on the user action:
if (A.state = level1 and A.pick = lantern)
A.state = LanternRoom
else if (A.state = level1 and A.pick = sword)
A.state = SwordRoom
else if (A.state = level1 and A.pick = book)
A.state = BookRoom
else if (A.state = level2 and A.pick = Door1)
A.state = GameEnds
and so forth.
In a more complex video game there
will be many entities, and the computer code
must go through a similar decision process
for each one to program its correct action
based on its current state and user input. The
environment itself may be an entity, requiring changes of background (from the lantern
room to the sword room, for example).
749
speCial interest page
fsMs Behind the Game
Everyone is familiar with the use of storyboards in designing a movie. Storyboards are sequences of illustrated panels that set the scene, sketch the action, and
outline the dialogue. Thumbing rapidly through pages of
such panels creates a “flipbook,” a primitive animation
of the movie. So these panels, laid end-to-end, are a onedimensional layout of the movie.
What differentiates a video game from a movie? A
movie (a film) is static in the sense that it always comes
out the same way; there are no variations in the scenes or
changes in the ending. A video game incorporates user
interaction, and based on user input, different outcomes
can occur at various points throughout the game. Design
of a video game requires a two-dimensional approach.
If you freeze the video game at some point where
it is waiting for user input, there is a certain scene on
the screen with particular characters in place, and these
characters may have certain attributes at this point in
time. We can consider this to be the “state” of the game
at the moment. User input is provided, and based on that
input and the current state, something happens to move
the game to a predefined new state. Sound familiar? Yes,
this is essentially a finite-state machine. “Finite state machines are the nuts and bolts of game AI.”
1
Here’s an outline, written as an English paragraph,
of a simple video game: The user starts the game by
C h a p t e r
9 9
1 AI for Game Development, David M Bourg and Glenn Seemann, O’Reilly Media, Inc., 2004, ISBN-13: 978-0-596-00555-9
Start
Level 1
Choose
level 1
Choose
level 2
Lantern
room
Lantern
Book
Find
codeword
Open treasure
chest
Slay
dragon
Plant
tree
Sword
roon
Sword
Book
room
Garden
Door 2
Door 1
Games
ends
Level 2
choosing to play at level 1 or level 2. In this simple
game, the only entity is the user’s avatar, call it object
A. A user who chooses level 1 sends A into a room
where A must pick up one of three objects: a book, a
sword, or a lantern. If the book is chosen, A enters a
room where the book can be searched for a secret code
word. When the code word is found, A moves on to the
opening screen for level 2. If the sword is chosen, A enters a room with a fearsome dragon. When A slays the
dragon, A receives the book and enters the book room
to search for the code word. If the lantern is chosen,
A enters a room to search for a treasure chest. When
the treasure chest is opened, it contains a sword and
A moves on to the room with the fearsome dragon. At
level 2, A chooses between door 1 and door 2. Choosing door 1 ends the game. Choosing door 2 moves A
into a garden, where A must find and plant a lilac tree.
Upon planting the tree, the game ends.
A state graph for a finite-state machine to model the
game behavior described above looks something like the
diagram shown.
Ultimately this design has to be translated into
computer code. Details will vary with the programming language used, of course, but in any event there
must be a way to make multiple choices from a given
state depending on the user action:
if (A.state = level1 and A.pick = lantern)
A.state = LanternRoom
else if (A.state = level1 and A.pick = sword)
A.state = SwordRoom
else if (A.state = level1 and A.pick = book)
A.state = BookRoom
else if (A.state = level2 and A.pick = Door1)
A.state = GameEnds
and so forth.
In a more complex video game there
will be many entities, and the computer code
must go through a similar decision process
for each one to program its correct action
based on its current state and user input. The
environment itself may be an entity, requiring changes of background (from the lantern
room to the sword room, for example).