Download presentation
Presentation is loading. Please wait.
1
第13章 游戏中的人工智能
2
游戏中的AI 人工智能（Artificial Intelligence，AI），是让计算机有一定的智能，能够与人进行交互的技术。
游戏中应用人工智能可增加游戏的可玩性，如果游戏中没有人工智能，就不会有象棋的人机对战，也不会有逃脱密室的怪物追捕英雄，更不会有网络游戏中玩家与怪兽的激烈战斗。
3
Eg:游戏中的路径搜索
4
1. Android中的路径搜索 深度优先路径搜索DFS 广度优先路径搜索BFS 路径搜索算法—Dijkstra A*算法优化搜索
5
(1)深度优先路径搜索DFS 深度优先搜索DFS在搜索过程中不考虑各个边的开销，只考虑路径的选择。其思路是站在一个连通图的节点上，然后尽可能地沿着一条边深入，当遇到死胡同时进行回溯，然后继续搜索，直到找到目标为止。 （1）从节点1出发，按人为规定的顺序选择一条路径到达节点2，如图8-5中A所示。 （2）在节点2处按之前的规定选择一条路径到达节点3，如图8-5中B所示。 （3）在节点3处仍然继续深入搜索到达节点4，如图8-5中C所示。 （4）当到达节点4时发现没有路可以走了。回溯到节点3查看，当发现节点3仍没有路可走时继续回溯到节点2，在节点2发现通往节点5的边且没有访问过，所以访问节点5，如图8-5中D所示。 （5）而在节点5处无路可走回溯到节点2，经过判断后再回溯到节点1，此时发现节点6没有访问过，则访问节点6，如图8-5中E所示。 （6）接着因节点6没有子节点，所以从节点6回溯到节点1，之后发现节点7没有访问过，则访问节点7，此时图中所有节点全部访问到了，搜索结束，
6
深度优先搜索的基本算法结构：递归实现 Procedure dfs_try(i); For i:=1 to maxr do begin if 子结点mr符合条件 then 产生的子结点mr入栈； if子结点mr是目标结点 then 输出； else dfs_try(i+1); 栈顶元素出栈； End;
7
深度优先搜索S到T的搜索路径 S T S T
8
(2)广度优先路径搜索BFS 广度优先搜索是在游戏中使用较多的一种搜索算法，其基本思路是站在一个节点上，先将所有连接到该节点的节点访问到，然后再继续访问下一层，直到找到目标为止。 （1）站在节点1处，检测所有与节点1相连的边，按一定规则访问到节点2，检测并记录所有与节点2相连的边，如图8-8中A所示。 （2）之后再访问节点3，同样检测并记录所有与节点3相连的节点，如图8-8中B所示。 （3）再访问节点4，如图8-8中C所示。 （4）然后访问节点5，并记录与节点5相连的边，如图8-8中D所示。 （5）同样原理依次再访问节点6、节点7、节点8。如图8-8中E、图8-8中F和图8-8中G所示。 Eg:扫雷游戏
9
BFS – 广度优先搜索 1 2 5 BFS在访问了起始顶点 A 之后, 由 A 出发, 依次访问 A 的各个未被访问过的邻接顶点 B, D,…, C, 然后再顺序访问 B, D, …, C 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，… 如此做下去，直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点。 B E A 4 3 7 D C G 6 H I F 8 9
10
BFS的代码分析 void BFS() { queue<point> q;//队列 q.push(st);//初始点入队列
while(!q.empty())//队列中还有要处理的点 从队列中取出下一个处理的点p； for(p的所有邻接点) if(该邻接点满足搜索条件) q.push(邻接点); 标记该邻接点为已访问； }
11
BFS 广度优先搜索过程 队列变化情况 I 1 2 5 H G F 4 3 7 E D 6 C 8 9 B 箭头表示当前访问节点 搜索完成
A 队列变化情况 G F 4 3 7 D C G E D 6 H I F C 8 9 B 箭头表示当前访问节点 A 指针
12
广度优先搜索S到T的搜索路径 S T S T
13
（3）路径搜索算法—Dijkstra Dijkstra算法是典型的最短路径算法，一般用于求出从一点出发到达另一点的最优路径，但是，因为其遍历运算的节点较多，所以运行效率较低。 出发点（源节点）为节点1，如图8-11所示。 （1）首先将节点1加入到最短路径树中，并且将从它出发的所有边加到搜索边界中，如图8-12所示。 （2）然后查找所有在计算搜索边界中的各个边所指向的节点中到源节点距离最近的点（是节点2），将节点2加入到最短路径树，然后将由节点2出发且到达点不在最短路径树上的边加入到搜索边界，如图8-13所示。 （3）再检查搜索边界上的边所指向的点，计算各点到源节点的距离，节点5距离是3，节点3距离是2.2，因此，将节点3加入到最短路径树，同时将节点3出发的边加入到搜索边界中，如图8-14所示。 （4）再检查搜索边界上的边所指向的点，节点5到源节点的距离是3，节点4到源节点的距离是3.4，因此，将节点5加入到最短路径树，而从节点5出发的边只有一条，但是，这条边指向的源节点为节点1，所以不需要加入到搜索边界上，如图8-15所示。 （5）此时再检测搜索边界中的边所指向的点，发现只有节点4没有访问，且节点4到源节点的距离是3.4，所以，将节点4加入到最短路径树，而从节点4出发的边只有一条，指向节点5，而距源节点的距离为6，比最短路径树中到节点5的距离大，所以不用继续考虑，如图8-16所示。 （6）此时已经访问到所有节点，搜索完成。
14
最短通路问题 Shortest-Path Problems
定义：设图G =<V,E>，给定 , 对G的每条边e， 称W(e)为边e的权。把这样的图称为带权图，记作 设P是G中的一条通路，P中所有边的权之和称为P的长度，记作：
15
最短通路问题 Shortest-Path Problems
例： a b c d 5 12 4 8 20 w(ab)=5， w(aa)=0， w(bd)= ∞， w(ad)=8
16
最短通路问题 Shortest-Path Problems
定义：在一个带权图G中，任给两点u，v，从u到v可能有多条路，在这些路中，所带的权和最小的那条路称为图中从u到v的最短路。这条最短路所带的权和称为u到v的距离，记为d(u,v)。 a b c d 5 12 4 8 20 a到c的路有： (a,b,c)长度为5+4=9; (a,c)长度为12; (a,d,c)长度为8+20= 28。 最短通路为： (a,b,c), d(a,c)=9
17
Dijkstra算法 实现上述距离的路称为u0到S’的最短路。 上述点到点集距离的定义等价于
定义 设G是有限带权图，SV(G)，u0S， S’= V(G) -S，定义u0到S’的距离为 实现上述距离的路称为u0到S’的最短路。 上述点到点集距离的定义等价于
18
Dijkstra算法 例：如图所示，令S={a, b, f}，则S’={c, d, e}， 求d(a, S’)？ a b c d 1 2 5 6 10 f e 4 3 S’ S
19
Dijkstra算法 设u0=a， 取u=a，则w(ac)=∞，w(ad)=10，w(ae)=∞， a b c d 1 2 5 6 10 f e 4 3
20
Dijkstra算法 f e a d b c 2 1 3 4 10 6 5 因而d(a, S’)=2，a到S’的最短路为
取 u=b，则d(a,b)=6，w(bc)=5，w(bd)=∞ w(be)=4， 取 u=f，则d(a,f)=1，w(fc)=1，w(fd)=∞，w(fe)=2 a b c d 1 2 5 6 10 f e 4 3 因而d(a, S’)=2，a到S’的最短路为 （a, f, c）。
21
Dijkstra算法 指导思想：设u0 V, v0 V ,要求u0到v0点的距离，我们通过求u0到图中其它各点的距离。先把V分成两个子集， 一个设为S, S={v|v V, u0到v的距离已求出}， 另一个是S’= V -S。 显然，S，因为至少u0S，算法不断扩大S，直到S= V(或者v0 S) 对任意的v S’= V -{u0}，设l(v)表示从u0仅经过S中的点到v的最短路的带权长度。 若不存在这样的路，置l(v)= ∞。
22
Dijkstra算法 (2)找到uiS’，满足
(1)初始化，令S={u0}，S’= V -S，对 S’中每一个点v, 令l(v)=w(u0,v)； (2)找到uiS’，满足 (3) 若S= V ，则终止；否则令S=S∪{ui}， S’=S’-{ui},对 S’中每一个点v，计算 其中，d(u0,u)对应的最短路，其全部的点均属于S. 转到(2)。
23
Dijkstra算法 b a c d 7 6 2 f e 8 1 4 3 5 u0 g
24
b a c d f e u0 g 7 5 1 8 3 2 4 执行过程: 6 S’ S 7 1 2 ∞ 4 8 abcdefg u0
l(g) l(f) l(e) l(d) l(c) l(b) l(a) S’ S 7 1 2 ∞ 4 8 abcdefg u0 abcdeg u0 f 3 abcdg u0 fe 6 9 abcg u0 fed acg u0 fedb 5 cg u0 fedba c u0 fedbag u0 fedbagc
25
Dijkstra搜索S到T的搜索路径 粗线为搜索结果，细线为搜索过程
26
（4）用A*算法优化搜索 A*算法是一种启发式搜索，所谓启发式搜索，就是利用一个启发因子评估每次寻找的路线的优劣，再决定往哪个节点走。
27
A*算法是一种静态路网中求解最短路最有效的方法。公式表示为：f(n) = g(n) + h(n)
f(n)是从初始点经由节点n到目标点的估价函数 g(n)实在状态空间中从初始节点到n节点的实 际代价 h(n)是从n到目标节点最佳路径的估计代价。 保证找到最短路径（最优解）的条件，关键在于估价函数h(n)的选取： 估价值h(n)<=n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。 如果估价值>实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解
28
常见估价函数 曼哈顿距离 欧氏距离 切比雪夫距离 在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。
例如:在平面上，点P1(x1,y1)与点P2(x2,y2)的曼哈顿距离为|x1-x2|+|y1-y2| 欧氏距离 在m维空间中两个点之间的真实距离。在二维和三维空间中的欧氏距离就是两点之间的距离。 例如在平面上，点P1(x1,y1)与点P2(x2,y2)的欧氏距离为：sqrt((x1-x2)^2+(y1-y2)^2) 切比雪夫距离 是两个向量之间各分量差值的最大值。 例如在平面上，点P1(x1,y1)与点P2(x2,y2)的切比雪夫距离为：max(|x1-x2|,|y1-y2|)
37
2.有限状态机 有限状态机就是一个具有有限数量状态，并且能够根据相应的操作从一个状态变换到另一个状态，而在同一时刻只能处在一种状态下的智能体。例如： 魔兽世界中的NPC就应用了有限状态机，它会根据不同的情况具有移动到位、巡逻、沿路前进等状态。 QQ宠物也是一个典型的有限状态机的例子，很久没有喂食它会饥饿，很久没有理它他会心情不好，而如果饲养不好它还会生病。 雷电中的导弹也可以理解成是一个有限状态机，具有移动、碰撞、消失等状态。 冒险类游戏中的怪物也应用了有限状态机，当与玩家战斗时，当玩家比较强时怪物会选择逃跑，而当玩家比较弱时，怪物会选择攻击。
38
洗澡 逗弄 寻找
39
状态机的引入 状态机理论最初的发展在数字电路设计领域。
在数字电路方面，根据输出是否与输入信号有关，状态机可以划分为Mealy型和Moore型状态机。 Moore型状态机的输出只和当前状态有关，和输入无关。 Mealy型状态机的输入是由当前状态和输入共同决定。 而在软件设计领域，状态机的理论俨然已经自成一体，它经常用来描述一些复杂的算法，表明一些算法的内部的结构和流程，更多的关注于程序对象的执行顺序。 2017/3/22
40
静态顺序结构 动态结构 2017/3/22
41
有限状态机 有限自动机（Finite Automata Machine）是计算机科学的重要基石，它在软件开发领域内通常被称作有限状态机（Finite State Machine），是一种应用非常广泛的软件设计模式。 有限状态机的作用主要是描述对象在它的生命周期内所经历的状态序列，以及如何响应来自外界的各种事件。 在现实中，有许多事情可以用有限个状态来表达，如: 红绿灯、电话机等等。 其实，在资讯领域中，很多事情都是由有限的状态所组成，再由于不同的输入而衍生出各个状态。 2017/3/22
42
有限状态机 有限状态机FSM思想广泛应用于硬件控制电路设计，也是软件上常用的一种处理方法(软件上称为FMM--有限消息机)。它把复杂的控制逻辑分解成有限个稳定状态，在每个状态上判断事件，变连续处理为离散数字处理，符合计算机的工作特点。同时，因为有限状态机具有有限个状态，所以可以在实际的工程上实现。但这并不意味着其只能进行有限次的处理，相反，有限状态机是闭环系统，有限无穷，可以用有限的状态，处理无穷的事务。 2017/3/22
43
有限状态机—例1 红绿灯 红绿灯运作的原理相当简单，从一开始绿灯，经过一段时间后，将变为黄灯， 再隔一会儿，就会变成红灯，如此不断反覆。 其FSM如下。 2017/3/22
44
有限状态机—例2 自动贩售机 假设有简单的一自动贩卖机贩售两类商品，一类售价20元，另一类售价50元。 如果该贩卖机只能辨识10元及50元硬币。 一开始机器处于Hello的状态，当投入10元时，机器会进入余额不足的状态，直到投入的金额大于20元为止。 如果一次投入50元，则可以选择所有的产品，否则就只能选择20元的产品。 完成选择后，将会卖出商品并且找回剩余的零钱，随后，机器又将返回初始的状态。 其FSM如下。 2017/3/22
45
基本概念 在描述有限状态机时，常会碰到的几个基本概念：
状态（State） 指的是对象在其生命周期中的一种状况，处于某个特定状态中的对象必然会满足某些条件、执行某些动作或者是等待某些事件。 事件（Event） 指的是在时间和空间上占有一定位置，并且对状态机来讲是有意义的那些事情。事件通常会引起状态的变迁，促使状态机从一种状态切换到另一种状态。 转换（Transition） 指的是两个状态之间的一种关系，表明对象将在第一个状态中执行一定的动作，并将在某个事件发生同时某个特定条件满足时进入第二个状态。 动作（Action） 指的是状态机中可以执行的那些原子操作，所谓原子操作指的是它们在运行的过程中不能被其他消息所中断，必须一直执行下去。 2017/3/22
46
有限状态机模型 通信协议建模 优点：简单明了，比较精确。 缺点：对许多复杂的协议，事件数和状态数会剧增，处理困难。
基本出发点：认为通信协议主要是由响应多个“事件”的相对简单的处理过程组成。 状态转移图 优点：简单明了，比较精确。 缺点：对许多复杂的协议，事件数和状态数会剧增，处理困难。 2017/3/22
47
为什么使用有限状态机 在面向对象的软件系统中，一个对象无论多么简单或者多么复杂，都必然会经历一个从开始创建到最终消亡的完整过程，这通常被称为对象的生命周期。 对象在其生命期内是不可能完全孤立的，它必须通过发送消息来影响其它对象，或者通过接受消息来改变自身。 2017/3/22
48
为什么使用有限状态机 游戏引擎是有限状态机最为成功的应用领域之一，由于设计良好的状态机能够被用来取代部分的人工智能算法，因此游戏中的每个角色或者器件都有可能内嵌一个状态机。 考虑RPG游戏中城门这样一个简单的对象，它具有打开（Opened）、 关闭（Closed）、上锁（Locked）、解锁（Unlocked）四种状态。当玩 家到达一个处于状态Locked的门时，如果此时他已经找到了用来开门 的钥匙，那么他就可以利用它将门的当前状态转变为Unlocked，进一步 还可以通过旋转门上的把手将其状态转变为Opened，从而成功进入城 内。 2017/3/22
49
确定的有限状态机 一个DFA M是一个五元组，记作 M = (S, , f, S0, Z)，其中
1) S = {状态i}，S是一个有限集，其中的每一个元素称为一个状态 2) = {输入字符i}，是一个有穷字母表，它的每一个元素称为一个输入字符 3) f : S × → S，f 是转换函数，表示某状态接受某个输入字符所到达的状态，如：f(p,a) = q，p，qS，a 4) S0 S， S0是S中的元素，是唯一的一个初态 5) ZS，且 Z ，Z是S的一个子集，是一个终态集，或叫结束集 2017/3/22
50
确定的有限状态机 1 3 a b c d 2 左侧的状态图，在数学上称作DFA，其形式化定义为： M=(S, , f, S0, Z)
1 3 a b c d 2 左侧的状态图，在数学上称作DFA，其形式化定义为： M=(S, , f, S0, Z) 其中，S = {0 , 1 , 2 , 3 } = {a , b , c , d } S0 = Z = {3} f: 源状态 输入 目的状态 a 1 C 2 d b 3 2017/3/22
51
不确定的有限状态机 一个NFA M定义为 M = (S, , f, S0, Z) f : S × → (S)， P Q N a
除 f 外其余成员与 DFA 相同，f定义为 f : S × → (S)， 其中 (S) 为集合S的幂集合，即有 |(S)| = 2^|S| f 表示某状态接受某个字母所到达的状态集合 如：f(p,a) = {q,m} p,q,m K, a P Q N a Q N P Q P Q 2017/3/22
52
不确定的有限状态机 S A B C a b a,b f : K × → (K) 源状态 输入 目的状态集合 S a {A, C} A
2017/3/22
53
控制城门的状态机 2017/3/22
54
主要内容 1. 有限状态机的基本概念 2. 有限状态机编程方法 2017/3/22
55
手工编写状态机 与其他常用的设计模式有所不同，程序员想要在自己的 软件系统中加入状态机时，必须再额外编写一部分用于 逻辑控制的代码，如果系统足够复杂的话，这部分代码 实现和维护起来还是相当困难的。 在实现有限状态机时，使用switch语句是最简单也是最 直接的一种方式，其基本思路是为状态机中的每一种状 态都设置一个case分支，专门用于对该状态进行控制。 学习doorFSM工程，如何编程实现有限状态机。 2017/3/22
56
状态机实现 switch/case if/else方式实现。用于少量状态（3个及其以下）的时候，不需要引入专门的状态机模块。这种方式不能编写通用的状态机模块，不再多说。 面向过程方式：宏是实现面向过程方式的通用方式。虽然在状态机层面还是可以用面向对象的方式封装，这里还是把它称为面向过程的方式。 2017/3/22
57
手工编写状态机 在很长一段时期内，使用switch语句一直是实现有限状态机的唯一方法，甚至像编译器这样复杂的软件系统，大部分也都直接采用这种实现方式。但之后随着状态机应用的逐渐深入，构造出来的状态机越来越复杂，这种方法也开始面临各种严峻的考验。如果状态机中的状态非常多，或者状态之间的转换关系异常复杂，那么简单地使用switch语句构造出来的状态机将是不可维护的。 2017/3/22
58
// 当前状态转换为Opened changeState(Opened); } // 检查是否有LockDoor事件
// 处理状态Closed的分支 case (Closed): { // 执行动作Close close(); // 检查是否有OpenDoor事件 if (openDoor()) { // 当前状态转换为Opened changeState(Opened); } // 检查是否有LockDoor事件 if (lockDoor()) { // 当前状态转换为Locked changeState(Locked); } break; } switch (state) { // 处理状态Opened的分支 case (Opened): {// 执行动作Open open(); // 检查是否有CloseDoor事件 if (closeDoor()) { // 当前状态转换为Closed changeState(Closed) } break; } 2017/3/22
59
使用switch语句实现的有限状态机的确能够很好地工作，但代码的可读性并不十分理想，主要原因是在实现状态之间的转换时，检查转换条件和进行状态转换都是混杂在当前状态中来完成的。
从代码重构的角度来讲，此时更好的做法是引入checkStateChange()和performStateChange()两个函数，专门用来对转换条件进行检查，以及激活转换时所需要执行的各种动作。 2017/3/22
60
if (checkStateChange()) // 对状态机的状态进行转换 performStateChange(); } break;
switch (state) { // 处理状态Opened的分支 case (Opened): { // 执行动作Open open(); // 检查是否有激发状态转换的事件产生 if (checkStateChange()) // 对状态机的状态进行转换 performStateChange(); } break; 2017/3/22
61
void DoorFSM::processEvent( Event e ) { States yOld = doorState;
//outcome actions doorState = Locked; pass = true; } else if( e == Open ) { doorState = Opened; break; case Locked: if( e == Unlock ) doorState = Unlocked; case Opened: if( e == Close ) doorState = Closed; void DoorFSM::processEvent( Event e ) { States yOld = doorState; bool pass = false; switch( yOld ) { //transitions case Closed: if( e == Open ) //outcome actions doorState = Opened; pass = true; } else if( e == Lock ) doorState = Locked; break; case Unlocked: if( e == Lock ) 2017/3/22
62
自动生成状态机 为实用的软件系统编写状态机并不是一件十分轻松的事情，特别是 当状态机本身比较复杂的时候尤其如此。人们开始尝试开发一些工 具来自动生成有限状态机的框架代码，而在Linux下就有一个挺不 错的选择──FSME（Finite State Machine Editor）。 FSME是一个基于Qt的有限状态机工具，它能够让用户通过图形化 的方式来对程序中所需要的状态机进行建模，并且还能够自动生成 用C++或者Python实现的状态机框架代码。 2017/3/22
63
可视化的FSME 2017/3/22
64
状态机建模 首先运行fsme命令来启动状态机编辑器，然后单击工具栏上" "New"按钮来创建一个新的状态机。FSME中用于构建状态机的基本元素一共有五种：事件（Event）、输入（Input）、输出（Output）、状态（State）和转换（Transition），在界面左边的树形列表中可以找到其中的四种。 2017/3/22
65
状态建模 在FSME界面左边的树形列表中选择"States"项，然后按下键盘上的Insert键来插入一个新的状态，接着在右下方的"Name"文本框中输入状态的名称，再在右上方的绘图区域单击该状态所要放置的位置，一个新的状态就创建好了。用同样的办法可以添加状态机所需要的所有状态。 2017/3/22
66
状态转换 状态转换是整个建模过程中最重要的一个部分，它用来定义有限状态机中的一个状态是如何切换到另一个状态的。例如，当用来控制城门的状态机处于Opened状态时，如果此时有Close事件产生，那么状态机的当前状态将切换到Closed状态，这样一个完整的过程在状态机模型中可以用closeDoor这样一个转换来进行描述。 2017/3/22
67
状态转换 要在FSME中添加这样一个转换，首先需要在界面左边的树形列表中选" "States"下的"Opened"项，然后按下键盘上的Insert键来添加一个新的转换，接着在右下角的"Name"文本框中输入转换的名字"closeDoor"，在"Condition"文本框中输入"Close"表明触发该转换的条件是事件Close的产生，在"Target"下拉框中选择"Closed"项表明该转换发生后状态机将被切换到Closed状态，最后再单击"Apply"按钮，一个新的状态转换关系就定义好了，如图5所示。用同样的办法可以添加状态机所需要的所有转换。 2017/3/22
68
事件建模 在FSME界面左边的树形列表中选" "Events"项，然后按下键盘上的Insert键来添加一个新的事件，接着在右下方的"Name"文本框中输入事件的名称，再单击"Apply"按钮，一个新的事件就创建好了。用同样的办法可以添加状态机所需要的所有事件 2017/3/22
69
自动生成状态机 使用FSME不仅能够进行可视化的状态机建模，更重要的是它还可以根据得到的模型自动生成用C++或者Python实现的状态机框架。首先在FSME界面左边的树形列表中选择"Root"项，然后在右下角的"Name"文本框中输入状态机的名字"DoorFSM"，再从"Initial State"下拉列表中选择状态"Opened"作为状态机的初始化状态。 2017/3/22
70
在将状态机模型保存为door.fsm文件之后，使用下面的命令可以生成包含有状态机定义的头文件：
code]$ fsmc door.fsm -d -o DoorFSM. 进一步还可以生成包含有状态机实现的框架代码： code]$ fsmc door.fsm -d -impl DoorFSM.h -o DoorFSM.cpp 如果想对生成的状态机进行验证，只需要再手工编写一段用于测试的代码就可以了： /* * TestFSM.cpp * 测试生成的状态机框架 */ #include “DoorFSM.h” int main() { DoorFSM door; door.A(DoorFSM::Close); door.A(DoorFSM::Lock); door.A(DoorFSM::Unlock); door.A(DoorFSM::Open); } 2017/3/22
71
使用下面的命令能够将生成的状态机框架和测试代码编译成一个可执行文件：
有限状态机是由事件来进行驱动的，在FSME生成的状态机框架代码中，方法A()可以被用来向状态机发送相应的事件，从而提供状态机正常运转所需要的"动力"。状态机负责在其内部维护一个事件队列，所有到达的事件都会先被放到事件队列中进行等候，从而能够保证它们将按照到达的先后顺序被依次处理。在处理每一个到达的事件时，状态机都会根据自己当前所处的状态，检查与该状态对应的转换条件是否已经被满足，如果满足的话则激活相应的状态转换过程。 使用下面的命令能够将生成的状态机框架和测试代码编译成一个可执行文件： code]$ g++ DoorFSM.cpp TestFSM.cpp -o fsm 2017/3/22
72
小结 在面向对象的软件系统中，有些对象具有非常复杂的生命周期模型，使用有限状态机是描述这类对象最好的方法。
作为一种软件设计模式，有限状态机的概念虽然不算复杂，实现起来也并不困难，但它的问题是当状态机的模型复杂到一定的程度之后，会带来实现和维护上的困难。 Linux下的FSME是一个可视化的有限状态机建模工具，而且支持状态机框架代码的自动生成，借助它可以更加轻松地构建基于有限状态机的应用系统。 2017/3/22
Similar presentations
