分层FSM父子状态划分与优化
分层FSM父子状态划分与优化
郑丹雅
（浙江工业大学 计算机技术与软件工程学院，浙江 杭州 310014）
摘要：游戏的本质是玩家通过操作达到环境状态改变，从而将消息传递给周围entity，实现周围entity状态改变，再反馈给玩家由玩家做出相应决策，其本质是输入与输出的结合。而能够实现这一要求的技术基础是FSM，其又可划分为单层FSM和多层FSM，多层FSM通过对行为逻辑的细致划分达到entity不同状态之间的优质转化，而对转化context的剥离与父子状态间的联系优化让分层FSM在性能上更加优秀。
关键词：有限状态机、状态分层、状态机优化
随着AI近年来的广泛普及，与AI融合许久的游戏行业在满足市场与时俱进的需求的同时，也面临着技术的革新，NPC智能化和游戏中entity复杂度的提高是部分游戏开发所追求的经久不衰的主题。那么作为游戏开发中经常用到的模型,有限状态机在未来的游戏设计中更扮演着举足轻重的角色。本文主要研究如何在划分更细小的状态同时保证父子状态逻辑的稳定，同时在保证不过分提高资源占有率的同时优化分层FSM。
有限状态机概要
某一单位的行为状态可以有两种集合划分，有限集合或无限，而有限状态即为有限状态机的讨论基础。有限状态机在任一时刻均处于有限状态集合中的某一状态，其启动时位于“起始状态”，而在运行结束后进入“消亡状态”，当前状态机根据获取的输入指令（环境因素改变），从当前状态转换为另一状态或仍保持当前状态。
有限状态机实现的数学基础是离散数据和映射，映射表示A集合中的元素满足某一个确定的对应关系f后能在B集合找到唯一与之相对应的元素，那么我们可以称A->B为集合A到集合B的一个映射。
图1 映射图表
在单层的有限状态机中，我们可以用以下模型来模拟：
图2 状态转化原理图表
图3 有限状态机流程（静态与动态）
有限状态机基础函数有：Enter()、Exit()、Drive()，即进入状态、退出状态、进行状态，语境单独被剥离出，我们假设现在entity要进行A状态，那么A状态机可以如下定义：
图4 状态机基础函数伪码
在单层有限状态机中，状态机的建立可以分为动态与静态两种方式，静态可以描述为A->B->C,只要不更新顺序结构，状态之间的迁移逻辑将永远使这种顺序；而动态是需要根据环境，即context，**相应的状态，比如玩家踏入怪物的警觉范围，怪物进入战斗模式，玩家跑出怪物的警觉范围脱离战斗模式。而有限状态机的触发信号可以分为以下几类：进入、退出、状态迁移、由输入触发、超时。
分层状态机及其父子状态划分
传统有限状态机仅能满足少量状态下的状态转化要求，而在状态基数过大时，需要列举大量的状态，使得程序在内存、处理性能等方面的优化不满足开发的低复杂度低占用要求。单层状态机在需求增加时，就需要增加状态或者代码分支，故我们引入了分层的概念。
分层状态机，顾名思义，状态群从原有的平行并列关系转化为树状层级关系。在划分父子关系前我们要先明确父子关系划分的几点要求：子状态一定由父状态驱动，父状态需要子状态的feedback来确定子状态的转化或保持，同时需要根据子状态列表的进行状态为自身设定status，反馈给上级操作后确定父状态的进行或转化。在划分状态中，首先这个状态必须是能被外界所观察到的，其次独立状态必须有输入和输出的差异性，这是架构状态机之前的状态划分工作。那么架构状态的层次结构需要我们对状态本身的性质深入分析，这里将其总结为状态特性：
第一，可打断性。能够被打断的状态不一定是父状态，不能被打断的状态一定是子状态。“打断”的定义是在状态进行中切换到其他状态。此处举例说明，entity在进行“就餐”这个状态的时候，可以选择吃鸡蛋，也可以选择吃胡萝卜，她可以在选择胡萝卜餐盘和鸡蛋餐盘两个状态之间来回切换，但是他不能在吃鸡蛋吃到一半跑去吃胡萝卜，同理也不能在胡萝卜入嘴后跑去吃鸡蛋，所以在这个案例中我们将“吃胡萝卜”、“吃鸡蛋”这两个状态定义为子状态，将“就餐”定义为父状态。第二个例子，entity为怪物，怪物在巡逻过程中可以进行敌军查探模式，或者进行非查探模式，查探模式下感知周围一定距离内entity是否为敌对生物，若感知到敌对生物则进入战斗模式。本例中我们将“巡逻”定义为父状态，将“查探”、“非查探”以及“战斗”定义为子状态。
第二，可扩展性。父状态在定义上是一个抽象的集合概念，其在代码实现中也以抽象类的形式实现，父状态一定是可扩展的，比如“entity与动物互动”，这个“与动物互动”中的“动物”就是一个抽象的集合概念，与动物互动可以分为“与鸟互动”、“与狮子互动”等，故此案例中我们将“与动物互动划分为父状态”，并在其基础上拓展延伸子状态集。
第三，静态分层保证上下逻辑唯一性。若entity进入a1状态，假设子状态a1能被父状态A驱动，那它便不能被父状态B驱动，我们可以采用以下树状结构来表示父子状态之间的层级结构：
图5 父子状态的层级结构
其中A、B、C作为ALL的子状态，箭头均其双向。
动态分层FSM需要根据上下文动态变化状态引用。
我们还要明确，父子状态划分后，子状态在以后的需求扩展中可能成为父状态，所以当前父子状态间的关系是绝对的，但是子状态并非绝对的子状态，而是另一种意义上的父状态。
图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.****.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．