脑浆不够用，寻求理论、方**上的帮助。

只看该作者 · 2007-11-19 12:21

近日写一程序，不多的几个分支，搞得脑浆涂地，突然想到没有真看过“状态机”的规范**， googl 一下，不甚明白，觉得匠人圈圈要是能出个 **，论述一下状态机之设计，用途，如何用状态机来处理问题，将是莫大功德。

贸然在此恳请两位达人出手。

1万 · 2007-11-20 21:18

附：以下内容为《匠人手记》一书中的一篇。

如果顺利的话，此书明年可以面世。现在让大家先睹为快。

（书中的图片，这里就不贴了，要不然明年的书就卖不掉了。嘿嘿）
---------------------------------------------------------------

手记3   编程思路漫谈
一、前言
长久以来，都想写一篇关于编程思想的**，但是一直没敢下笔。因为这实在是一个比较难以用文字表达清楚的话题。
思想是什么呢？
思想是隐藏在灵魂深处的东西。它对外的展现，也许是种观点，也许是种方法，也许是种技巧。
但更多时候，思想也许只是个一闪即逝的灵感，划过脑际不留痕迹。思想是活的精灵，就像流水，千回百转，奔流不息。而当我们想去捧起，那水却又悄悄从指尖缝隙里流走。
思想就是这么得不可捕捉，没有常形。而一旦被捕捉到了，那思想便也就从那一刻开始定格、僵化、失去活力，成为一潭死水。这样的思想又有何用呢？
语言文字，由于它的局限性，它也许可以表述编程的思路，却很难传递编程的思想。编程思想有时只能意会却不能言传。
因此，匠人只能退而求其次，就写一篇关于编程思路的手记吧。
二、程序的基本结构
对于新手来说，背熟了指令集并不代表你就会写程序了。就像我们普通人，即使认识了所有的汉字，但并不代表就会写**了。
如何把那一条条指令汇集成程序，并顺利实现预期的要求呢？或者说，如何根据具体的要求构建程序的框架呢？这往往成为新手上路后遇到的第一个“坎”。
那好，就随着匠人娓娓的叙说，从最简单的程序结构开始，进行一场进阶之旅吧……
单片机的程序都是为了实现某个特定的功能而定制的。因此每个程序的流程也不可能完全相同。但是写得多了，总还是有些规律可循。事实上，大多数程序都可以套用这样一个基本流程结构（参见图 3.1：基本程序结构）。

图 3.1：基本程序结构
这是一种比较完美的基本结构（完美的标准就是“简单有效”）。在这个程序结构中包含了两部分：
1、初始化程序
单片机上电复位后，从复位入口处开始运行程序。这个时候，应该先对系统进行自检和初始化动作。系统的初始化动作包括对IO口、RAM（变量）、堆栈、定时器、中断、显示、ADC、以及其它功能模块的初始化。初始化动作一般只需要执行一遍。
如果有必要，还可以在这段程序里建立分支结构，如热启动和冷启动分支。程序可以根据系统复位类型、系统自检的结果或其它条件，选择性地执行初始化动作。
2、主程序循环体
初始化程序结束后，系统的工作环境已经建立起来了，这时就可以进入主程序。
主程序一般是个循环体。在这里执行的是程序要实现的具体功能。如输入检测、输出控制及人机界面等等。这些功能语句可以直接写在主程序里，也可以写成子程序形式，由主程序进行调用。
三、模块化的程序结构
原则上来说，匠人是不会在主程序里直接写功能语句的（喂狗指令除外）。一个好的主程序结构应该通过子程序去调用具体功能模块，这是程序模块化的要求。那种“脚踩西瓜皮，滑到哪里算哪里”可不是我们的风格哦。
在这种模块化的程序结构中，主程序仅仅是执行调度功能，负责轮流调用功能模块程序。主程序每循环一圈，所有的功能模块都被调用一次（参见图 3.2：模块化程序结构）。

图 3.2：模块化程序结构
显然，采用了这种结构后，各个模块之间相互独立性较强。我们可以象搭积木一样，很方便地增加或减少主程序调用的模块。
四、模块的事件驱动机制
由于主程序是按顺序依次调用各个功能模块的，而有些模块可能在本轮循环中不具备执行的条件。那么如何避免这些模块也被执行呢？
一个比较好的解决办法是采取事件驱动机制，来加快了主程序的循环速度，提升整个系统的实时性。
所谓的事件驱动机制，就是给每个模块安排“使能标志”，通过使能标志来触发该模块代表的事件。也就是说，在每次进入功能模块（子程序）时，先判断该模块是否满足执行条件（功能模块使能标志=1），如果满足则执行（同时将使能标志清零）；否则直接返回即可（参见图 3.3：功能模块的程序结构）。

图 3.3：功能模块的程序结构
让我们举例说明。比如说，有一个显示功能模块，用于控制液晶的显示。实际上，我们没有必要在主程序的每次循环中都去刷新显示内容。我们只要为该显示模块定义一个显示刷新使能标志。在计时程序中定期（比如说是0.5秒）把该标志设置为“1”。然后在显示程序开始处先判断一下这个标志。如果时间没到，则不必进行刷新显示。
某个功能模块的使能标志，可以由其它模块进行设置。就像前面说到的显示刷新使能标志一样。其显示功能由显示程序模块实现，而标志却是由计时程序或定时程序来进行设置。也就是说，虽然显示程序的执行与否受到计时程序的控制，但这两个模块之间并不存在互相调用的情况。它们之间仅仅是通过标志位进行联系。
这个显示使能标志就是一个显示刷新事件的触发条件。同时也相当于其它程序对显示模块的控制条件。在整个系统的任何其他程序模块中，当我们觉得有必要刷新一次显示时，都可以通过这个标志去通知显示模块。比如，在按键处理程序中，当用户通过按键设置，修改了显示内容。按键程序可以将显示使能标志设置为“1”，通知显示程序立即刷新显示，而不必等到0.5秒计时完成。
有时，可能一个标志不足以传递所有的控制信息，我们可以用更多的标志或寄存器来实现命令和参数的传递。
五、顺序调度机制与优先调度机制
前面讲的是在进入功能模块时，先查询该功能模块的使能标志。我们也可以把这种查询的动作放在主程序中。并因此延伸出两种不同的主程序调度机制：
1、顺序调度机制
如果各个模块之间没有优先级区别，我们可以采取顺序调度机制。（参见图 3.4：顺序调度）。
这种调度机制的特征是，主程序按照一定的顺序，轮流查询各个功能模块的使能标志。如果标志有效，就执行相应的模块，并清除该标志。一个模块查询或执行结束后，继续对下一个模块进行操作。全部模块操作结束后，回到主程序开始初，如此循环不止，周而复始。
采取顺序调度机制的程序结构的优点，是可以保证所有的功能模块都得到执行的机会，并且这种机会是均等的。（排排座，吃果果，你一个，我一个。呵呵！）
顺序调度机制的缺点是，某些重要的模块无法得到及时的响应。

图 3.4：顺序调度机制
2、优先调度机制
如果各个功能模块有优先级的区别，我们可以采取优先调度机制。（参见图 3.5：优先调度）。
这种调度机制的特征是，主程序按照一定的优先级次序，去查询各个标志。如果高优先级功能模块的使能标志有效，则在执行完该模块（并清除该标志）后，不再执行后续模块的查询操作，而是跳转到主程序开始处，重新开始新一轮操作。
采取优先调度机制的程序结构的优点，是可以让排在前面的优先级高的功能模块获得更多更及时的执行机会。
优先调度机制的缺点是，那些排在末位的模块有可能被堵塞。

图 3.5：优先调度机制
六、中断与前/后台的程序结构
前面讲的在主程序中进行事件轮询的调度机制，应付一般的任务可以游刃有余了。但是一旦遇到紧急突发事件，还是无法保证即时响应。因此，单片机中引入了中断的概念。
我们把实时性要求更高的事件（比如：外部触发信号，或者通讯）放在中断中（前台）响应，把实时性要求较低的任务（比如：按键扫描、显示刷新）交给主程序（后台）去调度。这样，就形成了前/后台的程序结构模型。（参见图 3.6：前/后台程序结构）。

图 3.6：前/后台程序结构
那么，哪些任务应该放在中断中处理，哪些任务应该放在后台程序中处理呢？其实这是没有绝对的准则的。有些任务（比如前面提到的按键定时扫描）既可以放在前台（定时中断）执行，也可以放在后台执行。这取决于项目的具体情况，以及个人的编程习惯。
前/后台任务的配置，有两个比较极端的例子。
一种情况就是，对于有些单片机来说，根本就没有中断源（如PIC的一些低端芯片）。所有的任务都要依靠主程序去合理调度。应用这种芯片编程是一件痛苦的事情。但确实有许多高手做到了这一点，他们在主程序中将所有的任务调度安排的井井有条。这种严密的条理性，恐怕也体现了超越常人的思维能力吧（非人类啊，呵呵）。
另一种情况是，现在有些单片机的中断资源极大丰富，几乎所有任务都可以通过中断实现。有时，人们干脆就让中断承担了全部的工作。后台程序除了上电时的初始化动作外，平时什么都不干，干脆呼呼大睡（进SLEEP模式，或待机模式），以降低系统功耗，避免干扰。呵呵，这倒也算是一种新颖的编程理念。读者可以参阅本书中关于摇摇棒的项目。在那个项目中，匠人就是采用这种编程方式。
上面讲的毕竟都是极端的例子，而在大多数情况下，任务是由前台程序和后台程序分工合作完成的。
为了避免前台程序和后台程序互相抢夺CPU的控制权，发生竞争，匠人建议尽可能减少中断的执行时间。我们可以在中断服务程序中设置一些标志，然后回到主程序中来查询这些标志并做进一步的处理。
七、时间片与分时调度机制
在任务较多的时候，为了保证每个任务都能得到系统时间，我们可以尝试采用分时调度机制。将整个系统时间分成若干份时间片，并用ID进行标识。每个时间片内执行一个功能模块。
我们可以把整个程序中的所有任务都纳入分时调度机制中。这种情况下，分时调度的执行者就是主程序（参见图 3.7：主程序中采取分时调度结构）。

图 3.7：主程序中采取分时调度结构
我们也可以仅对部分任务采取分时调度。而其他的任务仍旧采取事件轮询调度。在这种情况下，分时调度的执行者可能就是一个子程序（参见图 3.8：子程序中采取分时调度结构）。
上述两种办法中，都是由后台程序实现分时调度。其实这项工作也可以交给定时中断去完成。原理差不多，这里就不详说了。

图 3.8：子程序中采取分时调度结构
八、多进程并行运行机制
从微观的角度来看，任何一个时刻里，CPU只能执行一个任务。而每个任务执行的时间有长有短。当一个耗时较长的任务在运行时，如果又发生一个紧急事件，需要响应，那该怎么办呢？一般有下面几种处理方法：
（1）第一种方法是采取顺序调度或优先调度机制。这两种调度机制都是要等待当前任务结束后，再处理下一个任务。这种方法的实时性无疑是最差的。
（2）第二种方法是采取前/后台程序结构。把紧急事件放在中断服务程序中处理。这种方法前面也已经介绍过。一般情况下，它可以满足系统的实时性要求了。但是，当前台和后台需要处理的任务都有实时性要求，或者存在多个中断的话，相互间也会为了抢夺CPU的系统时间而发生竞争。这种方法还有一个缺点，就是需要占用CPU的中断资源。
（3）第三种方法是采取分时调度机制。给每个任务分配一定的时间片。采用这种方法，每个任务的执行时间不能太长，必须在分配给它的规定时间片内结束，并交出系统控制权。但是，如果任务的执行时间较长，无法在单个时间片内结束，如何确保系统的实时性呢？这时我们可以采用本节要介绍的多进程并行机制。
多进程并行机制，就是把每个任务看作是一个进程，该进程可以被分成多个阶段，每个阶段的执行时间较短。当该进程获得系统的控制权后，每次只执行一个阶段，然后就将控制权交还给上级调度程序。待到下次重新获得系统控制权时，再执行一个阶段。（参见图 3.9：进程的分阶段运行结构）。

图 3.9：进程的分阶段运行结构
通过合理的调度，系统可以让多个进程交替执行，从而达到宏观上多任务并行运行的效果。（参见图 3.10：多进程并行运行示意图）。

图 3.10：多进程并行运行示意图
多进程并行运行机制的应用机会还是很多的。比如说在LED数码管动态扫描显示方面，假如要定期扫描多个LED数码管，并且每个LED点亮后，需要延时1毫秒。这个1毫秒如果直接用延时子程序去实现，就浪费了系统的时间资源。我们可以把这个显示程序当作一个进程，分多个阶段来执行。每个阶段切换显示一个LED管。而在当中的1毫秒延时期间，可以将系统控制权交还给调度程序，去执行其它程序。
同样，在作按键检测时，需要消抖延时；或在写外部E2PROM（如24C01芯片）时，需要写动作延时。这些时间都可以让系统去执行其它程序，提高整个系统的实时性。
九、多工序程序结构
这年头，多任务操作系统的概念显得很时髦，但那并不是解决问题的唯一手段。用最简单的办法实现既定功能，才是我们最终的目的。
比如说一个充电器程序，其充电过程包含了小电流预充电、大电流充电、涓流充电、充电完成等若干个阶段。每个充电阶段就像生产线上的一道特定工序，其电流、电压控制方式，以及显示内容等功能都不一样。另外，当发生故障时，还要进行保护。故障保护也可以视为一道特殊的工序。
如果按前面几节介绍的思路去编写程序，通过各种状态寄存器和标志位来区分这些工序，那么当这些杂七杂八的工序相互纠缠在一起，足以让人疯狂。
为什么会疯狂呢？因为我们只有一个主程序，而这个主程序要去区分处理那么多不同的状态、不同的工序。程序里面到处都是状态寄存器和标志位，相互牵扯，纠缠不清。最后不是程序疯掉，就是程序员疯掉了。（匠人也疯狂？呵呵。）
那么就让我们跳出常规的思维框架，另辟蹊径解决问题。
写一个8K的多任务程序是很累的，而写8个单任务的1K小程序却易如反掌，轻松愉快。我们的任务就是要将多任务分解成单任务，而不是相反。既然一个主程序不足以驾驭这么多工序，我们干脆把整个充电过程按工序划分。采用多个主程序来调度任务。每个主程序负责一道工序。第一个负责预充，第二个负责大电流充，第三个负责涓充……。
您瞧，这一不小心，就引出了这一节要介绍的——类似状态机的多工序程序结构。

图 3.11：单个工序的状态程序结构图
在这种程序结构中，有多个主程序。每个主程序相当于一个独立的单片机程序，有属于自己的初始化段和循环体。我们称每个这样的主程序为一个工序状态。
在单个工序的循环体内，定期判断工序迁移条件。如果没有满足特定的条件，就一直维持该工序的状态，其主程序将一直独占系统的控制权。如果满足了某个特定的迁移条件，则跳转到该条件指向的新工序状态。（参见图 3.11：单个工序的状态程序结构图）。
把多个这样的工序程序组合成起来，就构成了一个线性的或网络状的程序框架。每个工序都是这个网络的一个节点。它们相互之间是平级关系，通过条件来触发迁移动作。最终实现整体功能。（参见图 3.12：工序迁移图）

图 3.12：工序迁移图
补充一下，有时在几个工序里，都要执行一些相同的功能。我们可以把这些功能做成子程序，供各个工序去调用。
最后，需要说明的是，多工序程序结构并不符合程序结构化设计的要求。因为，按照结构化的要求，每一个程序模块应该只有一个入口和一个出口。这种多工序程序结构中的每个模块（工序）都有可能有多个入口或出口，因此有其应用的局限性。这就像一剂毒药，用好了可以治病，用不好可就会要老命的哦！切记！切记！
十、基于状态机思路的程序调度机制
在上一节中提到的多工序程序结构中，每个工序状态都是一个相对独立的主程序。这种结构仅仅适合那种明显带有工序特征的程序（如充电器程序）。当各个工序都拥有许多相同或相似的功能（如按键处理、AD转换、显示驱动等等）时，我们就要在每个工序状态的主循环体中，重复地调用或执行相同的程序段。程序的编写效率由此将变得非常低下。
另外，这种结构有其明显的缺点，就是不符合程序设计结构化的要求。也许当我们跳出了由诸多纠缠不清的标志淤积的泥潭后，却发现掉入更可怕的程序结构混乱不堪形同蛛网的盘丝洞。
有时，我们不得不摒弃这种程序结构。
不过，我们仍然可以利用状态机的思路，主调度程序只保留一个，用状态寄存器来表示程序的工作状态。在调度程序中，根据系统当前工作状态和触发条件，综合解析，执行相应的动作，或迁移到新的状态。由此，我们就得到了另一种更有效率的结构。
比如，在单片机中，按键是常见的人机交流手段。我们可以通过按键向单片机输入命令。在一键一义型键盘控制系统中，每个按键都有其特定的唯一的功能。这种类型实现起来相对容易。但在实际应用中，当程序需要实现较多功能时，受按键数量的制约，我们往往要让每个按键承担更多的功能。这就是所谓的一键多义型键盘控制系统。
在这种系统中，我们要先将系统的工作状态进行划分，并给每个状态编号。当某个按键被触发时，我们在判断按键的编号（键值）的同时，还要判断系统当前处于哪个状态下（现态）。对“键值”和“现态”综合解析，然后确定执行哪个功能，或者切换到新的工作状态（次态）。（参见图 3.13：一键多义按键执行程序结构图）。

图 3.13：一键多义按键执行程序结构图
这种基于状态机的程序调度机制。其中包含以下4个要素：
（1）现态：当前所处的工作状态；
（2）条件：触发动作或状态迁移的条件（在按键系统中，就是指键值）；
（3）动作：条件满足后执行的动作；
（4）次态：条件满足后要迁移的新状态。
我们可以看到，上述4个要素明显带有因果关系。前二者是因，后二者是果。这4个要素用一句话来表示，就是：当在A状态下，检测到B条件成立，即执行C动作，然后迁移到D状态。
将全部的因果关系集合在一起，就构成了整个状态机的内涵。
我们可以采用状态迁移图来地表示各个状态之间的迁移关系。我们会发现，这种方式比普通程序流程图更简练、直观、易懂（参见图 3.14：状态迁移图）。

图 3.14：状态迁移图
我们可以看到，状态迁移图和前一节提到的工序迁移图（参见图 3.12：工序迁移图）非常相似。二者的区别是：在工序迁移图中，箭头代表了程序PC指针的跳转（这一点和普通流程图一样）；而在状态迁移图中，箭头代表的是状态寄存器的改变。
除了状态迁移图，我们还可以用表格的形式来表示状态之间的关系。（参见表 3.1：状态迁移表）。在这张表中，我们将不但罗列出每个状态的4个要素，而且将每个状态的特征（如显示内容）也包含在内。
如果表格内容较多，我们也可以将状态迁移表进行拆分。将其中每个状态的显示内容单独列表。这种描述每个状态显示内容的表，匠人称之为“显示真值表”。对应的，也可以把单独表述基于按键的状态迁移表称为“按键功能真值表”。
状态迁移图和状态迁移表两种表达方式对比来看，图形的优点是直观；表格的优点是可容纳的文字信息量较多。二者互为补充，合理利用将相得益彰。
基于状态迁移的程序调度机制，其应用的难点并不在于对状态机概念的理解，而在于对系统工作状态的合理划分。初学者往往会把某个程序动作当作是一种状态来处理。匠人把这种称为“伪状态”。初学者的另一种比较致命的错误，就是在状态划分时漏掉一些状态。这两种错误的存在，将会导致程序结构的涣散。
工作状态（现态）    A键    B键    显示内容
编号    说明    次态    功能    次态    功能
0    显示时间    1    -    3    -    时:分:秒(12:00:00)
1    显示闹钟    2    -    5    -    时.分(TM 08:00)
2    显示秒表    0    -    -    启动/停止    时.分.秒(00.00.00)
3    设置小时    -    时+1    4    -    (12:▊▊:▊▊)
4    设置分钟    -    分+1；秒=0    0    -    (▊▊:00:00)
5    设置闹钟"时"    -    时+1    6    -    (TM 08:▊▊)
6    设置闹钟"分"    -    分+1    7    -    (TM ▊▊:00)
7    设置鸣叫时间    -    鸣叫分钟+1    1    -    (TM SP:00)
表 3.1：状态迁移表
十一、更复杂的状态结构
前面介绍的是一种简单的状态结构。它只有一级，并且只有一维。（参见图 3.15：线性状态结构）

图 3.15：线性状态结构
根据不同的状态划分方法，除了这种简单的状态结构外，还有一些更复杂的状态结构。如：
1、多级状态结构。
在某些状态下，还可以进一步划分子状态。
比如，我们可以把前面的例子修改一下。
把所有和时钟功能有关的状态，合并成1个一级状态。在这个状态下，又可以划分出3个二级子状态，分别为：显示时间、设置小时、设置分钟；
同样，我们也可以把所有和闹钟功能有关的状态，合并成1个一级状态。在这个状态下，再划分出4个二级子状态，分别为：显示闹钟、设置“时”、设置“分”、设置鸣叫时间。
我们需要用另一个状态寄存器来表示这些子状态。
子状态下面当然还可以有更低一级的孙状态（子子孙孙无穷尽也），从而将整个状态体系变成了树状多级状态结构。（参见图 3.16：树状多级状态结构）。

图 3.16：树状多级状态结构
2、多维状态结构。
在系统中，有时会存在多维状态划分。
比如，在按照按键和显示划分状态的同时，又按照系统的工作进程有做出另一种状态划分。这两种状态划分同时存在，相互交叉。从而构成了二维的状态结构空间。
这方面的例子如空调遥控器。（参见图 3.17：多维状态结构）

图 3.17：多维状态结构
同样，我们也可以构建三维、四维甚至更多维的状态结构。（呵呵，四维时空、科幻故事？）
说明一下，每一维的状态都需要用一个状态寄存器来表示。
无论多级状态结构和多维状态结构看上去多么迷人，匠人的忠告是，我们还是要尽可能地简化状态结构。能用单级、单维的结构，就不要自己给自己找事，去玩那噩梦般的复杂结构。
简单的，才是最有效的。
十二、后记
以上介绍的，都是构建单片机程序框架的一些思路。这些思路再经过排列组合，又可衍生出许多“组合拳法”来。
所谓“兵无常势，水无常形，能因敌变化而取胜者，谓之神”。万般变化，存乎一心。见招拆招，才是上招。
通过将各种程序结构灵活应用，各种调度机制有机结合，就可以更有效地管理各个任务，实现程序的预期目标。
这篇手记写到这里，也该告一段落了。

2万 · 2007-11-19 12:48

给一个大概描述：

Y = F1（X，S）;
S = F2（X，S）;

其中X是输入，Y是输出，S是状态。而F1和F2是函数。

其中的奥妙大了去了，找本书啃啃吧。

只看该作者 · 2007-11-19 13:02

只看该作者 · 2007-11-19 13:02

你说的是函数，用状态机以函数方式应用层的一种写法，算较高级阶段应用层。

关键是X 这个状态如何定义，再有，各个函数之间有参数要互相约束。

2万 · 2007-11-19 13:12

如果LZ想在程序中应用状态机，可以从分支散转语句（类似switch)入手，状态就对应于分支（case），输入输出就自己定了。

只看该作者 · 2007-11-19 13:18

关键是思想。

    关键希望达人能论述出一种思想，再大家用你的函数体现应用层的实现，比如我现在就是被几个在各个分支里发生的条件要互相约束给绊倒几回了，甚是气馁！

    谢谢 HWM 扔砖

1万 · 2007-11-19 13:21

2万 · 2007-11-19 13:24

找本书看看吧，注意其中的状态机简化或优化算法。

2万 · 2007-11-19 13:32

呵呵，这个话题广了，讨论个把也估计没问题……

只看该作者 · 2007-11-19 13:48

1万 · 2007-11-19 13:50

只看该作者 · 2007-11-19 13:56

转载：[python]有限状态机（FSM）简单实现
Posted on 2007-05-20 07:24:55 in .net教程

本文发表于恋花蝶的博客http://blog.csdn.net/lanphaday，欢迎转载，但必须保留**内容完整且包含本声明。违者必究。

[python]有限状态机（FSM）简单实现

简述
有限状态机（以下用FSM指代）是一种算法思想，简单而言，有限状态机由一组状态、一个初始状态、输入和根据输入及现有状态转换为下一个状态的转换函数组成。在Gof的23种设计模式里的state模式是一种面向对象的状态机思想，可以适应非常复杂的状态管理。
现在，FSM被普遍用于搜索引擎的分词、编译器实现和我们普遍关注的游戏开发中。游戏开发中，通常用FSM实现NPC控制，如当NPC受到攻击时根据健康、力量等选择逃跑还是反攻的行为，一般是用FSM实现的。FSM的实现方法有很多种，不能简单地说孰优孰劣，但现代开发中，一般都比较推荐面向对象的实现方式：因为可重用性和健壮性更高，而且当需求变更的时候，也有很好的适应性。
实践
理论从实践中来，也要回到实践中去。我们现在通过实例来探索一下FSM的实现吧。首先假设有这样一个世界（World），世界里只有一台永不缺乏动力的汽车（Car），汽车是次世代的，没有油门方向盘之类的落后设备，只有两个互斥的按钮——停止（Stop）和行进（Run），随着时间的流逝，汽车根据驾驶员的操作走走停停。下面的代码可以实现这种功能：
while True:
       key = get_key() # 按下什么键
       if key == "stop":
              stop(car)
       elif key == "run":
              go(car)
       keep(car) # 保持原态

完成了功能而且直观、简洁的程序员万岁！但这时候客户（策划或者玩家）觉得走走停停太没意思了，他们想要掉头、左转和右转的功能，我们就要在while循环里增加更多的if...else分支；他们想要更多的车，我们就要要在每一个分枝里增加循环；他们不仅仅想要Car了，他们还要要玩Truck，这时我们就需要在分枝的循环里判断当前的车是否支持这个操作（如Truck的装卸货物Car就不支持）；他们……
这个while循环终于无限地庞大起来，我们认识到这样的设计的确是有点问题的，所以我们尝试用另一种方法去实现FSM。首先我们来实现汽车（Car）：
class Car(object):
       def stop(self):
              print "Stop!!!"

       def go(self):
              print "Goooooo!!!"

只有两个方法stop和go，分别执行Stop和Run两个按钮功能。接下来我们编写两个状态管理的类，用以处理当按钮被按下、弹起和保持时需要工作的流程：
class stop_fsm(base_fsm):
       def enter_state(self, obj):
              print "Car%s enter stop state!"%(id(obj))

       def exec_state(self, obj):
              print "Car%s in stop state!"%(id(obj))
              obj.stop()

       def exit_state(self, obj):
              print "Car%s exit stop state!"%(id(obj))
class run_fsm(base_fsm):
       def enter_state(self, obj):
              print "Car%s enter run state!"%(id(obj))

       def exec_state(self, obj):
              print "Car%s in run state!"%(id(obj))
              obj.go()

       def exit_state(self, obj):
              print "Car%s exit run state!"%(id(obj))

stop_fsm和run_fsm都继承自base_fsm，base_fsm是一个纯虚的接口类：
class base_fsm(object):
       def enter_state(self, obj):
              raise NotImplementedError()

       def exec_state(self, obj):
              raise NotImplementedError()

       def exit_state(self, obj):
              raise NotImplementedError()

enter_state 在obj进入某状态的时候调用——通常用来做一些初始化工作；exit_state也离开某状态的时候调用——通常做一些清理工作；而 exec_state则在每一帧的时候都会被调用，通常做一些必要的工作，如检测自己的消息队列并处理消息等。在stop_fsm和run_fsm两个类的exec_state函数中，就调用了对象的stop和go函数，让汽车保持原有的状态。
至现在为止，Car还没有接触到FSM，所以我们需要提供一个接口，可以让它拥有一个FSM：
       def attach_fsm(self, state, fsm):
              self.fsm = fsm
              self.curr_state = state

我们还需要为Car提供一个状态转换函数：
       def change_state(self, new_state, new_fsm):
              self.curr_state = new_state
              self.fsm.exit_state(self)
              self.fsm = new_fsm
              self.fsm.enter_state(self)
              self.fsm.exec_state(self)

为Car提供一个保持状态的函数：
       def keep_state(self):
              self.fsm.exec_state(self)

现在只有两个状态，但我们知道需求随时会改动，所以我们最好弄一个状态机管理器来管理这些状态：
class fsm_mgr(object):
       def __init__(self):
              self._fsms = {}
              self._fsms[0] = stop_fsm()
              self._fsms[1] = run_fsm()

       def get_fsm(self, state):
              return self._fsms[state]

       def frame(self, objs, state):
              for obj in objs:
                     if state == obj.curr_state:
                            obj.keep_state()
                     else:
                            obj.change_state(state, self._fsms[state])

fsm_mgr最重要的函数就是frame，在每一帧都被调用。在这里，frame根据对象现在的状态和当前的输入决定让对象保持状态或者改变状态。
这时候，我们的实例基本上完成了。但我们还要做一件事，就是建立一个世界（World）来驱动状态机：
class World(object):
       def init(self):
              self._cars = []
              self._fsm_mgr = fsm_mgr()
              self.__init_car()

       def __init_car(self):
              for i in xrange(1):   # 生产汽车
                     tmp = Car()
                     tmp.attach_fsm(0, self._fsm_mgr.get_fsm(0))
                     self._cars.append(tmp)

       def __frame(self):
              self._fsm_mgr.frame(self._cars, state_factory())

       def run(self):
              while True:
                     self.__frame()
                     sleep(0.5)

从代码可见，World里有Car对象，fsm_mgr对象；在run函数里，每0.5s执行一次__frame函数（FPS = 2），而__frame函数只是驱动了fsm_mgr来刷新对象，新的命令是从state_factory函数里取出来的，这个函数用以模拟驾驶员的操作（按下Stop或者Run按钮之一）：
def state_factory():
       return random.randint(0, 1)

现在我们就要初始化世界（World）可以跑起我们的FSM了！
if __name__ == "__main__":
       world = World()
       world.init()
       world.run()

用python解释器执行上面的代码，我们可以看到程序不停地输出Car的状态：
......
Car8453392 exit run state!
Car8453392 enter stop state!
Car8453392 in stop state!
Stop!!!
Car8453392 in stop state!
Stop!!!
Car8453392 exit stop state!
Car8453392 enter run state!
Car8453392 in run state!
Goooooo!!!
Car8453392 exit run state!
Car8453392 enter stop state!
Car8453392 in stop state!
Stop!!!
Car8453392 exit stop state!
Car8453392 enter run state!
Car8453392 in run state!
Goooooo!!!
Car8453392 in run state!
Goooooo!!!
Car8453392 exit run state!
Car8453392 enter stop state!
Car8453392 in stop state!
Stop!!!
Car8453392 in stop state!
Stop!!!
Car8453392 exit stop state!
Car8453392 enter run state!
Car8453392 in run state!
Goooooo!!!
......


结论
这时再回头来看看我们之前的问题：
1、玩家想要功能更多的Car，比如掉头。
我们可以通过为Car增加一个调头（back）的方法来执行掉头，然后从base_fsm中继承一个back_fsm来处理调头。之后在fsm_mgr里增加一个back_fsm实例，及让state_factory产生调头指令。听起来似乎比之前while+if的方式还要麻烦不少，其实不然，这里只有 back_fsm和为fsm_mgr增加back_fsm实例才是特有的，其它步骤两种方法都要执行。
2、玩家要更多的Car。
这对于面向对象的FSM实现就太简单了，我们只要把World.__init_car里的生产数量修改一下就行了，要多少有多少。
3、玩家要更多型号的车，如Truck。
从Car派生一个Truck，然后增加装货、卸货的接口。最大的改动在于Truck状态转换的时候需要一些判断，如不能直接从装货状态转换到开动状态，而是装货、停止再开动。
通过这几个简单的问题分析，我们可以看到，使用面向对象的方式来设计FSM，在需求变更的时候，一般都只增删代码，而仍少需要改动已有代码，程序的扩展性、适应性和健壮性都得很大的提高；因此，在世界庞大、物种烦多、状态复杂且条件交错的游戏开发中应用面向对象的FSM实在是明智之选。还有一点，面向对象的 FSM可以非常容易地模拟消息机制，这有利于模块清晰化，更容易设计出正交的程序。

[收藏到我的网摘]   恋花蝶发表于 2007年02月15日 16:43:00

只看该作者 · 2007-11-19 14:00

能把逻辑关系描述清楚，应该就能把程序写出来。
另外，状态机是针对时序逻辑而不是组合逻辑的。

2万 · 2007-11-19 14:05

楼主只要能说明白C++对比C来说真正的突破就已经是达人啦。

只看该作者 · 2007-11-19 14:10

当初被BC3.1 MFC10 中一个“类” 的概念搞得举手投降，多年后才明白，类不过就是“结构” 罢了！唉，

2万 · 2007-11-19 14:14

提示一句：“结构”和“对象”有着本质的不同。呵呵

只看该作者 · 2007-11-19 14:35

横着写(在事件中判断状态)
竖着写(在状态中判断事件)

----- 阿冰的bolg

MD 试试把状态完全细分-----自己都觉得笨，像钝刀刮肉。

只看该作者 · 2007-11-19 15:48

2万 · 2007-11-19 17:15

void                 main(void)
{
Initsys();
while(1)
{
controlport=controlbuf;
if(bmain){
          rst_wdt;
          bmain=false;
          Dispflash();
          Getkeyval();
          Display();
          Time();
          switch(maincase)
          {
          case  meaT:       Measure();
                            break;
          case  keyact:     Keyscan();
                            break;
          case  wr_ee:      WriteEE();
                            break;
          case  wr_ee_alarm:WriteEEalarm();
                            break;
          case  rd_Err:     break;
          case  rd:         ReadEE();
                            break;
          default:          rst_mcu;
                            break;
          }
          SwitchState();
          }
}
}

只看该作者 · 2007-11-19 20:54

不错，是个原型，多努力。

看你签名是近来升级了哦！恭喜哈

脑浆不够用，寻求理论、方**上的帮助。

相关帖子

先爆点料，让大家先睹为快

状态机？呵呵。

lz搜一搜“状态机＋状态转移图”，应该就明白了

TO HWM

LZ：内涵全在里面了，但展开就够上几堂课拉。

呵呵 谢谢 HWM 指教

哈哈，偶也没去学过什么状态机，我就按照我的需要去写程

状态机非我发明，所以此定义非我所属，呵呵

看看……

脑浆不够用，寻求理论、方**上的帮助。

关键把你想要做的事情搞清楚（细分）就可以了

先转一篇.net的博文过来：一定要刺激MCU的达人出手！

楼主不如描述一下你的问题

呵呵，不用达人出手，

HWM 千万别提C++

16楼：非也，看来LZ离达人还有一段距离啊。

!~

看来坛子里的大大真得搞一个状态机的专题，哦也很想学！

俺献个丑，俺的一个MAIN程序……

TO: yewuyi

技术领袖奖章

十世金身

坚毅之洋流

终身成就奖章

荣誉元老奖章

以坛为家

精英会员奖章

奔腾之江水

技术高手奖章

永恒之光奖章

技术导师奖章

七世轮回

甘甜之泉水

技术奇才奖章

社区建设奖章

伴坛终老

呵呵谢谢 HWM 指教