informa
/
8 min read
Blogs

Bitmask Multi State Machine

A convenient and lightweight state machine implementation, that allows for multiple states active at the same time and makes complex transitioning easy to define and maintain.

One of the most common ways of storing state and managing state transitions in games is via a deterministic finite state machine. Recently, I’ve struggled to accomplish something, I thought was a simple modification of its behaviour. Namely, make it accept multiple states at once, for the sake of complex player actions, like aiming while walking and crouching, or not allowing to open doors while being dead. One of the ways of doing it, with a classic implementation, would be to create multiple layered state machines in which actions that exclude themselves mutually are on the same layer. The disadvantage of such an approach is the limited communication between layers that doesn’t allow to require some state in order to get into another (in a simple way) or to mix state exclusions between those levels. My solution was to implement it in probably the simplest, most lightweight way, that allow complex state dependencies being cleanly organized, making them easy to debug and change their behaviour.

Storing state in a bitmask

The backbone of the idea is to store the state in a bitmask. Let’s say that we have a following player states to support:

  1. Alive
  2. Moving
  3. Crouching
  4. Aiming
  5. Shooting
  6. Punching
  7. InDialogue

We store the names as an enum. The numbers of its fields indicate which field of a bitmask represent which state, so a state written as: 0011101 (least significant bit on the right) would indicate an alive, crouching player, who is shooting while aiming.

Defining transition schemes

Each state can have its own scheme of transitioning. The required behaviour can be defined with three sets of states:

  • required states - states that need to be active in order to activate and keep active this,
  • terminated states - states that are deactivated when this is activated,
  • states blocking this - states which prevent from activating this.

Let’s try to define how those sets would look like for our states: 

  1. Alive
    • Required {}
    • Terminated {}
    • BlockingThis {}
  2. Moving
    • Required {Alive}
    • Terminated {}
    • BlockingThis {InDialogue}
  3. Crouching
    • Required {Alive}
    • Terminated {}
    • BlockingThis {InDialogue}
  4. Aiming
    • Required {Alive}
    • Terminated {}
    • BlockingThis {InDialogue}
  5. Shooting
    • Required {Alive, Aiming}
    • Terminated {}
    • BlockingThis {InDialogue}
  6. Punching
    • Required {Alive}
    • Terminated {Aiming}
    • BlockingThis {Shooting, InDialogue}
  7. InDialogue
    • Required {Alive}
    • Terminated {Moving, Punching, Aiming}
    • BlockingThis {}

As we can see, to make a state not reachable while other is active is as simple as adding appropriate field to a set. The same goes for requiring and deactivating other states. In our example states would be activated or deactivated only (always) if (when) precise set of rules have been met.

Managing transitions

State managing component is a place where all the transitioning and storing state value takes place. In short, every state activation attempt makes the manager check whether activated state can be activated (checking its required and blocking states) and if it should make other states inactive (terminated states). When state is being deactivated it also checks if any state depended on it (again required states) and deactivates it as well.

side note:
In mathematical terms, the machine is simply a classical state machine, but with states, inputs and transitioning scheme defined implicitly. Each combination of bits is different state, which can transition into another under certain input (activation and deactivation requests). However it is true, it is also simply impractical to think of it that way (as well as trying to visualize it).

Custom activation logic

Usually, a state not only depends on other states in order to be valid for activation, but also some other custom logic (e.g. cooldown). It might be useful to implement a function, which could be overridden in implementations of particular states, that tells whether such conditions are met.

Retriggerable states

Sometimes it might be reasonable to make a state retriggerable as for example with our punching state. Whenever we press a button we might want the state to be deactivated and activated again in order to replay the whole code path. In this case a simple bool indicating such a behaviour would be appropriate.

Debugging

Debugging bitmask states is very simple. Requires a tool that displays all active and inactive states like so:

  1. Alive
  2. Moving
  3. Crouching
  4. Aiming
  5. Shooting
  6. Punching
  7. InDialogue

All the problems encountered with the states boil down to two cases and their algorithmic solutions:

  • State does not activate:
    • check if all required states are active,
    • check if any state blocking this is active,
    • check if custom activation logic is responsible,
    • check if activating function is called for sure.
  • State terminates unexpectedly:
    • check which state activates alongside with the termination and check its terminated states list,
    • check if other state, that is on the required list, was also deactivated,
    • check if deactivating function is not being called.

Networking

A bitmask state, as it is stored in a simple variable, is easily sent via network. Each change can be multicasted to clients and thus the whole mechanism of state activation / deactivation independently triggered on every connected machine. In that way, we ensure a proper visual or gameplay reaction in every instance of a game.
In case of a client request (pressing a button on a client) it might be sent to a server in form of an RPC, validated there and an updated state sent back via standard notification procedure. In such a case, the input lag would be the length of the ping, which could be unacceptable. An alternative is to trigger a state on a client and ask server for correction. It could however lead to an unpleasant situation like this:

A way of dealing with such a case, would be to establish a special channel of communication, used only to confirm activation of states that can be triggered independently on a client:

Implementation details

State

First step in implementing the architecture would be to define a state. Such a state, in a component architecture, would probably be stored in a BitmaskStateManagerComponent, to which states defined in other components, would register themselves. The interface of the state, called for the sake of discussion a BitmaskState, could be defined in a following manner:

GetStateMask() - returns the mask of the state which would be a single bit placed on an appropriate field:

long state = 1 << (int) State.Aiming;

long GetStateMask()
{
    return  state;
}

CanBeActivated() - designed to be overridden in particular implementations of state. Contains custom activation check.

IsRetriggerable() - tells whether the state can be deactivated and activated again if TryActivateState() is being called.

TryActivateState() and DeactivateState() - refer to the BitmaskStateManagerComponent, which checks the required conditions for the state and activates it with regard to them.

void TryActivateState()
{
    manager.TryActivateState(this);
}

void DeactivateState()
{
    manager.DeactivateState(this);
}

OnActivated() and OnDeactivated() - are to be implemented as a code that executes on the beginning and the and of a state, allowing to play animations or execute a gameplay code at the moment of transition to / from a state. OnDeactivated() is especially useful for cleaning up the state and ensuring that no artifacts are left around. One of the applications would be for example to reduce walking speed on crouch activation or reducing the mouse input sensitivity on activation of aiming state.

State transitions

Each of transition sets can be represented again as a bitmask, so the following functions can be added to our interface:

State[] requiredStates = {State.Alive, State.Aiming};
long requiredStatesMask = ToBitmask(requiredStates);

long GetRequiredStates()
{
    return requiredStatesMask;
}

long GetTerminatedStates()
{
    ...
}

long StatesBlockingThis()
{
   ...
}

Note that the implementation doesn’t actually depend on any particular enum, so it can be easily used for many types of states.

State manager

As the whole interface of a BitmaskStateManager shouldn’t be used by a final user implementing states, I will just give here a quick and clean run-through of the code that above examples referred to:

long currentState;
Dictionary<long, BitmaskState> registeredStates;

void TryActivateState(BitmaskState state)
{
    if(CanBeActivated(state))
    {
        if(state.IsRetriggerable())
        {
            DeactivateState(state)
        }
        ActivateState(state);
    }
}

bool CanBeActivated(BitmaskState state)
{
    return
        state.CanBeActivated()
        && (!IsActive(state) || state.IsRetriggerable())
        && !IsBlocked(state)
        && HasRequiredStates(state);
}

bool IsActive(BitmaskState state)
{
    return state.GetStateMask() && currentState != 0;
}

bool IsBlocked(BitmaskState state)
{
    return state.GetStatesBlockingThis() & currentState != 0;
}

bool HasRequiredStates(BitmaskState state)
{
    return state.GetRequiredStates() ^ currentState == 0; //XOR
}

void ActivateState(BitmaskState state)
{
    DeactivateStates(state.GetTerminatedStates());
    currentState |= state.GetStateMask();
    state.OnActivated();
}

void DeactivateStates(long states)
{
    var statesToDeactivate = currentState & states;
    var bitmaskStatesToDeactivate = GetStatesFromRegistered(statesToDeactivate);
    
    foreach(var stateToDeactivate in bitmaskStatesToDeactivate)
    {
        DeactivateState(stateToDeactivate);
    }
}


void DeactivateState(BitmaskState state)
{
    currentState &= !state.GetStateMask();
    state.OnDeactivated();
    DeactivateStates(GetStatesRequiring(state));
}

Summary

Bitmask states are very simple way of maintaining a consistent behaviour of any object in a game. It’s lightweight nature makes it perfect for usage in a great number of entities. Easily definable transitioning schemes are simple to debug and very flexible. It also makes it perfect for network usage, as a complex behaviours of state activation / deactivation can be triggered by sending a single variable value. The biggest downside of this implementation is a limited set of states that can be used (32 or 64 for standard int or long implementations), but if it would become a problem, an array of such could be employed. Additionally, a way of transitioning between states varies greatly from a standard state machine and requires the states to contain universal initialization / cleanup logic, independent from other states and transitioning reasons. It also makes a standard way of state machine visualisation not applicable. So far showing only which states are active / inactive proved to be sufficient for the debugging purposes.

Latest Jobs

Treyarch

Playa Vista, California
6.20.22
Audio Engineer

Digital Extremes

London, Ontario, Canada
6.20.22
Communications Director

High Moon Studios

Carlsbad, California
6.20.22
Senior Producer

Build a Rocket Boy Games

Edinburgh, Scotland
6.20.22
Lead UI Programmer
More Jobs   

CONNECT WITH US

Register for a
Subscribe to
Follow us

Game Developer Account

Game Developer Newsletter

@gamedevdotcom

Register for a

Game Developer Account

Gain full access to resources (events, white paper, webinars, reports, etc)
Single sign-on to all Informa products

Register
Subscribe to

Game Developer Newsletter

Get daily Game Developer top stories every morning straight into your inbox

Subscribe
Follow us

@gamedevdotcom

Follow us @gamedevdotcom to stay up-to-date with the latest news & insider information about events & more