State Machine – Basic

The article is currently being reviewed so it might contain some leftovers of previous version that are outdated.

The following article will introduce a basic state machine (or finite state machine FSM). The point here being to introduce some programming topics that are needed to develop a more advanced FSM without going to deep into it and losing the reader.

The article will cover the basic of a FSM, explaining the basic required for the tool. It will cover the definition of a FSM and talk about delegate and reflection. Those last two often bring confusion so we’ll try to clarify them.

Create a new script and name it StateMachine, go to the link below and copy paste the content onto your new script.

github-mark@1200x630

Basic of FSM

So, how to define a FSM? Well, any program is likely to contain some method like this:

void ControlMethod(int currentState)
{
    switch(currentState){
        case 0:
            Action0();
            break;
        case 1:
            Action1();
            break;
        case 2:
            Action2();
            break;
        default:
            ActionError();
            break;
    }
}

This is already a FSM. It has define actions for the appropriate state. So from there, it could be possible to create a more robust and maintainable situation via a class that would handle the process.

When we write a if-statement, we allow the program to be in either one of the two states. The more conditions, the more complex the machine becomes and more states we allow. It is also possible to set the program in two different states at a time though it is not recommended and more likely one main and one inner state. The problem is that as you add more states, it also becomes harder to debug and maintain, particularly for a sole developer.

So the idea lies in the term finite meaning limited. When building a FSM, we define its limits in each state so that we don’t end up running two states at a time. This way we keep full control since only one method is run. Think of it like the Update method you are already familiar with, but there would be one for each state.
Let’s try to visualize a common FSM we deal with every day (if you are no amish):

Mode Remote Control Functions
Off
  • Only the power button has any function.
  • Pressing power moves the TV into the On state.
On
  • Pressing the power button moves the TV to the Off state.
  • Pressing channel buttons changes the programme being received.
  • Pressing the up/down buttons surfs through the channels.
  • Pressing the menu button moves the TV to the Menu state.
Menu
  • Pressing the power button moves the TV to the Off state.
  • Pressing the up/down buttons moves through the menu.
  • Pressing the menu button moves the TV to the On state.

The logic contained in each state would probably be extended but nonetheless, we are given the user interface. We can also clearly see the limitations of the program and some functions are only available in some specific states.

It is also recommended to start your FSM on the paper, thinking what states and what transitions. There are some tools out there to help you with that, some free, some not.Draw.io is one I use every now and then (free).
States
The picture above indicates each state of the object and the conditions triggering a transition. Those conditions can be checked in update or via an event system. For instance, “Hit?” is a condition triggered by collision with a projectile (or any kind of weapon)
subtracting health and performing a check. If it is less than 0, it transits to “Dying”. On the other hand, the “Player/Enemy Approaches” bubble would require some kind of Update to be performed regularly.

Creating the FSM

The first step is to create the class, no surprise if we call it StateMachine and it could inherit from MonoBehaviour. Avoid StateMachineBehaviour as it is already used by UnityEngine (or create a namespace but well…).

It is not necessary to have the MonoBehaviour in the StateMachine but it will simplify a bit but just so you know, it could definitely be a non MB.

public class StateMachine:MonoBehaviour
{
}

Next, we are talking about state and machine so we can consider the machine to be the class and we need a state. Let’s create an inner class for that.

using UnityEngine;
using System;
public class StateMachine:MonoBehaviour
{
    class State{
        public Enum name = null;

        public State(Enum name)
        {
            this.name = name;
        }
    }
}

Our class is not public so we cannot screw with it from outside the StateMachine class. It only contains an enum and a constructor for now. The enum is there because we will define our state using an enumeration. We could also use strings, same same but different. Don’t forget the System namespace.

We should define what a state is at the point. So far it is a name only. What we want is that the machine has a pointer (a reference) to the current state and it runs its update. Also, for each changing of state, we want to run an entry and an exit method.
So we need three method pointer aka delegate.

using UnityEngine;
using System;
public class StateMachine:MonoBehaviour
{
    class State{
        public Enum name = null;
        public Action updateMethod = () => { };
        public Action<Enum> enterMethod = (state) => { };
        public Action<Enum> exitMethod = (state) => { };

        public State(Enum name)
        {
            this.name = name;
        }
    }
}

All items are public since we need them in the machine, the first is a basic Action delegate, the two others will receive a parameter of type Enum.

Why delegate?

Back in C/C++, a delegate was a function pointer.
A method MyMethod would require to be passed another method as parameter so that second method can be called from within. The programmer defines a method pointer and a method address is passed to it. The pointer then contains the address and can jump to that address and find the actual method. Ok this is confusing and I won’t explain much of the C/C++ version function pointer.

Now in C#, the .NET developer pushed the concept one step further. In C/C++, the pointer was a 4bytes variable (in 32bit) meant to receive the address of a method matching its signature. In C#, a delegate is a class and it contains all kind of methods.

The original way still in use:

public delegate void MyDelegateDeclaration();
public MyDelegateDeclaration myDelegateInstance = null;
void Start(){
    myDelegateInstance = MyMethod;
    myDelegateInstance();
}
void MyMethod(){ Debug.Log("Hell...oh World...");}

The first line declares the delegate in a similar pattern you would declare a new class. First comes the access modifier, then the delegate keyword indicating we are using a special type of class declaration. Comes next the return type, your own naming and the parameter list. This is the signature of methods the delegate can be assigned. In our example, MyMethod returns void and has no parameter so it does match the signature of the delegate.

Second line is the object creation. We now have a reference called myDelegateInstance which is an object of type MyDelegateDeclaration. We can create many object of type MyDelegateDeclaration. We cannot reuse MyDelegateDeclaration for a different type of delegate (just like you cannot reuse a class name)

In the Start, we assign the MyMethod to it. Notice that the () are missing. This is because we do not want to assign the return value (which is void here) by calling the method but instead we want to pass the address and it is done as such (this is equivalent to &Method; in C++). The next line is the invoke of the delegate as we use the parenthesis meaning we are not trying to use the address but the content of the delegate. In this case, it will point towards MyMethod and will print “Hell! Oh World…”. Since a delegate is an object, it can also be null.

The new way:

Action myDelegateInstance = null;
void Start(){
    myDelegateInstance = MyMethod;
    if(myDelegateInstance != null){
        myDelegateInstance();
    }
}

This is the generic way and was introduced later in the .NET framework. It works the exact same way as the previous since it is basically a wrapping of the delegate creation. As it is generic, the parameter list is also different and if a return value is needed, Func is used. I would recommend to look at the msdn for more info so that we can move along folks.

Starting with our machine

The idea is that our machine will store a collection of state and will transfer from the current state to the required state. In this version of the FSM, there will not be any constrains so any state can jump to any other state.

The first new feature is the current state of the machine. Basically, this is a reference to a state. We also want to be able to retrieve that state from outside the FSM

using UnityEngine;
using System;
public class StateMachine:MonoBehaviour
{
    class State{ // Code }

    private State currentState = null;
    public Enum CurrentState { get { return this.currentState.name; } }
}

The currentState is private and a getter is implemented. You could redefine that property if you feel more relevant to return a string for instance.

Now let’s initialised, shall we?

private bool initialized = false;
private bool debugMode = false;
private Dictionary < Enum, State > states;
private Action OnUpdate = ( ) => { };

protected void InitializeStateMachine<T>(Enum initialState, bool debug)
{
   if (this.initialized == true)
   {
       Debug.LogError("The StateMachine component on " + this.GetType().ToString() + " is already initialized.");
       return;
   }
   this.initialized = true;

   var values = Enum.GetValues(typeof(T));
   this.states = new Dictionary<Enum, State>();
   for (int i = 0; i < values.Length; i++)
   {
      this.initialized = this.CreateNewState((Enum)values.GetValue(i));
   }
   this.currentState = this.states[initialState];
   this.inTransition = false;
   this.debugMode = debug;

   this.currentState.enterMethod(currentState.name);
   this.OnUpdate = this.currentState.updateMethod;
}

Ok, quite a bunch of things added here. First, the method is generic and should be passed an enum as generic parameter. We will see soon how to do that. The initialized variable prevents many initializations if by mistake you would call that method many times.

The debugMode variable will allow us to print info on the console if the mode is on. The states dictionary creates a map between enum and state so that we can pass an enum and get the matching state fast. Finally, the OnUpdate delegate is the machine delegate pointing to the current update method. It is just a shortcut to the update in the current state.

In the method now, first we check if already initialized and set it if not yet. Then, we grab all members of the enumeration that was passed and create the dictionary.
The for loop iterates all enum values and create a new state (method is coming next). The method returns true if all fine and false if something wrong. This is stored in the initialized variable so that if something went wrong, you cannot use the FSM in a wrong way you would not be expecting.

Next, we set the debugMode and call the enterMethod on the currentState and set the OnUpdate with the update of the currentState.
Notice the parameter on the enterMethod, this is because the method is expecting to be passed the previous state but as we are starting, there is no previous state, so we pass the current one.

This is how you would use it in a simplified example:

public class MyClassExample : StateMachine
{
    void Start(){
        InitializeStateMachine <MyClassState> (MyClassState.Start, true);
    }
}
public enum MyClassState{ Start, Move, Run, Die }

And nothing else. At this point, the FSM has registered four states. Let’s jump to the creation of those states.

private bool CreateNewState(Enum newstate)
{
    if (this.Initialized() == false) { return false; }

    if (this.states.ContainsKey(newstate) == true)
    {
        Debug.Log(newstate + " is already registered in " + this.GetType().ToString());
        return false;
    }

    State s = new State(newstate);
    Type type = this.GetType();
    s.enterMethod = StateTest.GetMethodInfo<Action<Enum>> (this, type, "Enter" + newstate, DoNothingEnterExit);
    s.updateMethod = StateTest.GetMethodInfo <Action> (this, type, "Update" + newstate, DoNothingUpdate);
    s.exitMethod = StateTest.GetMethodInfo <Action<Enum>>  (this, type, "Exit" + newstate, DoNothingEnterExit);

    this.states.Add(newstate, s);

    return true;
}

The beginning of the method holds no secret. We then create a new State object. We pass the type of our class into a type reference. What you need to understand there is that the value of the type will not be StateMachine but the calling class. In our example, type would contain info about MyClassExample, since the this pointer points to an object of that type.

Then comes three calls to GetMethodInfoInheritance (coming soon). That method returns a reference to a method that is passed to the delegates of the State object we created. The purpose of that method is that if a specific method is found on the class then a delegate is created towards that method. We will need reflection for this. Think of the Awake/Start/Update/… of a MonoBehaviour, Unity needs to check if you implemented those methods in the script so that it can call them, we will do the same with our own method naming.

Once done, we add the state to the dictionary so that we can fetch a state by enum. This is it for this one.

Reflection

The purpose of reflection is to provide inner information on a type, an assembly or any meta data. In our case, we want to know if a class was implemented with methods that would carry specific names.

Consider you want to know if a class contains the method Start, there we go:

Type ourType = this.GetType();
MethodInfo methodInfo = ourType.GetMethod("Start", BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance);
if(methodInfo != null)
{
    Debug.Log("The given type contains a Start method");
}

You will need an extra namespace:

using System.Reflection;

And tadaaa. This is it. So again, no magic, if you know what you need and you look for the appropriate method, you get it. In our case, we want to look for a method so we use GetMethod. Then, we need to feed the correct parameters. We want a Start method that is public or private and an instance (non-static), this is done with the second parameter.

BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance

This performs a OR operation creating a bit value that will contain all three settings.

If the compiler finds a match in the assembly manifest (the file containing all the program info), it returns an information summary else you get null. The baseType reference is of type Type. It is in no way linked to the object it came from. In our example, we used this.GetType(), the call returned an object that contained the info about this object but you cannot get back to the object using baseType. Just like a handler’s manual contains information about a specific item, it is not the item itself. Here, you can find the documentation on Type from msdn.

Using the reflection method, we can find and register the FSM methods.

private static T GetMethodInfo<T>(object obj, Type type, string method, T Default) where T : class
{
    Type ourType = type;
    MethodInfo methodInfo = ourType.GetMethod(method, BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance);
    if (methodInfo != null)
    {
        return Delegate.CreateDelegate(typeof(T), obj, methodInfo) as T;
    }
    return Default;
}

The method is generic with a constrain (the generic has to be a class). The first parameter is the object on which we are working, the second parameter is the type we are working with. The string parameter is for the method name and the last parameter is the default method in case none was found.

Looking at the method, we find the same pattern we looked at earlier. If GetMethod found a method, then we create a delegate with Delegate.CreateDelegate to which we pass the needed info with a cast as T. if none was found Default is returned.

This might require an extra explanation. When you think of a method on a class, you have to understand the inner mechanism. If you have a class Dog with a method Eat and you create 10 instances of Dog, the compiler actually only creates one version of the Eat method that is stored in memory. When an instance calls the method, the compiler passes a this pointer as first parameter that is hidden. That is how you can use this keyword within a method. So think you have a whole bunch of dogs and when one eats, it passes a reference to himself to a unique Eat method. That unique method is able to know the instance members of the Dog object using that this pointer. The same mechanism is explicitly used in extension methods.

Back to our CreateDelegate method, it creates a delegate, so simply said a pointer to the method location, it takes a type as first parameter so that it can instantiate the delegate (remember a delegate is an object of a type). The second parameter is a reference to an actual instance of an object and will create the this pointer relation between the delegate and that object. The delegate is now able to look into members of that instance. The third parameter uses the content of the method info to know where the delegate should point at.

  • First -> Creates the delegate object
  • Second -> Gets the reference to the object it should deal with
  • Third -> Gets the method it should point at

Where does Default comes from?  Back up, when we called the method, we passed DoNothingUpdate and DoNothingEnterExit. Those are just empty method we use to fill the gap if nothing exists. So we can declare them:

public class StateMachine : MonoBehaviour
{
    private static void DoNothingUpdate() { }
    private static void DoNothingEnterExit(Enum state) { }
}

Now, let’s get back to the GetMethodInfo to look at the parameters again:

s.enterMethod = StateTest.GetMethodInfo<Action<Enum>>(this, type, "Enter" + newstate, DoNothingEnterExit);
s.updateMethod = StateTest.GetMethodInfo<Action>(this, type, "Update" + newstate, DoNothingUpdate);
s.exitMethod = StateTest.GetMethodInfo<Action<Enum>>(this, type, "Exit" + newstate, DoNothingEnterExit);

Pay attention to the third parameter, it shows

"Enter"+newState
"Update"+newState
"Exit" + newState"

Our reflection process will look for methods that are made of Enter/Update/Exit and the name of the state. So consider we have

public enum MyClassState{ Start, Move, Die }

We need to implement like this:

public class MyClassExample : StateMachine
{
    private void EnterStart(Enum previous){}
    private void UpdateStart(){}
    private void ExitStart(Enum nextState){}

    private void EnterMove(Enum previous){}

    private void UpdateDie(){}
}

Enter and exit are taking parameters. This may allow the user to perform specific actions based on previous or next state. Update does not require this process.

Finally concerning reflection, it tends to be fairly slow. So best is to use a pool if you plan on using it on object that gets regularly destroyed and instantiate. You can use my ObjectPool article.

Changing state

The final step is to be able to change state.

private bool inTransition = false;

protected bool ChangeCurrentState(Enum newstate)
{
    if (this.Initialized() == false) { return false; }

    if (this.inTransition)
    {
        if (this.debugMode == true)
        {
            Debug.LogWarning(this.GetType().ToString() + " requests transition to state " + newstate + " when still transitioning to state ");
        }
        return false;
    }
    if (this.debugMode == true)
    {
        Debug.Log(this.GetType().ToString() + " transition: " + this.currentState.name + " => " + newstate);
    }
    this.inTransition = true;
    State transitionTarget = this.states[newstate];
    if (this.currentState.name == transitionTarget.name)
    {
       Debug.LogError(this.GetType().ToString() + " transition: " + this.currentState.name + " => " + newstate +" is same state");
       return false;
    }
    if (transitionTarget == null || this.currentState == null)
    {
        Debug.LogError(this.GetType().ToString() + " cannot finalize transition; source or target state is null!");
        return false;
    }
    this.currentState.exitMethod(transitionTarget.name);
    transitionTarget.enterMethod(this.currentState.name);
    this.currentState = transitionTarget;
    this.inTransition = false;
    this.OnUpdate = this.currentState.updateMethod;
    return true;
}

The point of the ChangeCurrentState method is mainly to make sure we are not doing anything wrong first (do the states exist? are we not going from and to the same state?). The inTransition variable makes sure we are not trying to switch to a new state while already switching to a new state. It means you are not trying to call ChangeCurrentState while calling a Enter/Exit method.

Once all conditions are ok, we call the exit of the current state with the next state as parameter and then the enter of the next state with the current state as parameter

this.currentState.exitMethod(transitionTarget.name);
transitionTarget.enterMethod(this.currentState.name);

The final step is to reset the inTransition to false and set the update delegate to the new state update. Finally, we return true to say that it all went fine.

This last bit tells us we are missing one last method in our FSM, the update.

protected virtual void Update()
{
    this.OnUpdate();
}

Simply, we call the OnUpdate delegate that thanks to our ChangeCurrentState will always refer to the update of the current state.

This also means that our subclass using the FSM should not hide the Update and instead use an override that calls the base within it.

If you want to also implement FixedUpdate and LateUpdate, it goes the same way as we do for Update.

Practical use

using UnityEngine;
using System.Collections;
using System;

public class MyClassExample: StateTest
{
     protected virtual void Awake()
    {
        InitializeStateMachine<StateClass>(StateClass.Start, true);
    }

    void EnterStart(Enum previous) { Debug.Log("Enter Start"); }
    void ExitStart(Enum next) { Debug.Log("Exit Start"); }

    void EnterRun(Enum previous) { Debug.Log("Enter Run"); }
    void EnterDie(Enum next) { Debug.Log("Enter Die"); }
    void UpdateRun() { Debug.Log("update run");}

    protected override void Update()
    {
        base.Update();
        if (Input.GetKeyDown(KeyCode.S)) { ChangeCurrentState(StateClass.Start); }
        if (Input.GetKeyDown(KeyCode.R)) { ChangeCurrentState(StateClass.Run); }
        if (Input.GetKeyDown(KeyCode.D)) { ChangeCurrentState(StateClass.Die); }
    }
}
public enum StateClass
{
    Start, Run, Die
}

Note how the Update also calls the base.Update. Do not forget the override or the update in the base will be hidden. The example is really simple using some input to fake the start, the running state and the death of the object. If you switch to a new state, the transition is shown in the console.
If you try to jump from one state to the same state, you will see an error in the console. This is so far the only constrain. If you set the parameter in InitializeStateMachine to false, all printing will be removed.

Conclusion

This is a really basic introduction to FSM meant to be easy to begin with. Later, I will add some more features to the FSM so that it gets more robust. It can already be used as it is but is missing a main detail, one stage should only be able to move to defined stage. This is coming in the next article.
Any comment, go ahead.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s