Posted on 23 Jan 2014

A finite state machine framework

The goal

In my previous blog post about finite state machines(fsm) I went over the basics and how to implement a simple state machine. Here I will show you the way I chose to implement a more extensible state machine "framework". With the code I go over you should be able to create any number of state machines in your program, each with their own set of valid transitions that you define. After going over the code I will show an example of implementing it within a Unity project, however the finite state machine framework itself has no ties to Unity so can be used in any type of project. You may notice some Unity specific logging, and if you aren't using Unity just replace it with whatever logging mechanism you are using.

Let's get to crackin'!

Transitions

Transitions define the movement from one state to another, and in our case any actions that take place due to that change. A transition occurs because some set criteria has been met, and/or an event was triggered causing the transition to initiate. I say "and/or" because there is no set in stone rule as to how you must trigger a transition to happen...that is all up to the way it is implemented. That said, one of the main things you need to consider when using a state machine is how you want states to transition from one to another.

The way we are going to define a state transition is via a generic class that implements IEquatable<T>. The template argument to StateTransition<T> represents the type of the valid states of the state machine it is for. We implement IEquatable<T> and then override GetHashCode because objects of this class are meant to be used as keys in a Dictionary<K,V>. Here is the code for the class:

class StateTransition<T> : IEquatable<StateTransition<T>> {
    readonly T currentState;
    readonly T nextState;

    public StateTransition(T curr, T next) {
        this.currentState = curr;
        this.nextState = next;
    }

    public override int GetHashCode() {
        // Overflow is ok, let it wrap!
        unchecked {
            int hash = (7 * 13 + currentState.GetHashCode());
            hash = hash * 13 + nextState.GetHashCode();
            return hash;
        }
    }

    public bool Equals(StateTransition<T> other) {
        if(ReferenceEquals(this, other))
            return true;
        return other != null &&
               this.currentState.Equals(other.currentState) &&
               this.nextState.Equals(other.nextState);
    }

    public override string ToString() {
        return currentState.ToString() + " -> " + nextState.ToString();
    }
}

I initially wrote this with Unity® in mind so I defined the custom class you see above. However if you are using a more modern version of C# you could get away with using a Tuple<T,T> if you really wanted to. Unity doesn't support them yet so therefore I created this class.

The FSM class

Alright, now we have the main class we are writing, FiniteStateMachine<T>. In this class we will have a Dictionary<K,V> that defines what transitions are valid. There are are also 2 members named currState and prevState that should be self explanatory. Tracking the previous state isn't required, however I like doing it. Then we have EventHandler StateChanged which again should probably be self explanatory. It is a public variable so other areas of the code can sign up to listen for it to fire. So far we have:

public class FiniteStateMachine<T> {
    Dictionary<StateTransition<T>, TransitionActions> transitions;
    T currState;
    T prevState;

    public event EventHandler StateChanged;

#region Getters and Setters
    public T CurrentState {
        get;
        private set;
    }

    public T PrevState {
        get;
        private set;
    }
#endregion

    public FiniteStateMachine() {
        this.transitions = new Dictionary<StateTransition<T>, TransitionActions>();
    }

Woah Woah! What is that TransitionActions type?! I mentioned that StateTransition<T> was meant to be a key in a dictionary. Well this is the value in that dictionary. It is a private, nested class within FiniteStateMachine<T>. It contains two Action variables, before and after, and one Action<EventArgs> variable named announce. before represents an action to happen before the transition occurs, after represents an action to happen after the transition occurred, and announce represents a method that is meant to trigger an event to broadcast to any listeners that the transition occurred. All of these are optional, and by setting it up this way it allows the flexibility to potentially have different things happen when entering a state depending upon what state it is coming from.

private class TransitionActions {
    readonly Action before;
    readonly Action after;
    readonly Action<EventArgs> announce;

    public TransitionActions(Action before, Action after, Action<EventArgs> announce) {
        this.before = before;
        this.after = after;
        this.announce = announce;
    }

    public Action Before {
        get { return this.before; }
    }

    public Action After {
        get { return this.after; }
    }

    public Action<EventArgs> Announce {
        get { return this.announce; }
    }
}

Next let's take a look at the methods of the FiniteStateMachine<T> class! First up is the ChangeState method. It it the method that will actually initiate the transitions. It will only transition to the state requested if that StateTransition<T> was defined for the state machine. It will execute the before action if there is one, followed by changing the state. Next it calls the announce action if there is one. Finally it calls the after action, again if there is one. It triggers the StateChanged event by calling OnStateChanged.

public void ChangeState(T newState) {
    var t = new StateTransition<T>(this.CurrentState, newState);
    TransitionActions actions;
    // If this transition has been defined, proceed.
    if(this.transitions.TryGetValue(t, out actions)) {
        if(actions.Before != null)
            actions.Before();

        this.PrevState = this.CurrentState;
        this.CurrentState = newState;

        // Notify listeners that state has changed.
        this.OnStateChanged(EventArgs.Empty);

        if(actions.Announce != null)
            actions.Announce(EventArgs.Empty);

        if(actions.After != null)
            actions.After();
    } else {
        UnityEngine.Debug.Log("[FSM] Warning! ChangeState: Transition Not Defined - " + t);
    }
}

virtual protected void OnStateChanged(EventArgs e) {
    // Ensure things are safer with multiple threads.
    var changed = StateChanged;
    if(changed != null)
        changed(this, e);
}

Alright we are almost done! Last things for the FiniteStateMachine<T> class are the methods for adding and deleting transitions. I created 2 versions of AddTransition that just allow for different arguments to be passed. You could always add more versions if you really wanted to, but so far this has been convenient enough for me. DeleteTransition is a method I added because I just felt like I should, however I have yet to need to use it. Maybe one day!

public void AddTransition(T s1, T s2, Action before, Action after,
                          Action<EventArgs> announce) {
    var t = new StateTransition<T>(s1, s2);
    // If it already exists, don't add it again.
    if(transitions.ContainsKey(t)) {
        UnityEngine.Debug.Log("[FSM] Warning! AddTransition: Transition Already Exists - "
                                + t);
        return;
    }

    this.transitions.Add(t, new TransitionActions(before, after, announce));
}

public void AddTransition(T s1, T s2, Action<EventArgs> announce) {
    this.AddTransition(s1, s2, null, null, announce);
}

public void DeleteTransition(T s1, T s2) {
    var t = new StateTransition<T>(s1, s2);
    if(!transitions.Remove(t)) {
        UnityEngine.Debug.Log("[FSM] Warning! DeleteTransition: Transition not found - "
                                + t);
    }
}

Example!

This is just going to be a brief snippet of a few sections of the code that implements this fsm framework. For the full source of the example check the links below. The following would be in a GameManager type of class and gets things started for using the FiniteStateMachine<T> class.

public enum State { Initialize, SetupNewGame, Game, GameOver, Restart, Quit }

public FiniteStateMachine<State> mainFSM;

public event EventHandler SettingUpNewGame;
public event EventHandler GameStarted;

Then in some sort of Init() type of method call something like this:

mainFSM = new FiniteStateMachine<State>();
mainFSM.AddTransition(State.Initialize, State.SetupNewGame, null, InitializeNewGame,
                      OnSettingUpNewGame);
mainFSM.AddTransition(State.SetupNewGame, State.Game, null,
                      () => StartCoroutine(InitializeGameLogicStuff()), null);

mainFSM.StateChanged += (object s, EventArgs e) => {
        Debug.Log("state: " + mainFSM.CurrentState.ToString() + " | game state: " +
                  gameFSM.CurrentState.ToString());
    };

mainFSM.ChangeState(State.SetupNewGame);

As you see when the state changes from State.Initialize to State.SetupNewGame it does nothing before the transition, calls InitializeNewGame after, and announces this specific change via OnSettingUpNewGame. InitializeNewGame does some stuff and then transitions to State.Game, which is allowed because there is a second transition added going from State.SetupNewGame to State.Game. We also set up a listener to the StateChanged event of the fsm class via a lambda function, and just print out the state information to the console.

Conclusion

I hope that helps anyone that wasn't sure how something like this could be structured and used! If you have any questions please feel free to leave a comment, or shoot me a message via email or one of the social links to the left. As always, you can check out the repository for this project here, and it is also listed on my projects page.