Hierarchical Finite State Machine

I use finite state machines (FSMs) a lot when making games, both professionally and in my own projects. I find that dividing complex systems into separate states makes it easier to conceptualizing at visualizing them. This article is a brief description of my implementation of a hierarchical state machine. I’ll provide the source code and an example of how to set it up in the end. The implementation is in C#, but could easily be translated to other languages. Other than that there is nothing that limits this implementation to Unity or game programming (except for the assumption that states need an Update() function). If you only want to have a look at the source code straight away then follow the github link in the bottom of the article.

What I have found to be perhaps the biggest benefit of the FSM pattern is that it helps teams of developers to communicate and and get a common understanding of a system or codebase. The fact that you can draw up an entire system as a diagram of states and transitions is immensely powerful. You can then discuss system design, new features and bugs in a much more limited context. Instead of having discussions like “why is this bug happening in system X?” you have discussions like “why is bug a happening when going from state A to state B in system X?”. I.e. the scope of the problem is smaller and easier to isolate (and thus solve). Instead of discussing how an entire codebase needs to take new feature Z into account you can extend the FSM with a new state, or discuss how the given feature affects the related states state C and state D.

There are of course drawbacks to the state machine pattern. First of all the phenomenon called “state explosion” is common as your systems grow in complexity. This simply means that you end up with so many states that the clarity that the FSM pattern provides is overshadowed by a myriad of states, making it hard to navigate and understand. Secondly its quite easy to end up in situations where you need to write duplicated code in your different states. E.g. in a game a “RunState” and a “JumpState” might need to perform similar logic in terms of camera movement. That logic would then to be duplicated in both states to some degree. Both of these problems can be solved *ish* by a slightly different state machine pattern, the hierarchical finite state machine.

The hierarchical finite state machine not only divides your system into separate states, it puts them into a hierarchy of sub-states, which themselves can be state machines. The problematic example above could then be divided into a parent state (“MoveState”) and two substates (“RunState” and “JumpState”). The camera logic that had to be duplicated can then reside in the parent state, and the specifics for running and jumping resides in the substates (Image 1).

Image 1. Hirarchical states.

Before going through the source code and the example I want to point out that there are a million ways to implement state machines (hierarchical or not). My goal with this implementation was to keep it as simple and short as possible. If people feel functionality is missing then I would rather have few lines of code that can easily be modified or extended, instead of having a large sluggish framework that's hard to work with. I.e. there this is not a “blackbox” solution in any way. In fact the entire implementation is less than 100 lines of code. So here it is..

Image2. StateMachien code.

States and substates

The statemachine class shown above is a state in itself. To create a states you inherit from it and override the methods you need. The available ones “out of the box” are OnEnter(), OnUpdate() and OnExit(). See below:

Image 3. State example

Once you create your states and implement the logic you need in them you can arrange them in a hierarchy. You do this by adding substates and transitions. To add substates to state you use the LoadSubState(…) method:

Image4. LoadSubState method.

From the example above (Image 1) the states substates would be added as follows:

Image4. LoadSubState example.

The first substate you add will be the default substate. So in the example above the “runState” would be the default substate of “moveState”.

You must start the statemachine by using the method EnterStateMachine() on the root state (moveState in the example above). The OnEnter() methods will then be called hierarchically, from the root state to the deepest substate. You can then call the UpdateStateMachine() method on the root state. The OnUpdate() methods will then be called hierarchically aswell. The same principle goes for ExitStateMachine(), except that the OnExit() methods are called from the bottom up, starting with the lowest current substate.

Transitions

To create a transition from one sub state to another you use the AddTransition() method (Image 5):

Image 5: AddTransition method signature.

There is no specific class for transitions. You simply map a start state and a destination state to a trigger (an integer). These states must be added as sub states to the state you add the transition to, otherwise an exception will be thrown.

To make the transition happen you send a trigger to the statemachine. This trigger will work globally, so it doesn’t matter at which hierarchical level you send it. The trigger will work its way from the root state down through the current substates until it finds a consumer. Once a state (statemachine) has reacted to the trigger it will be consumed (states are changed) and it wont continue to propagate.

The full setup example from Image1 can be seen here, implemented in a Unity monobehaviour:

Image6. Full setup example.

The full source code, including the example is available in the following github repository:

johans2/FSM: A hierarchical finite state machine written in C#. (github.com)

Thanks for reading!