State machine – how to handle outside environment values

finite-state machineunity3d

I've got a state machine implementation in Unity that I'm working on (C#), the plan being that it will be mostly used for AI related things.

I'm not sure how I should deal with various "inputs" / how it should interact with knowledge from the outside environment. Two approaches I've considered and tried so far:

1, I have a dedicated "Query" class that holds various bools. At the end of the Tick() method in each state I make some checks like

if (queries.JumpUp) { SetState(JumpState); }

that take care of switching states. To change states, I simply set the bool to true.
This seems to work fine, creates a very loose relationship between the "query" and the resulting behaviour, and lets me place pretty much all the transition logic in a dedicated method (my base Tick() method calls an CheckForTransitions() method at its end, and it's this method that I override and put all the transition logic in).
It works fine so far, but I'm a bit worried that this type of logic might be almost a bit too loose. I think it might be somewhat similar to the blackboard design pattern. It also feels a bit like an observer pattern, which could be useful – I might have multiple different types of state machines active at the same time. A "Query" class that has booleans like I mentioned seems like a very natural way of implementing a general interface layer that will allow for loose "communication" between the layers etc.

2, Create virtual methods for all possible "events" I would like to be handled.

public override void TryJump() { SetState(JumpState); }

To change states, I explicitly call the method above (or some wrapper around it, implemented inside the StateMachine).

This also seems to work fine. Some slight negatives I can see compared to 1:
With approach 1, there's no issues if I choose to update my state machine independently of the game loop. With approach 2, there could be multiple calls that result in a transition between two state machine ticks/updates. This could be fixed by the making calls like "TryJump()" change some buffer variable that would just hold the desired next state, and the actual transition would perhaps happen at the end/start of the state machine update (rather than "TryJump()" causing an immediate change in states).
But at that point I'm getting very close to the approach used in 1, so I'd think I might as well just use that.

I don't have a single nice place in the code where I can check exactly what sort transitions can happen and what their conditions are.
I will have to have tons of virtual methods for each state, for each "TryJump" type event. If I don't want to work with a direct reference to the state machine, I will have to also write wrappers, that will call those TryJump events the currently active StateMachines – so something like say:

public void TryJump() 
{ 
 foreach (StateMachine stateMachine in ActiveStateMachines) 
     stateMachine.currentState.TryJump(); 
}

Despite that, something just feels a bit off about the method in 1, – using booleans like that just seems a bit weird. I'm also not terribly comfortable with event based approaches, and it feels a bit "wrong" to use a special layer with booleans etc., when I could just make a direct call that does what I want using approach 2.

EDIT – adding some example code to clarify how I'm doing things so far.

class StateMachine
{
    private State currentState;
    public void SetState(SimpleState newState)
    {        
        state = newState;        
    }  
    public void Tick()
    {
        state.Tick();
    }
}

abstract class State
{
    public parentStateMachine;
    protected void SetState(State newState) {parentStateMachine.SetState(newState);}        
    public void Tick()
    {    
        Update();
        Transition();
    }  
    protected virtual void Update(){}
    protected virtual void Transition(){}
}

the state machine tick is then called for example as:

public void Update() // game loop update inside Unity3D
{
   stateMachine.Tick();
   queries.Clear(); // Clears all the bool values inside queries
}

an example of how a Transition override could look when using approach 1:

protected override void Transition()
{
    if (queries.PickupAProp && currentProp == null)
        {
            SetState(PickupPropState);
            return;
        }
    if (2secondsPassedSinceEnteringThisState() && queries.WalkToTarget)
        {
            SetState(WalkState);
            return;
        }
}

in other words, all the logic concerning decision of what state to choose next is implemented mostly in the state extension itself. "queries" really just work as something that holds various data / signals. It shouldn't contain any complicated logic and in my current implementation it's mostly booleans.

The alternative approach 2, could then replace certain "checks" like so:

public override void TryPickupProp()
{
    if (currentProp == null)
    {
        SetState(PickupPropState);
        return;
    }
}

In places where I did queries.PickupAProp = true; I could now instead just do stateMachine.state.TryPickupProp();

But Transition() should still contain the check:

if (2secondsPassedSinceEnteringThisState() && queries.WalkToTarget)
{
    SetState(WalkState);
    return;
}

As that's a purely "internal" check. But the TryPickupProp() query could now just be called directly.

Best Answer

What’s the problem?

Three actions are needed to manage the state transition:

detecting the causes that trigger a state change;
determining the target state;
switch from the current to the target state.

Unfortunately, your narrative does not tell how you keep track of the current state, which influences all three actions. But it seems that:

Your tick() function is related to the frame refreshment and triggers the detecting of state change.
Your two alternatives are about detecting the changes and determining the next state:
- the first gives the responsibility detecting and target determination to the query class.
- the second gives the responsibility of the detecting and the target selection to each state.
The state machine itself then makes the switch happen.

Your approach has in any case the inconvenience of an active poll for state changes; polling is always a waste of resources, especially if the state changes are not related to the ticking. Moreover, the polling requires to know what to poll for, and this creates some tighter coupling.

How to improve it?

Both alternatives might currently lead to a maintenance nightmare. So my advice is to brainstorm on the consequences of adding a new state or changing the state transition rules on your current code. Up to you to see how this could be dealt with, but this thinking could be the driver for a more robust design.

One approach would be to use a “queue” of events. Whenever something implies a state change, put a state change event in the queue. When tick() is performed, just check if there is a state change event in the queue and activate the target state. If delaying to the tick is not desired, just activate the change immediately.

Now, a usual debate is whether to externalize the state transition rules (e.g. in a table) or to let the state decide what comes next. In games, where states are rich, the second approach seems a good candidate. But unlike your second alternative, the state would not call an overridden virtual function directly: it would just put an event corresponding to the next state in the queue.

A last point is how to detect the events. It makes no sense to answer this, as it depends heavily on how you manage your current state and react to input, and we don’t know. But I think that once you’ve started to implement the other ideas, this part will appear straightforward.

Related Solutions

State machine with additional variable

The computer science answer is that you do indeed have up to 18*3*2 distinct states to deal with. How these states should be encoded into your program depends on your goals.

By writing down all possible states and restricting yourself to simple state transitions, you have the advantage that your code corresponds directly to a DFA. This lets you check all state transitions easily (though tediously). By analysing the state transition table, you can prove that the program will always respond correctly to any input sequence. Without this explicitness, it can get difficult to show that the control flow exhibits certain constraints, e.g. that some state is only reachable when a is set. You can also show that the program will always halt.

Unfortunately, large numbers of states are not very maintainable. This is only a good solution if you need formal verification, and can preferably generate the necessary code from an automatically-checked model.

In most cases, you will want to focus on maintainability instead. Being obvious is more important than being absolutely 100% correct (you can ensure some level of correctness more cheaply through testing). The bad news is that state machines are not very easy to understand for more than three states or so. The there are various techniques to manage the cognitive load of state machines.

One you have already found: expressing only a set of primary states in the state machine, and handling secondary state separately. This can drastically simplify the code when most state transitions do not depend on the secondary states. However, it's easy to accidentally get the various states out of sync, e.g. forgetting to reset a secondary state whenever a certain primary state is left. This can be made more unlikely by requiring all state changes to go through a single function, that makes sure a complete state has been intentionally provided. If the state space is somehow constrained to certain combinations of values, this function can also perform consistency checks. So instead of

oldstate: event {
  if (a) {
    b = A
    → newstate1
  } else {
     // forgot: b = B
     → newstate2
  }
}

we would be forced to provide a b value with

oldstate: event {
  if (a) → state(newstate1, a: a, b: A)
  else   → state(newstate2, a: a, b: B)  // can't forget value for b
}

The biggest simplifications are possible when chopping up your complete DFA with its 108 states into nested DFAs. When you look at the complete state transition diagram, some parts of the graph will feature many transitions within that subgraph, but will only have few transitions entering that subgraph and one transition leaving the subgraph. You can then extract the subgraph as a separate DFA, and call the extracted DFA like a procedure/function. If the subgraph has multiple entry points, you need to pass the relevant state as parameters so that the suitable start state can be chosen. Compare also the Extract Method refactoring.

Sometimes, multiple extractable DFAs have the overall same structure: same states, same inputs, but differ in their output and in one dimension of the state (e.g. each is used for a different value of the b variable). Extracting these separately would hide their similarity and thus make maintenance more difficult. In such a case, you can make parts of the state transition table pluggable. We unify the states of the extracted DFAs, and represent the extracted table as data. If the state transitions have side effects or if the target state of a transition depends on other variables, the state transition table will hold function pointers. In an object oriented system, each extracted state transition table would be an object, and the cells of the table would be methods on these objects. The main state transition table now only considers the unified states, and delegates the state transition to that extracted state transition table that is required by the currently active secondary state.

oldstate: event {
  → transition_table_for(b).oldstate_event
}

In many cases, the secondary state can be directly represented as a pointer to the active state transition table.

Finally, it might be better to represent the state implicitly in terms of the control flow of imperative code, rather than hand-rolling a difficult to maintain state machine. Most programmers are used to reasoning about imperative programs. For example, any DFA can be expressed as a set of mutually recursive functions, where each function corresponds to a major state. (E.g. most handwritten parsers use a recursive descent approach, rather than specifying the tables for a LL or LR parser). Smaller states can be represent implicitly in the control flow within the function. The debuggability of such function-encoded state machines is excellent, since the stack trace contains relevant states that lead to the current state. However, an imperative encoding becomes tedious unless the state transition table is fairly sparse. If the DFA you are implementing was derived from an NFA, imperative encodings allow you to reduce the number of states back to the NFA states by using backtracking (though this does have an exponential worst case).

At this point, we have completely given up any chance of formal verification, but have possible arrived at a much terser and more maintainable representation. Where on this scale you want to be depends on the requirements and constraints of your project. E.g. I once saw a parser that could have been simplified by using conrol flow to represent the states. However, a requirement was that it operated asynchronously. Without language-level support for async operation, the state necessarily had to be made explicit.

Java – Trouble with circular dependency in state machine design

... my question is more around how I should change the design to avoid needing this circular dependency. – Jordan

One method I've seen is to have each state construct the next state. That works but feels like it's abusing the garbage collector. Here's a method that lets you bounce back and forth from two immutable states.

interface State {
    boolean process(Context context);
}

enum States implements State {
    A {
        public boolean process(Context context) {
            System.out.println(States.A);
            context.setState(States.B);
            return true;
        }
    }, B {
        public boolean process(Context context) {
            System.out.println(States.B);
            context.setState(States.A);
            return true;
        }
    }
}

class Context{
    State state;

    public Context(State state) {
        this.state = state;
    }

    public State getState() {
        return state;
    }

    public void setState(State state) {
        this.state = state;
    }
}

class Processor {

    public void process(Context context) {
        while(context.getState().process(context));
    }
}

public class EntryPoint {
    public static void main(String[] args) {
        Processor p = new Processor();
        Context cd = new Context(States.A);
        p.process(cd);
    }
}

Inspired by this