StateMachine – FSM – Part 3

J-Alves-impossible-gears

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

Final part of the FSM, in this article we should add some methods that will give us some more flexibility and information.
At the moment, we can know the current state but there will be situations when we need to know where we came from, or if a state exists based on what state we have already registered.
The FSM does not allow us to create what could be considered multi-transition so we would need that too.
How about adding and removing state at runtime? There could be cases where we want and need that.
And finally, adding a transition to an existing state will enable inheritance.

The extra step we could add but I will leave it up to you, is to override the methods containing debug line. You may want to create your own versions, shorter, longer with precise info and so on.

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

Adding helper methods

Let’s consider a UI system based on Model-View-Controller (MVC). In this situation, you have a class containing the methods for the UI buttons, mainly the action that should be performed on press of a button. This action is send to the UIController which contains most of the “intelligent” methods and also the FSM of the GUI. The last one contains all the view methods, mostly some methods called from the controller to switch on and off the UI items.
The Action class has a reference to the controller and the controller has a reference to the view.

Let’s think of the Pause button. It can be pressed anytime in the game and should return to the same state. When the action is pressed, the action class sends the info to the controller and set the FSM to pause, spreading the info to whatever is interested. Now once the pause is pressed again, either we recorded the previous state or we create it in the FSM.

Remember our transitionSource variable we create in the ChangeCurrentState, well, we just need to make it global.

public class StateMachine : MonoBehaviour{
    private State transitionSource = null;
    public Enum PreviousState { get { return this.transitionSource.name; } }
    protected ChangeCurrentState(Enum newstate, bool forceTransition = false)
    {
         // Code
          if (this.IsLegalTransition(this.currentState.name, newstate))
        {
            // Code

            this.transitionSource = this.currentState;
            State transitionTarget = this.states[newstate];
           
            // Code
            if (transitionTarget == null || this.transitionSource == null)
            {
                Debug.LogError(this.GetType().ToString() + " cannot finalize transition; source or target state is null!");
            }
            else
            {
                this.inTransition = false;
            }
        }
    }
}

I stripped the code to a minimum of lines so that you can see where it happens. Before we were creating the transition state and destroying it at the end of the method since it was local. Now that we made it global it will remain and contain the previous state.

Next helper method I could think of would be getting all the states currently registered as well as does a state exist then all the transitions registered in a state. We already can check if a state and transition are legit.

You should understand that those methods are only useful in some specific cases. IF we would have made the members public, this would be easier but also breaking encapsulation. So we need methods to get info without risking to break the machine.

protected bool ContainsState(Enum state)
{
    return this.states.ContainsKey(state);
}
protected Enum[] GetTransitionsFromState(Enum state) 
{
    if (this.states.ContainsKey(state) == false)
    {
        if (this.debugMode)
        {
            Debug.LogError("The given state " + state + " is not a registered state");
        }
        return null;
    }
    return this.states[state].transitions.ToArray(); 
}
protected State[] GetAllStates() 
{
    List<State>list = new List<State>();
    foreach(var kvp in this.states)
    {
        list.Add(kvp.Value);
    }
    return list.ToArray();
}

In order to enable the GetAllStates method, we need to make the State class public or the State type is not available outside the FSM.
This is it for the basic helper methods, let’s now move on to another topic.

Multi-transition

The way the FSM has been defined, we restricted the possibility to move to a new state while transitioning.
To explain the needs for that feature, consider the user can see a tutorial before entering a level, if he already saw the tutorial, then switch to game:

protected void EnterTutorial(Enum oldState)
{
    if(AppController.Instance.HasSeenTutorial == true)
    {
        this.ChangeCurrentState(AppState.GameOn);
        return;
    }
    // More code
}

As we enter, if the AppController tells the tutorial was already seen, then we switch state to game. Obviously, we could have checked for that earlier when the change of state was triggered. Or we can just allow this feature and make it easy.
I would consider the feature only available in EnterMethod. Think that you define state A to go to state B and this one defines that on some conditions, it goes directly to state C. The state was entered and left but it was run.
Other situation, state A goes to state B but in the exit method of A, it switch to state C. Now you were expecting B to happen but something made it jump to C. Now should we be queuing B so that it runs after C or should B be first and then C? Well, nope, let’s not make it happen, end of discussion.

It will also require to modify a couple of methods and a few new variables.

private State transitionQueue = null;
private bool allowMultiTransition = false;
private bool inExitMethod = false;

protected void InitializeStateMachine<T>(Enum initialState, bool debug, bool multiTransition = false) 
{
    // Code
    this.allowMultiTransition = multiTransition;
    // Code
}

We add three variables, transitionQueue is of type State and will inform if we should trigger a new transition. allowMultiTransition defines if we allowed the multi-transition feature (it is set in the initialization method) and the inExitMethod is tracking if we are trying to switch while in exit method (never underestimate how wrong a coder can code).

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

    if (this.inTransition == true)
    {
        if (this.allowMultiTransition == false) 
        {
            // Code
        } else if (this.allowMultiTransition == true)
        {
            if (this.inExitMethod == true)
            {
                Debug.LogWarning(this.GetType().ToString() + " requests new state in exit method is not recommended");
                return false;
            }
            this.transitionQueue = states[newstate]; // here
            return true;
        }
    }

    if (this.IsLegalTransition(this.currentState.name, newstate))
    {
        if (this.debugMode == true)
        {
            Debug.Log(this.GetType().ToString() + " transition: " + this.currentState.name + " => " + newstate);
        }

        this.transitionSource = this.currentState;
        State transitionTarget = this.states[newstate];
        this.inTransition = true;
        this.inExitMethod = true; // Added line here
        this.currentState.exitMethod(transitionTarget.name);
        this.inExitMethod = false; // Added line here
        transitionTarget.enterMethod(this.currentState.name);
        this.currentState = transitionTarget;

        if (transitionTarget == null || this.transitionSource == null)
        {
            Debug.LogError(this.GetType().ToString() + " cannot finalize transition; source or target state is null!");
        } else {
            this.inTransition = false;
        }
    } else {
        Debug.LogError(this.GetType().ToString() + " requests transition: " + this.currentState.name + " => " + newstate + " is not a defined transition!");
        return false;
    }
    // Added code here 
    if (this.allowMultiTransition == true && this.transitionQueue !=  null)
    {
        State temp = this.transitionQueue;
        this.transitionQueue = null;
        this.ChangeCurrentState(temp.name);
    }

    this.OnUpdate = this.currentState.updateMethod;

    return true;
}

ChangeCurrentState is a little longer. The idea is that if the FSM is transiting while this is called, it means while we were in the Enter method of a state, a ChangeCurrentState was found. So we are stacking up state transition. If we allow multi-transition, we check that we ar not in the exit method and register the new state into transitionQueue and return to avoid calling the rest of the method. This is the snippet below:

else if (this.allowMultiTransition == true)
{
    if (this.inExitMethod == true)
    {
        Debug.LogWarning(this.GetType().ToString() + " requests new state in exit method is not recommended");
        return false;
    }
    this.transitionQueue = states[newstate]; // here
    return true;
}

In order to prevent the switch in exit method, here is what we do:

this.inExitMethod = true; // Added line here
this.currentState.exitMethod(transitionTarget.name);
this.inExitMethod = false; // Added line here
transitionTarget.enterMethod(this.currentState.name);

The inExitMethod is set tot true, then we call the exiting method via the delegate. This jumps to the ExitMethod of the current state and if there was a call for ChangCurrentState within it, then the inExitMethod is true, it fails. Once the exit method returns fine without any failure, we reset the inExitMethod to false and call the enter method delegate of the new state. Now if there is a call for ChangeCurrentState in this one, no problem, we just run the method again but the new state will be added to the transitionQueue reference.

The final part of the method checks if any transiting state is pending:

// Added code here 
if (this.allowMultiTransition == true && this.transitionQueue !=  null)
{
    State temp = this.transitionQueue;
    this.transitionQueue = null;
    this.ChangeCurrentState(temp.name);
}

If the transitionQueue reference is not null, we have a pending state. We asiign it to a temporary state and set it to null (this prevent recursive call, a queue would have done it as well). Then we call for ChangeCurrentState with the new state and the process goes on again. Once all transition are done, the end of the method is run and finally, we give control back to the application.

Adding/Removing states

The final step for our FSM is to allow addition and removal of transitions into an existing state. Consider you have an object that evolve in time, so you may want to add attribute in time. This you can already do. But what we cannot do is remove states.

protected bool RemoveTransitionToExistingState(Enum state, Enum[]transitions) 
{
    if (this.states.ContainsKey(state) == false)
    {
        if (this.debugMode)
        {
            Debug.LogError("The given state " + state + " is not a registered state");
        }
        return false;
    }
    State existingState = this.states[state];
    foreach (Enum transition in transitions)
    {
        if (this.states.ContainsKey(transition) == false)
        {
            Debug.LogError(transition + " is not a registered state");
            return false;
        }
        if (existingState.transitions.Contains(transition) == false)
        {
            if (this.debugMode)
            {
                Debug.LogWarning(existingState.name + " does not contain " + transition);
            }
            continue;
        }
        existingState.transitions.Remove(transition);
    }
    return true;
}

We can now remove states if our object is losing ability for instance. We already know how to add states. We have only done it in Start but we can do it anytime.

Note that this allows us to consider upgrade as state additions. A newly collected item may add a new state that we can use.

Inheritance

In order to enable inheritance, we first need to update our GetMethodInfo and add a new method that will take care of adding new states later on when initialization is already done and cannot be called again:

private static T GetMethodInfo<T> (object obj, Type type, string method, T Default) where T : class
{
    Type baseType = type;
    while (baseType != typeof(MonoBehaviour))
    {
        MethodInfo methodInfo = baseType.GetMethod(method, BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance);
        if (methodInfo != null)
        {
            return Delegate.CreateDelegate(typeof(T), obj, methodInfo) as T;
        }
        baseType = baseType.BaseType;
    }
    return Default;
}
protected bool CreateNewStateWithTransitions(Enum newState, Enum[] transitions, bool forceTransition = false)
{
    if (this.Initialized() == false) { return false; }
    if (this.CreateNewState(newState) == false) { return false; }

    State s = states[newState];
    s.forceTransition = forceTransition;
    foreach (Enum t in transitions)
    {
        if (s.transitions.Contains(t) == true)
        {
            Debug.LogError("State: " + newState + " already contains a transition for " + t + " in " + this.GetType().ToString());
            continue;
        }
        s.transitions.Add(t);
    }
    return true;
}

If our base class contains private FSM methods, our sub class would not contain them, so if we want the FSM to find them, we need to iterate through the class inheritance. When the method info is null, we search the class above for the missing class.

This may seem confusing so look at this:

public class Top : StateMachine{
    void Start(){
        InitializeStateMachine<TopState>(TopState.Init, true);
    }
    private void UpdateInit(){}
}
public class Sub :Top{}

We have a problem. When the initialization method will run, it will consider the calling type, and that is Sub. But Sub has no UpdateInit since it is private in Top. One solution is to make it protected but maybe that is not intended or make the FSM search for it as we did.

The Add/Remove feature actually opens a whole new universe. Until now, we were not able to consider inheritance. If we add an Enemy class with a FSM, we were not able to create a Archer class with specific states to add to Enemy and another Cavalery class with different states to add to Enemy. Now we simply can.

public class Enemy : StateMachine{
    protected virtual void Awake() 
    {
        InitializeStateMachine<StateEnemy>(StateEnemy.Start, true, true);
        AddTransitionsToState(StateEnemy.Start, new Enum[]{StateEnemy.Walk});
        AddTransitionsToState(StateEnemy.Run, new Enum[] { StateEnemy.Walk });
        AddTransitionsToState(StateEnemy.Walk, new Enum[] { StateEnemy.Start, StateEnemy.Run });    
    }
}
public class Archer : Enemy
{
   protected virtual void Awake() 
    {
        // Call this one first
        base.Awake();
        // Do not call that one it was already in the base
        // InitializeStateMachineWithTransitions(true, true); 
        CreateNewStateWithTransitions(StateArcher.Shoot, new Enum[]{StateEnemy.Walk}); 
        AddTransitionsToState(StateEnemy.Walk, new Enum[]{StateArcher.Shoot});
    }
}
public class Cavalery :Enemy
{
   protected virtual void Awake() 
    {
        // Call this one first
        base.Awake();
        // Do not call that one it was already in the base
        // InitializeStateMachineWithTransitions(true, true); 
        CreateNewStateWithTransitions(StateCavalery.Ride, new Enum[]{StateEnemy.Walk}); 
        AddTransitionsToState(StateEnemy.Walk, new Enum[]{StateCavalery.Ride});
        ChangeCurrentState(StateCavalery.Ride);  // Set starting state
    }
}

Alright, so the base.Awake() has to be called before anything else so that it initializes the FSM. Calling it again in sub class would crash. If you want to know whether a class has a FSM above, make the IsInitialized method protected and call it to see if it is already done.
Each sub class registers its own states and add them to the Enemy states. Notice the Cavalery also sets the entry state. We would not be able to do that if the base.Awake was not called first, we would always end up in the state defined in Enemy.

Conclusion

This is now the end of the series, we went from a simple FSM to a more advanced. Based on what you are doing, the first one might be enough, if you do not consider inheritance for instance. In this case, I would use the second version for development and the first article once I got it all working.

Here is the interface of our FSM:

public Enum PreviousState{ get; }
public Enum CurrentState{ get; }
protected bool Initialized();
protected void Update();
protected void InitializeStateMachineWithTransitions(bool debug, bool multiTransition = false);
protected bool CreateNewStateWithTransitions(Enum newState, Enum[] transitions, bool forceTransition = false);
protected bool IsLegalTransition(Enum fromstate, Enum tostate);
protected bool ChangeCurrentState(Enum newstate, bool forceTransition = false);
protected bool AddTransitionToExistingState(Enum state, Enum[] transitions);
protected bool RemoveTransitionToExistingState(Enum state, Enum[]transitions);
protected Enum[] GetTransitionsFromState(Enum state);
protected State[] GetAllState();
protected bool ContainsState(Enum state);
Advertisements

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