通用Mealy状态机 + 计帧 + 恢复历史状态
2021/9/18 23:07:08
本文主要是介绍通用Mealy状态机 + 计帧 + 恢复历史状态，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
前言
明明这学期很紧张，但是没课选——限制某个类型只能选一两门，开的课程又少，学术讲座也不知道哪里通知。只能做做自己的事，从枯燥的生活中汲取一点成就感了。好几个月没敲代码了，我腱鞘炎快好了吧！可惜很快又要变差了！骑山地车远行的计划失败了，就骑了一天，顶着36度的太阳在主道与公路与林间小路与田间小路与城市小路里狂奔了一百公里，高德地图还给我导错路了！仅仅依靠激情还是不行的啊，如果我计划做的完善，或者有人陪着一起，事情会简单一些！
Mealy状态机
状态机每个状态有N条线到别的状态，有M条线到当前状态，Mealy型状态机中状态之间的
转换都依靠输入，输入事件也有W个。
状态机需要的信息
- N个状态
- M条线
每条线的信息：当前状态，事件，下一个状态，动作，其他信息
- W个事件
动态数组
状态之间的线就是转换规则。
状态ID可以设置为0~状态数-1。
事件ID可以设置为0~事件数-1。
但是，规则的信息比较多，放入结构体。规则的指针都存入动态数组，这样好节省空
间！！！
动态数组数据结构
#define bol uint8_t
#define true 1
#define false 0
#define unint size_t
/*动态数组*/
struct dynamic_array {
void** arr; //指针数组，每个元素都是指针
unint size; //动态数组中当前元素个数
unint capacity; //动态数组当前容量
};
动态数组方法实现
/*
effect: 创建一个初始化了的动态数据对象
output: 动态数组指针
*/
struct dynamic_array*
da_create() {
struct dynamic_array* da = (struct dynamic_array*)malloc(sizeof(struct dynamic_array));
if (da == NULL) {
printf("[da_create] allocation of dynamic array has failed\n");
return NULL;
}
da->capacity = 4;
da->size = 0;
da->arr = (void**)malloc(sizeof(void*) * da->capacity);
return da;
}
/*
effect: 为动态数组添加元素，动态数组的长度就是size，使用0~size-1的元素
input : _da动态数组指针
_data数据指针
*/
void
da_push(struct dynamic_array* _da, void* _data) {
/*安全检查*/
if (_da == NULL) {
printf("[da_push] dynamic array is null\n");
return;
}
//空间不够,已经满了，需要扩大内存
if (_da->capacity == _da->size) {
//前期增速为2倍，后期为1.5倍
unint temp = (unint)(_da->capacity <= 128 ? (_da->capacity * 2) : (_da->capacity * 1.5));
//申请一块更大的空间
void** new_space = (void**)malloc(sizeof(void*) * temp);
//检查空间是否分配成功
if (new_space == NULL) {
printf("[da_push] allocation of new space has failed\n");
return;
}
//成功
_da->capacity = temp;
//拷贝数据到新空间上
memcpy(new_space, _da->arr, _da->capacity * sizeof(void*));
//释放旧空间内存
free(_da->arr);
//更新空间
_da->arr = new_space;
}
//添加新元素
_da->arr[_da->size++] = _data;
}
/*
effect: 删除最后一个元素并返回
input : _da动态数组指针
output: 最后一个元素的指针
*/
void*
da_pop(struct dynamic_array* _da) {
/*安全检查*/
if (_da == NULL) {
printf("[da_pop] dynamic array is null\n");
return NULL;
}
if (_da->size == 0) {
printf("[da_pop] size of dynamic array is zero\n");
return NULL;
}
return _da->arr[--_da->size];
}
/*
effect: 根据位置查找元素
input : _da动态数组指针
_position元素指针的位置
output: _position位置的元素的指针
*/
void*
da_at(const struct dynamic_array* _da, unint _position) {
/*安全检查*/
if (_da == NULL) {
printf("[da_at] dynamic array is null\n");
return NULL;
}
if (_position >= _da->size) {
printf("[da_at] position is illegal\n");
return NULL;
}
return _da->arr[_position];
}
/*
effect: 根据值查找元素
input : _da动态数组指针
_judge返回元素指针内数据是否是需要的自定义函数
output: _judge函数返回true对应的元素的指针
*/
void*
da_find(const struct dynamic_array* _da, bol(*_judge)(void*)) {
/*安全检查*/
if (_da == NULL) {
printf("[da_find] dynamic array is null\n");
return NULL;
}
for (unint i = 0;i<_da->size;++i) {
if (_judge(_da->arr[i]) == true) return _da->arr[i];
}
printf("[da_find] can not find the expected data\n");
return NULL;
}
/*
effect: 打印动态数组元素的数据
input : _da动态数组指针
_print打印元素指针内数据的自定义函数
*/
void
da_print(const struct dynamic_array* _da, void(*_print)(void*)) {
/*安全检查*/
if (_da == NULL) {
printf("[da_print] dynamic array is null\n");
return ;
}
printf("array print procedure begin>\n");
for (unint i = 0;i < _da->size; ++i) {
printf("[%5d]",i);
_print(_da->arr[i]);
printf("\n");
}
printf("array print procedure ended!\n");
}
/*
effect: 根据位置删除元素
input : _da动态数组指针
_position需要删除的元素的位置
*/
void
da_del(struct dynamic_array* _da, unint _position) {
/*安全检查*/
if (_da == NULL) {
printf("[da_del] dynamic array is null\n");
return ;
}
if (_position >= _da->size) {
printf("[da_del] position is illegal\n");
return;
}
if (_da->size == 0) {
printf("[da_remove] dynamic array is empty\n");
return;
}
//把后面的元素前移一个
for (unint i = _position;i < _da->size - 1; ++i) {
_da->arr[i] = _da->arr[i + 1];
}
--_da->size;
}
/*
effect: 根据值删除元素
input : _da动态数组指针
_judge返回元素指针内数据是否是需要删除的自定义函数
*/
void
da_remove(struct dynamic_array* _da, bol(*_judge)(void*)) {
/*安全检查*/
if (_da == NULL) {
printf("[da_remove] dynamic array is null\n");
return;
}
if (_da->size == 0) {
printf("[da_remove] dynamic array is empty\n");
return;
}
da_remove_recursion(_da, _judge,0);
}
/*
effect: 根据值删除元素的递归删除函数
input : _da动态数组指针
_judge返回元素指针内数据是否是需要删除的自定义函数
_start递归函数内，遍历开始的位置
*/
static void
da_remove_recursion(struct dynamic_array* _da, bol(*_judge)(void*), unint _start) {
if (_da->size == 0) {
printf("[da_remove_recursion] dynamic array is empty\n");
return;
}
//开始位置的检查
if (_start >= _da->size) {
printf("[da_remove_recursion] start in the illegal position\n");
return;
}
for (unint i = _start;i<_da->size; ++i) {
if (_judge(_da->arr[i]) == true) {
da_del(_da, i);
//不是最后一个元素，继续递归
if (i < _da->size) {
da_remove_recursion(_da,_judge, i);
}
break;
}
}
}
/*
effect: 清空动态数组中的元素，保留动态数组内存
input : _da动态数组指针
*/
void
da_clear(struct dynamic_array* _da) {
/*安全检查*/
if (_da == NULL) {
printf("[da_clear] dynamic array is null\n");
return;
}
_da->size = 0;// ###%%%%%% 再添加新的元素指针，就覆盖了之前的指针
}
/*
effect: 释放动态数组内存，置空_da,注意：并不是否元素内存
input : _da动态数组指针
*/
void
da_free(struct dynamic_array* _da) {
/*安全检查*/
if (_da == NULL) {
printf("[da_free] dynamic array is null\n");
return;
}
if (_da->arr != NULL) free(_da->arr);
_da->capacity = 0;
_da->size = 0;
_da = NULL;
free(_da);
}
动态数组测试
struct test_data {
char c;
};
void test_print(void* _data) {
struct test_data* d = (struct test_data*)_data;
printf("%c", d->c);
}
bol test_judge(void* _data) {
struct test_data* d = (struct test_data*)_data;
return d->c == 'q' ? true : false;
}
void test_dynamic_aay() {
struct dynamic_array* a = da_create();
struct test_data a0, a1, a2, a3, a4;
a0.c = 'w';
a1.c = 'Z';
a2.c = 'Z';
a3.c = 'q';
a4.c = 'Z';
da_push(a, &a0);
da_push(a, &a1);
da_push(a, &a2);
da_push(a, &a3);
da_push(a, &a4);
printf("size = %d\n", a->size);
da_print(a, test_print);
//da_remove(a, test_judge);
//struct test_data* after = da_pop(a);
//printf("after = %c\n", after->c);
//after = da_pop(a);
//printf("after = %c\n", after->c);
//after = da_pop(a);
//printf("after = %c\n", after->c);
//after = da_pop(a);
//printf("after = %c\n", after->c);
//after = da_pop(a);
//printf("after = %c\n", after->c);
//after = da_pop(a);
printf("after = %c\n", after->c);
/*struct test_data* v = da_at(a, 0);
printf("v = %c\n", v->c);
v = da_find(a, test_judge);
printf("v = %c\n", v->c);*/
da_clear(a);
da_push(a, &a4);
da_push(a, &a0);
printf("size = %lu\n", a->size);
da_print(a, test_print);
}
测试结果
状态机
状态机数据结构
#define state_machine_history_depth 20 //状态历史记录
/*
事件到来后进入转换规则，
找到当前状态和符合的事件，更新状态机的“当前状态”，
执行动作。
*/
/*状态机规则XN */
struct state_machine_rule {
unint cur_state; //当前状态
unint event; //从当前状态跳到下一个状态的事件
unint next_state; //下一个状态
void (*action)(unint _event); //状态转换到下一个状态后的动作
/*额外信息*/
void* note; //纪录每个状态的某个信息
};
/*状态机X1 */
struct state_machine {
/*定义*/
unint num_of_state; //状态数，状态ID为0~状态数-1
unint num_of_event; //事件数，事件ID为0~事件数-1
/*关键*/
unint cur_state; //当前状态
struct dynamic_array* rules; //规则的规则数组
/*额外功能*/
unint timer; //计时器，当前状态持续的时间片数或(step)帧数
bol isbegin; //是否是开始状态,非零为true,零为false
unint stack[state_machine_history_depth]; //历史状态记录
unint stack_pointer; //头部为栈底，stack_pointer是栈顶上一个，元素个数为stack_pointer
指向当前状态，当前状态不保存在栈里
};
状态机方法实现
/*
effect: 创建初始化了的状态机指针
output: 状态机指针
*/
struct state_machine*
sm_create() {
struct state_machine* sm = (struct state_machine*)malloc(sizeof(struct state_machine));
if (sm == NULL) {
printf("[sm_create] allocation of state machine has failed\n");
return NULL;
}
/*实际初始化交给用户*/
sm->num_of_event = 0;
sm->num_of_state = 0;
sm->cur_state = 0;
sm->isbegin = true; //遇到第二个事件之前，都是开始状态（即第二个状态，因为第一个状态是无动作的）
sm->stack_pointer = 0; //无元素
sm->timer = 0; //计时器，从状态更新——即动作之前——开始计时，到下一次状态更新为止
sm->rules = da_create(); //创建规则的动作数组
return sm;
}
/*
effect: 初始化状态数、事件数、当前状态
input : _sm状态机指针
_num_of_state状态数
_num_of_event事件数
_cur_state当前状态
*/
void
sm_init(struct state_machine* _sm, unint _num_of_state, unint _num_of_event, unint _cur_state) {
/*安全检查*/
if (_sm == NULL) {
printf("[sm_init] state machine is null\n");
return;
}
_sm->cur_state = _cur_state;
_sm->num_of_state = _num_of_state;
_sm->num_of_event = _num_of_event;
}
/*
effect: 为状态机增加状态
状态元素id即为元素在数组中的位置
状态信息为状态名，状态动作函数，笔记
input : _sm状态机指针
_cur_state规则的当前状态
_event规则的事件
_next_state规则的下个状态
_action该状态的函数,传入导致状态更新的事件
_note该状态的某个信息
*/
void
sm_add(struct state_machine* _sm, unint _cur_state, unint _event, unint _next_state, void(*_action)(unint), void* _note) {
/*安全检查*/
if (_sm == NULL) {
printf("[sm_add] state machine is null\n");
return;
}
if (_cur_state >= _sm->num_of_state ||
_next_state >= _sm->num_of_state ||
_event >= _sm->num_of_event) {
printf("[sm_add] _cur_state or _next_state or _event has out of range\n");
return;
}
struct state_machine_rule* r = (struct state_machine_rule*)malloc(sizeof(struct state_machine_rule));
if (r == NULL) {
printf("[sm_add] allocation of rule of state machine has failed\n");
return NULL;
}
r->cur_state = _cur_state;
r->event = _event;
r->next_state = _next_state;
r->action = _action;
r->note = _note;
da_push(_sm->rules, r);
}
/*
effect: 根据输入事件选择规则，进行状态转换、动作调用
input : _sm状态机指针
_event事件
*/
void
sm_trans(struct state_machine* _sm, unint _event) {
/*安全检查*/
if (_sm == NULL) {
printf("[sm_trans] state machine is null\n");
return;
}
if (_event >= _sm->num_of_event) {
printf("[sm_trans] _event has out of range\n");
return;
}
//遍历规则
for (unint i = 0; i < _sm->rules->size; ++i) {
struct state_machine_rule* r = (struct state_machine_rule*)_sm->rules->arr[i];
if (r->cur_state == _sm->cur_state) {
if (r->event == _event) {
//记录历史状态
//to do something
//更新状态
_sm->cur_state = r->next_state;
//重置计时器
_sm->timer = 0;
//调用动作
r->action(_event);
//更新状态机开始标志
if(_sm->isbegin == true) _sm->isbegin = false;
//
return;
}
}
}
//当前状态停留时间加一///按输入事件分割时间的情况
++_sm->timer;
}
/*
effect: 运行状态机
input : _sm状态机指针
_event_array事件数组，元素(事件ID)个数不一定等于状态机事件数num_event
_size_of_event_array事件数组元素个数
*/
void
sm_run(struct state_machine* _sm, unint* _event_array, unint _size_of_event_array) {
/*安全检查*/
if (_sm == NULL) {
printf("[sm_run] state machine is null\n");
return;
}
//遍历事件数组
printf("[sm_run] event array size = %d\n", _size_of_event_array);
for (unint i = 0;i< _size_of_event_array; ++i) {
//打印当前状态、事件
printf("[sm_run] cur_state = %3d, event = %3d\n",_sm->cur_state,_event_array[i]);
//状态转换
sm_trans(_sm, _event_array[i]);
}
}
/*
effect: a
input : _sm状态机指针
_event事件
output: 上个状态持续的帧数(时间片数)
*/
unint
sm_exec(struct state_machine* _sm, unint _event) {
/*安全检查*/
if (_sm == NULL) {
printf("[sm_exec] state machine is null\n");
return;
}
if (_event >= _sm->num_of_event) {
printf("[sm_exec] _event has out of range\n");
return;
}
//打印当前状态、事件
printf("[sm_exec] cur_state = %3d, event = %3d\n", _sm->cur_state, _event);
//状态转换
sm_trans(_sm, _event);
}
状态机测试1——事件数组
准备四个状态、四个事件、四个函数，当前状态初始化为1，输入事件数组运行状态
机！！！
void fun1(unint _event) {
printf("[fun1] event = %d\n",_event);
}
void fun2(unint _event) {
printf("[fun2] event = %d\n", _event);
}
void fun3(unint _event) {
printf("[fun3] event = %d\n", _event);
}
void fun4(unint _event) {
printf("[fun4] event = %d\n", _event);
}
int main(int _argc, char** _argv) {
printf("---------------------------------------------------------\n");
//test_dynamic_aay();
struct state_machine* sm = sm_create();
sm_init(sm, 4, 4, 1);//初始化状态数、事件数、当前状态
sm_add(sm, 0, 3, 1, fun1, NULL);
sm_add(sm, 1, 2, 2, fun2, NULL);
sm_add(sm, 2, 1, 3, fun3, NULL);
sm_add(sm, 3, 0, 0, fun4, NULL);
unint evt_arr[] = { 0,1,2,3,3,2,1,0,3,1,2,3,1,1,2,0,3,0,0 };
sm_run(sm, evt_arr,sizeof(evt_arr)/sizeof(unint));
printf("---------------------------------------------------------\n");
return 0;
}
测试结果
状态机时间帧
计时器timer记录状态机在当前状态停留的时间片数目，时间片怎么算呢？
上面的是按事件输入来算的，每次输入一个事件即经历了一个时间片。但是事件的输入
并不是等间隔的！ 每个状态的动作经历时间也不是相同的！该如何定义
状态机的时间片呢？
\;
\;
\;
\;
- system time. 按具体时间来的话，需要使用多线程，每隔一段时间更新一下timer
- loop. 游戏循环、屏幕显示等系统中，需要循环做一些事，每个循环中很多事的顺序是固定的，也是一样的
\;
\;
\;
还没用C写过多线程，所以这里就用第二种方法！！！
\;
//state_machine.c
void
sm_trans(struct state_machine* _sm, unint _event) {
...
//打印上一个状态持续时间片数,在更新状态之前！！！
printf("[sm_trans] last action duration = %d\n",_sm->timer);
...
}
//main.c
srand((unsigned)time(NULL));
for (unint i = 0; i < 20; ++i) {
printf("%d\n", i);
//事件在每一次循环中只有3分之一的概率会发生
//事件发生后，只有四分之一的概率会跳到下一个状态
if (rand() % 3 == 0) {
sm_exec(sm, rand() % 4);
}
//更新计数器
++sm->timer;
}
测试结果
\;
状态机历史状态
历史状态的栈深度为 state_machine_history_depth
通过指针stack_pointer确定栈的深浅
我不想用链表，只用数组，最多也就 state_machine_history_depth 这么多个，
我定义长度为20, 状态转换次数可多可少，我不能定义的太大。
当状态转换了19次，数组已经满了，stack_pointer=20。
再转换一次，状态就要记录到0，从头开始覆盖。
这样的话，还要再增加一个变量stack_filled，
表示数组是否填满过
\;
历史状态函数
栈顶指针SP，指向栈顶元素的上一位！
SP为零即没有元素，所以SP不能为零！
令回退个数为R(recovery)
令栈长为SD(stack depth)
\;
\;
1. 当栈未被填满时。
S P a f t e r = S P b e f o r e − R , R < S P b e f o r e SP_{after}=SP_{before} - R \;\;\;,\;\; { R < SP_{before}} SPafter=SPbefore−R,R<SPbefore
2. 当栈填满后。
S P a f t e r = { S D − R + S P b e f o r e , R > S P b e o f r e S D , R = S P b e f o r e S P b e f o r e − R , R < S P b e f o r e SP_{after} = \begin{cases} SD - R + SP_{before} \;\;\;,\;\;\;R >SP_{beofre} \\ SD \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; , \;\;\; R = SP_{before} \\ SP_{before} - R \;\;\;\;\;\;\;\;\;\;\;\;\;,\;\;\;R<SP_{before}\end{cases} SPafter=⎩⎪⎨⎪⎧SD−R+SPbefore,R>SPbeofreSD,R=SPbeforeSPbefore−R,R<SPbefore
\;
/*
effect: 回退到多少个状态前
input : _sm状态机指针
_recovery回退个数
*/
void
sm_history(struct state_machine* _sm, unint _recovery) {
/*安全检查*/
if (_sm == NULL) {
printf("[sm_history] state machine is null\n");
return;
}
//filled之后，最多也只能回退state_machine_history_depth-1
if (_recovery >= state_machine_history_depth) {
printf("[sm_history] recovery too much\n");
return;
}
if (_sm->stack_filled == false) { //栈还没被填满
if (_recovery >= _sm->stack_pointer) { //不能回退到0，0时状态是不存在的
printf("[sm_history] stack of history's state did not filled,and can not back off to expect location\n");
return;
}
//指针回退
_sm->stack_pointer -= _recovery;
}
else { //栈被填满了
if (_recovery > _sm->stack_pointer) {
_sm->stack_pointer = state_machine_history_depth - _recovery + _sm->stack_pointer;
}
else if(_recovery == _sm->stack_pointer){ //SP变成0，即变成state_machine_history_depth
_sm->stack_pointer = state_machine_history_depth;
}
else{
_sm->stack_pointer -= _recovery;
}
}
//更新状态
_sm->cur_state = _sm->stack[_sm->stack_pointer - 1];
}
\;
更新sm_trans
\;
/*
effect: 根据输入事件选择规则，进行状态转换、动作调用
input : _sm状态机指针
_event事件
*/
void
sm_trans(struct state_machine* _sm, unint _event) {
/*安全检查*/
if (_sm == NULL) {
printf("[sm_trans] state machine is null\n");
return;
}
if (_event >= _sm->num_of_event) {
printf("[sm_trans] _event has out of range\n");
return;
}
//遍历规则
for (unint i = 0; i < _sm->rules->size; ++i) {
struct state_machine_rule* r = (struct state_machine_rule*)_sm->rules->arr[i];
if (r->cur_state == _sm->cur_state) {
if (r->event == _event) {
//记录历史状态
if (_sm->stack_pointer < state_machine_history_depth) {
_sm->stack[_sm->stack_pointer++] = _sm->cur_state;
}
else {
if (_sm->stack_filled == false) _sm->stack_filled = true;
//覆盖了前面的头部元素
_sm->stack_pointer = 1;
_sm->stack[0] = _sm->cur_state;
}
//更新状态
_sm->cur_state = r->next_state;
//打印上一个状态持续时间片数
//printf("[sm_trans] last action duration = %d\n",_sm->timer);
//重置计时器
_sm->timer = 0;
//调用动作
r->action(_event);
//更新状态机开始标志
if(_sm->isbegin == true) _sm->isbegin = false;
//
return;
}
}
}
//当前状态停留时间加一///按输入事件分割时间的情况
//++_sm->timer;
}
回退历史状态1
state_machine_history_depth定义为6，好调试！
struct state_machine* sm = sm_create();
sm_init(sm, 4, 4, 0);
sm_add(sm, 0, 3, 1, fun1, NULL);
sm_add(sm, 1, 2, 2, fun2, NULL);
sm_add(sm, 2, 1, 3, fun3, NULL);
sm_add(sm, 3, 0, 0, fun4, NULL);
unint evt_arr[] = { 3,2,1,0};
sm_run(sm, evt_arr,sizeof(evt_arr)/sizeof(unint));
sm_history(sm, 2);
测试结果
回档之前的当前状态不保存在栈里，是SP指向的位置！
回档之后的当前状态就是cur_state！
回退历史状态2
struct state_machine* sm = sm_create();
sm_init(sm, 4, 4, 0);
sm_add(sm, 0, 3, 1, fun1, NULL);
sm_add(sm, 1, 2, 2, fun2, NULL);
sm_add(sm, 2, 1, 3, fun3, NULL);
sm_add(sm, 3, 0, 0, fun4, NULL);
unint evt_arr[] = { 3,2,1,0,3,2,1,0};
sm_run(sm, evt_arr,sizeof(evt_arr)/sizeof(unint));
sm_history(sm, 5);
测试结果
这篇关于通用Mealy状态机 + 计帧 + 恢复历史状态的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-01后台管理开发学习：新手入门指南
- 2024-11-01后台管理系统开发学习：新手入门教程
- 2024-11-01后台开发学习：从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习：从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习：新手入门教程
- 2024-11-01登录鉴权入门：新手必读指南
- 2024-11-01动态面包屑入门：轻松掌握导航设计技巧
- 2024-11-01动态权限入门：新手必读指南
- 2024-11-01动态主题处理入门：新手必读指南
