求知 文章 文库 Lib 视频 iPerson 课程 认证 咨询 工具 讲座 Modeler   Code  
会员   
 
  
 
 
     
   
分享到
从有限状态机(FSM)到行为树(Behavior Tree)
 
作者 Finney,火龙果软件    发布于 2013-10-29
 

选这次主题,要感谢一位网友的来信,他询问了一些如何将有限状态机转成行为树的问题,当时,我回信给了一些建议,但后来我仔细想了一下,觉得可能说得还不够全面,所以我就想通过这篇文章,来整理出一些比较典型的转化“模板”,给有这方面疑惑的朋友一些帮助,如果有朋友有一些自己的见解的,可以在后面留言,我们一起讨论。

有限状态机维护了一张图,图的节点是一个个的状态,节点和节点的连线是状态间根据一定的规则做的状态转换,每一个状态内的逻辑都可以简要描述为:

如果满足条件1,则跳转到状态1

如果满足条件2,则跳转到状态2

否则,不做跳转,维持当前状态

稍作整理的话,我们可以对状态机的几种跳转的情况一一描述出来,然后看看如果将这些情况用行为树来表示的话,可以怎么做。这就是我前面说的“转化模板”,当然我不能保证我下面列出的是状态机的所有可能情况,如果大家在实践中发现还有其他的情况,欢迎留言,我随时更新。

在这之前,我们可以先回忆一些关于行为树的一些概念(可以参考1,2)

控制节点:选择节点,序列节点,并行节点,等等

行为节点:两种运行状态,“运行中”和“完成”

前提条件

模式1:当处在任何状态中,一旦某条件满足,即跳转到某个特定的状态。

比如,在状态机中的一些错误处理,经常会用到上面的这种模式,当状态在运行过程中,发生了某些异常,那一般,我们会把状态机跳转到某个异常状态。这种情况,我们可以用到带优先级的选择节点(Priority Selector)方式,如下图,可以看到,我们把状态c作为行为树里的行为节点,跳转条件(Condition1)作为这个节点的前提(Precondition)。

再用上面举到的错误处理的例子,在状态机中,我们一般会这样写:

STATE A::Update()
2: {
3: ...
4: if(error)
5: {
6: return TO_ERROR_STATE();
7: }
8: ...
9: return UNCHANGED_STATE();
10: }

转换到行为树中,我们会通过外部的黑板来做通信(可以参考这里),在行为节点a中,我们会这样写

EXECUTE_STATE A::Execute(BlackBoard& out)
2: {
3: ...
4: if(error)
5: {
6: out.error = error;
7: return EXECUTE_STATE_FINISH;
8: }
9: ...
10: return EXECUTE_STATE_RUNNING;
11: }

然后对于节点c的前提里,我们来读取黑板里的error值

 bool Condition1::IsTrue(const BlackBoard& in) const
2: {
3: return in.error == true;
4: }

模式2:对于同一个跳转条件,处在不同的状态会有不同的跳转

比如,我们有两个状态,a和b,他们都对同一个跳转条件作出响应,但和模式1不同的是,a对跳转到状态c,而b会跳转到状态d,换句话说,这是一种带有上下文的状态跳转方式。对于这种情况,可以用到序列节点的相关特性,如下图

序列节点中,当前一个节点运行完成后,会执行下一个节点,利用此特性,在上图中可以看到,我们在a中,当满足条件Condition1的时候,则返回“完成”,那行为树就会自动跳转到c节点中,参考代码如下:

EXECUTE_STATE A::Execute(BlackBoard& out)
2: {
3: ...
4: if(condition1 == true)
5: {
6: return EXECUTE_STATE_FINISH;
7: }
8: ...
9: return EXECUTE_STATE_RUNNING;
10: }

对于这种模式的另一种转化,可以不用序列节点,还是用到选择和前提的组合,但我们在前提中加上一个当前状态的附加条件,如下图

在第二层的前提中,我们可以这样写

bool InACState::IsTrue(const BlackBoard& in)
2: {
3: return in.current_running_node = A::GetID() ||
4: in.current_running_node = C::GetID();
5: }
6: bool InBDState::IsTrue(const BlackBoard& in)
7: {
8: return in.current_running_node = B::GetID() ||
9: in.current_running_node = D::GetID();
10: }

这样对于c的前提就是Condition1和InACState的“与”(回想一下前提的相关内容)。由于我们保留了上下文的信息,所以通过对于前提的组合,我们就转化了这种模式的状态机。

模式3:根据条件跳转到多个状态,包括自跳转

这是在状态机里最常见的模式,由于是基于条件的跳转,所以可以非常方便的用选择节点和前提的组合来描述,特别值得注意的是,对于自跳转而言,其实就是维持了当前的状态,所以,在构建行为树的时候,我们不需要特别考虑自跳转的转换。如下图所描述了,我们先用序列节点来保证跳转的上下文(可以参考模式2中的相关内容),这里用到的另一个技巧是,我们会在状态a结束的时候,在黑板中记录其结束的原因,以供后续的选择节点来选择。另外,我们在第二层选择节点第一次用到了非优先级的选择节点,和带优先级的选择节点不同,它每次都会从上一次所能运行的节点来运行,而不是每次都从头开始选择。

当然,和模式2类似的是,我们也可以不用序列节点,而是单纯的用选择节点,这样的话,作为默认状态的状态a就需要处在选择节点的最后一个,因为仅当所有跳转条件都不满足的时候,我们才会维持在当前的状态。如上图的下面那颗行为树那样。请仔细查看,我在前三个节点对于前提的定义,除了本身的跳转条件外,还加上了一个额外的条件,InAXState,它保证了仅在上一次运行的是A状态或自身的时候,我们才会运行当前的节点,这样就保证了和原本状态机描述是一致的。

模式4:循环跳转

在状态机中存在这样一种模式,在状态a中,根据某条件1,会跳转到状态b中,而在状态b的时候,又会根据某条件2,跳转到状态a,产生了这样一个跳转的“环”。显而易见的是,行为树是一种树形结构,而带环的状态机是一种图的结构,所以对于这种情况,我想了下,觉得需要引入一种新的选择节点,我称之为动态优先级选择节点(Dynamic Priority Selector),这种选择节点的工作原理是,永远把当前运行的节点作为最低优先级的节点来处理。如下图

当我们在节点a的时候,我们会先判断b的前提,当b的前提满足的时候,我们会运行节点b,下一帧再进来的时候,由于现在运行的是节点b,那它就是最低优先级的,所以,我们会先判断节点a的前提,满足的话,就运行节点a,不满足则继续运行节点b,依次类推。下面是我写的相关代码,可以给大家参考。

void DynamicPrioritySelector::Test(const Blackboard& in) const
 2: {
 3:     bool hasRunningChild = IsValid(m_iCurrentRunningChildIndex);
 4:     int nextRunningChild = -1;
 5:     for(int i = 0; i < m_ChildNodes.Count(); ++i)
 6:     {
 7:         if(hasRunningChild &&
 8:            m_iCurrentRunningChildIndex == i)
 9:         {
 10:             continue;
 11:         }
 12:         else
 13:         {
 14:             if(m_ChildNodes[i]->Test(in))
 15:             {
 16:                 nextRunningChild = i;
 17:                 break;
 18:             }
 19:         }
 20:     }
 21:     if(IsValid(nextRunningChild))
 22:     {
 23:         m_iCurrentRunningChildIndex = nextRunningChild;
 24:     }
 25:     else
 26:     {
 27:         //最后测试当前运行的子节点
 28:         if(hasRunningChild)
 29:         {
 30:             if(!m_ChildNodes[m_iCurrentRunningChildIndex]->Test(in))
 31:             {
 32:                 m_iCurrentRunningChildIndex = -1;
 33:             }
 34:         }
 35:     }
 36:     return IsValid(m_iCurrentRunningChildIndex);
 37: }

总结

从上面4种模式的转化方式中,我们好像会有种感觉,用行为树的表达好像并没有状态机的表述清晰,显的比较复杂,罗嗦。这主要是因为我们用行为树对状态机做了直接的转化,并想要尽力的去维持状态机的语义的缘故。其实,在AI设计过程中,一般来说,我们并不是先有状态机,再去转化成行为树的,当我们选择用行为树的时候,我们就要充分的理解控制节点,前提,节点等概念,并试着用行为树的逻辑方式去思考和设计。

不过,有时,我们也许想用行为树改造一个已有的状态机系统,那这时就可以用我上面提到的这些模式来尝试着去转换,当然在实际转换的过程中,我的建议是,先理清并列出每一个状态跳转的条件,查看哪些是带上下文的跳转,哪些是不带上下文的跳转,哪些是单纯的序列跳转(比如,从状态A,到状态B,到状态C,类似这样的单线跳转,常见于流程控制中),哪些跳转是可以合并的等等,然后再用行为树的控制节点,把这些状态都串联起来,当发现有些跳转用已有的控制节点不能很好的描述的时候,可以像我上面那样,添加新的控制节点。

这四种模式,是我现在能想到的,可能不全,如果大家有问题,可以在后面留言,有指教的也欢迎一起讨论。

 
相关文章

UML概览
UML图解:用例图(Use case diagram )
UML图解:活动图(activity diagram )
UML图解:类图(class diagram )
UML图解:对象图(object diagram)
UML图解:顺序图( sequence diagram )
 
相关文档

模型跟踪:跟踪图、矩阵、关系(建模工具EA)
自定义表格(Custom Table)在EA中的使用
元素的详情浏览控制
UAF 1.2规范解读(DMM 和 UAFML )
EA中支持的各种图表
EA中的界面原型建模
 
相关课程

UML与面向对象分析设计
UML + 嵌入式系统分析设计
业务建模与业务分析
基于SysML和EA进行系统设计与建模
基于模型的需求管理
业务建模 & 领域驱动设计
 
分享到
 
 


如何向妻子解释OOD
OOAD与UML笔记
UML类图与类的关系详解
UML统一建模语言初学
总结一下领域模型的验证
基于 UML 的业务建模


面向对象的分析设计
基于UML的面向对象分析设计
UML + 嵌入式系统分析设计
关系数据库面向OOAD设计
业务建模与业务架构
使用用例进行需求管理


某航空IT部门 业务分析与业务建模
联想 业务需求分析与建模
北京航管科技 EA工具与架构设计
使用EA和UML进行嵌入式系统分析
全球最大的茶业集团 UML系统分析
华为 基于EA的嵌入式系统建模
水资源服务商 基于EA进行UML建模
更多...