前言

状态机或叫有限状态机 ，缩写 FSM（Finite State Machine）

状态机会根据当前状态，执行某些事件，在这些事件中达到某些条件后，执行一个动作（或无动作），随后变化到新的状态，依次循环。


FSM 有以下特点

  • 状态有限且确定

  • 某一时刻只在一种状态中

  • 状态的转换有规律

  • 事件触发状态的转换，或事件中某条件下触发状态的转换


电梯例子

视频地址: https://www.bilibili.com/video/BV1vV411C7uk ，以电梯运行作为例子。

image-20210919163523204


枚举 状态 以及 动作(行为)

1
2
enum state_codes { _idle=0, _goingUp=1, _goingDown=2, _AtTop=3, _AtBottom=4,  _malfunction=5, _unexpected=6, _end=7 };
enum ret_codes   {   up=0,    down=1,      halt=2,   top=3,   bottom=4, fail=5, quit=6 };

为这 8 种状态分别设置对应的 8 个 事件 函数

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
int event_idle(void){
	// ...
}
int event_goingUp(void){
	// ...
}
int event_goingDown(void){
	// ...
}
int event_atTop(void){
  	// ...
}
int event_atBottom(void){
   	// ...
}

int event_malfunction(void){
	// ...
}
int event_unexpected(void){
	// ...
}
int event_end(void){
	// ...
}

// 定义指向一个函数的数组类型指针，无参数
int (* event[])(void) = { event_idle, event_goingUp, event_goingDown, event_atTop, event_atBottom, event_malfunction, event_unexpected, event_end };


一个二维数组，通过传入 当前状态 以及 动作(行为) ，得到对应的下一 状态

此状态在主函数中即可链接到相应 事件

1
2
3
4
5
6
7
8
9
10
11
12
int lookup_transitions[][7] = { 
                // return codes:
                //      up       down       halt          top         bottom         fail          quit
    [_idle]      = {_goingUp,    _goingDown,  _idle,     _unexpected, _unexpected,  _malfunction,  _end},
    [_goingUp]   = {_goingUp,    _unexpected, _idle,     _AtTop,      _AtBottom,    _malfunction,  _end},
    [_goingDown] = {_unexpected, _goingDown,  _idle,     _AtTop,      _AtBottom,    _malfunction,  _end},
    [_AtTop]     = {_unexpected, _goingDown,  _AtTop,    _unexpected, _unexpected,  _malfunction,  _end},
    [_AtBottom]  = {_goingUp,    _goingDown,  _AtBottom, _unexpected, _unexpected,  _malfunction,  _end},
    [_malfunction] = {_end, _end, _end, _end, _end, _end, _end},
    [_unexpected]  = {_end, _end, _end, _end, _end, _end, _end}
    /* transitions from end state aren't needed */
};

主函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define ENTRY_STATE _idle
#define END_STATE   _end

	
    enum state_codes cur_state = ENTRY_STATE; //初始化状态为空闲（_idle）
    enum ret_codes rc;
    int (* state_func)(void);
    printf("Start the elevator!\n");

    for (;;) {
        // 指针指向当前状态的函数
        state_func = event[cur_state];
        rc = state_func();
        
        // 如果函数返回的状态为 _end 则结束循环（结束程序）
        if (END_STATE == cur_state)
            break;
        
        // 通过当前状态和rc值，在 lookup_transitions 查询下一种状态并赋值
        cur_state = lookup_transitions[cur_state][rc];
    }

完整代码：

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
// Reference: 
// FSM: https://stackoverflow.com/questions/50165534/finite-state-machines-in-c
// C Enum: https://www.geeksforgeeks.org/enumeration-enum-c/

/* standard lib */
#include <stdio.h> // printf #include <stdbool.h> // bool for _Bool and true for 1
#include <conio.h> // for clrscr, and getch()
#include "stdlib.h" // for rand()
#include "math.h"

/* event array and enum below must be in sync! */
enum state_codes { _idle=0, _goingUp=1, _goingDown=2, _AtTop=3, _AtBottom=4,  _malfunction=5, _unexpected=6, _end=7 };
enum ret_codes   {   up=0,    down=1,      halt=2,   top=3,   bottom=4, fail=5, quit=6 };

enum state_codes x = _idle;

int target_floor_number = 8;
int current_floor_number = 1;
int accumulated_floor_number = 0;
#define TOP_FLOOR 9
#define BOTTOM_FLOOR 1

int event_idle(void){
    printf("Idle!\n");
    printf("Input target floor number in [1, 9] (which floor you want to go?): \n");
    target_floor_number = getch() - '0';

    if(current_floor_number < target_floor_number)
        return up;
    else if(current_floor_number > target_floor_number)
        return down;
    else if(current_floor_number == target_floor_number)
        return halt;
}
int event_goingUp(void){
    current_floor_number += 1;
    accumulated_floor_number += 1;
    printf("Going up! Floor number is %d\n", current_floor_number);

    if(accumulated_floor_number > 100)
        return fail;
    else if(TOP_FLOOR == current_floor_number)
        return top;
    else if(BOTTOM_FLOOR == current_floor_number)
        return bottom;
    else if(current_floor_number < target_floor_number)
        return up;
    else if(current_floor_number == target_floor_number)
        return halt;
    else
        return quit;
}
int event_goingDown(void){
    current_floor_number -= 1;
    accumulated_floor_number += 1;
    printf("Going down! Floor number is %d\n", current_floor_number);

    if(accumulated_floor_number > 100)
        return fail;
    else if(TOP_FLOOR == current_floor_number)
        return top;
    else if(BOTTOM_FLOOR == current_floor_number)
        return bottom;
    else if(current_floor_number > target_floor_number)
        return down;
    else if(current_floor_number == target_floor_number)
        return halt;
    else
        return quit;
}
int event_atTop(void){
    printf("At top! current_floor_number= %d\n", current_floor_number);
    printf("Input target floor number in [1, 9] (which floor you want to go?): \n");
    target_floor_number = getch() - '0';

    if(current_floor_number > target_floor_number)
        return down;
    else if(current_floor_number == target_floor_number)
        return halt;
}
int event_atBottom(void){
    printf("At Bottom! current_floor_number= %d\n", current_floor_number);
    printf("Input target floor number in [1, 9] (which floor you want to go?): \n");
    target_floor_number = getch() - '0';

    if(current_floor_number < target_floor_number)
        return up;
    else if(current_floor_number == target_floor_number)
        return halt;}

int event_malfunction(void){
    printf("Elevator needs maintanence!\n");
    printf("accumulated_floor_number = %d\n", accumulated_floor_number);
    return quit;
}
int event_end(void){
    printf("Exit!");
    return 0;
}
int event_unexpected(void){
    printf("Debug.");
    return quit;
}


int (* event[])(void) = { event_idle, event_goingUp, event_goingDown, event_atTop, event_atBottom, event_malfunction, event_unexpected, event_end };

// Nice, thanks for this. The only thing possible flaw here is that the lookup_transitions will likely be linear (O(n)) with this transition table datastructure. Its possible to make it better with multidimentional array - guaranteed O(1). Eg. the table can be represented as a multidimentional array where key is state and the value is an array where the key is the return code and value is the next state: int state_transitions[][3] = { [entry] = { foo, end, foo }, ... } /* ok, fail, repeat */    
int lookup_transitions[][7] = { 
                // return codes:
                //      up       down       halt          top         bottom         fail          quit
    [_idle]      = {_goingUp,    _goingDown,  _idle,     _unexpected, _unexpected,  _malfunction,  _end},
    [_goingUp]   = {_goingUp,    _unexpected, _idle,     _AtTop,      _AtBottom,    _malfunction,  _end},
    [_goingDown] = {_unexpected, _goingDown,  _idle,     _AtTop,      _AtBottom,    _malfunction,  _end},
    [_AtTop]     = {_unexpected, _goingDown,  _AtTop,    _unexpected, _unexpected,  _malfunction,  _end},
    [_AtBottom]  = {_goingUp,    _goingDown,  _AtBottom, _unexpected, _unexpected,  _malfunction,  _end},
    [_malfunction] = {_end, _end, _end, _end, _end, _end, _end},
    [_unexpected]  = {_end, _end, _end, _end, _end, _end, _end}
    /* transitions from end state aren't needed */
};

#define ENTRY_STATE _idle
#define END_STATE   _end

int main(){
    
    enum state_codes cur_state = ENTRY_STATE;
    enum ret_codes rc;
    int (* state_func)(void);
    printf("Start the elevator!\n");

    for (;;) {
        state_func = event[cur_state];
        rc = state_func();
        if (END_STATE == cur_state)
            break;
        cur_state = lookup_transitions[cur_state][rc];
    }
    printf("END.");
    getch();
    getch();
    getch();
    return 0;
}