2013-09-26

Implementing a Transition-based State Machine

Warning: this is one of the code heavy posts I once warned about. Those allergic to discussions of programming topics or big listings of code (C# code; it's not that bad), keep walking. Or stay and become harder, better, faster, stronger...

In this article I will introduce a (probably not so) new approach to implementing State Machines, mostly for videogames. The reference is, as usual, Buckland's implementation in his Programming Game AI by Example book. His version of the state machine was and still is the de facto standard when coding small AIs or logical behaviours. Although new and improved systems exist, like Behaviour Trees, FSMs are still pervasive in the video game industry.

FSMs have been slightly improved through time, as languages and techniques developed, offering new possibilities, but the core remains pretty much unchanged. Here I will introduce one major revision to how SMs are implemented and, more important, used.

Basic introduction to the classic State Machine

In Buckland's book, State Machines are composed of several elements:
  • The State Machine itself, which contains
    •  A reference to the machine's owner
    • The current state to execute
    • The global state to execute
    • The previous state, in case a behaviour requires going back to it
  • A base generic abstract class State<T>, with methods Enter, Update and Exit. Enter is called when the state becomes the current one, Exit when it stops being so. Update is called on every execution cycle (of the state machine, not necessarily of the game or entity).
  • A collection of singletons derived from State<T>, one for each behaviour T can display.
  • A messaging system which allows communication between entities. State<T> includes an abstract method to evaluate messages and treat them if appropriate.
Important details:
  • States are, curiously, stateless. That's why a reference to the owner is required: it must contain all the state information the machine needs.
  • It is considered in bad taste (but unfortunately common) to transition from outside the states themselves, but the state machine usually allows this through several hijacking methods.
Thus, each state is responsible for checking its possible transitions. State hijacking is supported via the global states, which check conditions outside the scope of low level ones. If used, global states usually become a state machine of their own, to support all the possible situations.


Problems with this State Machines

A list of the issues affecting state machines.

Verifying transitions

My biggest issue with the classic implementation is that it hides the transitions inside each state. To verify that a state machine is properly implemented you need to check each state's Enter, Update, Exit and TreatMessage methods, including the global states', and verify that the graph is properly represented. It doesn't take long before this approach becomes unwieldy.

This stems from a very simple fact regarding state machines: the number of transitions is always at least equal to the number of states, and usually increases non-linearly with it.

Code required

In well constructed state machines, the code each state is really about is usually small and clear. Unfortunately, given the requirements for each state to be a singleton and evaluate transitions, they end containing lots of boiler-plate code. The singleton itself can easily take more space than the actual state functionality.
Transitions introduce an extra series of ifs cluttering the Update method and rendering it hard to read. Add in the fact that if a state change is triggered, you must include an early return to avoid the rest of the Update to execute after the Exit method, and you've got yourself a pretty mess.

Having to evaluate messages doesn't help either, as it usually includes code to discard undesired messages (easily reduced by using messaging systems with configurable notifications), and treating all the accepted messages.

This means that the ratio of useful code (what the state does) to actual code in each state is way below half.

Global states

Global states are required to reduce the number of transition checks each state must do. If several states, under a common circumstance, transition to the same state, a global state can take care of checking and changing the state itself. This includes checking messages and the world state.

But the possible transitions can change over time, so global states also transition from one to another. Now, can we go to a previous global state? Can they be hijacked? Who controls their transitions? If kept unchecked, global transitions can become a monster themselves. Their only role was allowing reduction of transitions, but we now have more transitions to control in a level above all the actually relevant states.
Or, you can have just one global state which checks the current state and runs the required conditions for each. This gets ugly fast, too.

Messaging as hijacking mechanism

Eventhough state changes are expected to only happen from inside the state machine, by offering the possibility of checking messages the floodgates open. Now, if a new transition is required that no state checks, we can just send a message from the outside and add some code in the required state to react to the message. We might be upholding the letter of the law, as the transition is launched from inside a state, but its intent is broken: anyone is allowed to send a message and force a transition at any time. And your state machine suddenly looks like a very ellaborate goto-label with cheese all over it.

The ability to evaluate messages is useful beyond that, of course. Some messages only make sense if in a given state and produce reactions of their own, beyond transitions. But too often they become a simple hijacking system. As a matter of fact, Buckland's example of message treating in his book is just that: an entity waits for another one to send a specific message, and changes to the corresponding state.

No states reusing

Since a state contains its transition logic in itself, different machines are unable to reuse existing states, or would have a hard time doing so.

Poor support for hierarchical entities

This is a really bad one. If you have a hierarchy of entities controlled by state machines, you'd expect to reuse common, low level states for all of them. Unfortunately, given the fact that a state machine is defined as StateMachine<EntityType> and its states must match that type argument, that's usually not possible. The rules of covariance and contravariance play against us, most of the time. I'm currently working on a solution to this problem, which I'll try to publish later.

Transition Machine


Now, I'll explain my approach to solving some of these issues. Although my classes still use StateMachine as their name (that's the mathematical term, and I'll respect that), for this article I'll refer to my implementation as Transition Machine, to emphasize the difference.

The idea is to define states and transitions independently. The transition machine will store all the possible transitions, each containing the source and target state, and the condition required for the transition to be executed.

In other fields of computer science, it is common to define also Actions as part of the state machine. A transition may trigger an action, as well as entering, executing or terminating a state. In our case, we will be limiting the execution of actions to the Enter, Update and Exit methods of each state, so we don't need a particular class for that.

By defining transitions outside states we can now configure a transition machine in a much more straightforward way. The definition of transitions between states will be easily verified by checking it against the state diagram. Modifying and adding transitions is also easy to do, as it only requires changing the configuration of the transition machine. Worst case scenario, we will have to add new states and conditions, but these are now so simple that their construction is easy and less error prone than with the traditional approach.

So let's chech some code (all of it is available at the project's GitHub page). I've removed the XMLDoc, but the code is simple enough to be understandable without it. Refer to the repository if you need help.

The base state is no longer an abstract class, so we can instantiate and build a new one on the fly, provided the required functions are available:

    public class State<T> {

        public Action<T> OnEnter { get; protected set; }
        public Action<T> OnUpdate { get; protected set; }
        public Action<T> OnExit { get; protected set; }

        protected State() { }

        public static State<T> Build(Action<T> onEnter, Action<T> onUpdate, Action<T> onExit) {
          return new State<T>() {
            OnEnter = onEnter,
            OnUpdate = onUpdate,
            OnExit = onExit
          };
        }
    }


A new state can be created without requiring the whole singleton jadda-jadda, and can be kept as a static variable:

    static class EntityStates {

        #region Idle state

        private static State<Entity> idle = null;
        public static State<Entity> Idle {
            get {
                if (idle == null) {
                    idle = State<Entity>.Build(
                        null,
                        IdleUpdate,
                        null );
                }

                return idle;
            }
        }

        private static void IdleUpdate(Entity ett) {
            // Look for target
        }

        #endregion

        // ...
    }


And transitions are equally simple. Just a condition to check, a collection of states from which it can start or from which it cannot, a target state and a simple evaluation function:

    public class Transition<T> {

        public Func<bool> Condition { get; private set; }

        private State<T>[] fromStates;
        public IEnumerable<State<T>> FromStates {
            get {
                return fromStates;
            }
        }

        private State<T>[] exceptionStates;
        public IEnumerable<State<T>> ExceptionStates {
            get {
                return exceptionStates;
            }
        }

        public State<T> ToState { get; private set; }

        // ...

        public bool IsApplicable(State<T> currentState) {
            bool stateMatches = false;

            if (fromStates != null) {
                for (int i = 0; i < fromStates.Length; ++i) {
                    if (currentState == fromStates[i]) {
                        stateMatches = true;
                        break;
                    }
                }
            } else {
                stateMatches = true;

                if (exceptionStates.Length > 0) {
                    for (int i = 0; i < exceptionStates.Length; ++i) {
                        if (currentState == exceptionStates[i]) {
                            stateMatches = false;
                            break;
                        }
                    }
                }
            }

            return stateMatches && Condition();
        }

        // ...
    }


The State Machine code is similarly simple. It has the current and previous states, the list of transitions, a means to change states (via properties which do all the transition calls), and means to add transitions and check them.
You will notice that there is no global state or message managing here. Global states are unneeded because transitions can be defined for several source states at once. And messages should be treated by the machine's owner, who would update the information the transitions check as their conditions.

    public class StateMachine<T> {

        public T Owner { get; private set; }

        private State<T> prevState = null;

        public State<T> PrevState {
            get { return prevState; }
            private set {
                prevState = value;

                if (null != prevState && null != prevState.OnExit) {
                    prevState.OnExit( Owner );
                }
            }
        }

        private State<T> state = null;

        public State<T> State {
            get { return state; }
            private set {
                PrevState = state;
                state = value;

                if (null != state && null != state.OnEnter) {
                    state.OnEnter( Owner );
                }
            }
        }

        private List<Transition<T>> transitions = new List<Transition<T>>();

        public StateMachine(T owner, State<T> initialState) {
            Owner = owner;
            State = initialState;
        }

        public StateMachine<T> AddTransition(Transition<T> transition) {
            transitions.Add( transition );

            return this;
        }

        public StateMachine<T> AddTransitions(params Transition<T>[] trans) {
            foreach (var transition in trans) {
              transitions.Add( transition );
            }

            return this;
        }

        // ...

        public void Update() {
            var toStates = from transition in transitions
                           where transition.IsApplicable( State )
                           select transition.ToState == null

                               ? prevState
                               : transition.ToState;

            if (toStates.Any()) {
                State = toStates.First();
            }

            if (null != State.OnUpdate) {
                State.OnUpdate( Owner );
            }
        }

        // ...
    }


For those worried about lost CPU cycles, it would be quite easy to store all the transitions which can start from the current state and only check those on each update, saving some time. It is also very easy to add fuzzy logic into the mix: just add a viability calculation on the transitions, and randomly choose between the possible ones, according to their relative probability.

And, finally, thanks to some fluent magic and variadic parameters, instantiating a state machine becomes something as simple as:

    class Entity : IStateful<Entity> {

        private StateMachine<Entity> stateMachine = null;

        // ...

        public void Initialize() {

            stateMachine = new StateMachine<Entity>( this, EntityStates.Idle )
                .AddTransitions(
                    Transition<Entity>
                        .FromAny()
                        .Except( EntityStates.Idle, EntityStates.Talk )
                        .To( EntityStates.Idle )
                        .When( HasNoTarget ),
                    Transition<Entity>
                        .From( EntityStates.Idle )
                        .To( EntityStates.Walk )
                        .When( HasTarget ),
                    Transition<Entity>
                        .From( EntityStates.Walk )
                        .To( EntityStates.Talk )
                        .When( IsTargetInRange ),
                    Transition<Entity>
                        .From( EntityStates.Talk )
                        .To( EntityStates.Idle )
                        .When( DoneTalking ) );

        }

        // ...
    }


Gains from Transition Machine

This implementation solves most of the problems from classic state machines:

Verifying transitions

To verify that a state machine is properly coded, you just need to check the transition definitions. If they match the design, errors are limited to the states or the design itself. Adding transitions and states only increases the definition code, but, it being greatly localized, adding errors is harder than on the highly distributed structure of the classic approach.

Reduced boiler-plate code

States now only care about what they actually do, whether they reproduce an animation, start an attack or scan the area. Transitions are also divided into smaller, independent conditions, so they require less code and are easy to debug. The state machine itself is now simpler, too, and no global states are needed.

No global states

They have been replaced by transitions which can start from one, several, all or all but a few states. And this can be easily expressed in a single line of code in the state machine's initialization.

Messaging cannot directly hijack

By not supporting messaging we have prevented an arbitrary source of state changing. Messages are instead expected to produce a change on the state machine's owner or its world, triggering the relevant conditions. Thus, a message telling "Honey, I'm home" would set "JohnyIsHome = true", and a transition could evaluate that variable.

State reusing

States can now be reused among different transition machines, since they are now independent from the machine they are a part of and the transitions from and to them. The only limitation in the current implementation is related to the generic type with which the state machine is defined.


Scripting ease

As a bonus, with this approach it is a lot easier to define a state machine as a configuration file in XML, Json or whatever, to be scanned and turned into a working state machine. You'd need to define identifiers for each state and condition, and build them at load time (probably using a factory), but that code would be simple enough and would let your designers (or even the coders) easily re-define the state machine without the need to touch the code.

Conclusion

I've presented a noticeable improvement over classic state machines, based on the separation of states and transitions. This has made them a lot easier to implement and use, even making it more scripting friendly.
To check a C# implementation (with no license at all), check the repository. In the future I expect to write a C++ implementation (which will be unfortunately way uglier and more verbose). If I find the time, I'll release a D version too.

Future work

The states in this implementation are still ungracefully coupled to their type parameter and that of the state machine. I intend to tackle this problem by making states depend only on the data they require to function, be that defined as an interface or an element in a flyweight context. I'll let you know when I find a suitable solution.

Acknowledgments

This would not have been possible if people like Buckland and many others had not collected their know-how and made it available to all. Only by letting others see our work can we expect to see it improved.

Of great importance have been my endles discussions and conversations with @cookingsource. Because of him, I am a better programmer. Also, most of the cool stuff you'll see in my code was known to me through him. But not Yoda conditions; those are all mine. And I love them.

Also, while writing this I've found several articles specifying similar approaches, although usually a little more complex. Check this for an in-depth analysis of short-comings on the usual definition of state machines, and a more complete solution to their problems. Documents like this one are also a big help when trying to conceptualize the nature of state machines.

No comments:

Post a Comment