Finite State Machine

A finite-state machine, or finite automaton is a model of computation. An abstract machine defined by a set of States and a the set of events that trigger State changes called Transitions. The finite model states that the Machine can be in only one State at any given time, which is called the CurrentState.

It’s been since a long time I first met FSM, probably early 2000, when I was CTO at a social multiplayer games site, were people played against people in real-time. Every game context had to be held remotely, had to be secure as much as possible and deterministic, to name a few of the core features. Modeling a whole game, cards, table, etc. and making it fulfill such features is not an easy task unless you rely on a powerful framework. The best solution I came up with was FSMs, which allowed me to build whole game models declaratively.

Some years ago I developed a formal FSM implementation in Javascript as a client side library or npm-hosted node package. I am currently making use of it in some multiplayer games, and the Automata code is still in good shape. The following are some features of the library:

Declarative definition

FSM must be defined declaratively. You must be able to declare the set of States and Transitions in a JSON object. The FSM definition must be unique and non instantiable. For example, there’s only one definition of the Dominoes game.
The FSM Model must allow for deep FSM nesting so that an State can spawn a whole new FSM. Think of a nested behavior, where a game table ‘playing’ state, is a whole ‘dominoes’ FSM.
Each stacked FSM will have its own FSM context, like a stack trace of States.

An example declaration could be:

context.registerFSM( {

    name    : "Test2",
    logic   : function() { 
        // convention function called when State 'a' exits.
        this.aExit = function(...) { ... };

        // convention function called when State 'b' enters.
        this.bEnter = function(...) { ... };
    },

    state  : [
        {
            name    : "a",
            initial : true,
            onTimer : {         // Timed transition.
                timeout: 4000,  // after 4 seconds.
                event: {
                    msgId: "ab" // if exits fire transition "ab".
                }
            }
        },
        {
            name    : "b"
        },
        {
            name    : "c"
        }
    ],

    transition : [
        {
            event       : "ab",
            from        : "a",
            to          : "b"
        },
        {
            event   : "bc",
            from    : "b",
            to      : "c"
        }
    ]
} );

Session

For each dominoes played game, a game Session is created. Sessions have common initial conditions and changes when Transitions are triggered. It exposes full lifecycle events for:

• context creation. Each time a new FSM is pushed to the session.
• context destruction. Each time a FSM pops.
• final state reached. Once the final state is reached, the Session is empty and not further interaction can happen on it.
• state changed. The CurrentState changes. It could auto-transition, which means the previous and Current States will be same
• custom event exposure. Whenever you want to notify an event to the external world.

This lifecycle allows for full FSM traceability and deterministic behavior. Whenever the ‘state changed’ callback is invoked, you can save the event that triggered this change. If all the events that fire a state change are saved sequentially, and later fed to a freshly created session, you’ll always get to the same results. If a user notifies of a bug and have previously saved a game ‘state change’ messages collection, magically you’ll get to the same bug. The FSM framework guarantees code traceability. Black Magic !!

As an implementation note, it is desirable the Session object to be serializable in JSON format. Saving and restoring the game session on-the-fly is definitely a feature you want to have near you.

Lifecycle

FSM elements will expose full lifecycle:

• enter State
• exit State
• transition fired
• pre and post guard events

These callback hooks will be invoked by the FSM engine to notify of the named events. The ‘transition fired’ event is normally the point to change the Session data. ‘Enter/exit State’ events are on average the points to manage the Session, like setting timers, ending the Session, initializing sub-State FSM, etc.

Timed transitions

Desirable is to have a per-state event scheduler. A very common use case is the following: A game must start in certain amount of time. When the FSM enters ‘start game’ state, a timer is triggered. If the FSM does not change state to ‘playing’ in (for example) 30 seconds, the CurrentState receives a transition event to ‘end game’ state automatically instead of keeping players locked in the game table forever.
Another thing to note, is that the server hosting the remote FSM will timeout in for example 1 minute, and the game clients in half the time. Legit clients will have a local timeout of 30 seconds to start the game, and request ‘go to the lobby’ otherwise. If an unfair client is connected to the FSM and does not send the ‘go to the lobby’ event, the server FSM will trigger it on its side anyway. So the game server is secure.

Guards

Transition guards are FSM Transition vetoes. They can either cancel the Transition event, or force the Event to be an auto-transition instead of a State change.

• pre transition guards. A pre-transition guard, nulls the Transition event as if it never happened. Though this is not defined in any FSM literature I’ve read about, I have found it to be invaluable useful under some circumstances, that’s why it’s been added to the framework.
• post transition guards (regular guards). This kind of guards will coerce the transition from State A to State B, to be an auto transition from State A, to State A. Being said a transition is fired, the sequence of actions: ExitA -> TransitionAB -> EnterA will be fired. The use case for this is a counting semaphore. For example, a game table is in state ‘waiting for players’, and needs 4 people to start. The FSM will only change to State ‘playing’ after there’s 4 people. The post-transition guard will make the Transition ‘wait for players’->’playing’ transition to fail until the counter is 4. Bonus points: The table can be waiting for players for one minute as much after each player enters. Whenever ‘wait for players’ State exits, a timer is canceled, and whenever the ‘wait for players’ State enters, the timer is set. The post-transition guard guarantees this behaviour since it fires the transition. Pre transition guard will inevitable fail for this scenario.

No dependencies

Automata is an standalone package. Has no dependencies and works on both the client and server sides.

FSM masking

Though not a FSM framework requirement, remote Session content masking is a must for multiplayer games. For security purposes, we don’t want to share the remote game Session content with each of the connected clients. For example in the Dominoes, we don’t want to share each players tiles with every connected user/player.
The masking will make sure only the necessary information per player will be shared with each of them.
This process is not integrated into the FSM framework, but all the tools are already there: There’s a session listener, and information will only be sent to the connected clients whenever a state change happens. So the rules for masking are not something inherent to the FSM itself, but some external rules to add on top of the reflected events happening at the core of the framework.

These are all the elements that for years have made the multiplayer space I’ve been working with secure, traceable and deterministic. Let me know about your own experiences.