C语言 有限状态机

状态 存储关于过去的信息，就是说：它反映从系统开始到现在时刻的输入变化。转移指示 状态 变更，并且用必须满足来确使转移发生的条件来描述它。动作是在给定时刻要进行的活动的描述。有多种类型的动作：

进入动作（entry action）：在进入 状态 时进行

退出动作：在退出 状态 时进行

输入动作：依赖于当前 状态 和输入条件进行

转移动作：在进行特定转移时进行

下面展示最常见的表示：当前 状态 （B）和条件（Y）的组合指示出下一个状态（C）。完整的动作信息可以只使用脚注来增加。包括完整动作信息的FSM 定义可以使用状态表。

除了建模这里介绍的反应系统之外， 有限状态自动机 在很多不同领域中是重要的，包括 电子工程 、  语言学 、 计算机科学 、 哲学 、 生物学 、 数学 和 逻辑学 。有限 状态 机是在 自动机理论 和 计算理论 中研究的一类自动机。在 计算机科学 中，有限 状态 机被广泛用于建模应用行为、硬件电路系统设计、软件工程，编译器、网络协议、和计算与语言的研究。

地位

在数字电路系统中，有限 状态 机是一种十分重要的 时序逻辑电路 模块

作用

它对 数字系统 的设计具有十分重要的作用。

有限 状态 机是指输出取决于过去输入部分和当前输入部分的 时序逻辑电路 。一般来说，除了输入部分和输出部分外，有限 状态 机还含有一组具有“记忆”功能的 寄存器 ，这些寄存器的功能是记忆有限状态机的内部状态，它们常被称为状态寄存器。在有限 状态 机中，状态 寄存器 的的下一个状态不仅与输入信号有关，而且还与该寄存器的当前状态有关，因此有限状态机又可以认为是组合逻辑和寄存器逻辑的一种组合。其中， 寄存器 逻辑的功能是存储有限 状态 机的内部状态；而组合逻辑又可以分为次态逻辑和输出逻辑两部分，次态逻辑的功能是确定有限状态机的下一个状态，输出逻辑的功能是确定有限状态机的输出。

分类

在实际的应用中，根据有限 状态 机是否使用输入信号，设计人员经常将其分为Moore型有限状态机和Mealy型有限状态机两种类型。1Moore型有限 状态 机其输出信号仅与当前状态有关，即可以把Moore型有限状态的输出看成是当前状态的函数。2 Mealy型有限 状态 机其输出信号不仅与当前状态有关，而且还与所有的输入信号有关，即可以把Mealy型有限状态机的输出看成是当前状态和所有输入信号的函数。

编程

有限状态机体现了两点：首先是离散的，然后是有限的。

State：

状态 这个词有些难以定义，状态存储关于过去的信息，就是说它反映从系统开始到现在时刻的输入变化。

Actions & Transitions：

转换指示 状态 变更，并且用必须满足来确使转移发生的条件来描述它。动作是在给定时刻要进行的活动的描述。

Guards:

检测器出现的原因是为了检测是否满足从一个 状态 切换到另外一个状态的条件。

Event：

事件，又见事件，笼统说来，对系统重要的某件事情被称为事件。

恩，就这些了，有些迷惑么:),恩，我们来理清一下思路：先从事件说起，事件是有生命

的，它经历:

1).被产生(被接受，等待被处理，一般放入事件队列)

2).被分发(从事件队列取出，分发到响应的 状态 机处理)

3).死亡(当 状态 机处理了该事件，它随之死亡)

从一个 状态 切换到另外一个状态被称为状态转换，而引起它的事件称为触发事件.(可以看到，不是所有的事件都会引起 状态 的转换).

提到 状态 转换，不能不提及检测器(Guards)，只有当检测器的值为TRUE时候，才能启动转换

应用

常见的计算机就是使用有限状态机作为计算模型的：对于内存的不同状态，CPU通过读取内存值进行计算，更新内存中的状态。CPU还通过消息总线接受外部输入设备（如键盘、鼠标）的指令，计算后更改内存中的状态，计算结果输出到外部显示设备（如显示器），以及持久化存储在硬盘。

电脑游戏设计中也经常使用有限状态机模型。以水果忍者游戏为例，游戏中水果的状态是有限状态，其运行轨迹是由模拟物理运动规律的计算公式运算而成的，一个香蕉抛起来后会按照抛物线运行，其每一帧位置变化都是一个状态的改变，状态改变通过计算公式来决定。当然作为游戏不会仅仅这么简单，如果这么简单就是动画了，游戏还有复杂的人机交互事件，比如用手在屏幕上“切”了水果，水果感知到这个事件后，会按照程序逻辑进入爆炸状态。

1、状态机的要素

状态机可归纳为4个要素，即现态、条件、动作、次态。“现态”和“条件”是因，“动作”和“次态”是果。详解如下：

①现态：是指当前所处的状态。

②条件：又称为“事件”。当一个条件被满足，将会触发一个动作，或者执行一次状态的迁移。

③动作：条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是必需的，当条件满足后，也可以不执行任何动作，直接迁移到新状态。

④次态：条件满足后要迁往的新状态。“次态”是相对于“现态”而言的，“次态”一旦被激活，就转变成新的“现态”了。

这里需要注意的两个问题：

1、避免把某个“程序动作”当作是一种“状态”来处理。那么如何区分“动作”和“状态”？“动作”是不稳定的，即使没有条件的触发，“动作”一旦执行完毕就结束了；而“状态”是相对稳定的，如果没有外部条件的触发，一个状态会一直持续下去。

2、状态划分时漏掉一些状态，导致跳转逻辑不完整。

所以维护上述一张状态表就非常必要，而且有意义了。从表中可以直观看出那些状态直接存在跳转路径，那些状态直接不存在。如果不存在，就把对应的单元格置灰。每次写代码之前先把表格填写好，并且对置灰的部分重点review，看看是否有“漏态”，然后才是写代码。QA拿到这张表格之后，写测试用例也是手到擒来。

有限状态机FSM

思想广泛应用于硬件控制电路设计，也是软件上常用的一种处理方法(软件上称为FMM--有限消息机)。它把复杂的控制逻辑分解成有限个稳定状态，在每个状态上判断事件，变连续处理为离散数字处理，符合计算机的工作特点。同时，因为有限状态机具有有限个状态，所以可以在实际的工程上实现。但这并不意味着其只能进行有限次的处理，相反，有限状态机是闭环系统，有限无穷，可以用有限的状态，处理无穷的事务。

有限状态机的工作原理如图1所示，发生事件(event)后，根据当前状态(cur_state)，决定执行的动作(action)，并设置下一个状态号(nxt_state)。

-------------

| |-------->执行动作action

发生事件event ----->| cur_state |

| |-------->设置下一状态号nxt_state

-------------

当前状态

图1 有限状态机工作原理

e0/a0

--->--

| |

-------->----------

e0/a0 | | S0 |-----

| -<------------ | e1/a1

| | e2/a2 V

---------- ----------

| S2 |-----<-----| S1 |

---------- e2/a2 ----------

图2 一个有限状态机实例

--------------------------------------------

当前状态 s0 s1 s2 | 事件

--------------------------------------------

a0/s0 -- a0/s0 | e0

--------------------------------------------

a1/s1 -- -- | e1

--------------------------------------------

a2/s2 a2/s2 -- | e2

--------------------------------------------

表1 图2状态机实例的二维表格表示(动作/下一状态)

图2为一个状态机实例的状态转移图，它的含义是：

在s0状态，如果发生e0事件，那么就执行a0动作，并保持状态不变；

如果发生e1事件，那么就执行a1动作，并将状态转移到s1态；

如果发生e2事件，那么就执行a2动作，并将状态转移到s2态；

在s1状态，如果发生e2事件，那么就执行a2动作，并将状态转移到s2态；

在s2状态，如果发生e0事件，那么就执行a0动作，并将状态转移到s0态；

有限状态机不仅能够用状态转移图表示，还可以用二维的表格代表。一般将当前状态号写在横行上，将事件写在纵列上，如表1所示。其中“--”表示空(不执行动作，也不进行状态转移)，“an/sn”表示执行动作an,同时将下一状态设置为sn。表1和图2表示 的含义是完全相同的。

观察表1可知，状态机可以用两种方法实现：竖着写(在状态中判断事件)和横着写(在事件中判断状态)。这两种实现在本质上是完全等效的，但在实际操作中，效果却截然 不同。

竖着写C代码片段

cur_state = nxt_state;

switch(cur_state){ //在当前状态中判断事件

case s0: //在s0状态

if(e0_event){ //如果发生e0事件，那么就执行a0动作，

并保持状态不变；

执行a0动作;

//nxt_state = s0; //因为状态号是自身，所以可以删除此句

，以提高运行速度。

}

else if(e1_event){ //如果发生e1事件，那么就执行a1动作，

并将状态转移到s1态；

执行a1动作;

nxt_state = s1;

}

else if(e2_event){ //如果发生e2事件，那么就执行a2动作，

并将状态转移到s2态；

执行a2动作;

nxt_state = s2;

}

break;

case s1: //在s1状态

if(e2_event){ //如果发生e2事件，那么就执行a2动作，

并将状态转移到s2态；

执行a2动作;

nxt_state = s2;

}

break;

case s2: //在s2状态

if(e0_event){ //如果发生e0事件，那么就执行a0动作，

并将状态转移到s0态；

执行a0动作;

nxt_state = s0;

}

}

横着写(在事件中判断状态)C代码片段

//e0事件发生时，执行的函数

void e0_event_function(int * nxt_state)

{

int cur_state;

cur_state = *nxt_state;

switch(cur_state){

case s0: //观察表1，在e0事件发生时，s1处为空

case s2:

执行a0动作;

*nxt_state = s0;

}

}

//e1事件发生时，执行的函数

void e1_event_function(int * nxt_state)

{

int cur_state;

cur_state = *nxt_state;

switch(cur_state){

case s0: //观察表1，在e1事件发生时，s1和s2处为

空

执行a1动作;

*nxt_state = s1;

}

}

//e2事件发生时，执行的函数

void e2_event_function(int * nxt_state)

{

int cur_state;

cur_state = *nxt_state;

switch(cur_state){

case s0: //观察表1，在e2事件发生时，s2处为空

case s1:

执行a2动作;

*nxt_state = s2;

}

}

5G游戏 C 语言

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。