Introduction
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.
FSM
A classic FSM pseudo-code has a structure as follows:
Code Snippet
- class FSM
- {
- // Current state the FSM uses
- State* currentState;
-
- // Calls the Update function of
- // the currentState
- Update();
-
- // Calls exit of the currentState
- // sets newState as currentState
- // call enter of currentState
- ChangeState(State * newState);
- };
State
And a base state pseudo-code has the following structure:
Code Snippet
- class State
- {
- // Pointer to the parent FSM
- FSM* fsmReference;
-
- // Called when the state is initialized
- // by the FSM
- public virtual void Enter();
-
- // Called when the state is ended by the
- // FSM
- public virtual void Exit();
-
- // Called every update cycle by the FSM
- protected virtual void Update();
- }
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
Problem
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->Exit();
- 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.
Solution
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:
Code Snippet
- class FSM // With delay state change
- {
- private:
- // Current state the FSM uses
- State* currentState;
-
- // Temporal pointer to the new state
- State* newState;
-
- // Flag indicating wheter to change state
- bool requestedStateChange;
-
- // Calls the Update function of
- // the currentState
- void Update();
-
- // If a requested state pending,
- // change to new state
- void DoStateReplacement();
-
- // Calls exit of the currentState
- // sets newState as currentState
- // call enter of currentState
- void RequestReplaceState(State * newState);
- };
-
- void FSM::Update()
- {
- if(requestedStateChange)
- {
- DoStateReplacement();
- }
- else if(this.currentState != null)
- {
- currentState->Update();
- }
- }
-
- void FSM::RequestReplaceState(SinState newState)
- {
- nextState = newState;
- requestedStateChange = true;
- }
-
- void FSM::DoStateReplacement()
- {
- if(nextState == null)
- { return; }
-
- requestedStateChange = false;
-
- if(currentState != null)
- { currentState->Exit(); }
-
- currentState = this.nextState;
- nextState = null;
-
- currentState->Enter();
- }
Push & Pop
Problem
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.
Solution
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:
Code Snippet
- class State
- {
- // Pointer to the parent FSM
- FSM* fsmReference;
-
- // Indicates whether the state is paused
- bool isPaused;
-
- // Overriden in base clases to put pause
- // logic
- protected virtual void Pause();
-
- // Overriden in base clases to put
- // resume logic
- protected virtual void Resume();
-
- // Called when the state is initialized
- // by the FSM
- public virtual void Enter();
-
- // Called when the state is ended by the
- // FSM
- public virtual void Exit();
-
- // NOT CALLED BY FSM ANYMORE
- protected virtual void Update();
-
- // Called by the FSM every update
- // cycle
- public void ManagerUpdate();
-
- // CAlled by FSM on pause
- public void ManagerPause();
-
- // Called by FSM on resume
- public void ManagerResume();
- }
-
-
- void State::ManagerUpdate()
- {
- if(!this.isPaused)
- { this.Update(); }
- }
-
- void State::ManagerPause()
- {
- this.isPaused = true;
- this.Pause();
- }
-
- void State::ManagerResume()
- {
- this.isPaused = false;
- this.Resume();
- }
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.
Timed Update
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:
Code Snippet
- public void ManagerUpdate()
- {
- if(!this->isPaused)
- {
- if(this->updatePeriod == 0 ||
- CurrentTime() - this->lastUpdateTime >=
- this->updatePeriod)
- {
- this->Update();
- this->lastUpdateTime = CurrentTime();
- }
- }
- }
The Code
It’s not “by example” if it doesn’t have an example, so here is a complete example in Java.
Finite State Machine
State
Code Snippet
- /**
- * Base class for states.
- * Supports state pause.
- * @author Ying
- *
- */
- public abstract class SinState
- {
- /**
- * Whether the state is paused.
- */
- protected boolean isPaused;
-
- /**
- * Update period of the state.
- */
- protected int updatePeriod;
-
- /**
- * Last update period.
- */
- private long lastUpdateTime;
-
- /**
- * Reference to the FSM
- */
- protected StateMachine FSM;
-
- /**
- * State name.
- */
- public String name;
-
- /**
- * Whether the state was pushed.
- */
- private boolean wasPushed;
-
- /**
- * Initializes an instance of the SinState class.
- * @param updatePeriod The time (in ms) between
- * each update. Set 0 for going as fast as possible.
- */
- public SinState(int updatePeriod, StateMachine FSM, String name)
- {
- this.isPaused = false;
- this.updatePeriod = updatePeriod;
- this.lastUpdateTime = System.currentTimeMillis();
- this.FSM = FSM;
- this.name = name;
- }
-
- // Override functions
- public abstract void Enter();
- public abstract void Exit();
- protected abstract void Update();
- protected abstract void Pause();
- protected abstract void Resume();
-
- // Manager functions
- public void ManagerUpdate()
- {
- if(!this.isPaused)
- {
- if(this.updatePeriod == 0 ||
- System.currentTimeMillis() - this.lastUpdateTime >=
- this.updatePeriod)
- {
- this.Update();
- this.lastUpdateTime = System.currentTimeMillis();
- }
- }
- }
-
- public void ManagerPause()
- {
- this.isPaused = true;
- this.Pause();
- }
-
- public void ManagerResume()
- {
- this.isPaused = false;
- this.Resume();
- this.lastUpdateTime = System.currentTimeMillis();
- }
-
- public void SetWasPushed(boolean pushed)
- { this.wasPushed = pushed; }
-
- public boolean WasPushed()
- { return this.wasPushed; }
- }
Conclusion
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.
Enjoy.