层次化状态机的讨论


最近和一个同事讨论状态机的问题,记录一下。

我们知道状态机是AI(当然,不光是AI了)中常用的一种架构,有很多中实现方式,总体来说对于表达简单逻辑,还是很有帮助的,而且实现简单,甚至用一个switch-case就可以了,但在实践中状态机有一个致命的缺点,当状态一旦多了之后,它的跳转就会变的不可维护,假设有n个状态的话,那我们就需要维护最多n*n的跳转链接(因为状态机允许自己跳转自己),而且对于当前处在的状态而言,我不能知道我的跳转历史,也就是说,我很难知道为什么我会在这个状态里。这也就是为什么行为树现在成为相对主流的AI架构的原因。下图就演示了多状态间的跳转链接,对于AI程序员来说是非常头疼的。

shit-fsm

所以一般而言,除非是只有两三个状态的简单状态机,如果想要用状态机作为AI整体架构的话,现在都会选择层次化状态机结构(HFSM),并在一定程度上规范状态机的跳转行为。据我所知,微软的著名游戏光环2(Halo2)里就用到了层次化状态机的结构。HFSM就是为了减少跳转链接而做出的努力,举个决策小狗行为的例子,我们对小狗定义了有很多行为,比如跑,吃饭,睡觉,咆哮,撒娇,摇尾巴等等,如果每个行为都是一个状态,用常规状态机的话,我们就需要在这些状态间定义跳转,比如在“跑”的状态下,如果累了,那就跳转到“睡觉”状态,再如,在“撒娇”的状态下,如果感到有威胁,那就跳转到“咆哮”的状态等等,我们会考量每一个状态间的关系,定义所有的跳转链接,建立这样一个状态机。如果用层次化的状态机的话,我们就先会把这些行为“分类”,把几个小状态归并到一个状态里,然后再定义高层状态和高层状态中内部小状态的跳转链接,可能这样说有点晕,还是看图吧

hfsm

从上图可以看到,其实层次化状态机从某种程度上,就是限制了状态机的跳转,而且状态内的状态是不需要关心外部状态的跳转的,这样也做到了无关状态间的隔离,比如对于小狗来说,我们可以把小狗的状态先定义为疲劳,开心,愤怒,然后这些状态里再定义小状态,比如在开心的状态中,有撒桥,摇尾巴等小状态,这样我们在外部只需要关心三个状态的跳转(疲劳,开心,愤怒),在每个状态的内部只需要关心自己的小状态的跳转就可以了。这样就大大的降低了状态机的复杂度,另外,如果觉得两层的状态机还是状态太多的话,可以定义更多的状态层次以降低跳转链接数。

说回到和同事讨论的事情,当然同事的需求并不是用在AI中,是为了处理UI和网络异步请求的问题,我们知道,在网络游戏的UI中,经常需要给网络发送异步请求,然后得一些数据,正因为这些请求是异步的,所以需要在发送后等待网络返回结果,当这些请求很多的时候,很容易在UI端产生混乱(所以,一般来说,在项目中UI的bug是最多的:)),所以他提出了一种结构来改善这样的问题,总结下来,其实就类似于这种AI中常用的这种层次化状态机的概念,不过针对他的需求,还增加了一个并行的概念,也就是在一个状态内部,可能有多个同时运行的状态机(因为有同时多个的网络异步请求),所以当收到一个跳转请求或者消息的时候,还需要决定是哪个状态机需要跳转。另外为了防止跳转混乱,我们还谈到给状态机加更多跳转限制,增加语义支持等等问题。

最后,对于状态机,列出一些小的tips作为总结,希望对大家有所帮助

  • 要为状态定义入口动作/出口动作
  • 要详细设计每一个状态,列出层次化状态结构
  • 针对具体问题,严格限制状态跳转的请求
  • 同一层次的状态数量不宜超过5个
  • 记录每一次的跳转历史,方便调试
  • 可能的话,最好使用编辑器来编辑状态机

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————



(已被阅读8,530次)

7 评论

    1. “层”本身也是一个状态,“层”内部是一个独立的状态机,所以
      1、只要满足A层的转移触发即可从A层跳转,不用管子状态,但是要依次执行子状态的退出
      2、进入B层就相当于执行B层FSM的start,直接进入初始状态

发表评论

电子邮件地址不会被公开。

Copyright © 2011-2017 AI分享站    登录