Finite state machines in game development

This post assumes that you have knowledge about finite state machines, for a good understanding of that subject follow this link or use your favorite search engine to find more about this topic.

Recently I had to add additional functionalities to one of my game characters, at the time the character’s actions were only idle, running and jumping, but I had plans for actions such as rolling, ducking, walking and ledge grabbing.

The problem was that adding additional functionality was becoming not only an unpredictable bug hunting but also was opening holes for new ones to come in, and when this happens it’s clearly a sign of a bad design.

My initial pseudo code for the three initial actions could be interpreted as:

void Update()
{
	if(Input.A)
	{
		MoveLeft();
	}
	else if(Input.D)
	{
		MoveRight();
	}
	
	if(Input.Spacebar)
	{
		Jump();
	}
}

Readability is not a big issue here, since there’s not many instructions, but there’s a bug there not very difficult to spot, the character can infinitely jump, let’s fix that.

void Update()
{
	if(Input.A)
	{
		MoveLeft();
	}
	else if(Input.D)
	{
		MoveRight();
	}
	
	if(IsGrounded && Input.Spacebar)
	{
		Jump();
	}
}

Only when our character is grounded we can perform a jump, but I wanted to do something more than this, something awesome! I’m going to add double jump.

void Update()
{
	if(IsGrounded)
	{
		DoubleJumping = false;
	}
	
	if(Input.A)
	{
		MoveLeft();
	}
	else if(Input.D)
	{
		MoveRight();
	}
	
	if(Input.Spacebar)
	{
		if(IsGrounded)
		{
			Jump();
		}
		else if(!DoubleJumping)
		{
			Jump();
			DoubleJumping = true;
		}
	}
}

There you go, now the character double jumps, and doesn’t allow for triple jumps!
There problem is, this code is quite messy, first we have to check the state of the character, then we have to check the inputs and then we perform the actions, this to me seems like 3 steps that can be completely separate.

It was at this same point that I knew that this spaghetti wouldn’t be a tasty dish, so the next step here was a good refactoring. How? By introducing state machines.

My implementation of the state machines is slightly different than the usual ones you can find around in other blogs, usually other authors perform state checks inside the states to transition between states, I preferred to avoid this because:

  • I wanted my states as clean as possible do the actions and don’t worry with if-else chains.
  • I wanted my states to be reusable, since I predicted that other characters would have the same states, but with different quantities of states and transitions I preferred to keep them separate.
  • When debugging transition conditions I didn’t want to go from one state file to the other to understand what’s failing, I wanted the conditions in one single screen.

Let’s start by defining what is a state with the follow code snipped:

public interface IState<TStateController, TAction>
{
	TStateController StateController { get; set; }
	float TimeInState { get; set; }

	void OnStateEnter(TAction action);
	void Perform(TAction action);
	void OnStateExit(TAction action);
}

So, let’s take a deeper look at what we have, we have a generic interface with two generic parameters, TStateController and TAction.

TStateController is meant to be the character controller, remember before where we check for the character information like IsGrounded property? That is the place where you should deal with these properties assignment, and will contain methods for the state to call, like “Move(…)” and “Jump(…)” and so on.

TAction on the other hand is where we will assign the actions the user wants to perform: move, jump, etc

The property TimeInState is useful because some states require some time inputs, so having this on the state interface is always a plus.

OnStateEnter method should be called when there’s a transition to this state, while OnStateExit is called when there’s a transition out of this state.

Perform is the state action.

Now for some more code that I will explain after

public interface IStateFactory<TController, TAction>
{
	TState State<TState>() where TState : class, IState<TController, TAction>, new();
	StateContainer<TController, TAction> GetContainer<TState>() where TState : class, IState<TController, TAction>, new();
}
public class StateManager<TController, TAction> : IStateFactory<TController, TAction>
    {
        private TController _controller;

        private StateContainer<TController, TAction> _root;
        private StateContainer<TController, TAction> _currentStateContainer;

        private Dictionary<Type, StateContainer<TController, TAction>> _states;

        public IState<TController, TAction> CurrentState
        {
            get
            {
                return _currentStateContainer.State;
            }
        }

        public StateManager(TController controller)
        {
            _controller = controller;
            _states = new Dictionary<Type, StateContainer<TController, TAction>>();
        }

        public void Perform(TAction action)
        {
            if(_currentStateContainer == null)
            {
                return;
            }
            var current = _currentStateContainer;
            current.State.TimeInState += Time.fixedDeltaTime;

            var child = current.Transitions.FirstOrDefault(t => t.Condition(_controller, action, current.State.TimeInState));
            if(child != null)
            {
                current = child.StateContainer;
                _currentStateContainer.State.OnStateExit(action);
                _currentStateContainer = current;
                _currentStateContainer.State.TimeInState = 0;
                _currentStateContainer.State.OnStateEnter(action);
            }

            _currentStateContainer.State.Perform(action);
        }

        public TransitionConfiguration<TController, TAction> SetInitialState<TState>() where TState : class, IState<TController, TAction>, new()
        {
            var state = State<TState>();
            var container = _states[state.GetType()];
            _root = container;
            _currentStateContainer = _root;
            return new TransitionConfiguration<TController, TAction>(this, _root);
        }

        public TransitionConfiguration<TController, TAction> From<TState>() where TState : class, IState<TController, TAction>, new()
        {
            var state = State<TState>();
            var container = _states[state.GetType()];
            return new TransitionConfiguration<TController, TAction>(this, container);
        }

        public TState State<TState>() where TState : class, IState<TController, TAction>, new()
        {
            var type = typeof(TState);
            StateContainer<TController, TAction> cachedState;
            if (_states.TryGetValue(type, out cachedState))
            {
                return cachedState.State as TState;
            }
            var state = new TState()
            {
                StateController = _controller
            };

            var stateContainer = new StateContainer<TController, TAction>(state);
            _states.Add(type, stateContainer);
            return state;
        }

        public StateContainer<TController, TAction> GetContainer<TState>() where TState : class, IState<TController, TAction>, new()
        {
            var state = State<TState>();
            return _states[state.GetType()];
        }
    }
public class StateContainer<TStateController, TAction>
{
	public IState<TStateController, TAction> State { get; private set; }
	public List<StateTransition<TStateController, TAction>> Transitions { get; private set; }

	public StateContainer(IState<TStateController, TAction> state)
	{
		State = state;
		Transitions = new List<StateTransition<TStateController, TAction>>();
	}
}
public class StateTransition<TStateController, TAction>
{
	private Func<TStateController, TAction, float, bool> _condition;
	private StateContainer<TStateController, TAction> _stateContainer;

	public Func<TStateController, TAction, float, bool> Condition { get { return _condition; } }
	public IState<TStateController, TAction> State { get { return _stateContainer.State; } }
	public StateContainer<TStateController, TAction> StateContainer { get { return _stateContainer; } }

	public StateTransition(StateContainer<TStateController, TAction> stateContainer, Func<TStateController, TAction, float, bool> condition)
	{
		_stateContainer = stateContainer;
		_condition = condition;
	}
}

So, the IStateFactory is a factory interface to create states, there’s not much to say there.

The StateManager implements the factory interface and handles the cyclic transitions between the states, and deals with calling their methods and updating their properties, this is the most complex class in the whole mechanism.

StateTransition and StateContainer and used to store data to simplify the StateManager work.

After this if I wanted to create a state machine for my character I could create a class called PlatformerCharacterStateManager, inherit from the StateManager and start to set the states in the following way in the constructor:

this
	.SetInitialState<MoveState>()
		.To<JumpState>((controller, action, time) => a.Jump && c.IsGrounded);

this
	.From<JumpingState>()
		.To<MoveState>((c, a, t) => c.IsGrounded);

Where MoveState would implement the Perform method by calling the controller’s Move() method and the JumpingState would implement OnStateEnter method and call the controller’s Jump() method.

To conclude just need to set Controller’s properties, create the Action object and use it to call the StateManager‘s Perform method.

You can check an example of this implementation on my github repository to get a better idea of a bigger implementation.

Software developer in Edinburgh, passionate about web and solutions for difficult problems, in my free time I like to do game development coding, art, level design and story writing.

Your email address will not be published. Required fields are marked *