State Machines By Example: A Useful FSM

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

1. class FSM
2. {
3.     // Current state the FSM uses
4.     State* currentState;
5.  
6.     // Calls the Update function of
7.     // the currentState
8.     Update();
9.  
10.     // Calls exit of the currentState
11.     // sets newState as currentState
12.     // call enter of currentState
13.     ChangeState(State * newState);
14. };

 

State

And a base state pseudo-code has the following structure:

Code Snippet

1. class State
2. {
3.     // Pointer to the parent FSM
4.     FSM* fsmReference;
5.  
6.     // Called when the state is initialized
7.     // by the FSM
8.     public virtual void Enter();
9.  
10.     // Called when the state is ended by the
11.     // FSM
12.     public virtual void Exit();
13.  
14.     // Called every update cycle by the FSM
15.     protected virtual void Update();
16. }

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

1. class FSM // With delay state change
2. {
3. private:
4.     // Current state the FSM uses
5.     State* currentState;
6.  
7.     // Temporal pointer to the new state
8.     State* newState;
9.  
10.     // Flag indicating wheter to change state
11.     bool requestedStateChange;
12.  
13.     // Calls the Update function of
14.     // the currentState
15.     void Update();
16.  
17.     // If a requested state pending,
18.     // change to new state
19.     void DoStateReplacement();
20.  
21.     // Calls exit of the currentState
22.     // sets newState as currentState
23.     // call enter of currentState
24.     void RequestReplaceState(State * newState);
25. };
26.  
27. void FSM::Update()
28. {
29.     if(requestedStateChange)
30.     {
31.         DoStateReplacement();
32.     }
33.     else if(this.currentState != null)
34.     {
35.         currentState->Update();
36.     }
37. }
38.  
39. void FSM::RequestReplaceState(SinState newState)
40. {
41.     nextState = newState;
42.     requestedStateChange = true;
43. }
44.  
45. void FSM::DoStateReplacement()
46. {
47.     if(nextState == null)
48.     { return; }
49.     
50.     requestedStateChange = false;
51.  
52.     if(currentState != null)
53.     { currentState->Exit();    }
54.     
55.     currentState = this.nextState;
56.     nextState = null;
57.     
58.     currentState->Enter();
59. }

 

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

1. class State
2. {
3.     // Pointer to the parent FSM
4.     FSM* fsmReference;
5.  
6.     // Indicates whether the state is paused
7.     bool isPaused;
8.  
9.     // Overriden in base clases to put pause
10.     // logic
11.     protected virtual void Pause();
12.  
13.     // Overriden in base clases to put
14.     // resume logic
15.     protected virtual void Resume();
16.  
17.     // Called when the state is initialized
18.     // by the FSM
19.     public virtual void Enter();
20.  
21.     // Called when the state is ended by the
22.     // FSM
23.     public virtual void Exit();
24.  
25.     // NOT CALLED BY FSM ANYMORE
26.     protected virtual void Update();
27.  
28.     // Called by the FSM every update
29.     // cycle
30.     public void ManagerUpdate();
31.     
32.     // CAlled by FSM on pause
33.     public void ManagerPause();
34.  
35.     // Called by FSM on resume
36.     public void ManagerResume();    
37. }
38.  
39.  
40. void State::ManagerUpdate()
41. {
42.     if(!this.isPaused)
43.     { this.Update(); }
44. }
45.     
46. void State::ManagerPause()
47. {
48.     this.isPaused = true;
49.     this.Pause();
50. }
51.     
52. void State::ManagerResume()
53. {
54.     this.isPaused = false;
55.     this.Resume();
56. }

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.

Code Snippet

1. class FSM
2. {
3.     // Current state the FSM uses
4.     State* currentState;
5.  
6.     // Calls the Update function of
7.     // the currentState
8.     Update();
9.  
10.     // Calls exit of the currentState
11.     // sets newState as currentState
12.     // call enter of currentState
13.     ChangeState(State * newState);
14.  
15.     
16.     // Stores a pushed state.
17.     // Make this->a list to store a pile of states.
18.     private State pushedState = null;
19.     
20.     
21.     // Indicates whether a new state push
22.     // has been requested.
23.     private bool requestedStatePush
24.     
25.     
26.     // Indicates whether a new state pop has
27.     // been requested.
28.     private bool requestedStatePop;
29.  
30.     void DoStatePop();
31.  
32.     void RequestStatePop();
33.  
34.     void DoStatePush();
35.  
36.     void RequestPushState(State newState);
37. };
38.  
39. void FSM::Update()
40. {
41.     if(this->requestedStateChange)
42.     {
43.         this->DoStateReplacement();
44.     }
45.     else if(this->requestedStatePush)
46.     {
47.         this->DoStatePush();
48.     }
49.     else if(this->requestedStatePop)
50.     {
51.         this->DoStatePop();
52.     }
53.     else if(this->currentState != null)
54.     {
55.         this->currentState.ManagerUpdate();
56.     }
57. }
58.  
59. void FSM::RequestPushState(State newState)
60. {
61.     this->nextState = newState;
62.     this->requestedStatePush = true;
63. }
64.  
65. void FSM::DoStatePush()
66. {
67.     if(this->nextState == null)
68.     {
69.         Log.Write("ERROR! Attempting state push in null state");
70.         return;
71.     }
72.  
73.     if(this->currentState == null)
74.     {
75.         Log.Write("ERROR! Attempting state push back null state");
76.         return;
77.     }
78.     
79.     this->requestedStatePush = false;
80.     this->pushedState = this->currentState;
81.     
82.     this->pushedState.ManagerPause();
83.     
84.     this->currentState = this->nextState;
85.     this->nextState = null;
86.     
87.     this->currentState.SetWasPushed(true);
88.     this->currentState.Enter();
89. }
90.  
91. void FSM::RequestStatePop()
92. {
93.     this->requestedStatePop = true;
94. }
95.  
96. void FSM::DoStatePop()
97. {
98.     if(this->pushedState == null)
99.     {
100.         Log.Write("ERROR! Attempting state pop null state");
101.         return;
102.     }
103.     
104.     if(this->currentState != null)
105.     {
106.         this->currentState.Exit();
107.     }
108.     
109.     this->requestedStatePop = false;
110.     this->currentState = this->pushedState;
111.     this->pushedState = null;
112.     
113.     assert this->currentState != null;
114.     this->currentState.ManagerResume();
115. }

 

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

1. public void ManagerUpdate()
2. {
3.     if(!this->isPaused)
4.     {
5.         if(this->updatePeriod == 0 ||
6.                 CurrentTime() - this->lastUpdateTime >=
7.                 this->updatePeriod)
8.         {
9.             this->Update();
10.             this->lastUpdateTime = CurrentTime();
11.         }
12.     }
13. }

 

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

Code Snippet

1. /**
2. * State machine behavior to provided
3. * different decision states.
4. *
5. * Supports push/pop and replace
6. * mechanisms. (Stack of only 1 stored state.)
7. *
8. * Supports safe-state switch via request.
9. * @author Ying
10. *
11. */
12. public class FSM
13. {    
14.     /**
15.      * Reference to current state.
16.      */
17.     private SinState currentState = null;
18.     
19.     /**
20.      * Reference to next state requested.
21.      */
22.     private SinState nextState = null;
23.     
24.     /**
25.      * Indicates whether a new
26.      * state replace has been requested.
27.      */
28.     private boolean requestedStateChange = false;
29.     
30.     /**
31.      * Stores a pushed state.
32.      * Make this a list to store a pile of states.
33.      */
34.     private SinState pushedState = null;
35.     
36.     /**
37.      * Indicates whether a new state push
38.      * has been requested.
39.      */
40.     private boolean requestedStatePush = false;
41.     
42.     /**
43.      * Indicates whether a new state pop has
44.      * been requested.
45.      */
46.     private boolean requestedStatePop = false;
47.  
48.     /**
49.      * Initializes a new instance of the StateMachine
50.      * class.
51.      */
52.     public FSM() {}
53.  
54.     /**
55.      * Update the FSM, and the current state if any.
56.      */
57.     @Override
58.     public void action()
59.     {
60.         if(this.requestedStateChange)
61.         {
62.             this.DoStateReplacement();
63.         }
64.         else if(this.requestedStatePush)
65.         {
66.             this.DoStatePush();
67.         }
68.         else if(this.requestedStatePop)
69.         {
70.             this.DoStatePop();
71.         }
72.         else if(this.currentState != null)
73.         {
74.             this.currentState.ManagerUpdate();
75.         }
76.     }
77.     
78.     /**
79.      * Request to change the current state to a new one.
80.      * Request will be stored till FSM update.
81.      * @param newState New state to change to.
82.      */
83.     public void RequestReplaceState(SinState newState)
84.     {
85.         this.nextState = newState;
86.         this.requestedStateChange = true;
87.     }
88.  
89.     /**
90.      * Do the actual state replace.
91.      */
92.     private void DoStateReplacement()
93.     {
94.         String prev = "Null";
95.         String next = "Null";
96.         if(this.nextState == null)
97.         {
98.             Log.Write("ERROR! Attempting state replacement to null state");
99.             return;
100.         }
101.         
102.         next = this.nextState.name;
103.         this.requestedStateChange = false;
104.         if(this.currentState != null)
105.         {
106.             this.currentState.Exit();
107.             prev = this.currentState.name;
108.         }
109.         
110.         this.currentState = this.nextState;
111.         this.nextState = null;
112.         
113.         assert this.currentState != null;
114.         this.currentState.SetWasPushed(false);
115.         this.currentState.Enter();
116.         Log.Write("STATE CHANGE: " + prev + " --> " + next);
117.     }
118.     
119.     /**
120.      * Request to push the current state to
121.      * storage and run another one.
122.      * @param newState New state to run.
123.      */
124.     public void RequestPushState(SinState newState)
125.     {
126.         this.nextState = newState;
127.         this.requestedStatePush = true;
128.     }
129.     
130.     /**
131.      * Do the actual state push.
132.      */
133.     private void DoStatePush()
134.     {
135.         String prev = "Null";
136.         String next = "Null";
137.         if(this.nextState == null)
138.         {
139.             Log.Write("ERROR! Attempting state push in null state");
140.             return;
141.         }
142.         
143.         next = this.nextState.name;
144.         
145.         if(this.currentState == null)
146.         {
147.             Log.Write("ERROR! Attempting state push back null state");
148.             return;
149.         }
150.         
151.         prev = this.currentState.name;
152.         this.requestedStatePush = false;
153.         this.pushedState = this.currentState;
154.         
155.         this.pushedState.ManagerPause();
156.         
157.         this.currentState = this.nextState;
158.         this.nextState = null;
159.         
160.         assert this.currentState != null;
161.         this.currentState.SetWasPushed(true);
162.         this.currentState.Enter();
163.         Log.Write("STATE PUSH: " + prev + " --> "
164.                 + next + " [Pushed state: "+
165.                 this.pushedState.name +"]");
166.     }
167.     
168.     /**
169.      * Request pop of current state and
170.      * restoring of the pushed one.
171.      */
172.     public void RequestStatePop()
173.     {
174.         this.requestedStatePop = true;
175.     }
176.     
177.     /**
178.      * Does the actual pop.
179.      */
180.     private void DoStatePop()
181.     {
182.         String prev = "Null";
183.         String next = "Null";
184.         if(this.pushedState == null)
185.         {
186.             Log.Write("ERROR! Attempting state pop null state");
187.             return;
188.         }
189.         
190.         next = this.pushedState.name;
191.         
192.         if(this.currentState != null)
193.         {
194.             this.currentState.Exit();
195.             prev = this.currentState.name;
196.         }
197.         
198.         this.requestedStatePop = false;
199.         this.currentState = this.pushedState;
200.         this.pushedState = null;
201.         
202.         assert this.currentState != null;
203.         this.currentState.ManagerResume();
204.         Log.Write("STATE POP: " + prev + " --> " + next);
205.     }
206. }

 

State

Code Snippet

1. /**
2. * Base class for states.
3. * Supports state pause.
4. * @author Ying
5. *
6. */
7. public abstract class SinState
8. {
9.     /**
10.      * Whether the state is paused.
11.      */
12.     protected boolean isPaused;
13.     
14.     /**
15.      * Update period of the state.
16.      */
17.     protected int updatePeriod;
18.     
19.     /**
20.      * Last update period.
21.      */
22.     private long lastUpdateTime;
23.     
24.     /**
25.      * Reference to the FSM
26.      */
27.     protected StateMachine FSM;
28.     
29.     /**
30.      * State name.
31.      */
32.     public String name;
33.     
34.     /**
35.      * Whether the state was pushed.
36.      */
37.     private boolean wasPushed;
38.     
39.     /**
40.      * Initializes an instance of the SinState class.
41.      * @param updatePeriod The time (in ms) between
42.      *  each update. Set 0 for going as fast as possible.
43.      */
44.     public SinState(int updatePeriod, StateMachine FSM, String name)
45.     {
46.         this.isPaused = false;
47.         this.updatePeriod = updatePeriod;
48.         this.lastUpdateTime = System.currentTimeMillis();
49.         this.FSM = FSM;
50.         this.name = name;
51.     }
52.     
53.     // Override functions
54.     public abstract void Enter();
55.     public abstract void Exit();
56.     protected abstract void Update();
57.     protected abstract void Pause();
58.     protected abstract void Resume();
59.  
60.     // Manager functions
61.     public void ManagerUpdate()
62.     {
63.         if(!this.isPaused)
64.         {
65.             if(this.updatePeriod == 0 ||
66.                     System.currentTimeMillis() - this.lastUpdateTime >=
67.                     this.updatePeriod)
68.             {
69.                 this.Update();
70.                 this.lastUpdateTime = System.currentTimeMillis();
71.             }
72.         }
73.     }
74.     
75.     public void ManagerPause()
76.     {
77.         this.isPaused = true;
78.         this.Pause();
79.     }
80.     
81.     public void ManagerResume()
82.     {
83.         this.isPaused = false;
84.         this.Resume();
85.         this.lastUpdateTime = System.currentTimeMillis();
86.     }
87.     
88.     public void SetWasPushed(boolean pushed)
89.     { this.wasPushed = pushed; }
90.     
91.     public boolean WasPushed()
92.     { return this.wasPushed; }
93. }

 

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.