^title State
^section Design Patterns Revisited
Confession time: I went a little overboard and packed way too much into this
chapter. It's ostensibly about the State
design pattern, but I can't talk about that and games without going into the
more fundamental concept of *finite state machines* (or "FSMs"). But then once I
went there, I figured I might as well introduce *hierarchical state machines*
and *pushdown automata*.
That's a lot to cover, so to keep things as short as possible, the code samples
here leave out a few details that you'll have to fill in on your own. I hope
they're still clear enough for you to get the big picture.
Don't feel sad if you've never heard of a state machine. While well known to
AI and compiler hackers, they aren't that familiar
to other programming circles. I think they should be more widely known, so I'm
going to throw them at a different kind of problem here.
## We've All Been There
We're working on a little side-scrolling platformer. Our job is to implement the
heroine that is the player's avatar in the game world. That means making her
respond to user input. Push the B button and she should jump. Simple enough:
^code spaghetti-1
Spot the bug?
There's nothing to prevent "air jumping" -- keep hammering B while she's in the
air, and she will float forever. The simple fix is to
add an `isJumping_` Boolean field to `Heroine` that tracks when she's jumping,
and then do:
^code spaghetti-2
Next, we want the heroine to duck if the player presses down while she's on the
ground and stand back up when the button is released:
^code spaghetti-3
Spot the bug this time?
With this code, the player could:
1. Press down to duck.
2. Press B to jump from a ducking position.
3. Release down while still in the air.
The heroine will switch to her standing graphic in the middle of the jump. Time
for another flag...
^code spaghetti-4
Next, it would be cool if the heroine did a dive attack if the player presses
down in the middle of a jump:
^code spaghetti-5
Bug hunting time again. Find it?
We check that you can't air jump while jumping, but not while diving. Yet
another field...
Something is clearly wrong with our approach. Every time
we touch this handful of code, we break something. We need to add a bunch more
moves -- we haven't even added *walking* yet -- but at this rate, it will
collapse into a heap of bugs before we're done with it.
## Finite State Machines to the Rescue
In a fit of frustration, you sweep everything off your desk except a pen and
paper and start drawing a flowchart. You draw a box for each thing the heroine
can be doing: standing, jumping, ducking, and diving. When she can respond to a
button press in one of those states, you draw an arrow from that box, label it
with that button, and connect it to the state she changes to.
Congratulations, you've just created a *finite state machine*. These came out of
a branch of computer science called *automata theory* whose family of data
structures also includes the famous Turing machine. FSMs are the simplest member
of that family.
The gist is:
* **You have a fixed *set of states* that the machine can be in.** For our
example, that's standing, jumping, ducking, and diving.
* **The machine can only be in *one* state at a time.** Our heroine can't be
jumping and standing simultaneously. In fact, preventing that is one reason
we're going to use an FSM.
* **A sequence of *inputs* or *events* is sent to the machine.** In our example,
that's the raw button presses and releases.
* **Each state has a *set of transitions*, each associated with an input and
pointing to a state.** When an input comes in, if it matches a transition for
the current state, the machine changes to the state that transition points
to.
For example, pressing down while standing transitions to the ducking state. Pressing down while jumping transitions to diving. If no transition is defined for an input on the current state, the input is ignored.
In their pure form, that's the whole banana: states, inputs, and transitions.
You can draw it out like a little flowchart. Unfortunately, the compiler doesn't
recognize our scribbles, so how do we go about *implementing* one? The Gang of
Four's State pattern is one method -- which we'll get to -- but let's start simpler.
## Enums and Switches
One problem our `Heroine` class has is some combinations of those Boolean fields
aren't valid: `isJumping_` and `isDucking_` should never both be true, for
example. When you have a handful of flags where only one is `true` at a time,
that's a hint that what you really want is an `enum`.
In this case, that `enum` is exactly the set of states for our FSM, so let's
define that:
^code enum
Instead of a bunch of flags, `Heroine` will just have one `state_` field. We
also flip the order of our branching. In the previous code, we switched on
input, *then* on state. This kept the code for handling one button press
together, but it smeared around the code for one state. We want to keep that
together, so we switch on state first. That gives us:
^code state-switch
This seems trivial, but it's a real improvement over the previous code. We still
have some conditional branching, but we simplified the mutable state to a single field. All of the code for
handling a single state is now nicely lumped together. This is the simplest way
to implement a state machine and is fine for some uses.
Your problem may outgrow this solution, though. Say we want to add a move where
our heroine can duck for a while to charge up and unleash a special attack.
While she's ducking, we need to track the charge time.
We add a `chargeTime_` field to `Heroine` to store how long the attack has
charged. Assume we already have an `update()` that
gets called each frame. In there, we add:
^code switch-update
We need to reset the timer when she starts ducking, so we modify
`handleInput()`:
^code state-switch-reset
All in all, to add this charge attack, we had to modify two methods and add a
`chargeTime_` field onto `Heroine` even though it's only meaningful while in
the ducking state. What we'd prefer is to have all of that code and data nicely
wrapped up in one place. The Gang of Four has us covered.
## The State Pattern
For people deeply into the object-oriented mindset, every conditional branch is an opportunity to use dynamic dispatch (in other
words a virtual method call in C++). I think you can go too far down that
rabbit hole. Sometimes an `if` is all you need.
But in our example, we've reached a tipping point where something
object-oriented is a better fit. That gets us to the State pattern. In the words
of the Gang of Four:
> Allow an object to alter its behavior when its internal state changes. The object will appear to change its class.
That doesn't tell us much. Heck, our `switch` does that. The concrete pattern
they describe looks like this when applied to our heroine:
### A state interface
First, we define an interface for the state. Every bit of behavior that is
state-dependent -- every place we had a `switch` before -- becomes a virtual
method in that interface. For us, that's `handleInput()` and `update()`:
^code heroine-state
### Classes for each state
For each state, we define a class that implements the interface. Its methods
define the heroine's behavior when in that state. In other words, take each `case`
from the earlier `switch` statements and move them into their state's class. For example:
^code ducking-state
Note that we also moved `chargeTime_` out of `Heroine` and into the `DuckingState`
class. This is great -- that piece of data is only meaningful while in that state,
and now our object model reflects that explicitly.
### Delegate to the state
Next, we give the `Heroine` a pointer to her current state, lose each big `switch`, and delegate to the state instead:
^code gof-heroine
In order to "change state", we just need to assign `state_` to point to a
different `HeroineState` object. That's the State pattern in its entirety.
## Where Are the State Objects?
I did gloss over one bit here. To change states, we need to assign `state_` to
point to the new one, but where does that object come from? With our `enum`
implementation, that was a no-brainer -- `enum` values are primitives like
numbers. But now our states are classes, which means we need an actual instance
to point to. There are two common answers to this:
### Static states
If the state object doesn't have any other fields, then
the only data it stores is a pointer to the internal virtual method table so
that its methods can be called. In that case, there's no reason to ever have
more than one instance of it. Every instance would be identical anyway.
In that case, you can make a single *static* instance. Even if you have a
bunch of FSMs all going at the same time in that same state, they can all point
to the same instance since it has nothing
machine-specific about it.
*Where* you put that static instance is up to you. Find a place that makes
sense. For no particular reason, let's put ours inside the base state class:
^code heroine-static-states
Each of those static fields is the one instance of that state that the game
uses. To make the heroine jump, the standing state would do something like:
^code jump
### Instantiated states
Sometimes, though, this doesn't fly. A static state won't work for the ducking
state. It has a `chargeTime_` field, and that's specific to the heroine that
happens to be ducking. This may coincidentally work in our game if there's only
one heroine, but if we try to add two-player co-op and have two heroines on
screen at the same time, we'll have problems.
In that case, we have to create a state
object when we transition to it. This lets each FSM have its own instance of the state. Of course, if we're allocating a *new* state, that means we need to free the *current* one. We have to be careful here, since the code that's triggering the change is in a method in the current state. We don't want to delete `this` out from under ourselves.
Instead, we'll allow `handleInput()` in `HeroineState` to optionally return a new state. When it does, `Heroine` will delete the old one and swap in the new one, like so:
^code swap-instance
That way, we don't delete the previous state until we've returned from its method. Now, the standing state can transition to ducking by creating a new instance:
^code duck
When I can, I prefer to use static states since they don't burn memory and CPU cycles allocating objects
each state change. For states that are more, uh, *stateful*, though, this is the
way to go.
## Enter and Exit Actions
The goal of the State pattern is to encapsulate all of the behavior and data for
one state in a single class. We're partway there, but we still have
some loose ends.
When the heroine changes state, we also switch her sprite. Right now, that code is owned by the state she's switching *from*. When she goes from ducking to standing, the ducking state sets her image:
^code enter-standing-before
What we really want is each state to control its own graphics. We can
handle that by giving the state an *entry action*:
^code standing-with-enter
Back in `Heroine`, we modify the code for handling state changes to call that
on the new state:
^code change-state
This lets us simplify the ducking code to:
^code enter-standing
All it does is switch to standing and the standing state takes care of
the graphics. Now our states really are encapsulated. One particularly nice thing
about entry actions is that they run when you enter the state regardless of
which state you're coming *from*.
Most real-world state graphs have multiple transitions into the same state. For
example, our heroine will also end up standing after she lands a jump or dive. That means we would end up duplicating some code everywhere that transition
occurs. Entry actions give us a place to consolidate that.
We can, of course, also extend this to support an *exit action*. This is just a
method we call on the state we're *leaving* right before we switch to the new
state.
## What's the Catch?
I've spent all this time selling you on FSMs, and now I'm going to pull the rug
out from under you. Everything I've said so far is true, and FSMs are a good fit
for some problems. But their greatest virtue is also their greatest flaw.
State machines help you untangle hairy code by enforcing a very constrained structure on it. All you've got is a fixed set
of states, a single current state, and some hardcoded transitions.
If you try using a state machine for something more complex like game AI, you
will slam face-first into the limitations of that model. Thankfully, our
forebears have found ways to dodge some of those barriers. I'll close this
chapter out by walking you through a couple of them.
## Concurrent State Machines
We've decided to give our heroine the ability to carry a gun. When she's packing
heat, she can still do everything she could before: run, jump, duck, etc. But
she also needs to be able to fire her weapon while doing it.
If we want to stick to the confines of an FSM, we have to *double* the number of
states we have. For each existing state, we'll need another one for doing the
same thing while she's armed: standing, standing with gun, jumping, jumping with
gun, you get the idea.
Add a couple of more weapons and the number of states explodes combinatorially.
Not only is it a huge number of states, it's a huge amount of redundancy: the
unarmed and armed states are almost identical except for the little bit of code
to handle firing.
The problem is that we've jammed two pieces of
state -- what she's *doing* and what she's *carrying* -- into a single machine.
To model all possible combinations, we would need a state for each *pair*. The
fix is obvious: have two separate state machines.
We keep our original state machine for what she's doing and leave it alone. Then
we define a separate state machine for what she's carrying. `Heroine` will have
*two* "state" references, one for each, like:
^code two-states
When the heroine delegates inputs to the states, she hands it to both of them:
^code handle-two-inputs
Each state machine can then respond to inputs, spawn behavior, and change its
state independently of the other machine. When the two sets of states are mostly
unrelated, this works well.
In practice, you'll find a few cases where the states do interact. For example,
maybe she can't fire while jumping, or maybe she can't do a dive attack if she's
armed. To handle that, in the code for one state, you'll probably just do some
crude `if` tests on the *other* machine's state to coordinate them. It's not the most
elegant solution, but it gets the job done.
## Hierarchical State Machines
After fleshing out our heroine's behavior some more, she'll likely have a bunch
of similar states. For example, she may have standing, walking, running, and
sliding states. In any of those, pressing B jumps and pressing down ducks.
With a simple state machine implementation, we have to duplicate that code in
each of those states. It would be better if we could implement that once and
reuse it across all of the states.
If this was just object-oriented code instead of a state machine, one way to
share code across those states would be using inheritance. We could define a class for an "on
ground" state that handles jumping and ducking. Standing, walking, running, and
sliding would then inherit from that and add their own additional behavior.
It turns out, this is a common structure called a *hierarchical state machine*.
A state can have a *superstate* (making itself a *substate*). When an event
comes in, if the substate doesn't handle it, it rolls up the chain of
superstates. In other words, it works just like overriding inherited methods.
In fact, if we're using the State pattern to implement our FSM, we can
use class inheritance to implement the hierarchy. Define a base class for the
superstate:
^code on-ground
And then each substate inherits it:
^code duck-on-ground
This isn't the only way to implement the hierarchy, of course. If you aren't
using the Gang of Four's State pattern, this won't work. Instead, you can model
the current state's chain of superstates explicitly using a *stack* of states
instead of a single state in the main class.
The current state is the one on the top of the stack, under that is its
immediate superstate, and then *that* state's superstate and so on. When you
dish out some state-specific behavior, you start at the top of the stack and
walk down until one of the states handles it. (If none do, you ignore it.)
## Pushdown Automata
There's another common extension to finite state machines that also uses a stack
of states. Confusingly, the stack represents something entirely different, and
is used to solve a different problem.
The problem is that finite state machines have no concept of *history*. You know
what state you *are* in, but have no memory of what state you *were* in. There's
no easy way to go back to a previous state.
Here's an example: Earlier, we let our fearless heroine arm herself to the
teeth. When she fires her gun, we need a new state that plays the firing
animation and spawns the bullet and any visual effects. So we slap together a
`FiringState` and make all of the states that she can
fire from transition into that when the fire button is pressed.
The tricky part is what state she transitions to *after* firing. She can pop off
a round while standing, running, jumping, and ducking. When the firing sequence
is complete, she should transition back to what she was doing before.
If we're sticking with a vanilla FSM, we've already forgotten what state she was
in. To keep track of it, we'd have to define a slew of nearly identical states
-- firing while standing, firing while running, firing while jumping, and so on
-- just so that each one can have a hardcoded transition that goes back to the
right state when it's done.
What we'd really like is a way to *store* the state she was in before firing and
then *recall* it later. Again, automata theory is here to help. The relevant
data structure is called a [*pushdown
automaton*](http://en.wikipedia.org/wiki/Pushdown_automaton).
Where a finite state machine has a *single* pointer to a state, a pushdown
automaton has a *stack* of them. In an FSM, transitioning to a new state
*replaces* the previous one. A pushdown automaton lets you do that, but it also
gives you two additional operations:
1. You can *push* a new state onto the stack. The "current" state is always the
one on top of the stack, so this transitions to the new state. But it leaves
the previous state directly under it on the stack instead of discarding it.
2. You can *pop* the topmost state off the stack. That state is discarded, and
the state under it becomes the new current state.
This is just what we need for firing. We create a *single* firing state. When
the fire button is pressed while in any other state, we *push* the firing state
onto the stack. When the firing animation is done, we *pop* that state off, and
the pushdown automaton automatically transitions us right back to the state we
were in before.
## So How Useful Are They?
Even with those common extensions to state machines, they are still pretty
limited. The trend these days in game AI is more toward exciting things like
*[behavior trees][]* and *[planning systems][]*. If complex AI is what you're interested in,
all this chapter has done is whet your appetite. You'll want to read other books
to satisfy it.
[behavior trees]: http://web.archive.org/web/20140402204854/http://www.altdevblogaday.com/2011/02/24/introduction-to-behavior-trees/
[planning systems]: http://web.media.mit.edu/~jorkin/goap.html
This doesn't mean finite state machines, pushdown automata, and other simple
systems aren't useful. They're a good modeling tool for certain kinds of
problems. Finite state machines are useful when:
* You have an entity whose behavior changes based on some internal state.
* That state can be rigidly divided into one of a relatively small number of
distinct options.
* The entity responds to a series of inputs or events over time.
In games, they are most known for being used in AI, but they are also common in
implementations of user input handling, navigating menu screens, parsing text,
network protocols, and other asynchronous behavior.
Congratulations, you've just created a *finite state machine*. These came out of
a branch of computer science called *automata theory* whose family of data
structures also includes the famous Turing machine. FSMs are the simplest member
of that family.
The gist is:
* **You have a fixed *set of states* that the machine can be in.** For our
example, that's standing, jumping, ducking, and diving.
* **The machine can only be in *one* state at a time.** Our heroine can't be
jumping and standing simultaneously. In fact, preventing that is one reason
we're going to use an FSM.
* **A sequence of *inputs* or *events* is sent to the machine.** In our example,
that's the raw button presses and releases.
* **Each state has a *set of transitions*, each associated with an input and
pointing to a state.** When an input comes in, if it matches a transition for
the current state, the machine changes to the state that transition points
to.
For example, pressing down while standing transitions to the ducking state. Pressing down while jumping transitions to diving. If no transition is defined for an input on the current state, the input is ignored.
In their pure form, that's the whole banana: states, inputs, and transitions.
You can draw it out like a little flowchart. Unfortunately, the compiler doesn't
recognize our scribbles, so how do we go about *implementing* one? The Gang of
Four's State pattern is one method -- which we'll get to -- but let's start simpler.
## Enums and Switches
One problem our `Heroine` class has is some combinations of those Boolean fields
aren't valid: `isJumping_` and `isDucking_` should never both be true, for
example. When you have a handful of flags where only one is `true` at a time,
that's a hint that what you really want is an `enum`.
In this case, that `enum` is exactly the set of states for our FSM, so let's
define that:
^code enum
Instead of a bunch of flags, `Heroine` will just have one `state_` field. We
also flip the order of our branching. In the previous code, we switched on
input, *then* on state. This kept the code for handling one button press
together, but it smeared around the code for one state. We want to keep that
together, so we switch on state first. That gives us:
^code state-switch
This seems trivial, but it's a real improvement over the previous code. We still
have some conditional branching, but we simplified the mutable state to a single field. All of the code for
handling a single state is now nicely lumped together. This is the simplest way
to implement a state machine and is fine for some uses.
Your problem may outgrow this solution, though. Say we want to add a move where
our heroine can duck for a while to charge up and unleash a special attack.
While she's ducking, we need to track the charge time.
We add a `chargeTime_` field to `Heroine` to store how long the attack has
charged. Assume we already have an `update()` that
gets called each frame. In there, we add:
^code switch-update
We need to reset the timer when she starts ducking, so we modify
`handleInput()`:
^code state-switch-reset
All in all, to add this charge attack, we had to modify two methods and add a
`chargeTime_` field onto `Heroine` even though it's only meaningful while in
the ducking state. What we'd prefer is to have all of that code and data nicely
wrapped up in one place. The Gang of Four has us covered.
## The State Pattern
For people deeply into the object-oriented mindset, every conditional branch is an opportunity to use dynamic dispatch (in other
words a virtual method call in C++). I think you can go too far down that
rabbit hole. Sometimes an `if` is all you need.
But in our example, we've reached a tipping point where something
object-oriented is a better fit. That gets us to the State pattern. In the words
of the Gang of Four:
> Allow an object to alter its behavior when its internal state changes. The object will appear to change its class.
That doesn't tell us much. Heck, our `switch` does that. The concrete pattern
they describe looks like this when applied to our heroine:
### A state interface
First, we define an interface for the state. Every bit of behavior that is
state-dependent -- every place we had a `switch` before -- becomes a virtual
method in that interface. For us, that's `handleInput()` and `update()`:
^code heroine-state
### Classes for each state
For each state, we define a class that implements the interface. Its methods
define the heroine's behavior when in that state. In other words, take each `case`
from the earlier `switch` statements and move them into their state's class. For example:
^code ducking-state
Note that we also moved `chargeTime_` out of `Heroine` and into the `DuckingState`
class. This is great -- that piece of data is only meaningful while in that state,
and now our object model reflects that explicitly.
### Delegate to the state
Next, we give the `Heroine` a pointer to her current state, lose each big `switch`, and delegate to the state instead:
^code gof-heroine
In order to "change state", we just need to assign `state_` to point to a
different `HeroineState` object. That's the State pattern in its entirety.
## Where Are the State Objects?
I did gloss over one bit here. To change states, we need to assign `state_` to
point to the new one, but where does that object come from? With our `enum`
implementation, that was a no-brainer -- `enum` values are primitives like
numbers. But now our states are classes, which means we need an actual instance
to point to. There are two common answers to this:
### Static states
If the state object doesn't have any other fields, then
the only data it stores is a pointer to the internal virtual method table so
that its methods can be called. In that case, there's no reason to ever have
more than one instance of it. Every instance would be identical anyway.
In that case, you can make a single *static* instance. Even if you have a
bunch of FSMs all going at the same time in that same state, they can all point
to the same instance since it has nothing
machine-specific about it.
*Where* you put that static instance is up to you. Find a place that makes
sense. For no particular reason, let's put ours inside the base state class:
^code heroine-static-states
Each of those static fields is the one instance of that state that the game
uses. To make the heroine jump, the standing state would do something like:
^code jump
### Instantiated states
Sometimes, though, this doesn't fly. A static state won't work for the ducking
state. It has a `chargeTime_` field, and that's specific to the heroine that
happens to be ducking. This may coincidentally work in our game if there's only
one heroine, but if we try to add two-player co-op and have two heroines on
screen at the same time, we'll have problems.
In that case, we have to create a state
object when we transition to it. This lets each FSM have its own instance of the state. Of course, if we're allocating a *new* state, that means we need to free the *current* one. We have to be careful here, since the code that's triggering the change is in a method in the current state. We don't want to delete `this` out from under ourselves.
Instead, we'll allow `handleInput()` in `HeroineState` to optionally return a new state. When it does, `Heroine` will delete the old one and swap in the new one, like so:
^code swap-instance
That way, we don't delete the previous state until we've returned from its method. Now, the standing state can transition to ducking by creating a new instance:
^code duck
When I can, I prefer to use static states since they don't burn memory and CPU cycles allocating objects
each state change. For states that are more, uh, *stateful*, though, this is the
way to go.
## Enter and Exit Actions
The goal of the State pattern is to encapsulate all of the behavior and data for
one state in a single class. We're partway there, but we still have
some loose ends.
When the heroine changes state, we also switch her sprite. Right now, that code is owned by the state she's switching *from*. When she goes from ducking to standing, the ducking state sets her image:
^code enter-standing-before
What we really want is each state to control its own graphics. We can
handle that by giving the state an *entry action*:
^code standing-with-enter
Back in `Heroine`, we modify the code for handling state changes to call that
on the new state:
^code change-state
This lets us simplify the ducking code to:
^code enter-standing
All it does is switch to standing and the standing state takes care of
the graphics. Now our states really are encapsulated. One particularly nice thing
about entry actions is that they run when you enter the state regardless of
which state you're coming *from*.
Most real-world state graphs have multiple transitions into the same state. For
example, our heroine will also end up standing after she lands a jump or dive. That means we would end up duplicating some code everywhere that transition
occurs. Entry actions give us a place to consolidate that.
We can, of course, also extend this to support an *exit action*. This is just a
method we call on the state we're *leaving* right before we switch to the new
state.
## What's the Catch?
I've spent all this time selling you on FSMs, and now I'm going to pull the rug
out from under you. Everything I've said so far is true, and FSMs are a good fit
for some problems. But their greatest virtue is also their greatest flaw.
State machines help you untangle hairy code by enforcing a very constrained structure on it. All you've got is a fixed set
of states, a single current state, and some hardcoded transitions.
If you try using a state machine for something more complex like game AI, you
will slam face-first into the limitations of that model. Thankfully, our
forebears have found ways to dodge some of those barriers. I'll close this
chapter out by walking you through a couple of them.
## Concurrent State Machines
We've decided to give our heroine the ability to carry a gun. When she's packing
heat, she can still do everything she could before: run, jump, duck, etc. But
she also needs to be able to fire her weapon while doing it.
If we want to stick to the confines of an FSM, we have to *double* the number of
states we have. For each existing state, we'll need another one for doing the
same thing while she's armed: standing, standing with gun, jumping, jumping with
gun, you get the idea.
Add a couple of more weapons and the number of states explodes combinatorially.
Not only is it a huge number of states, it's a huge amount of redundancy: the
unarmed and armed states are almost identical except for the little bit of code
to handle firing.
The problem is that we've jammed two pieces of
state -- what she's *doing* and what she's *carrying* -- into a single machine.
To model all possible combinations, we would need a state for each *pair*. The
fix is obvious: have two separate state machines.
We keep our original state machine for what she's doing and leave it alone. Then
we define a separate state machine for what she's carrying. `Heroine` will have
*two* "state" references, one for each, like:
^code two-states
When the heroine delegates inputs to the states, she hands it to both of them:
^code handle-two-inputs
Each state machine can then respond to inputs, spawn behavior, and change its
state independently of the other machine. When the two sets of states are mostly
unrelated, this works well.
In practice, you'll find a few cases where the states do interact. For example,
maybe she can't fire while jumping, or maybe she can't do a dive attack if she's
armed. To handle that, in the code for one state, you'll probably just do some
crude `if` tests on the *other* machine's state to coordinate them. It's not the most
elegant solution, but it gets the job done.
## Hierarchical State Machines
After fleshing out our heroine's behavior some more, she'll likely have a bunch
of similar states. For example, she may have standing, walking, running, and
sliding states. In any of those, pressing B jumps and pressing down ducks.
With a simple state machine implementation, we have to duplicate that code in
each of those states. It would be better if we could implement that once and
reuse it across all of the states.
If this was just object-oriented code instead of a state machine, one way to
share code across those states would be using inheritance. We could define a class for an "on
ground" state that handles jumping and ducking. Standing, walking, running, and
sliding would then inherit from that and add their own additional behavior.
It turns out, this is a common structure called a *hierarchical state machine*.
A state can have a *superstate* (making itself a *substate*). When an event
comes in, if the substate doesn't handle it, it rolls up the chain of
superstates. In other words, it works just like overriding inherited methods.
In fact, if we're using the State pattern to implement our FSM, we can
use class inheritance to implement the hierarchy. Define a base class for the
superstate:
^code on-ground
And then each substate inherits it:
^code duck-on-ground
This isn't the only way to implement the hierarchy, of course. If you aren't
using the Gang of Four's State pattern, this won't work. Instead, you can model
the current state's chain of superstates explicitly using a *stack* of states
instead of a single state in the main class.
The current state is the one on the top of the stack, under that is its
immediate superstate, and then *that* state's superstate and so on. When you
dish out some state-specific behavior, you start at the top of the stack and
walk down until one of the states handles it. (If none do, you ignore it.)
## Pushdown Automata
There's another common extension to finite state machines that also uses a stack
of states. Confusingly, the stack represents something entirely different, and
is used to solve a different problem.
The problem is that finite state machines have no concept of *history*. You know
what state you *are* in, but have no memory of what state you *were* in. There's
no easy way to go back to a previous state.
Here's an example: Earlier, we let our fearless heroine arm herself to the
teeth. When she fires her gun, we need a new state that plays the firing
animation and spawns the bullet and any visual effects. So we slap together a
`FiringState` and make all of the states that she can
fire from transition into that when the fire button is pressed.
The tricky part is what state she transitions to *after* firing. She can pop off
a round while standing, running, jumping, and ducking. When the firing sequence
is complete, she should transition back to what she was doing before.
If we're sticking with a vanilla FSM, we've already forgotten what state she was
in. To keep track of it, we'd have to define a slew of nearly identical states
-- firing while standing, firing while running, firing while jumping, and so on
-- just so that each one can have a hardcoded transition that goes back to the
right state when it's done.
What we'd really like is a way to *store* the state she was in before firing and
then *recall* it later. Again, automata theory is here to help. The relevant
data structure is called a [*pushdown
automaton*](http://en.wikipedia.org/wiki/Pushdown_automaton).
Where a finite state machine has a *single* pointer to a state, a pushdown
automaton has a *stack* of them. In an FSM, transitioning to a new state
*replaces* the previous one. A pushdown automaton lets you do that, but it also
gives you two additional operations:
1. You can *push* a new state onto the stack. The "current" state is always the
one on top of the stack, so this transitions to the new state. But it leaves
the previous state directly under it on the stack instead of discarding it.
2. You can *pop* the topmost state off the stack. That state is discarded, and
the state under it becomes the new current state.
This is just what we need for firing. We create a *single* firing state. When
the fire button is pressed while in any other state, we *push* the firing state
onto the stack. When the firing animation is done, we *pop* that state off, and
the pushdown automaton automatically transitions us right back to the state we
were in before.
## So How Useful Are They?
Even with those common extensions to state machines, they are still pretty
limited. The trend these days in game AI is more toward exciting things like
*[behavior trees][]* and *[planning systems][]*. If complex AI is what you're interested in,
all this chapter has done is whet your appetite. You'll want to read other books
to satisfy it.
[behavior trees]: http://web.archive.org/web/20140402204854/http://www.altdevblogaday.com/2011/02/24/introduction-to-behavior-trees/
[planning systems]: http://web.media.mit.edu/~jorkin/goap.html
This doesn't mean finite state machines, pushdown automata, and other simple
systems aren't useful. They're a good modeling tool for certain kinds of
problems. Finite state machines are useful when:
* You have an entity whose behavior changes based on some internal state.
* That state can be rigidly divided into one of a relatively small number of
distinct options.
* The entity responds to a series of inputs or events over time.
In games, they are most known for being used in AI, but they are also common in
implementations of user input handling, navigating menu screens, parsing text,
network protocols, and other asynchronous behavior.