分层FSM父子状态划分与优化

分层FSM父子状态划分与优化

郑丹雅

（浙江工业大学 计算机技术与软件工程学院，浙江 杭州 310014）

摘要：游戏的本质是玩家通过操作达到环境状态改变，从而将消息传递给周围entity，实现周围entity状态改变，再反馈给玩家由玩家做出相应决策，其本质是输入与输出的结合。而能够实现这一要求的技术基础是FSM，其又可划分为单层FSM和多层FSM，多层FSM通过对行为逻辑的细致划分达到entity不同状态之间的优质转化，而对转化context的剥离与父子状态间的联系优化让分层FSM在性能上更加优秀。

关键词：有限状态机、状态分层、状态机优化

有限状态机概要

某一单位的行为状态可以有两种集合划分，有限集合或无限，而有限状态即为有限状态机的讨论基础。有限状态机在任一时刻均处于有限状态集合中的某一状态，其启动时位于“起始状态”，而在运行结束后进入“消亡状态”，当前状态机根据获取的输入指令（环境因素改变），从当前状态转换为另一状态或仍保持当前状态。

有限状态机实现的数学基础是离散数据和映射，映射表示A集合中的元素满足某一个确定的对应关系f后能在B集合找到唯一与之相对应的元素，那么我们可以称A->B为集合A到集合B的一个映射。

图2 状态转化原理图表

图4 状态机基础函数伪码

在单层有限状态机中，状态机的建立可以分为动态与静态两种方式，静态可以描述为A->B->C,只要不更新顺序结构，状态之间的迁移逻辑将永远使这种顺序；而动态是需要根据环境，即context，激活相应的状态，比如玩家踏入怪物的警觉范围，怪物进入战斗模式，玩家跑出怪物的警觉范围脱离战斗模式。而有限状态机的触发信 可以分为以下几类：进入、退出、状态迁移、由输入触发、超时。

分层状态机及其父子状态划分

传统有限状态机仅能满足少量状态下的状态转化要求，而在状态基数过大时，需要列举大量的状态，使得程序在内存、处理性能等方面的优化不满足开发的低复杂度低占用要求。单层状态机在需求增加时，就需要增加状态或者代码分支，故我们引入了分层的概念。

分层状态机，顾名思义，状态群从原有的平行并列关系转化为树状层级关系。在划分父子关系前我们要先明确父子关系划分的几点要求：子状态一定由父状态驱动，父状态需要子状态的feedback来确定子状态的转化或保持，同时需要根据子状态列表的进行状态为自身设定status，反馈给上级操作后确定父状态的进行或转化。在划分状态中，首先这个状态必须是能被外界所观察到的，其次独立状态必须有输入和输出的差异性，这是架构状态机之前的状态划分工作。那么架构状态的层次结构需要我们对状态本身的性质深入分析，这里将其总结为状态特性：

第一，可打断性。能够被打断的状态不一定是父状态，不能被打断的状态一定是子状态。“打断”的定义是在状态进行中切换到其他状态。此处举例说明，entity在进行“就餐”这个状态的时候，可以选择吃鸡蛋，也可以选择吃胡萝卜，她可以在选择胡萝卜餐盘和鸡蛋餐盘两个状态之间来回切换，但是他不能在吃鸡蛋吃到一半跑去吃胡萝卜，同理也不能在胡萝卜入嘴后跑去吃鸡蛋，所以在这个案例中我们将“吃胡萝卜”、“吃鸡蛋”这两个状态定义为子状态，将“就餐”定义为父状态。第二个例子，entity为怪物，怪物在巡逻过程中可以进行敌军查探模式，或者进行非查探模式，查探模式下感知周围一定距离内entity是否为敌对生物，若感知到敌对生物则进入战斗模式。本例中我们将“巡逻”定义为父状态，将“查探”、“非查探”以及“战斗”定义为子状态。

第二，可扩展性。父状态在定义上是一个抽象的集合概念，其在代码实现中也以抽象类的形式实现，父状态一定是可扩展的，比如“entity与动物互动”，这个“与动物互动”中的“动物”就是一个抽象的集合概念，与动物互动可以分为“与鸟互动”、“与狮子互动”等，故此案例中我们将“与动物互动划分为父状态”，并在其基础上拓展延伸子状态集。

第三，静态分层保证上下逻辑唯一性。若entity进入a1状态，假设子状态a1能被父状态A驱动，那它便不能被父状态B驱动，我们可以采用以下树状结构来表示父子状态之间的层级结构：

图6 分层有限状态机流程（静态和动态）

分层状态机优化

实现了基础的分层功能后，已经相当于在基础的单层状态机优化了一大步，但是状态的迁移仍然需要迁移函数来完成，并且在附加上下文语境的动态状态转化中，context仍需要进一步的分离，以达到减少内存和处理器占用的目的。

首先，我们要理解子状态之间的关系可以是重复执行，比如entity走路，迈左脚和迈右脚是两个不同的状态，但是这两个状态在子状态激活集合中是并存的，也就是说两个状态均被激活，轮流执行，而非先激活A状态执行完毕后删除A，激活B，执行B、删除B……等诸如此类的操作，采取轮转方式可以减少操作。我们要明确语境包含的内容，输入context可能是上一个状态的feedback，输出context又是下一个state的输入，而一个state作为一个最小粒度单元，其概念是输入一个concept后输出一个result。在先前的基础结构中，Enter()与Exit()函数作为接口，其存在的必要性是证明一个状态的开始与退出，同时隐藏内部信息，而在状态执行与context分离的结构下这两个函数可以被状态机丢弃。在优化状态机后，父状态需要实现的功能有：接收来自子状态的反馈（跨帧状态可能需要多次反馈）、通过子状态反馈实现自身状态的设置、向上反馈自身状态、从向上的context中获取信息并将其传递给子状态；子状态需要实现的功能有：将自身状态反馈给父状态。

修改过后的状态驱动接口中仅需要一个进行函数Drive()，而被分离出来的语境单独划分为一个类。

Context类中需要实现的功能有：向下传递信息给父状态机，保证父状态的运行或切换、向上获取玩家指令或其他信息、定义当前个体。根据语境判断当前状态的继续与否。这样我们能够实现动态语境与静态状态的结合。

结  论

在建立分层有限状态机时我们采取可打断性、可拓展性、（静态）逻辑的唯一性作为父子状态的划分标准；在优化时致力于将语境与决策分离，动态的context代表输入的同时也代表输出，而决策行为状态是相对静止的存在。

参考文献：

[1]陈勇.有限状态机的建模与优化设计[J].重庆工学院学 (自然科学版),2007(05):55-58.

[2]徐小良,汪乐宇,周泓.有限状态机的一种实现框架[J].工程设计学 ,2003(05):251-255.

[3]fingerpass．漫谈游戏中的人工智能[ＥＢ／ＯL]．[2015-09-05]．http://www.cnblogs.com/fingerpass/p/discussion-about-game-ai.html．

[4]qq276492716．游戏中分层状态机的实现[ＥＢ／ＯL]．[2014-10-25]．http://blog.csdn.net/qq276592716/article/details/40441443．

[5]AaronBlogs．AI逻辑实现-取舍行为树还是状态机[ＥＢ／ＯL]．[2017-06-17]．https://www.cnblogs.com/AaronBlogs/p/7039816.html．

[6]benxintuzi．有限状态机FSM详解及其实现[ＥＢ／ＯL]．[2015-11-02]．https://www.cnblogs.com/benxintuzi/p/4931258.html．