State machine design pattern

Question

TLDR: Are there any known design pattern to represent a state machine configuration as code without the usage of goto statements?

What are the possible issues with refactoring:

{
   a: {
      title: 'Step A',
      onActionXGoTo: 'b',
      onActionYGoTo: 'c',
   },
   b: {
      title: 'Step B',
      onAnyActionGoTo: 'c',
   }
   c: {
      title: 'Step C',
      onActionXGoTo: 'a',
      onActionYGoTo: 'b',
   }
}

as something like the example below. Where buildGraph will return the object above

buildGraph((builder) => {
     builder.while(() => {
        if (builder.initial() {
            builder.setStep({ title: 'Step A'});
        } else {
           if (builder.isActionX()) {
              builder.setStep({ title: 'Step A'});
           }
           if (builder.isActionY()) {
              builder.setStep({ title: 'Step B'});
           }
        }
        
        if (builder.isActionX()) {
           builder.setStep({ title: 'Step B'});
           builder.setStep({ title: 'Step C'});
        }
        if (builder.isActionY()) {
           builder.setStep({ title: 'Step C'});
        }
    });
});

This use case might not make sense as it's harder to follow. However, we've got a state machine with hundreds of connections which is challenging to maintain.

1. Are there any design patterns that can help with that?
2. The spec for the state machine is given by UX/Product as goto statements. Converting goto statements to sequential code might now worth the effort because of increased complexity when implementing a new state machine. Am I missing something?
3. Are there any caveats with that type of sequential code to state machine conversion? On the surface it might appear as compiling code to custom machine code but I think the difference here is that it is a finite state machine not code.

Answer 1

IMHO, you should write your system to be data-driven and load the states+transitions from a configuration file.

I recently wrote a tutorial about using FSMs in gamedev, maybe you can find it useful: https://www.davideguida.com/blazor-gamedev-part-9-finite-state-machine/

The gist is quite simple: each state is in its own class, orchestrated by a generic FSM class that keeps track of the state of the entity.

Answer 2

The way I like to implement FSMs in C is to define the whole machine as a matrix. The rows of the matrix represent the states, while the columns represent events that cause transitions between states. So if there are M states and N events, the matrix has size M*N, although most of the individual cells probably represent invalid combinations of state and event. Each state, and each event, can be represented by an integer, or possibly an enum, with value 0...M-1 and 0...N-1 respectively. These numbers are simply indexes into the matrix. The matrix itself can be implemented in C (and probably in Java) as an M*N two-dimensional array. One of the states often indicates "finished". There will be a defined "start" state, which could usefully be state zero, but it doesn't have to be.

In C, the cells of the matrix (that is, entries in the array) can be function pointers. Each pointer is to a function that takes as its argument a pointer to some data structure representing the data model, and which returns an integer. The integer represents the new state of the system, after processing the event. There will be some specific return value (e.g., -1) that indicates an error condition. I put NULL pointers in cells that correspond to invalid combinations of state and event.

As each event arrives, the code looks up the cell in the matrix (array) that indicates the current state and the event. If it isn't a NULL (error), the code calls the function by its pointer. The function does whatever is appropriate for the particular state/event combination, and returns the new state. If it's an error value, or the value of the "finished" state, the machine stops.

I don't think this approach would work directly in Java, as it lacks function pointers. However, I imagine you could use function references or lambda functions to the same effect.

For small models, the matrix can be transformed into a simple, large, switch statement. In fact, this works for large models, too, but the code is hard to read (actually, I think any FSM implementation is hard to read when you get to hundreds of transitions). Each case of the switch is the sum of the current state multiplied by the width of the state array, plus the event. So, for example, if there are ten events in each row, there will be a case for each of the possible values of M*10 + N. These values are constants known at compile time, so they can be used as case values in a switch.

Of course, just as the array will usually have many NULL values indicating invalid events, many of the cases of the switch will do nothing but transition to the error state. I still write out each case, just for regularity -- there are always M*N cases in the switch.

In short, an M*N matrix of events and states, many of whose members are NULL, can be transformed to a switch with M*N cases, many of which do nothing but transition to the error state. The implementations are actually equivalent. Both are completely regular -- a fixed-size array or a fixed number of cases. Both allow new states or events to be added without (usually) creating a sprawling, unmaintainable mess. Both, of course, require high levels of self-discipline to implement in a readable way.

Answer 3

here's three state machine implementations. theoretically, each state processes an input and returns another state (unless it is a terminating state). technically, you have a value, branch to some address to perform some side effect, and set/return a value; you decide which one is best for your use case:

1. while/switch
2. state transition table
3. state pattern

the while/switch (or any branching construct)

simple and maintainable for small state machines. for large state machines, this gets out of hand fast and making changes is nontrivial

var states = {
    STATE_A: 1,
    STATE_B: 2,
    STATE_C: 3,
    STATE_ERR: 4,
};

var inputs = {
    ACTION_X: 1,
    ACTION_Y: 2,
};

var state = states.STATE_A;

while (1) {
    var action = getAction();
    
    switch (state) {
    case states.STATE_A:
        if (action === inputs.ACTION_X) {
            state = states.STATE_B;
        } else if (action === inputs.ACTION_Y) {
            state = states.STATE_C;
        } else {
            state = states.STATE_ERR;
        }
        break;

    case states.STATE_B:
        if (isAnyAction(action)) {
            state = states.STATE_C;
        }
        break;

    case states.STATE_C:
        if (action === inputs.ACTION_X) {
            state = states.STATE_A;
        } else if (action === inputs.ACTION_Y) {
            state = states.STATE_B;
        }
        break;

    case states.STATE_ERR:
        throw 'invalid';
        break;
    }
}

the state transition table

easy to change, scales well, locality of reference, bitmap-able, simple to generate. unfortunately, the state input handler is separate from the state itself and the size can get large

var states = {
    STATE_A: 0,
    STATE_B: 1,
    STATE_C: 2
};

var inputs = {
    ACTION_X: 0,
    ACTION_Y: 1,
};


var transitionTable = [
    // ACTION_X,     // ACTION_Y
    [states.STATE_B, states.STATE_C], // STATE_A
    [states.STATE_C, states.STATE_C], // STATE_B
    [states.STATE_A, states.STATE_B], // STATE_C
];

function transition(state, action) {
    return transitionTable[state][action];
}

var state = states.STATE_A; // starting state

while (1) {
    var action = getAction();

    state = transition(state, action);

    // do something for state
}

the state pattern

decentralized (unlike the table above), provides encapsulation, scales decently. pretty slow due to indirection needed to support polymorphism. loses locality of reference benefits

class StateA {
    handleAction(action) {
        if (action === inputs.ACTION_X) {
            return new StateB();
        } else if (action === inputs.ACTION_Y) {
            return new StateC();
        }
    }
}

class StateB {
    handleAction(action) {
        if (isAnyAction(action)) {
            return new StateC();
        }
    }
}

class StateC {
    handleAction(action) {
        if (action === inputs.ACTION_X) {
            return new StateA();
        } else if (action === inputs.ACTION_Y) {
            return new StateB();
        }
    }
}


var state = new StateA(); // starting state

while (1) {
    var action = getAction();

    state = state.handleAction(action);
}

none of these use goto (not like javascript has one) and each provide their own trade-offs