嵌入式状态机（四）层次状态机
本文介绍了一种层次状态机(HSM)的实现方法。
·
目录
前言
在嵌入式中状态机大致可以分为两种：一、有限状态机（FSM）。二、层次状态机（HSM）。
层次状态机与有限状态机的区别在于有限状态机的状态都是平级处于同一个平面，而层次状态机的结构是树状的，状态与状态之间(父状态与子状态)是可以继承的。
前置知识:
树、链表、深度搜索、广度搜索
完整代码：
#include <stdio.h>
#include <stdbool.h>
//状态机事件
typedef enum EventType
{
EVE_Enter, //内部状态进入事件
EVE_Exit, //内部状态退出事件
EVE_OpenLED, //开灯
EVE_CloseLED, //关灯
EVE_ECLED, //节能
EVE_ColorLED, //彩色灯
EVE_BrightLED, //照明灯
}EventType;
//状态机事件结构体
typedef struct Event
{
EventType e;
}Event;
//状态机状态函数
typedef struct state state;
typedef state* (*StateHandle)(void *machine,Event *e);
//状态机状态结构体
struct state
{
StateHandle handle;
state *parent;
const char * mane;
};
//状态机上下文
typedef struct KZmachine
{
state *s; //当前状态
char LED_state; //灯光状态，0为关灯，正数照明模式；负数彩色模式
char LED_EC; //节能状态，0为关，1为开
}KZmachine;
state* user_state(void *me,Event *e);
state* light_state(void *me,Event *e);
state* light_warm_state(void *me,Event *e);
state* light_cold_state(void *me,Event *e);
state* color_state(void *me,Event *e);
state* color_red_state(void *me,Event *e);
state* color_blue_state(void *me,Event *e);
state* close_state(void *me,Event *e);
state* ec_state(void *me,Event *e);
state user_node={
.handle=user_state,
.mane="用户状态",
.parent=NULL,
};
state light_node={
.handle=light_state,
.mane="照明状态",
.parent=&user_node,
};
state light_warm_node={
.handle=light_warm_state,
.mane="照明暖光状态",
.parent=&light_node,
};
state light_cold_node={
.handle=light_cold_state,
.mane="照明冷光状态",
.parent=&light_node,
};
state color_node={
.handle=color_state,
.mane="彩灯状态",
.parent=&user_node,
};
state color_red_node={
.handle=color_red_state,
.mane="红色彩灯状态",
.parent=&color_node,
};
state color_blue_node={
.handle=color_blue_state,
.mane="蓝色彩灯状态",
.parent=&color_node,
};
state close_node={
.handle=close_state,
.mane="关灯状态",
.parent=&user_node,
};
state ec_node={
.handle=ec_state,
.mane="休眠状态",
.parent=&user_node,
};
state* user_state(void *me,Event *e)
{
KZmachine *m=(KZmachine*)me;
switch (e->e)
{
case EVE_Enter:
printf("---进入用户---\n");
return NULL;
break;
case EVE_Exit:
printf("---退出用户---\n");
return NULL;
break;
case EVE_OpenLED:
m->LED_state=1;
m->LED_EC=0;
printf("开灯\n");
return &light_warm_node;
break;
case EVE_CloseLED:
printf("关灯\n");
return &close_node;
break;
case EVE_ECLED:
printf("节能\n");
return &ec_node;
break;
default:return NULL;
break;
}
}
state* light_state(void *me,Event *e)
{
KZmachine *m=(KZmachine*)me;
switch (e->e)
{
case EVE_Enter:
printf("---进入照明模式---\n");
return NULL;
break;
case EVE_Exit:
printf("---退出照明模式---\n");
return NULL;
break;
case EVE_BrightLED:
printf("照明模式切换灯光\n");
if(m->LED_state<0)
{
m->LED_state=-m->LED_state;
}
if(++m->LED_state>2)m->LED_state=1;
if(m->LED_state==1)
return &light_warm_node;
if(m->LED_state==2)
return &light_cold_node;
break;
default:return NULL;
break;
}
}
state* light_warm_state(void *me,Event *e)
{
KZmachine *m=(KZmachine*)me;
switch (e->e)
{
case EVE_Enter:
printf("---进入暖色模式---\n");
return NULL;
break;
case EVE_Exit:
printf("---退出暖色模式---\n");
return NULL;
break;
default:return NULL;
break;
}
}
state* light_cold_state(void *me,Event *e)
{
KZmachine *m=(KZmachine*)me;
switch (e->e)
{
case EVE_Enter:
printf("---进入冷色模式---\n");
return NULL;
break;
case EVE_Exit:
printf("---退出冷色模式---\n");
return NULL;
break;
default:return NULL;
break;
}
}
state* color_state(void *me,Event *e)
{
KZmachine *m=(KZmachine*)me;
switch (e->e)
{
case EVE_Enter:
printf("---进入彩色模式---\n");
return NULL;
break;
case EVE_Exit:
printf("---退出彩色模式---\n");
return NULL;
break;
case EVE_ColorLED:
printf("彩色模式切换灯光颜色\n");
if(m->LED_state>0)
{
m->LED_state=-m->LED_state;
}
if(--m->LED_state<-2)m->LED_state=-1;
if(m->LED_state==-1)return &color_red_node;
if(m->LED_state==-2)return &color_blue_node;
break;
default:return NULL;
break;
}
}
state* color_red_state(void *me,Event *e)
{
KZmachine *m=(KZmachine*)me;
switch (e->e)
{
case EVE_Enter:
printf("---进入红色模式---\n");
return NULL;
break;
case EVE_Exit:
printf("---退出红色模式---\n");
return NULL;
break;
default:return NULL;
break;
}
}
state* color_blue_state(void *me,Event *e)
{
KZmachine *m=(KZmachine*)me;
switch (e->e)
{
case EVE_Enter:
printf("---进入蓝色模式---\n");
return NULL;
break;
case EVE_Exit:
printf("---退出蓝色模式---\n");
return NULL;
break;
default:
return NULL;
break;
}
}
state* close_state(void *me,Event *e)
{
KZmachine *m=(KZmachine*)me;
switch (e->e)
{
case EVE_Enter:
printf("---进入关灯模式---\n");
return NULL;
break;
case EVE_Exit:
printf("---退出关灯模式---\n");
return NULL;
break;
default:
return NULL;
break;
}
}
state* ec_state(void *me,Event *e)
{
KZmachine *m=(KZmachine*)me;
switch (e->e)
{
case EVE_Enter:
printf("---进入休眠模式---\n");
return NULL;
break;
case EVE_Exit:
printf("---退出休眠模式---\n");
return NULL;
break;
default:
return NULL;
break;
}
}
state* Fint_LCA(state* present,state* target)
{
if(present==NULL&&target==NULL)
{
printf("输入状态为空\n");
return NULL;
}
state * p=present;
while (p!=NULL)
{
/* code */
state* t=target;
while (t!=NULL)
{
/* code */
if(t==p)
{
return t;
}
t=t->parent;
}
p=p->parent;
}
printf("没有LCA\n");
return NULL;
}
void exchange_state(void *me,state *s)
{
KZmachine *m=(KZmachine*)me;
//找到最小共同祖先
state *LCA_state=Fint_LCA(m->s,s);
if(LCA_state==NULL)return ;
//从当前状态退出到LCA状态 Exit
state* exit_state=m->s;
Event exit_event={.e=EVE_Exit};
while (exit_state!=NULL&&exit_state!=LCA_state)
{
printf("当前-->%s\n执行的动作:",exit_state->mane);
exit_state->handle(m,&exit_event);
exit_state=exit_state->parent;
}
//收集从LCD到目标状态的路径
state *array_state[12]={NULL};
char enter_num=0;
state *enter_state=s;
while (enter_state!=NULL&&enter_state!=LCA_state)
{
array_state[enter_num++]=enter_state;
enter_state=enter_state->parent;
}
printf("++++++++++++++++++++++\n");
//根据收集到的路径从LCD进入到目标路径 enter
Event enter_event={.e=EVE_Enter};
for(char i=enter_num-1;i>=0;i--)
{
printf("当前-->%s\n执行的动作:",array_state[i]->mane);
array_state[i]->handle(m,&enter_event);
}
printf("开始状态转移,%s---->%s\n",m->s->mane,s->mane);
m->s=s;
}
void state_bubbling_event(void *me,Event *e)
{
KZmachine *m=(KZmachine*)me;
state *stata_buf=m->s;
while (stata_buf!=NULL)
{
state *t=stata_buf->handle(me,e);
if(t!=NULL)
{
exchange_state(me,t);
break;
}
stata_buf=stata_buf->parent;
}
}
KZmachine me={.s=&user_node};
Event Eve={.e=EVE_CloseLED};
void main(void)
{
Eve.e=EVE_OpenLED;
state_bubbling_event(&me,&Eve);
printf("%s\n\n",me.s->mane);
Eve.e=EVE_CloseLED;
state_bubbling_event(&me,&Eve);
printf("%s\n\n",me.s->mane);
Eve.e=EVE_BrightLED;
state_bubbling_event(&me,&Eve);
printf("%s\n\n",me.s->mane);
Eve.e=EVE_ECLED;
state_bubbling_event(&me,&Eve);
printf("%s\n\n",me.s->mane);
}状态转换图
代码解析
一、寻找共同祖先（LCA）
state* Fint_LCA(state* present,state* target)这个函数是用来寻找共同祖先的(最近的父节点)。
//状态机状态结构体
struct state
{
StateHandle handle;
state *parent;
const char * mane;
};由于状态结构体的指针是指向父节点的所以可以使用两个while (p!=NULL)、while (t!=NULL)循环遍历就可以轻易的离他们最近的父节点。
二、层次状态转换
什么是层次状态转换：从当前状态向上退出----->到LCA状态停止退出------>从LCA状态加入到目标状态。
void exchange_state(void *me,state *s)
这是用于状态转换的核心代码，它由这几个核心思想组成
//找到最小共同祖先状态
state *LCA_state=Fint_LCA(m->s,s);确定LCA
//从当前状态退出到LCA状态 Exit
state* exit_state=m->s;
Event exit_event={.e=EVE_Exit};
while (exit_state!=NULL&&exit_state!=LCA_state)
{
printf("当前-->%s\n执行的动作:",exit_state->mane);
exit_state->handle(m,&exit_event);
exit_state=exit_state->parent;
}从当前状态退出到LCA状态，使用EVE_Exit事件与 while(exit_state!=NULL&&exit_state!=LCA_state)保证退出的过程中每一个状态函数都经过退出状态从而保证状态机的线程安全。
//收集从LCD到目标状态的路径
state *array_state[12]={NULL};
char enter_num=0;
state *enter_state=s;
while (enter_state!=NULL&&enter_state!=LCA_state)
{
array_state[enter_num++]=enter_state;
enter_state=enter_state->parent;
}这里需要收集从LCD到目标状态的路径是应为状态机结构体的指针是向上父节点的，只能从目标状态开始遍历enter_num变量就是为此准备的。可以理解为enter_num与state *array_state[12]={NULL};构成了一个简易的栈结构。
//根据收集到的路径从LCD进入到目标路径 enter
Event enter_event={.e=EVE_Enter};
for(char i=enter_num-1;i>=0;i--)
{
printf("当前-->%s\n执行的动作:",array_state[i]->mane);
array_state[i]->handle(m,&enter_event);
}根据收集到的路径从LCD进入到目标路径，根据之前的路径array_state从LCD开始与EVE_Enter事件一起进入目标状态。为什么要从EVE_Enter事件进入呢?同样是应为要保证从当前状态到目标状态的线程完整(在层次状态机中状态的退出与进入动作本身就是状态转移的一部分)。
printf("开始状态转移,%s---->%s\n",m->s->mane,s->mane);
m->s=s;可以看到状态转移的部分很简单只有m->s=s;这一句话，这是为什么呢？
除了之前说的退出与进入动作是确保状态转换的完整性和正确性以外，还应为这是维护层次结构、实现行为继承（HSM的核心优势）的体现。
在层次状态机HSM中子状态会继承父状态的所有行为。换句话说只要是子状态所指向、的在子状态之上的、与子状态形成了链表的状态，子状态都可以使用它们的事件与对应的行为(应为exchange_state本质是一个冒泡函数)。
三、事件处理(事件分发)
void state_bubbling_event(void *me,Event *e)
{
KZmachine *m=(KZmachine*)me;
state *stata_buf=m->s;
while (stata_buf!=NULL)
{
state *t=stata_buf->handle(me,e);
if(t!=NULL)
{
exchange_state(me,t);
break;
}
stata_buf=stata_buf->parent;
}
}
状态在while (stata_buf!=NULL)中不断通过stata_buf=stata_buf->parent;向上遍历，在遍历的过程中不断的尝试写入的事件知道事件触发(exchange_state(me,t);)或者遍历到根节点(stata_buf!=NULL)，这就是子状态会继承父状态的程序。
结语
从有限状态机FSM到层次状态机HSM状态机是实现方法有着不小的变化，但状态机的思想一直没有改变。在状态机中层次状态机HSM虽然有些复杂但是它却不是终点，再跟进一步就是事件驱动系统QPC了。
小编的水平有限且当是抛砖引玉了！
智能硬件社区聚焦AI智能硬件技术生态，汇聚嵌入式AI、物联网硬件开发者，打造交流分享平台，同步全国赛事资讯、开展 OPC 核心人才招募，助力技术落地与开发者成长。
更多推荐
12
0- 0
已为社区贡献4条内容
所有评论(0)