A finite state machine is a highly useful tool for programmers in general and for video game programmers in particular. If you’re not familiar with the notion, think about the Finite State Machine (FSM) as a GameBoy, and the States as different cartridges or games.
The GameBoy can only have one game running at any time (or no game at all, in which case it’s not very useful). Obviously, all cartridges share some characteristics (shape, connection pins, etc.…) that allow the GameBoy to interact with any game without knowing or caring what it actually does, just plug it in and it works.
There is one last, important, characteristic that defines this system. Each “game” or state has the rules to decide when to change to another different game (this kind of fucks up the metaphor, but I could not find any better).
So, code-wise, this would be a system as follows:
The FSM has one state active, which it updates every cycle. At any moment, the FSM can be told to change to a different state. All states inherit from the State class, and have a common interface so the FSM doesn’t need to know what they do internally, just call the appropriate functions.
A classic FSM pseudo-code has a structure as follows:
And a base state pseudo-code has the following structure:
Actual states are not instantiated, only derived states (in our example ShootEnemy, Defend, etc. )
Making it Useful
This basic FSM has several problems or shortcomings that limit it’s use, so let’s have a look at some of them.
Changing State at the Proper Time
The main flaw the basic FSM pattern has is the fact that at any moment, the current state can request the FSM to change to a different state. When this happens, the following steps take place:
- CurrentState = NewState;
- CurrentState->Enter() // This is the new state
If the fsmReference->ChangeState() call was in the middle of the the Update function, this can leave the state in an undefined state, and propagate errors later on.
We shall make a request mechanism in the FSM, instead of changing the state, we will request the FSM to change to a state, and the FSM after the state update will change to a different state. For this we replace the ChangeState function for a RequestoReplaceState, and a DoStateReplacement.
Check this pseudo-code for a clearer idea:
Push & Pop
Now we have a FSM that won’t inadvertently introduce subtle ninja bugs when we’re not looking, and can replace the current state for another. But we want to add to the FSM the ability of when we change to a state, to push the current state back into memory, to be popped later on. This might be useful for example in this scenario:
- Guard.state = patrolling –> Hears sound
- Guard.state = goSeeDisturbance , PushBack( patrolling )
- Guard –> Doesn’t find anything in sound source. Pop ( goSeeDisturbance )
- Guard.state = patrolling
Instead of destroying the patrolling state and then having to create it again, we just push it back, store it, and once the temporal state (goSeeDisturbance) is over, we resume patrolling.
To properly do this we need to add a pause functionality to our states. Notice a very important detail that is that the Pause / Update / Resume functions, overloaded in the base classes, are no longer called by the FSM but instead we have Manager functions (ManagerUpdate, ManagerPause, ManagerResume) that are called by the FMS, while derived classes (from State) just override the same version without the “Manager” part. This allows us to add some extra functionality to all Update / Pause / Resume calls of all derived classes. With this, we can implement pause / resume, by letting the user specify what is going to happen in his state when it pauses / resumes, while doing the maintenance work (setting flags and safety checks) in the manager version. Check the code for a clearer idea:
And add a push & pop mechanism to the FSM, very similar to the replace mechanism, but we store the pushed state in a variable, to restore it later. This is only an example, so it’s not very useful. For it to be useful we would need a list of pushed states, because that would allow us to push and pop as much as we wanted.
Last improvement we can add is a timed update, by simply passing a “update time” to each state constructor and making the State::ManagerUpdate keep track of it:
It’s not “by example” if it doesn’t have an example, so here is a complete example in Java.
Finite State Machine
Finite states machines are a very useful construct for controlling the flow of a game, how your game scene updates in different situations, how your character acts… It’s not a holly grail, all purpose solution, but it works surprisingly well for many scenarios.