状态机教程

Question

我想知道在互联网上是否有人知道一些开发状态机的好教程。还是电子书？

我开始在状态机上工作，只是需要一些通用的东西来开始。

Answer 1

如果你使用函数指针，状态机在C中是非常简单的。

基本上你需要两个数组-一个用于状态函数指针，一个用于状态转换规则。每个状态函数返回代码，您逐个状态查找状态转换表，并返回代码以找到下一个状态，然后执行它。

int entry_state(void);
int foo_state(void);
int bar_state(void);
int exit_state(void);

/* array and enum below must be in sync! */
int (* state[])(void) = { entry_state, foo_state, bar_state, exit_state};
enum state_codes { entry, foo, bar, end};

enum ret_codes { ok, fail, repeat};
struct transition {
    enum state_codes src_state;
    enum ret_codes   ret_code;
    enum state_codes dst_state;
};
/* transitions from end state aren't needed */
struct transition state_transitions[] = {
    {entry, ok,     foo},
    {entry, fail,   end},
    {foo,   ok,     bar},
    {foo,   fail,   end},
    {foo,   repeat, foo},
    {bar,   ok,     end},
    {bar,   fail,   end},
    {bar,   repeat, foo}};

#define EXIT_STATE end
#define ENTRY_STATE entry

int main(int argc, char *argv[]) {
    enum state_codes cur_state = ENTRY_STATE;
    enum ret_codes rc;
    int (* state_fun)(void);

    for (;;) {
        state_fun = state[cur_state];
        rc = state_fun();
        if (EXIT_STATE == cur_state)
            break;
        cur_state = lookup_transitions(cur_state, rc);
    }

    return EXIT_SUCCESS;
}

我没有把lookup_transitions()函数放在那里，因为它很琐碎。

这就是我多年来处理状态机的方式。

Answer 2

与庞大的switch语句相比，我更喜欢使用函数指针，但与qrdl's answer相比，我通常不使用显式的返回码或转换表。

此外，在大多数情况下，您需要一种机制来传递额外的数据。下面是一个状态机示例：

#include <stdio.h>

struct state;
typedef void state_fn(struct state *);

struct state
{
    state_fn * next;
    int i; // data
};

state_fn foo, bar;

void foo(struct state * state)
{
    printf("%s %i\n", __func__, ++state->i);
    state->next = bar;
}

void bar(struct state * state)
{
    printf("%s %i\n", __func__, ++state->i);
    state->next = state->i < 10 ? foo : 0;
}

int main(void)
{
    struct state state = { foo, 0 };
    while(state.next) state.next(&state);
}

Answer 3

不幸的是，大多数关于状态机的文章都是为C++或其他直接支持多态性的语言编写的，因为将有限状态机实现中的状态建模为从抽象状态类派生的类非常好。

但是，使用switch语句将事件分派到状态(对于简单的FSM，它们几乎都是直接编码的)，或者使用表将事件映射到状态转换，在C中实现状态机是相当容易的。

这里有几篇关于用C编写的状态机基本框架的简单但很不错的文章：

• http://www.gedan.net/2008/09/08/finite-state-machine-matrix-style-c-implementation/
• http://www.gedan.net/2009/03/18/finite-state-machine-matrix-style-c-implementation-function-pointers-addon/

编辑：网站“维护中”，web档案链接：

• http://web.archive.org/web/20160517005245/http://www.gedan.net/2008/09/08/finite-state-machine-matrix-style-c-implementation
• http://web.archive.org/web/20160808120758/http://www.gedan.net/2009/03/18/finite-state-machine-matrix-style-c-implementation-function-pointers-addon/

基于有限状态机的状态机通常使用一组宏来“隐藏”if/then/else语句的机制(或者使用一组switch语句而不是switch)，并创建一种相当于“switch语言”的语言来描述C源代码中的状态机。我个人更喜欢基于表的方法，但这些方法肯定有优点，被广泛使用，特别是对于更简单的FSM。

Steve Rabin在"Game Programming Gems" Chapter 3.0 (Designing a General Robust AI Engine)中概述了一个这样的框架。

这里讨论了一组类似的宏：

• https://contrarymotion.net/2008/02/12/some-code-snippets-for-a-simple-c-state-machine/

如果您对C++状态机实现也感兴趣，还可以找到更多。如果你感兴趣，我会给你一些提示。