Complex Finite State Machines

in Technical

Finite State Machines (FSM for short) are a very common phenomenon in game programming. Even if you have never heard of the term, it is unlikely that you have never used it before. While the concept behind Finite State Machines is simple, simple implementations can often lead to code that becomes hard to maintain. In this post we will focus on slowly abstracting from an ad hoc implementation to a simple framework we can apply in many different circumstances.

Basic implementation

We will start with a very basic implementation of a Finite State Machine. Let us recall what a state machine is: we have some sort of object that in any point of time has one of a finite number of states. The current state of the object influences or decides the behaviour of the object. The state of the object changes based on a set of predefined transition conditions.

Finite State Machine

In the image above we can see a simple example of a Finite State Machine with three states and four transitions. The most trivial implementation of a machine like this uses an enumerator to determine the current state. An example of a Finite State Machine with the above states and transitions would look like this:

class FiniteStateMachine
{
    enum State
    {
        State1,
        State2,
        State3
    }

    State currentState;

    public FiniteStateMachine()
    {
        this.currentState = State.State1;
    }

    public void Update(float dt)
    {
        switch (this.currentState)
        {
            case State1:
                // some logic

                if (condition)
                    this.currentState = State.State2;
                return;

            case State2:
                // some logic

                if (condition)
                    this.currentState = State.State1;
                else if (otherCondition)
                    this.currentState = State.State3;
                return;

            case State3:
                // some logic

                if (condition)
                    this.currentState = State.State1;
                return;
        }
    }
}

The class looks quite manageable, but as the logic for each state gets more complicated or the amount of states increases, the class can quickly grow to a size that is larger than we would desire.

Splitting off states

Right now the Finite State Machine has multiple responsibilities: keeping track of the current state, transitioning between states, and executing the behaviour that comes with the current state. We will change the Finite State Machine in such a way that it will only be responsible for one of these.

Right now we are using an enumerator, but we don’t have to be limited by it. What if the enumerator would know what to do if it’s the current active state? That would simplify the Finite State Machine greatly. Let’s create an abstract class (not an interface, as we will be introducing some shared behaviour later on) for the states:

abstract class State
{
    public abstract void Update(FiniteStateMachine fsm, float dt);
}

Now, instead of storing the current state as enumerator, we will store the current state as an object that inherits from the abstract class State:

class FiniteStateMachine
{
    public State CurrentState;

    public FiniteStateMachine()
    {
        this.CurrentState = new State1();
    }

    public void Update(float dt)
    {
        this.CurrentState.Update(this, dt);
    }
}

The class has all of a sudden become a lot simpler, since its only responsibility is now to keep track of the current state. It still executes the behaviour of the current state, but it does not know what this behaviour is.

Note that the current state has been made publicly accessible. Since we do not distinguish between states any more, the states themselves have to transition to the next state and thus have to be able to change the current state of the Finite State Machine.

A very important advantage of this implementation is that we could easily reuse states in different Finite State Machines, reducing the amount of code duplication.

Generalising transitions

Even though we made the Finite State Machine responsible for only on thing, the states right now have to deal with both their own behaviour and the outgoing transitions. It is not visible from the above code fragments, but we still have a lot of little blocks that look like if (condition) changeState();. This is something that is undesirable for several reasons:

First of all the state has multiple responsibilities, which is something that should be avoided whenever possible. Secondly, it reduces the re-usability of states, since its outgoing transitions are fixed in its behaviour. Finally, we will have code duplication for many common transition conditions. If a state ends after n seconds, we have to keep track of the time and trigger the state transition when that time has passed. While this is just simple bookkeeping, it is bad practice to implement this for each state individually.

Transitions are in fact tuples of a condition and a description of the next state. For now we will store conditions as a Func<bool>, but it should be noted that in practical cases you may want a more complex object representing your conditions.

class StateTransition
{
    private readonly Func<bool> condition;
    private readonly State newState;

    public bool ConditionMet { get { return this.condition(); } }
    public State NewState { get { return this.newState; } }

    public StateTransition(Func<bool> condition, State newState)
    {
        this.condition = condition;
        this.newState = newState;
    }
}

The only thing left to do is hooking these transitions into the State class we defined earlier:

abstract class State
{
    private readonly List<StateTransition> transitions = new List<StateTransition>();

    public sealed void Update(FiniteStateMachine fsm, float dt)
    {
        DoLogic(fsm, dt);

        foreach (var t in this.transitions)
            if (t.ConditionMet)
            {
                fsm.CurrentState = t.NewState;
                return;
            }
    }

    protected abstract void DoLogic(FiniteStateMachine fsm, float dt);

    public void AddTransition(StateTransition t)
    {
        this.transitions.Add(t);
    }
}

Defining the structure

Another interesting subject to discuss is how and where to store the structure of the Finite State Machine. In our initial implementation the whole structure is contained within a single class, and every Finite State Machine is contained within a single object. This is not the case in our final version. We have to define the structure of the states and transitions in some other way.

The easiest is solution to treat all the states as singletons. The implementation above was purposely designed to allow for this. It is possible to store a state within a state (stateception!), but if a separate instance of a State for each instance of a FiniteStateMachine is required, storing the structure becomes a bit more complicated. Every transition has to know how to create the new state and its outgoing transitions. Since the outgoing transitions are the same for all incoming transitions, some sort of StateTemplate object could be created to keep track of the complete object (again, we could define the outgoing transitions in the State, but this would reduce the re-usability of the states). If further the outgoing transitions/conditions need to keep track of a state, we soon find ourselves building factories upon factories. Based on this, my personal recommendation would be to keep the States stateless, as described in this article.

Conclusion

We now have a very basic framework in which we have separated the state machine, the states, and the transitions between them. It is possible to go even further and find neat solutions to once again encapsulate the current state of the finite state machine. The framework can be used for a wide variety of applications. States could be replaced by menu states, AI nodes, game states, etc. Not only the framework itself is reusable, but it also allows us to write reusable code ourselves, in case we find ourselves in need of multiple variations of the Finite State Machine.

All in all, I think this framework has a lot of use in more complex Finite State Machines. Very simple state machines might still benefit from a simpler implementation. There are many different possibilities of setting up an architecture for state machines, and the solution described here is probably not the only right solution. Feel free to let me know about how you approached the subject differently! For now, thanks for reading, and until the next time.

Place comment

Your email address will not be published. Required fields are marked *