— AI分享站

Archive
Tag "Blackboard"

第一部分见这里

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

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

Fsm2BtPattern3

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

模式4:循环跳转

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

Fsm2BtPattern4

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

 1: 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,类似这样的单线跳转,常见于流程控制中),哪些跳转是可以合并的等等,然后再用行为树的控制节点,把这些状态都串联起来,当发现有些跳转用已有的控制节点不能很好的描述的时候,可以像我上面那样,添加新的控制节点。

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

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

Read More

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

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

如果满足条件1,则跳转到状态1
如果满足条件2,则跳转到状态2
...
否则,不做跳转,维持当前状态

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

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

  • 控制节点:选择节点,序列节点,并行节点,等等
  • 行为节点:两种运行状态,“运行中”和“完成”
  • 前提条件

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

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

Fsm2BtPattern1

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

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

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

 1: 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值

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

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

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

Fsm2BtPattern2

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

 1: 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: }

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

Fsm2BtPattern2 (1)

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

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

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

(待续…)

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

Read More

这篇文章针对于已了解行为树和黑板的读者,如果不是很了解,请参考此处(123)。

黑板(Blackboard)是一种数据集中式的设计模式,一般用于多模块间的数据共享,我在做行为树的过程中,发现黑板非常适合作为行为树的辅助模块来使用,这次就来谈谈如何在行为树中使用黑板。

行为树的决策一般要依赖于外部的输入,如下图所示。

输入内容的来源取决于行为树用在整个AI架构的哪一层,可以是游戏世界的信息,或者是上层模块的输出。输入的形式,可以是分散的(Decentralized),也可以是集中的(Centralized)。举个例子来说,如果我们做一个战士是移动,还是攻击的决策,这是决策层的行为,所以输入内容就是游戏世界的信息,它可能包括战士自身状态(在模块A中),敌人状态(在模块B中),装备物品情况(在模块C),地图场景情况(在模块D中)等等,所以,当我们搜索和执行行为树时,我们需要从4个模块中获取信息来帮助决策,这样的方式就是我上面说的分散的方式,它的好处是调用非常直接(可能是用多个Singleton提供的接口),没有数据冗余,缺点是使得行为树对于数据的依赖度太分散。

集中的方式的话,就是我们可以定义一个数据结构专门用于行为树的输入,将上面提到的需要用到的数据,在进行行为树决策前,先从各个模块中收集到这个数据结构里,然后再递交给行为树使用。集中式的输入减少了输入和行为树之间的接口数量(只和预定义的数据结构通信),但缺点是,存在数据冗余。不过,我们可以看到集中式的数据输入使得行为树的表现更像一个黑盒了(可以伪造数据来测试行为树),这也是我们一直以来想要的。可以参看下面对于两种方式的示意图:

BehaviorTreeInputModule_1

基于上面的原因,黑板(Blackboard)这样一个概念正好符合我们的需要,所以我们就可以用黑板从各个模块中来收集行为树决策和执行的过程中需要用到的数据,然后提交给行为树使用。值得注意的是,这块黑板对于行为树来说是只读(Readonly)的,行为树不允许修改和添加任何信息到这块黑板上面。因为很难从程序上去限制(就算用const,有时为了方便还能强转成非const),所以限制只能是一种规则,或者说约定。

说完了外部世界的黑板,我们再说说另一块可能会被用到的黑板。这也可以看成是对上面这块只读黑板的补偿吧, :)

在行为树的使用过程中,发现有时候节点和节点间,行为树和行为树之间确实需要有数据共享,比如对于序列(Sequence)节点来说,它的执行行为是依次执行每一个子节点,直白一点说的话,就是执行完一个再执行下一个。一般用到序列的行为,其子节点间总会有一些联系,这里就可能存在节点间通信的问题。再比如,在一些团队AI的决策过程中,当前AI的行为树决策可能需要参考其他AI的决策结果,所以这样就存在了行为树之间需要通信的情况。

所以,在实践过程中,我们还会定义另一块黑板来负责行为树间和节点间的通信需求,示意图如下

BehaviorTreeInputModule_2

可以看到这块黑板是又可以读又可以写的,为了防止黑板混乱的问题(可以参看我以前对于共享数据的文章),我们必须在使用时规定一些限制,可以称之为黑板数据的“作用域”,我们知道很多编程语言里,变量都是存在作用域的概念的,有全局,有局部等等,借鉴于此,我也在这块黑板上规定了作用域,由上面的分析我们可以将黑板上的数据分成如下几种作用域

  • 全局域(G):此数据可以给其他行为树访问
  • 行为树域(T):此数据可以给行为树内的任意节点访问
  • 指定节点域(N):此数据可以给指定的行为树内的某节点(可以是多个)访问

这样的话,黑板的混乱程度就会好很多了,我们可以提供相关的接口来帮助操作黑板上的这些变量。

好了,基本上黑板在行为树中的应用就聊这么多了,希望对大家在使用行为树的过程中有所帮助。

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

Read More

上次提到了一些行为树的基本概念,包括行为节点,控制节点(选择,序列,并行),这次来更多,更深入的讨论行为树的一些东西,如果对行为树不是很了解,请参看这里

一. 关于选择节点的讨论

我们说过选择节点的定义是通过判断子节点的前提条件来选择一个节点执行,这就牵涉到判断顺序的问题,是自左向右,还是随机选择,或者其他的一些规则等等,这样就延伸出各种各样的选择节点。

  • 带优先级的选择节点(Priority Selector):这种选择节点每次都是自左向右依次选择,当发现找到一个可执行的子节点后就停止搜索后续子节点。这样的选择方式,就存在一个优先级的问题,也就是说最左边的节点优先级最高,因为它是被最先判断的。对于这种选择节点来说,它的子节点的前提设定,必须是“从窄到宽”的方式,否则后续节点都会发生“饿死”的情况,也就是说永远不会被执行到,为了更清楚的说明,看下面第一张图,这三个子节点在一个带优先级的选择节点下,它们的前提会被依次判断,可以看到这个三个子节点的前提从左向右,一个比一个更严格,如果我们现在a为9,按照下图的定义会执行第一个子节点,如果a为7,则会执行第二个子节点,如果a=11,则会执行第三个子节点。下面的第二张图演示了一种节点“饿死”(Starvation)的情况,我们看到第一个子节点的前提,比第二个子节点更宽泛,只要a<10,那自左向右判断的话,永远会进第一个节点,所以,如果要用到带优先级的选择节点,则必须检查每一个子节点的前提,以防止节点饿死的情况.

bv-tree-priority-selector-1

bv-tree-priority-selector-2

  • 不带优先级的选择节点(Non-priority Selector):这种选择节点的选择顺序是从上一个执行过的子节点开始选择,如果前提满足,则继续执行此节点,如果条件不满足,则从此节点开始,依次判断每一个子节点的前提,当找到一个满足条件的子节点后,则执行该节点。这种方式,是基于一种称之为“持续性”的假设,因为在游戏中,一个行为一般不会在一帧里结束,而是会持续一段时间,所以有时为了优化的目的,我们可以优先判断上一个执行的节点,当其条件不满足时,再寻找下一个可执行的节点。这种寻找方式不存在哪个节点优先判断的问题,所以对于前提的设置的要求,就是要保证“互斥”(Exclusion)。如果我们用上面第一张图来说明,如果我们把控制节点换成不带优先级的选择节点,可以看到,当a=3时,第二个子节点会被执行,下一次当a变成9时,由于不是从头依次判断前提的,所以,我们还是会选择第二个节点,而不是我们可能期望的第一个节点。正确的做法见下图,注意每一个子节点的前提是“互斥的”。所以对于不带优先级的选择节点,它子节点的排列顺序就不是那么重要了,可以任意排列。

bv-tree-nonpriority-selector-1

  • 带权值的选择节点(Weighted Selector):对于这种选择节点,我们会预先为每一个分支标注一个“权值”(Weight Value),然后当我们选择的时候,采用随机选择的方式来选,随机时会参考权值,并且保证已经被测试过的节点的不会再被测试,直到有一个节点的前提被满足,或者测试完所有的节点。带权值的选择节点对于子节点前提由于随机的存在,所以子节点的前提可以任意,而不会发生“饿死”的情况,一般来说,我们通常会把所以子节点的前提设为相同,以更好的表现出权值带来的概率上的效果。当所有子节点的权值一样时,这种选择节点就成为了随机选择节点(Random Selector)带权值的选择节点对于需要丰富AI行为的地方,非常适用,比如养成类游戏中,小狗表示开心的时候,可能会有各种各样的表现,我们就可以用这种选择节点,添加各种子节点行为来实现。

bv-tree-weighted-selector-1

这些就是常用的选择节点类型,我们可以根据需要,定义更多的选择节点的选择行为,其实我们可以看到,不同的选择行为对于子节点前提的要求会有略微的不同,这是在我们搭建行为树的时候需要注意的地方。

二. 关于并行节点结束条件的讨论

我们每个节点都会有一个运行状态,来表示当前行为是否结束。对于控制节点来说,它的运行状态就是其子节点的运行状态,选择节点和序列节点比较好处理,因为对于这两种控制节点来说,每时刻,只会有一个子节点在运行,只要返回在运行的这个子节点的状态即可。但对于并行节点来说,它同时刻会有多个子节点运行,那我们如何来处理并行节点的运行状态问题呢?一般有两种:

  • 与:只有所有的子节点都运行结束,才返回结束。
  • 或:只要有一个子节点运行结束,就返回结束。

为什么要需要有节点的运行状态呢?

  • 序列控制节点中,需要用运行状态来控制序列的执行
  • 外部世界需要了解行为的运行状态,来决定是否要更新决策(如果行为树在决策层)/请求(如果行为树在行为层),关于AI分层,请参考这里

对于第二点,可以举个例子,比如我们有一个行为是“走到A点”,假设这个行为是不可被打断的,那当我们在走向A点的过程中,行为树的运行状态就是“正在执行”,当到达A点时,行为树就返回“已完成”,这样,对外部来说,当我们看到行为树是“正在执行”的时候,我们就不需要做任何新的行为(为了优化,或者为了行为抖动等等),当看到“已完成”的时候,我们就可以做新的决策或者行为了。这样一个运行状态还有助于我们检测行为树的状态,帮助调试。

三.关于具体实现的讨论

行为树的实现可以有多种多样,我这边提出一些建议,一般来说,行为树每个节点需要有进入(Enter),离开(Exit),运行(Execute)等部分,需要有行为节点(ActionNode),控制节点(ControlNode),前提(Precondition)等基类,然后,还需要定义行为树的输入(InputParam)和输出(OutputParam),一般来说,我们希望行为树是一个黑盒,也就是说,它仅依赖于预定义的输入。输入可以是黑板(Blackboard),工作池(Working Memory)等等数据结构,输出可以是请求(Request),或者其他自定义的数据结构,如下图:

bv-tree-arch

代码的话,就不写了,因为blog没有代码插件,写代码效果不是很好,以后我会在TsiU里面发布一个行为树的库的版本。

四.关于绘制和调试的讨论

看到行为树的定义后,作为程序员的直觉,我们很自然的就会想到,这好像应该能做一个工具来辅助行为树的创建和调试,我们可以把预定义好的前提和节点,在一个可视化的编辑器里搭建成行为树,然后再导出成数据给游戏用。对于调试来说,我们可以让工具和游戏通信,然后实时的检测行为树的运行状况,比如当前在哪个分支中等等。由于行为树的逻辑是可见的,并且是静态的,所以我们看其选择的路径,我们就可以知道AI为什么会作出这样的决策了。当我刚接触到行为树的时候,就在想做这样一个编辑器,但迫于项目压力,一直没有时间做(工作量还是挺大的),有兴趣,有时间的朋友,可以考虑做一个。顺便说一句,我现在对于行为树的搭建都是在代码中完成的,虽然没有数据驱动那么“先进”,但通过宏定义,排版等方式,还是能非常清晰的表示树的整体结构。

关于行为树,我想这个系列就到这里了。在使用行为树的过程中,可能还会碰到这样和那样的问题,包括我自己在实践中的一些经验,我想就先不包括在这个系列里了,以后再单独拿出来聊,这个系列作为行为树的入门,希望对大家有所帮助,欢迎指教和讨论。

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

Read More

AI结构中,有一种情况非常容易出现,就是程序员会非常希望有一块区域,大家可以读取,存储一些信息,并且这块区域是全局共享的。不管是写作看似丑陋的全局变量,还是有一定组织的Blackboard结构,或者作为参数一路传到底,这种结构可以被统称为共享数据(Share Data)。作用就是在不同的模块间传递变量。

共享数据的需求,从某种程度上说,源自程序员的一种”偷懒“(当然这里没有任何贬义),试想一下,一块可以非常方便,存我想存的,读我想读的结构,一块非常松散且容易理解的结构,一块非常容易架构(或者几乎不用架构)的结构,相信很多人都会作为第一选择吧。确实,共享数据的优势很大,很有吸引力,在开发中,可以作为很多问题的解决方案,几乎在所有的引擎中,都或多或少存在着一些共享数据的模块。

在网上的很多文章里,探讨了多种共享数据的结构,OO开发,使得这种结构多了更多的灵活性,不再是以前一个structure走天下了,比如前面说到黑板系统,这个可以说是现在AI中经常会用到的结构,在FEAR的GOAP里就用到了Blackboard,用作在Planner间作数据共享(以后可以写篇文章介绍一下GOAP,我非常喜欢的一个AI架构)。但不管这么样,共享数据的本质还是相同的。

共享数据是一种优点和缺点同样明显结构,下面我们来看看它的缺点

首先,就是共享数据很容易乱,这是伴随它的随意性而生的,共享数据的内容会随着开发进程不停的被修改,或添加新的变量(这种情况居多),或删除冗余的变量(由于开发过程是多人协作的,所以,非常有可能的一种情况就是存在两个作用完全相同的变量,只是因为是不同的人加的),如果没有好的维护和清理,共享数据就会逐渐变成”垃圾堆“ -- 随便说一句,这也是我对共享数据的昵称

其次,共享数据会比较难debug,因为修改和读取都是匿名的,也就是说,谁也不知道,谁会在什么时候修改什么变量!这会导致变量被莫名修改,当然,加数据断点,或者好的统一入口,会使情况有所改善。

还有,共享数据很容易造成程序员对他的依赖,会认为任何变量都可以存在其中,而忽视了对本身模块的架构,在某些情况下,它会成为解决问题的最后一棵稻草,问题是,共享数据可以是,但不能每次都是!

sharingdata-1

像我写的标题,”黄金屋“还是”垃圾堆“,不取决于共享数据本身,而是取决于,我们如何去实现,如何去维护,如何去规范,如何去使用。想到这个问题,也源自我最近一段时间的实践和体会,作为一个新的系列的开始吧,下一篇,写点我对架构共享数据模块的想法。

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

Read More