Simple yet powerful FSM implementation

There is one thing common to all the games I have worked on and all the languages I have used: state machines, or how they are called nowadays: FSMs (finite state machines). You don't really need to learn anything before starting to use them and probably you have already used them without even knowing it. As seen in the Game Programming Patterns at some point you end up using them naturally.

But, event though the idea is pretty simple and intuitive, iterating it and creating something that really makes your life easier it's a bit more complicated than it seems. I'd like to show you how I have been iterating my FSM over the years and what are the main problems that I have seen in other approaches

1. The initial approach: using enums

Before starting to code anything it will be good to review what exactly an FSM is. I am going to copy the definition from the Game Programming Patterns book:

- You have a set of states that the machine can be in

- The machine can only be in one state at a time 

- Each state has a set of transitions that causes the machine to change from one state to another

Do you see how I have skipped the part where the author is assuming input or events are tied to state changes? That was on purpose. I'll talk about it later but in my opinion FSMs become really complicated because of that assumption. State changes should happen whenever we directly tell the FSM to change its state.

Using enums we can create an state machine very similar to the one we have in the Game Programming Patterns book (I am going to use C# and Unity on this post):

public class ObjectWithFSM : MonoBehaviour {
 public enum State {
  STATE_0,
  STATE_1,
  STATE_2
 };
 public State currentState;

 public void SetState(State newState) {
  switch(currentState) {
   case State.STATE_0:
    //State 0 exit
    break;

   case State.STATE_1:
    //State 1 exit
    break;

   case State.STATE_2:
    //State 2 exit
    break;
  }

  currentState = newState;

  switch (currentState)  {
   case State.STATE_0:
    //State 0 enter
    break;

   case State.STATE_1:
    //State 1 enter
    break;

   case State.STATE_2:
    //State 2 enter
    break;
  }
 }
 
 void Update() {
  switch (currentState)  {
   case State.STATE_0:
    //State 0 update
    break;

   case State.STATE_1:
    //State 1 update
    break;

   case State.STATE_2:
    //State 2 update
    break;
  }
 }
}

The update of this class is managed by an internal FSM that processes one of the states only. If at any point I want to change to a new state I just need to call SetState passing the new State. Adding new states is as simple as adding new enums and creating new cases for them.

This approach is pretty simple and it works, I used it a lot back in the days of J2ME and still use it a lot when I want to write some quick code. I have actually being using this approach for my recent Game Boy games wit ZGB (like in polka sheep)

The main problem with this approach is that anytime you want to use this FSM you need to copy this template from scratch, no OOP is used. There is actually a good reason for this, back on the days of J2ME a new empty class added 130 bytes to your final build so we tried to avoid it at all cost (we had a limit of 64kb). But, it is 2018 and just an empty Unity project is around 20mb so we no longer need to worry about that (thank good!)

2. Using Object Oriented Programming

Let's try to define an FSM class that we can reuse. This is the simplest thing I came up with:

public class FSM : MonoBehaviour {
 //Base class for all states, only the required methods need to be overriden 
 public class State {
  [HideInInspector]public FSM fsm;

  public virtual void Enter() {}
  public virtual void Update(){}
  public virtual void Exit()  {}
 };

 //Current state being handled in this FSM
 public State currentState { private set; get;}

 public void ChangeState(State newState) {
  //Exit the current state
  if(currentState != null)
   currentState.Exit();

  //Change to the new state
  currentState = newState;

  //Enter the new state
  if(newState != null) {
   newState.fsm = this;
   newState.Enter();
  }
 }

 void Update() {
  //Update the currentState
  if(currentState != null)
   currentState.Update();
 }
}

This class keeps a reference to a single State that is set using the ChangeState function, and updates it (I am using the Update function available in Unity). In case we want to change to another State we just need to call ChangeState passing this new state as argument. Here is an example of how to use it:

public class ObjectWithFSM2 : MonoBehaviour {
 [System.Serializable]
 public class State0 : FSM.State {
  public override void Enter(){
   Debug.Log("Entering state 0");
  }

  public override void Update(){
   Debug.Log("Updating state 0");
  }

  public override void Exit(){
   Debug.Log("Exit state 0");
  }
 };

 [System.Serializable]
 public class State1 : FSM.State {
  public override void Update(){
   Debug.Log("Updating state 1");
  }
 };

 public State0 state0;
 public State1 state1;
 FSM fsm;

 void Start() {
  fsm = gameObject.AddComponent< FSM >();
  fsm.ChangeState(state0);
 }

 void Update() {
  if(Input.GetKeyDown(KeyCode.A)) {
   if(fsm.currentState == state0)
    fsm.ChangeState(state1);
   else
    fsm.ChangeState(state0);
  }
 }
}

This is just a class with two states that uses an internal FSM to process them. Pressing the key A it changes between the two of them, A few things that it s worth commenting in this code.

- I have defined State0 and State1 as System.Serialiable for 2 reasons:

• Unity will automatically create and instance of them in the editor (so we don't have to allocate them manually)
• Public vars will appear in the inspector so you can assing them in the editor (this also answers the question in the Game Programming Patterns book: Where are the State Objects? Based on my experinece this is the best place to put them, you don't need to constanlty destroy them when changing from one to another and you don't need static allocations, every instance has its own states)
  

- State0 overrides the 3 methods: Enter, Update and Exit but State1 only implements Update. The more states you create the more you realize that not all states do stuff entering or exiting, so it is a good idea to leave the implementation empty on the base class.

- All states keep a reference to the fsm after Enter has been called. This is useful to access the GameObject containing the FSM and from there the Monobehaviour containing the states (using fsm.GetComponent< ObjectWithFSM >()) that is not directly accessible from internal classes

This new FSM is much better than the previous one. We can reuse it, just need to add an FSM to our Objects and all the set of States we need... but it has a big problem that sooner or later arises. Let me show it to you with an example.

I used this FSM on Touch Racing 2. The FSM of the Main Menu was something like this:

The game starts on the Main Menu showing the three vehicles, from there you either go to the Options menu or select a car and go to the Car Menu. In the Car Menu a list of pieces is displayed: the chasis, the wheels, the engine and so on. If the user clicks on any of them then he's tken to the Pieces menu where he can select any of the different car pieces. The back option is always there to go back to the previous menu too.

Both the Car Menu and the Car Piece display different things depending on which option was selected on the previous menu. If the user selects the boat on the Main Menu then the Car Menu will center the View on the boat but if he chooses the Offroad the Car Menu will do the same with that car. We need to store which car was selected in a variable when exiting the Main Menu. Things get more complicated in the Car Piece menu, because it depends in both the selected vehicle and the selected piece, but no problem: we can just add another varible for the selected piece and properly set it when exiting the Car Menu

So the flow is like this: the user selects a vehicle and we store the selection on the var selectedVehicle. Then he selects a part and we store that on the var selectedPart. Great! This all fits perfectly!

Soon things start to get a bit more complicated. In TRN2 when you buy a vehicle piece it takes some time until it arrives, if that happens when the game is in the background a local notification is thrown informing  the user the new piece has arrived. When the user enters after this the game must show a popup and then go directly to the Car Piece state and show this piece. The problem is that because we haven't gone through Main Menu and Car Menu neither selectedVehicle nor selectedPart has been assigned, and the game will  likely crash

This is really easy to fix, just assign the variables before entering the Car Piece state and everything will just work. Yes, but the problem is: you can still enter the car piece from any other part of the code where these vars hasn't been assigned. For example when the user has enough money  to buy one of the pieces a popup appears informing him: "Hey you can now purchase a new part. Do you want me to show it?", if the user click yes then the game changes to the Car Piece state and again we need to remember to assign the variables or it won't display the right info! Oh, and don't forget the gacha machine: when the user wins a new prize the menu also changes to Car Piece to show the new adquisition



We have also forgotten one thing, the Car Piece state automatically selects the next piece the user should buy to progress in the game (by design). But in all these cases we also need another variable to tell the state which piece we want to be selected instead. In at least three parts of the code I needed to write

 vehicleIdx = _vehicleIdx;
 pieceSelected = _piece;
 defaultPieceIndex = _defaultIndex;
 fsm.ChangeState(carPieceState);

And because code duplication must be avoided In the end I ended up with a special function to move to the Car Piece State

void ChangetoStateCarPiece(int _vehicleIdx, PieceSelected _piece, int _defaultIndex) {
 vehicleIdx = _vehicleIdx;
 pieceSelected = _piece;
 defaultPieceIndex = _defaultIndex;
 fsm.ChangeState(carPieceState);

}

This function was handy but still someone could easily call fsm.ChangeState(carPieceState) without setting the required vars because nothing was forcing him to do so.

This was just an example of how something very simple can become a horror to maintain. I saw the same pattern repeated several times in other usages of this FSM clearly indicating that it had a serious problem and was far from perfect.

3. State enter parameters

If we could pass some parameters to the Enter funcions of the State class we will force the programmers to pass these arguments always before entering certain states. The problem is that each state requires a different number of parameters and of different types. A naive approach to fix this will be passing an object[] or a HashTable or event a List< object  >. But certainly this

Hashtable t = new Hashtable();
t.Add("vehicleIdx", _vehicleIdx);
t.Add("pieceSelected", _piece);
t.Add("defaultPieceIndex", _defaultIndex);

fsm.ChangeState(carPieces, t);

not only doesn't solve anything because any programmer could easily forget to add any of the required parameters (or all of them) but also this code is allocating a HashTable before entering the state and when entering we need to search the parameters. Instead of solving the problem we have created two new ones

In C++ whenever you need to create a function that could work with parameters of different types you end up using templates (or void* if you want to irritate everyone :D). In C# there are generics, which work in a similar way. Templates and generics will fix the problem with having different types of parameters but not the number. Again, based on my experience, I have never passed more than 3 parameters so we could do something like this:

public class FSM2 : MonoBehaviour {
 //Base class for all states, only the required methods need to be overriden 
 public class StateBase {
  [HideInInspector]public FSM2 fsm;

  public virtual void Update(){}
  public virtual void Exit()  {}
 };

 public class State : StateBase { public virtual void Enter() {} }
 public abstract class State1Param  < T >         : StateBase { public abstract void Enter(T p); }
 public abstract class State2Params < T0, T1 >    : StateBase { public abstract void Enter(T0 p0, T1 p1); }
 public abstract class State3Params < T0, T1, T2 >: StateBase { public abstract void Enter(T0 p0, T1 p1, T2 p2); }

 //Current state being handled in this FSM
 public StateBase currentState { private set; get;}

 bool ChangeStateBase(StateBase _newState) {
  //Exit the current state
  if(currentState != null)
   currentState.Exit();

  //Change to the new state
  currentState = _newState;

  if(_newState != null) {
   _newState.fsm = this;
   return true;
  }
  return false;
 }

 public void ChangeState(State _newState) {
  if(ChangeStateBase(_newState)) _newState.Enter();
 }

 public void ChangeState< T >(State1Param< T > _newState, T p) {
  if(ChangeStateBase(_newState)) _newState.Enter(p);
 }

 public void ChangeState< T0, T1 >(State2Params< T0, T1 > _newState, T0 p0, T1 p1) {
  if(ChangeStateBase(_newState)) _newState.Enter(p0, p1);
 }

 public void ChangeState< T0, T1, T2 >(State3Params< T0, T1, T2 > _newState, T0 p0, T1 p1, T2 p2) {
  if(ChangeStateBase(_newState)) _newState.Enter(p0, p1, p2);
 }

 void Update() {
  //Update the currentState
  if(currentState != null)
   currentState.Update();
 }
}

Notice how I have declared the Enter functions as abstract this time because it doesn't make sense to have any of the states with parameters without the Enter function required. Using this new FSM we could now declare the Car Piece state like this:

[System.Serializable]
public class CarPieceState : FSM2.State3Params< int, PieceSelected, int> {
 public override void Enter(int _vehicleIdx, PieceSelected _piece, int _defaultIndex) {
  //Select _defaultIndex of piece _piece and vehicle _vehicleIdx
 }
};

and then in order to enter this state we should call ChangeState like this

//-1 in this case indicates the default selection (selecting the next piece the user needs to purchase)
fsm.ChangeState(carPieceState, 0, PieceSelected.Piece0, -1);

or the code won't compile. There is no need to specify the template arguments in ChangeState since the compiler is capable of  infer them.

We can finally sleep happily knowing that no one could break the behaviour we wanted to have! I wish I had had this piece of code when I was coding TRN2!

Ok, this is the FSM I wanted to show you. But we are far from done. Let's see why adding some new features to our class may always not be such a good idea...

4. Using graphs

I am gonna be honest with you: I hate graphs. I don't like Playmaker, or the Animator State Machine and neither the new shaderGraph feature available in Unity. Using graphs as replacement of regular programming is a big mistake. People end up making noob mistakes, code duplication (hyper duplication) being the worst of them. Sadly this kind of stuff  is very common:

It is funny, until you are the one  who has to fix all that mess in order to continue adding content to a project you have been assigned to.

"Any fool can write code that a computer can understand. Good programmers write code that humans can understand.Martin Fowler, 2008."

Having said that I think a post talking about FSMs would be incomplete without talking about State Machine Behaviours in Unity. These are basically scripts that you can attach to states in the animation machine state and then you just need to override the desired functions OnStateEnter, OnStateExit or OnStateUpdate (sounds familiar?). If you are interested on State Machine Behaviours  and how to use the Animator as an FSM take a look at this post

Using State Machine Behaviours we could recreate the TRN2 menu FSM like this

Some people love this because with a single peek they can easily get an idea of how the FSM of the main menu works. And I agree, this is similar to the graph I draw at the beginning of this post to show you the FSM I had. The problem is that this representation is not true, you can still navigate to any state you want, just call Animator.Play and you can navigate from the Options menu to Car Piece even thought they are not linked. In other words the graph you see in the Animator is not the graph you have. This is the real graph:

The main problems that I've seen with FSMs is how state entering restrictions are undesrstood. Even the Game Programming Patterns book seems to indicate that you can only enter an specific state if you have a transition coming from another specific state (with an arrow linking them). According to this the restriction to get into the Car Piece state is to pass first through the Car Menu State and properly assign the required variables there.

But what happens if we need to enter the Car Piece state when a new part has arrived, a new prize is given on the gacha machine or the game encourages you to buy a new piece? It doesn't seem like this code is capable of adapt to changes like these easily

In my opinion (and this has worked like a charm for me) the restriction to enter an specific state is to pass the required enter parameters. You should design states that work perfectly if they receive all the required enter parameters, with zero dependencies to the other states

So, again, what benefits do we get from using the Animator state machine and State Machine Behaviours?:
- A graph that doesn't represent the real transitions we have
- We can't pass enter parameters which solved one of the main problems of our FSM
- Plus, we lose the ability to assign scene objects since Animator Controllers are not instantiated on the scene

I am sorry, get your own conclusions, but I totally discourage the use of Animators as FSMs (and totally encourage you to reinvent the wheel sometimes, because that's the only way to improve it)

5. The Back Queue

One of the things everyone implementing FSMs tend to do sooner or later is to add a stack of states to keep a history of the states it has been through and easily navigate back (this is what the Game Programming Patterns book refers to as a Pushdown Automata). Before entering a new state the current one is pushed into the stack and then when going back it is popped from there automatically.

Let's get back to TRN2 Menu. All its states except the Main Menu have a back functionality. If we are on the Main Menu and then move to the Car Menu we could automatically go back by just popping the state from the stack. The same way if we reach the Car Piece state we could go back twice since we passed through Main Menu and Car Menu.

The first problem appears when we enter the Car Piece state directly (when a new part arrives, a prize is given in the gacha machine or the game suggest the user a new part to purchase). We won't have a back stack there unless we create a fake one (manually adding states) or add some ugly conditions saying that, if the stack is empty, then move the Car Menu.

The second problem is even worse. Imagine you use a stack for an FSM like the one in the Game Programming Patterns

the stack will constantly grow because you never go back to the previous state in FSMs like this. You need to make sure that you clear the stack before changing to a new state or add a boolean to your FSM indicating if you want to use the stack or not.

What if instead of using a stack we add a new enter parameter to some states to indicate which state they should go in case the back button is pressed? This is actually not very helpful in TRN2 because the back button in Car Pieces always goes to Car Menu (by design), so we don't need the stack or the extra return parameter, but imagine we could enter the options menu from any of the other states. Then it will make sense to do something like this:

[System.Serializable]
public class OptionsState : FSM2.State1Param< FSM2.State > {
 private FSM2.State stateBack;
 public override void Enter(FSM2.State _stateBack) {
  stateBack = _stateBack;
 }

 public void OnBackClicked() {
  fsm.ChangeState(stateBack);
 }
};

and then when the back button is pressed, OnBackClicked is called and will return to the state passed as paramater. You may have already realized that there is a problem with this... We can safely do this in the Main Menu

fsm.ChangeState(optionsState, stateMainMenu);

but if we try to pass the stateCarMenu or the stateCarPieces it won't even compile because these states need enter parameters. Notice also how this is another reason why the back stack is incompatible with an FSM with States with enter parameters. Luckily there is a solution for this. Instead of passing an State to go back, we could pass a function callback

[System.Serializable]
public class OptionsState : FSM2.State1Param< System.Action > {
 private System.Action onBack;
 public override void Enter(System.Action _onBack) {
  onBack = _onBack;
 }

 public void OnBackClicked() {
  onBack();
 }
};

and then we can enter the OptionsState from either the CarMenu state

[System.Serializable]
public class CarMenuState : FSM2.State1Param< int > {
 int vehicleIdx;
 public override void Enter(int _vehicleIdx) {
  vehicleIdx = _vehicleIdx;
  
  //some other stuff
 }

 public void OnBack() {
  OptionsState optionsState = fsm.GetComponent< TRN2Menu >().optionsState;
  fsm.ChangeState(optionsState, () => { fsm.ChangeState(this, vehicleIdx); });
 }
};

or the CarPieces state:

[System.Serializable]
public class CarPieceState : FSM2.State3Params< int, PieceSelected, int> {
 int vehicleIdx;
 PieceSelected piece;
 int defaultIndex;
 public override void Enter(int _vehicleIdx, PieceSelected _piece, int _defaultIndex) {
  //Select _defaultIndex of piece _piece and vehicle _vehicleIdx
 }

 public void OnBack() {
  OptionsState optionsState = fsm.GetComponent< TRN2Menu >().optionsState;
  fsm.ChangeState(optionsState, () => { fsm.ChangeState(this, vehicleIdx, piece, defaultIndex); });
 }
};

That's it

I have been iterating this FSM a lot during the past years. Even though it is just 60 lines of code that doesn't mean there isn't a lot of work behind it

I have actually iterated it a bit more. You may be wondering how you could create States that are Monobehaviours at the same time (I'll leave it to you, but if you need help just let me know)

There is also a problem that I haven't been able to solve happily: when you call fsm.ChangeState() during the Update function of any of the States the rest of the lines of code in that Update will continue to execute even though it is no longer the current state. Throwing an exception and catching it on the FSM could work but I don't think using exceptions for this would be a good idea... If you have a solution for it I'll be happy to hear it

Also if you are interested on a C++ implementation you can take a look at it here (FSM.h FSM.cpp) It is a bit different and it uses some specific engine functions but you can get the idea