FSM有限状态机其三

发表于 更新于

我们在上篇博客中通过提取状态转移这个步骤为函数，实现了状态进入/退出动作的自动执行，在这篇博客中，我们将加入层次状态这个内容

顺带一提，这个层次状态真是看的我头痛，因为C语言并不是一门面向对象语言，所以我们在这里发生了一些并不令人愉快的抽象泄露

一、父状态的实现机制拆解

1. 数据结构的基石：parent_state 数组

1
State parent_state[STATE_COUNT];

初始化：

1
2
3
4
fsm->parent_state[STATE_IDLE]    = -1;          // 根状态
fsm->parent_state[STATE_ACTIVE]  = -1;          // 容器状态，本身无父
fsm->parent_state[STATE_PLAYING] = STATE_ACTIVE;
fsm->parent_state[STATE_PAUSED]  = STATE_ACTIVE;

这个数组构建了一棵单父树，每个状态最多有一个直接父状态。-1 表示该状态是顶层节点。

2. 事件冒泡：从子到父的查找链

1
2
3
4
5
6
7
8
9
10
void fsm_dispatch(StateMachine *fsm, Event evt) {
    State current = fsm->current_state;
    while (current != -1) {
        fsm->state_table[current](fsm, evt);   // 尝试让当前状态处理
        if (fsm->current_state != current) {    // 状态变了？
            break;   // 事件被处理，停止冒泡
        }
        current = fsm->parent_state[current];   // 未处理，向父状态回溯
    }
}

核心逻辑：

  • 事件首先交给叶子状态（如 Playing）处理。
  • 如果该状态函数不改变 current_state（即忽略事件），则循环继续，将 current 更新为其父状态（Active）。
  • 父状态的处理函数被调用，若它执行了转移（改变了 current_state），循环终止。
  • 若一直回溯到 -1 仍无状态处理，事件被丢弃。

这相当于在运行时动态查找当前状态下针对该事件的有效转移，优先子状态，后父状态。

3. 转移时的层次进入/退出顺序

版本3中采用了硬编码判断，因为已知层次结构只有一层：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
static void fsm_transition_to(StateMachine *fsm, State target) {
    if (fsm->current_state == target) {
        return;
    }
    // 1. 找出从当前状态到目标状态需要退出的状态路径
    //    原理：从当前叶子向上找父状态，直到找到与目标状态的公共祖先。
    //    为简化，本例硬编码处理，完整通用算法将在博客中说明。
    State old = fsm->current_state;
    State new = target;
    printf("[Transition] %d -> %d\n", old, new);
    // ---------- 执行退出动作（自底向上） ----------
    // 退出当前叶子
    if (fsm->exit_actions[old])
        fsm->exit_actions[old]();
    // 如果当前叶子有父状态且与目标的祖先不同，则继续退出父状态
    if ((old == STATE_PLAYING || old == STATE_PAUSED) && (new == STATE_IDLE)) {
        if (fsm->exit_actions[STATE_ACTIVE])
            fsm->exit_actions[STATE_ACTIVE]();
    }
    // ---------- 更新当前状态 ----------
    fsm->current_state = new;

    if ((new == STATE_PLAYING || new == STATE_PAUSED) &&
        (old != STATE_PLAYING && old != STATE_PAUSED)) {
        if (fsm->entry_actions[STATE_ACTIVE])
            fsm->entry_actions[STATE_ACTIVE]();
    }
    if (fsm->entry_actions[target]) {
        fsm->entry_actions[target]();
    }
}

设计思想：

  • 利用 parent_state 的隐含知识：Playing 和 Paused 同属一个父状态 Active。
  • 通过判断目标状态是否在 Active 的“子状态集合”内，来决定是否执行父状态的进入/退出动作。
  • 顺序上：先处理子状态自己的退出动作，再判断是否需要退出父状态；进入时相反。

二、为什么要这么实现？

1. 为什么不用嵌套 switch-case？

嵌套 switch 的层次实现：

1
2
3
4
5
6
switch (current_state) {
    case STATE_PLAYING:
    case STATE_PAUSED:
        // 共享代码？
        break;
}
  • 无法优雅地复用进入/退出动作（Active 的 entry/exit 需要在每个子状态转移时手动插入）。
  • 事件处理代码会急剧膨胀，难以维护。

2. 为什么不用函数递归模拟继承？

递归方案（每个状态函数返回一个布尔值表示是否处理）确实更“优雅”，但：

  • 每次事件都需要多层函数调用，在资源紧张的MCU上可能造成栈溢出。
  • 状态处理函数需要额外返回值，接口复杂化。

3. 为什么使用 parent_state 数组 + 循环？

  • 内存效率：每个状态只需一个字节（或枚举大小）的存储。
  • 速度：while 循环比递归调用开销小，且无栈风险。
  • 确定性：适合硬实时系统，行为完全可预测。

三、更好的实现方案？

方案A：状态嵌套结构体（显式层次）

1
2
3
4
5
6
7
8
9
10
11
typedef struct State {
    StateID id;
    struct State *parent;          // 指向父状态
    void (*entry)(void);
    void (*exit)(void);
    void (*handle)(struct State *self, Event e);
} State;

State active = { .parent = NULL, ... };
State playing = { .parent = &active, ... };
State paused  = { .parent = &active, ... };

优点：层次关系通过指针直接可见，parent 指针就是天然的冒泡路径。
缺点：占用内存更大（每个状态需存储多个指针），且需额外处理状态ID到结构体指针的映射。

这个其实就是之前提到过的面向对象模拟法

方案B：状态处理函数返回处理标志

1
2
3
4
5
6
7
8
9
10
11
typedef bool (*StateHandler)(StateMachine *fsm, Event evt);

void fsm_dispatch(StateMachine *fsm, Event evt) {
    State current = fsm->current_state;
    while (current != -1) {
        if (fsm->state_table[current](fsm, evt)) {
            break;   // 返回 true 表示事件已处理
        }
        current = fsm->parent_state[current];
    }
}

优点：语义清晰，不需要通过检查 current_state 是否改变来判断处理与否。
缺点：状态函数必须返回布尔值，且如果转移发生在更深层调用的函数中，返回值传递会复杂化。

这个其实会更直观

方案C：真正的LCA算法（通用层次引擎）

1
2
3
4
5
6
7
8
9
10
11
// 伪代码
void transition_to(StateMachine *fsm, State target) {
    // 1. 计算LCA（最小公共祖先）
    State lca = find_lca(fsm->current_state, target);
    // 2. 从当前状态退出到LCA（自底向上）
    exit_to_lca(fsm->current_state, lca);
    // 3. 从LCA进入目标状态（自顶向下）
    enter_from_lca(lca, target);
    // 4. 更新当前状态
    fsm->current_state = target;
}

这是完全符合UML规范的实现，可以处理任意深度的嵌套、正交区域等。但需要：

  • 为每个状态存储完整的祖先路径，或维护状态深度和父链。
  • 复杂的路径比较算法。

QP/C框架就是采用这种方案，其核心引擎约800行C代码。

或许在遥远的未来，我会去研究这个QP/C(最好是)

方案D：状态表 + 编译期层次展开（宏魔法）

利用X宏或C预处理器技巧，在编译期生成扁平的状态转移表，同时将层次语义转换为索引计算。例如：

1
2
3
4
5
#define STATES \
    X(IDLE)    \
    X(ACTIVE)  \
    X(PLAYING, ACTIVE) \
    X(PAUSED, ACTIVE)

通过宏生成 parent_state 数组和转移表。这种方法在大型项目中能减少手动维护错误，但代码可读性下降。

可读性真的下降的很多了

这里插一嘴关于这个宏方法的实现

1
2
3
4
5
6
7
8
9
10
// states.def —— 状态定义文件（无头文件保护，可被多次包含）

// 格式：X(状态枚举名, 父状态枚举名或-1, 进入动作函数名, 退出动作函数名)
// 父状态为 -1 表示顶层状态

X(STATE_IDLE,    -1,            entry_idle,    NULL)
X(STATE_ACTIVE,  -1,            entry_active,  exit_active)
X(STATE_PLAYING, STATE_ACTIVE,  entry_playing, exit_playing)
X(STATE_PAUSED,  STATE_ACTIVE,  entry_paused,  exit_paused)
X(STATE_MENU,    -1,            entry_menu,    exit_menu)

基本上来说就是一个X宏，记录了多种元素，在需要的地方用不同的宏进行二次展开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
typedef struct {
    State current_state;
    
    // 指向外部生成的静态表
    const State *parent_state; 
    void (*const *entry_actions)(void); 
    void (*const *exit_actions)(void);
    
    // ... 其他成员
} StateMachine;

// 1. 生成状态枚举
typedef enum {
#define X(name, parent, entry_func, exit_func) name,
#include "states.def"
#undef X
    STATE_COUNT
} State;

// 2. 生成父状态数组
static const State parent_state[STATE_COUNT] = {
#define X(name, parent, entry_func, exit_func) parent,
#include "states.def"
#undef X
};

// 3. 生成进入动作函数指针表
static void (*const entry_actions[STATE_COUNT])(void) = {
#define X(name, parent, entry_func, exit_func) entry_func,
#include "states.def"
#undef X
};

// 4. 生成退出动作函数指针表
static void (*const exit_actions[STATE_COUNT])(void) = {
#define X(name, parent, entry_func, exit_func) exit_func,
#include "states.def"
#undef X
};

// 5. 生成状态名称字符串表（便于调试）
static const char *state_names[STATE_COUNT] = {
#define X(name, parent, entry_func, exit_func) #name,
#include "states.def"
#undef X
};

void fsm_init(StateMachine *fsm) {
    fsm->current_state = STATE_IDLE;
    fsm->history_active = -1;
    // 将生成的静态表赋值给状态机实例
    fsm->parent_state  = parent_state;
    fsm->entry_actions = entry_actions;
    fsm->exit_actions  = exit_actions;
    fsm->state_table   = state_table;

    // 执行初始状态进入动作
    if (fsm->entry_actions[fsm->current_state]) {
        fsm->entry_actions[fsm->current_state]();
    }
}

当然，在这种将状态机成员置于全局数据段的写法下，我们在结构体内部很明显更适合存储指针而不是完整的数组成员

当前方案采用树形结构的扁平化存储，通过维护一个 parent_state 数组，显式记录每个状态节点的父节点索引。

数组中元素取值规则为：

  • 若值为 -1，表示该状态为根节点，无父节点；
  • 若为非 -1 数值，则该数值直接对应其父节点的索引，以此建立节点间的层级关联。

整体思路是用线性数组结构模拟树形层级关系，通过索引映射替代显式的树形指针或嵌套结构。