状态机设计模式

Question

简述：有没有已知的设计模式可以将状态机配置表示为代码，而不使用goto语句？

重构可能存在的问题：

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

如下示例所示。其中buildGraph将返回上述对象

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'});
        }
    });
});

这个用例可能不太合理，因为它更难跟踪。但是，我们有一个状态机，其中有数百个连接，很难维护。

1. 是否有任何设计模式可以帮助解决这个问题？
2. UX/产品给出的状态机规范采用了goto语句。将goto语句转换为顺序代码可能并不值得，因为在实现新状态机时会增加复杂性。我是否忽略了其他方面？
3. 将这种类型的顺序代码转换成状态机是否有任何注意事项？表面上看起来可能像是将代码编译成自定义的机器码，但我认为这里的区别在于它是有限状态机而不是代码。

- Kirill Kulakov

---

我们总是使用GoF中的状态模式来实现状态机。在这里看一下：https://refactoring.guru/design-patterns/state - Mohammad

你有没有考虑过使用宏（例如Lisp宏）？它与你的代码有点相似，但你可以用状态来描述，让宏将你的状态转换为所需的代码。很抱歉我不能给你更多信息，因为我自己也在学习中。 - TheChetan

Answer 1

这里有三种状态机实现。理论上，每个状态处理一个输入，并返回另一个状态（除非它是终止状态）。在技术上，您有一个值，跳转到某个地址以执行一些副作用，并设置/返回一个值；您可以决定哪个对于您的用例最佳：

1. while/switch
2. 状态转换表
3. 状态模式

while/switch（或任何分支结构）

适用于小型状态机，简单且易于维护。但对于大型状态机，这很快就会变得难以掌控，而且更改也不容易。

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;
    }
}

状态转移表

易于修改，可很好地扩展，具有参考局部性，可以使用位图技术，易于生成。不幸的是，状态输入处理程序与状态本身分开，且大小可能会变大。

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
}

状态模式

分散的（不像上面的表格），提供了封装，具有相当的可扩展性。由于需要间接引用以支持多态性，因此相当慢。失去了局部性参考的好处。

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);
}

这些语言都没有使用goto（不像JavaScript有一个），每种语言都有自己的权衡取舍。

- Rafael

Answer 2

我喜欢在C语言中实现有限状态机(FSM)的方式是将整个机器定义为一个矩阵。矩阵的行表示状态，而列表示导致状态转换的事件。因此，如果有M个状态和N个事件，则矩阵的大小为M*N，尽管大多数单元格可能表示状态和事件的无效组合。每个状态和每个事件都可以用一个整数或可能是一个枚举来表示，值为0... M-1和0... N-1。这些数字只是矩阵中的索引。矩阵本身可以在C语言（以及可能Java语言）中作为M*N的二维数组来实现。其中一个状态通常表示"完成"。将定义一个"开始"状态，有用的状态零，但它不一定是。

在C语言中，矩阵的单元格(即数组条目)可以是函数指针。每个指针指向一个函数，该函数以代表数据模型的某个数据结构的指针作为其参数，并返回一个整数。该整数表示处理事件后系统的新状态。将使用特定的返回值(例如-1)来表示错误条件。我将NULL指针放入对应于状态和事件的无效组合的单元格中。

当每个事件到达时，代码会查找矩阵(数组)中指示当前状态和事件的单元格。如果它不是NULL(错误)，代码将按其指针调用该函数。该函数对于特定的状态/事件组合执行适当的操作，并返回新状态。如果它是一个错误值或"完成"状态的值，机器将停止。

我不认为这种方法可以直接在Java语言中使用，因为它缺少函数指针。然而，我想你可以使用函数引用或lambda函数来达到相同的效果。

对于小模型，矩阵可以转换为一个简单的大switch语句。实际上，这也适用于大模型，但代码很难读取(事实上，我认为任何FSM实现在涉及数百个转换时都很难读取)。switch的每个case是当前状态乘以状态数组的宽度，加上事件的和。例如，如果每行有十个事件，则对于M*10+N的每个可能值，都会有一个case。这些值是在编译时已知的常量，因此可以将它们用作switch的case值。

当然，就像数组通常具有许多NULL值表示无效事件一样，switch的许多情况只会转换到错误状态。我仍然写出每种情况，只是为了保持一致性——switch中总是有M*N种情况。

简而言之，一个M*N的事件和状态矩阵，其中许多成员为空，可以转换为具有M*N个case的开关，其中许多case什么都不做，只是转换到错误状态。这些实现实际上是等效的。两者都是完全规则的——固定大小的数组或固定数量的case。两者都允许添加新的状态或事件，而不会创建庞大且难以维护的混乱代码。当然，要以可读的方式实现这些，需要高度的自律性。

- Kevin Boone

Answer 3

在我看来，你应该编写数据驱动的系统，并从配置文件中加载状态和转换。

最近我写了一篇关于在游戏开发中使用FSM的教程，也许你会觉得有用：https://www.davideguida.com/blazor-gamedev-part-9-finite-state-machine/

要点很简单：每个状态都在自己的类中，由一个通用的FSM类协调实体的状态。

- David Guida

---

尝试在答案中包含所有所需资源，而不是链接到外部资源，因为链接可能因任何原因而失效。 - Gustavo Kawamoto

你说得对。实际上，真正的答案是使系统数据驱动，链接只是一个参考。我已经更新了文本，希望现在更清晰了。 - David Guida