Confession time: I went a little overboard and packed way too much into thischapter. It’s ostensibly about the Statedesign pattern, but I can’t talk about that and games without going into themore fundamental concept of finite state machines (or “FSMs”). But then once Iwent there, I figured I might as well introduce hierarchical state machinesand pushdown automata.
That’s a lot to cover, so to keep things as short as possible, the code sampleshere leave out a few details that you’ll have to fill in on your own. I hopethey’re still clear enough for you to get the big picture.
- State machines Traditionally, we would default to the AI Behavior Tree, which is available to anyone using UE4. However, in our scenario, we will break the job of Behavior Tree into components directly written in blueprint.
- Sets up a native state exit delegate from state with StateName, in the state machine with name MachineName. Void AddNativeTransitionBinding.
A state machine can share signal with another one. So the state machine that indicate prod or dev can send a signal to the other one. In fact, if you have only 2 state on the state machine, you can use a variable for that purpose. So you will have one state machine that will do different job depending on the value of the variable.
Don’t feel sad if you’ve never heard of a state machine. While well known toAI and compiler hackers, they aren’t that familiarto other programming circles. I think they should be more widely known, so I’mgoing to throw them at a different kind of problem here.
This pairing echoes the early days of artificial intelligence. In the ’50s and’60s, much of AI research was focused on language processing. Many of thetechniques compilers now use for parsing programming languages were invented forparsing human languages.
We’ve All Been There
We’re working on a little side-scrolling platformer. Our job is to implement theheroine that is the player’s avatar in the game world. That means making herrespond to user input. Push the B button and she should jump. Simple enough:
Spot the bug?
There’s nothing to prevent “air jumping” — keep hammering B while she’s in theair, and she will float forever. The simple fix is toadd an isJumping_ Boolean field to Heroine that tracks when she’s jumping,and then do:
There should also be code that sets isJumping_ back to false when theheroine touches the ground. I’ve omitted that here for brevity’s sake.
Next, we want the heroine to duck if the player presses down while she’s on theground and stand back up when the button is released:
Spot the bug this time?
With this code, the player could:
- Press down to duck.
- Press B to jump from a ducking position.
- Release down while still in the air.
The heroine will switch to her standing graphic in the middle of the jump. Timefor another flag…
Next, it would be cool if the heroine did a dive attack if the player pressesdown in the middle of a jump:
Bug hunting time again. Find it?
We check that you can’t air jump while jumping, but not while diving. Yetanother field…
Something is clearly wrong with our approach. Every timewe touch this handful of code, we break something. We need to add a bunch moremoves — we haven’t even added walking yet — but at this rate, it willcollapse into a heap of bugs before we’re done with it.
Those coders you idolize who always seem to create flawless code aren’t simplysuperhuman programmers. Instead, they have an intuition about which kinds ofcode are error-prone, and they steer away from them.
Complex branching and mutable state — fields that change over time — are twoof those error-prone kinds of code, and the examples above have both.
Finite State Machines to the Rescue
In a fit of frustration, you sweep everything off your desk except a pen andpaper and start drawing a flowchart. You draw a box for each thing the heroinecan be doing: standing, jumping, ducking, and diving. When she can respond to abutton press in one of those states, you draw an arrow from that box, label itwith that button, and connect it to the state she changes to.
Congratulations, you’ve just created a finite state machine. These came out ofa branch of computer science called automata theory whose family of datastructures also includes the famous Turing machine. FSMs are the simplest memberof 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’trecognize our scribbles, so how do we go about implementing one? The Gang ofFour’s State pattern is one method — which we’ll get to — but let’s start simpler.
My favorite analogy for FSMs is the old text adventure games like Zork. You havea world of rooms that are connected to each other by exits. You explore them byentering commands like “go north”.
This maps directly to a state machine: Each room is a state. The room you’re inis the current state. Each room’s exits are its transitions. The navigationcommands are the inputs.
Enums and Switches
One problem our Heroine class has is some combinations of those Boolean fieldsaren’t valid: isJumping_ and isDucking_ should never both be true, forexample. 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’sdefine that:
Instead of a bunch of flags, Heroine will just have one state_ field. Wealso flip the order of our branching. In the previous code, we switched oninput, then on state. This kept the code for handling one button presstogether, but it smeared around the code for one state. We want to keep thattogether, so we switch on state first. That gives us:
This seems trivial, but it’s a real improvement over the previous code. We stillhave some conditional branching, but we simplified the
In particular, the heroine can no longer be in an invalid state. With theBoolean flags, some sets of values were possible but meaningless. With the enum,each value is valid.
Your problem may outgrow this solution, though. Say we want to add a move whereour 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 hascharged. Assume we already have an update() thatgets called each frame. In there, we add:
If you guessed that this is the Update Method pattern, you win a prize!
We need to reset the timer when she starts ducking, so we modifyhandleInput():
All in all, to add this charge attack, we had to modify two methods and add achargeTime_ field onto Heroine even though it’s only meaningful while inthe ducking state. What we’d prefer is to have all of that code and data nicelywrapped up in one place. The Gang of Four has us covered.
The State Pattern
For people deeply into the object-oriented mindset, every conditional if is all you need.
There’s a historical basis for this. Many of the original object-orientedapostles like Design Patterns‘ Gang of Four, and Refactoring‘s Martin Fowlercame from Smalltalk. There, ifThen: is just a method you invoke on thecondition, which is implemented differently by the true and false objects.
But in our example, we’ve reached a tipping point where somethingobject-oriented is a better fit. That gets us to the State pattern. In the wordsof 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 patternthey 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 isstate-dependent — every place we had a switch before — becomes a virtualmethod in that interface. For us, that’s handleInput() and update():
Classes for each state
For each state, we define a class that implements the interface. Its methodsdefine the heroine’s behavior when in that state. In other words, take each casefrom the earlier switch statements and move them into their state’s class. For example:
Note that we also moved chargeTime_ out of Heroine and into the DuckingStateclass. 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:
In order to “change state”, we just need to assign state_ to point to adifferent HeroineState object. That’s the State pattern in its entirety.
This looks like the Strategy and Type Object patterns. In all three, you have a main objectthat delegates to another subordinate one. The difference is intent.
With Strategy, the goal is to decouple the main class from some portion of its behavior.
With Type Object, the goal is to make a number of objects behave similarly by sharing a reference to the same type object.
With State, the goal is for the main object to change its behavior by changing the object it delegates to.
Where Are the State Objects?
I did gloss over one bit here. To change states, we need to assign state_ topoint to the new one, but where does that object come from? With our enumimplementation, that was a no-brainer — enum values are primitives likenumbers. But now our states are classes, which means we need an actual instanceto point to. There are two common answers to this:
Static states
If the state object doesn’t have any other fields, thenthe only data it stores is a pointer to the internal virtual method table sothat its methods can be called. In that case, there’s no reason to ever havemore than one instance of it. Every instance would be identical anyway.
If your state has no fields and only one virtual method in it, you cansimplify this pattern even more. Replace each state class with a statefunction — just a plain vanilla top-level function. Then, the state_ fieldin your main class becomes a simple function pointer.
In that case, you can make a single static instance. Even if you have abunch of FSMs all going at the same time in that same state, they can all pointto the same instance since it has nothingmachine-specific about it.
This is the Flyweight pattern.
Where you put that static instance is up to you. Find a place that makessense. For no particular reason, let’s put ours inside the base state class:
Each of those static fields is the one instance of that state that the gameuses. To make the heroine jump, the standing state would do something like:
Instantiated states
Sometimes, though, this doesn’t fly. A static state won’t work for the duckingstate. It has a chargeTime_ field, and that’s specific to the heroine thathappens to be ducking. This may coincidentally work in our game if there’s onlyone heroine, but if we try to add two-player co-op and have two heroines onscreen at the same time, we’ll have problems.
In that case, we have to create a stateobject 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:
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:
When I can, I prefer to use static states since they don’t burn memory and CPU cycles allocating objectseach state change. For states that are more, uh, stateful, though, this is theway to go.
When you dynamically allocate states, you may have to worry about fragmentation.The Object Pool pattern can help.
Enter and Exit Actions
The goal of the State pattern is to encapsulate all of the behavior and data forone state in a single class. We’re partway there, but we still havesome 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:
What we really want is each state to control its own graphics. We canhandle that by giving the state an entry action:
Back in Heroine, we modify the code for handling state changes to call thaton the new state:
This lets us simplify the ducking code to:
All it does is switch to standing and the standing state takes care ofthe graphics. Now our states really are encapsulated. One particularly nice thingabout entry actions is that they run when you enter the state regardless ofwhich state you’re coming from.
Most real-world state graphs have multiple transitions into the same state. Forexample, 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 transitionoccurs. Entry actions give us a place to consolidate that.
We can, of course, also extend this to support an exit action. This is just amethod we call on the state we’re leaving right before we switch to the newstate.
What’s the Catch?
I’ve spent all this time selling you on FSMs, and now I’m going to pull the rugout from under you. Everything I’ve said so far is true, and FSMs are a good fitfor some problems. But their greatest virtue is also their greatest flaw.
State machines help you untangle hairy code by enforcing a very
A finite state machine isn’t even Turing complete. Automata theory describescomputation using a series of abstract models, each more complex than theprevious. A Turing machine is one of the most expressive models.
“Turing complete” means a system (usually a programming language) is powerfulenough to implement a Turing machine in it, which means all Turing completelanguages are, in some ways, equally expressive. FSMs are not flexible enoughto be in that club.
If you try using a state machine for something more complex like game AI, youwill slam face-first into the limitations of that model. Thankfully, ourforebears have found ways to dodge some of those barriers. I’ll close thischapter 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 packingheat, she can still do everything she could before: run, jump, duck, etc. Butshe 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 ofstates we have. For each existing state, we’ll need another one for doing thesame thing while she’s armed: standing, standing with gun, jumping, jumping withgun, 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: theunarmed and armed states are almost identical except for the little bit of codeto handle firing.
The problem is that we’ve jammed two pieces ofstate — 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. Thefix is obvious: have two separate state machines.
If we want to cram n states for what she’s doing and m states for what she’scarrying into a single machine, we need n × m states. With two machines,it’s just n + m.
We keep our original state machine for what she’s doing and leave it alone. Thenwe define a separate state machine for what she’s carrying. Heroine will havetwo “state” references, one for each, like:
For illustrative purposes, we’re using the full State pattern for her equipment.In practice, since it only has two states, a Boolean flag would work too.
When the heroine delegates inputs to the states, she hands it to both of them:
A more full-featured system would probably have a way for one state machine toconsume an input so that the other doesn’t receive it. That would prevent bothmachines from erroneously trying to respond to the same input.
Each state machine can then respond to inputs, spawn behavior, and change itsstate independently of the other machine. When the two sets of states are mostlyunrelated, 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’sarmed. To handle that, in the code for one state, you’ll probably just do somecrude if tests on the other machine’s state to coordinate them. It’s not the mostelegant solution, but it gets the job done.
Hierarchical State Machines
After fleshing out our heroine’s behavior some more, she’ll likely have a bunchof similar states. For example, she may have standing, walking, running, andsliding states. In any of those, pressing B jumps and pressing down ducks.
With a simple state machine implementation, we have to duplicate that code ineach of those states. It would be better if we could implement that once andreuse it across all of the states.
If this was just object-oriented code instead of a state machine, one way toshare code across those states would be using
This has both good and bad implications. Inheritance is a powerful means of codereuse, but it’s also a very strong coupling between two chunks of code. It’s a bighammer, so swing it carefully.
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 eventcomes in, if the substate doesn’t handle it, it rolls up the chain ofsuperstates. In other words, it works just like overriding inherited methods.
In fact, if we’re using the State pattern to implement our FSM, we canuse class inheritance to implement the hierarchy. Define a base class for thesuperstate:
And then each substate inherits it:
This isn’t the only way to implement the hierarchy, of course. If you aren’tusing the Gang of Four’s State pattern, this won’t work. Instead, you can modelthe current state’s chain of superstates explicitly using a stack of statesinstead of a single state in the main class.
The current state is the one on the top of the stack, under that is itsimmediate superstate, and then that state’s superstate and so on. When youdish out some state-specific behavior, you start at the top of the stack andwalk 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 stackof states. Confusingly, the stack represents something entirely different, andis used to solve a different problem.
The problem is that finite state machines have no concept of history. You knowwhat state you are in, but have no memory of what state you were in. There’sno easy way to go back to a previous state.
Here’s an example: Earlier, we let our fearless heroine arm herself to theteeth. When she fires her gun, we need a new state that plays the firinganimation and spawns the bullet and any visual effects. So we slap together aFiringState and make all of the states that she canfire from transition into that when the fire button is pressed.
Since this behavior is duplicated across several states, it may also be a goodplace to use a hierarchical state machine to reuse that code.
The tricky part is what state she transitions to after firing. She can pop offa round while standing, running, jumping, and ducking. When the firing sequenceis 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 wasin. 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 theright state when it’s done.
What we’d really like is a way to store the state she was in before firing andthen recall it later. Again, automata theory is here to help. The relevantdata structure is called a pushdownautomaton.
Where a finite state machine has a single pointer to a state, a pushdownautomaton has a stack of them. In an FSM, transitioning to a new statereplaces the previous one. A pushdown automaton lets you do that, but it alsogives you two additional operations:
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.
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. Whenthe fire button is pressed while in any other state, we push the firing stateonto the stack. When the firing animation is done, we pop that state off, andthe pushdown automaton automatically transitions us right back to the state wewere in before.
So How Useful Are They?
Even with those common extensions to state machines, they are still prettylimited. The trend these days in game AI is more toward exciting things likebehavior 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 booksto satisfy it.
This doesn’t mean finite state machines, pushdown automata, and other simplesystems aren’t useful. They’re a good modeling tool for certain kinds ofproblems. 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.
Ue4 State Machine Slots Double Diamond
In games, they are most known for being used in AI, but they are also common inimplementations of user input handling, navigating menu screens, parsing text,network protocols, and other asynchronous behavior.