— AI分享站

Archive
Tag "决策"

记得以前我在博客中,提到过一种层次化的AI架构,这种架构的核心就是定义了“请求层”的概念,用来分隔决策和行为,并通过行为请求来清晰的定义了决策和行为之间的输入输出关系,不过,当我们仔细审视这个结构的时候,发现其中貌似缺失了对于某种情况的处理,这就是我今天要谈到,如何处理“被动式的行为请求”

一般来说,我们通常所认为的决策是一种“主动式(Active)的行为请求”,比如,我按了个键,玩家所控制的角色就是做出某些行为,或者AI通过对于当前情况的判断,做出了下一步的行为决策,所以说,主动式的行为请求,就是表达了一种“我想要去做什么”的语义。在游戏中,大部分的行为都是输入主动式的行为,那FPS(第一人称射击)类游戏来说,它可能包含的主动式行为有,移动,跳跃,射击,与游戏场景中物体的交互(拾取物品,开门)等等,当玩家和NPC在行动的时候,就是在这些已经定义的主动式行为中,做出决策。在我们以前提到的那种层次化的AI架构中,可以很好的满足这些需求。

但在游戏中,还是一些行为并不在主动式的行为中,比如死亡,当角色生命值等于0的时候,游戏系统就会触发这个行为请求,它不是由玩家或者NPC所发起的,而是有游戏系统判断出某些条件满足的时候,自动触发并赋予角色的行为请求。这一类的请求,我们就可以称之为“被动式(Passive)的行为请求”,在谈如何处理前,我们可以先看看这种请求有什么样的特点。

首先它可能会覆盖原本的主动式的行为请求。比如玩家想要快跑向前走,那他就会发出一个“快速移动”的行为请求,但就在这个时候,角色正好被横在路中间的一根树干绊了一下,当游戏系统检测到这个事件的时候,就会触发一个“绊倒”的行为请求,期望做一个摔倒的行为。显然,“绊倒”这个行为不是玩家主动做出的,是属于被动式的请求,而且这个请求应该被立刻响应(要不就不真实了),所以,当比较这两个请求的时候,我们就会用“绊倒”覆盖掉原先的“快速移动”,将其作为当前请求传给行为层。那我这里为什么说是“可能会覆盖”呢?因为并不是所有的被动请求都需要被响应的,这取决于当前产生的主动和被动,这两个请求的优先级设定,这种优先级设定一般来说会来自与游戏设计的需要。假设,我们在游戏中有一个行为是“超级移动”,这种行为很强大,效果也很炫,是游戏的一个很大的卖点和可玩点,所以游戏设计者就希望尽量能让玩家触发出这种行为,以提到游戏的游戏性和画面效果,所以当玩家触发“超级移动”的时候,我们可能就会忽略掉同时触发的“绊倒”这个行为请求。

其次,它是触发式的,所以意味着同一时刻它可能会有多个。试想一下,对于主动式请求来说,因为角色不可能分身嘛(除非是超人游戏),所以一般来说,同一时刻主动请求只会有一个,也就说,你不可能既想做这个,又想做那个。而被动式请求,就完全不同,在同一时刻,可能会有多个条件被满足,然后同时触发了多个被动行为请求,比如在被绊倒的那一刻,你中了一枪,然后生命值正好减到0(真倒霉。。),所以同时就产生了“绊倒”,“死亡”两个被动请求。那我们就面对,多个请求需要权衡的情况,在上述的例子里,显然,“死亡”的优先级应该是最高的,所以它会成为最后的请求被送到行为层。

还有一个特点就是关于被动请求产生源,在角色与角色交互的时候会非常容易产生被动式的行为请求。举个FIFA的例子(对此我研究了很多 :) ),在足球游戏中,我们可以看到很多球员间交互的例子,比如碰撞后的摔倒,争头球的挤位,带球过程中的拉扯,躲避铲球的跳跃,等等,这些都是被动式的行为请求,是玩家不可操控的,而且这些请求,不像我前面举到的例子,是单个人身上的,而是属于一种“相互作用(Interaction)”的行为请求。它的触发和处理,都会牵涉到两个,甚至多个人的判断。

谈完了特点,接下去来思考下如何来处理这些请求。当然,处理的方案多种多样,我先抛砖引玉的谈谈我想到的两种结构。还是基于原有的层次化的AI架构模型,做一些小的修改。第一种方案采用的是比较直观的集中化的处理。先定义一个结构表示当前时刻所有产生的行为请求。

 1: struct CandidateRequests
 2: {
 3:     Request        m_ActiveRequest;      //主动请求,假设同一时刻只有一个 
 4:     Array<Request> m_PassiveRequests;    //被动请求,同一时刻可以有多个
 5: }

然后,我们定义一个模块来负责处理这个结构,并产生一个最终的行为请求,值得注意的是,我们把当前正在处理的请求也作为考虑的因素之一,传入这个函数中。

 1: class RequestFinalizedModule
 2: {
 3: public:
 4:     static Request GetFinalRequest(
 5:                 const Entity& entity,
 6:                 const Request& curReq,
 7:                 const CandidateRequests& nextReq)
 8:     {
 9:         //添加选择的规则,根据当前请求和下一时刻的候选请求,抉择出最终应该做的行为
 10:     }
 11: }

集中式的处理方式将所以处理的可能性放到一个函数中,这样的好处是便于排查可能导致的选择不正确的问题,而且对于原有的结构没有什么更改,仅仅是在决策和请求层之间加了一个处理模块。缺点就是这块的代码,随着优先级关系的复杂,会显的相对比较乱,不过将脏代码堆在一个地方,也是一种不错的设计 :) ,下面是修改后的架构图

layered-ai-architecture_modified

另一种方案是让游戏系统不直接触发被动式请求,而是触发一些标记,然后AI在决策的时候将这些标记作为决策参考信息的一部分,最终做出一个合理的行为决策,这种方案延伸了决策部分的定义,使其即能产生主动式请求,也能产生被动式请求。如果用行为树的话,可以非常好的表示出这种优先级的关系,如下图:

bt-flag-passive-action

这种方式的优点是可以用到行为树本身对于优先级处理的优势,而不需要额外的添加模块,只需修改原本行为树的设计即可,作为游戏信息的一部分,也可以沿用原有的收集游戏信息的相关模块,做适当的扩展就可以了。缺点是,由于我们将原有的触发式的模式,变成了轮询式的,所以,可能会降低行为树的些许效率,而且对于行为树的设计也提出了更高的要求。不过从架构上来看,是比较清晰,并且能很好的融入原有的设计。修改的架构图如下:

layered-ai-architecture_modified_2

好,就聊到这里了,不知道大家有什么想法,欢迎一起留言讨论。

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

Read More

前置阅读推荐:1 2 3

一直在说AI可以分为决策层(Strategy Layer)和行为层(Behavior Layer),和行为层打交道最多的,就是动画了,说到动画,游戏引擎一般都会提供完整的底层的动画系统,包括如何转换数据,如何做动画Blend等等,但这些一般不属于AI程序员的工作范畴,所以不在这次的讨论范围内,我们这次说到的“动画的选择和控制”是相对比较高层的东西,在我的定义里是属于AI行为层的内容。

现在的游戏中,动画越来越多,也越来越复杂,据说FIFA里就用到了4000到5000个动画,所以如何来驱动和组织这些动画,就成了AI行为层需要考虑的问题。就拿足球游戏为例,比如决策层发出“射门”的请求,那行为层就要从几千个动画中决定播放哪个动画来完成这个请求。直观感觉上,这就是一个if-else的问题,但我们要做的,是要有一个好的AI架构来做这样的一个对于动画的选择和控制。

从上面的描述中,我们可以看到,其实行为层的决策问题,和决策层的决策问题是一样的(这也是为什么他们都属于AI的原因),只是输入和输出的不同。对于决策层而言,输入是游戏世界信息(Game World Info),输出是请求(Request),而对于行为层而言,输入是请求和游戏世界信息,输出是动画和动画的播放控制信息(Animation Info)。如下图所示:

StrategyLayerAndBehaviorLayer

对于单个动画来说,我们可以定义两个附加的信息来选择和控制动画

  • 动画的选择条件信息(Animation Condition)
  • 动画的运行时状态(Animation Running Info))

动画的选择条件信息定义了播放此动画的条件,举个例在来说,在足球游戏中,我们有一个倒挂金钩的动画,要播放这个动画,就需要定义一系列的条件,比如球要在一定的高度,人要背对球门等等,这些条件都是预先定义好的,是选择动画的一个依据。

动画的运行时状态定义了动画在播放时的所有相关信息,诸如当前放到哪一帧等等,我们都知道,动画数据中存的都是用关键帧(key-frame)信息,有时,AI程序员需要在动画的关键帧中添加一些自定义辅助信息,比如,假设我们想在某一帧之后就可以接下一个动画,那就可以在这一帧上打个标记来标识,再比如,我们想在身体某部位触到地面的时候发个声音,那也可以在动画中身体碰到地面的那一帧上打标记。再用前面那个倒挂金钩的例子,我们可能会在触球的那一帧上有个标记,在更新动画运行时状态的时候,我们就可以知道在这一帧,要把球踢出去了。所以,这些信息,都是需要被监控的,它会影响到游戏方方面面,不仅仅是给行为层来使用。

下面是示意图,可以看到动画运行时状态是可以在多动画间共享的,因为一般来说,同一时刻只会有一个动画在播放,如果会有多个动画的Blend,比如上下身分开的动画系统,可以仅关心需要关心的那个主要动画的运行状态。所以动画运行时状态也可以称为“当前动画运行时状态”。

AnimationAtomStructure

有了动画,有了动画选择的条件后,我们会发现,这和行为树(Behavior Tree)的结构很像,如果我们把动画看成行为树的节点(Node),把动画选择条件看成节点的前提(Precondition),那我们就可以用行为树来搭建这样一个“动画选择树”。用行为树还有一个好处是,由于控制节点的存在,所以对于一个请求,我们可以用序列节点,作出序列动画的能力,举个例子来说,我们有一个摔倒(Falling Down)的动画,然后后续想接不同的起身(Getup)动画来丰富行为,那用行为树的话,就可以很轻松的做到这点,看下图,我们用了一个序列节点和一个选择节点的组合。

SeqAnimation

对于动画运行信息呢,就比较自由,可以放在行为树中,也可以单独的做一个模块来更新。如果选择放在行为树中的话,可以在根节点使用并行控制节点(而不是一般的选择控制节点),然后左子树是更新动画运行信息,右子树是动画选择树,这样在更新的时候,就会又执行左子树(更新运行时状态),又执行右子树(根据新的请求选择动画),将动画运行时信息放在前面更新的原因是,我们在选择动画时,可能需要参考当前的动画运行状态,就像我们前面所说的那个接下一个动画的问题那样。所以一般推荐先更新动画信息,再选择新的动画。

如果想用行为树来做动画的选择和控制,最需要考虑的就是“叶节点的粒度问题”,如果叶节点是单个动画的话,对于动画量不大的游戏,还可以接受,但像我前面说的类似FIFA的这种有几千个动画的游戏,会导致行为树过于庞大,不好维护,所以,有时我们需要控制叶节点的粒度,比如,将叶节点针对一组动画(相关性很大的一些动画)等。

好,这次就聊这么多,如果大家有什么想法,可以直接留言在下面,我都会回复的 :)

————————————————————————
作者: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结构,最近在整理一些东西的时候,发现这样的AI结构具有一定的通用性,而且层与层之间耦合度相对较低,作为一种层次化的AI架构,非常值得一谈。

在我的脑海中,AI一般分为两个部分,一个是决策(Decision)部分,一个是行为(Behavior)部分,决策部分负责做什么,行为部分负责怎么做。在一些国外的公司里,AI程序员也大致分为这两种(不过,一些国内的企业可能就分的没有这么细,一般都是统称为AI程序员,或者有的分的更粗,将一些游戏中的其他游戏逻辑部分一起涵盖,统称为游戏性(Gameplay,GPP)程序员)。正因为这样,所以我们一般希望,在AI架构上,这两个部分的耦合度是相对较低的,这样也便于任务的分工。所谓层次化的AI架构(Layered AI Architeture)也就基于了这样的理念。看下面这个图:

layered-ai-architecture-1

在这样一个层次化的AI框图中,我们定义了“请求(Request)”这样一个概念,请求可以看作是AI决策的结果,或者称之为一个命令,比如,在射击游戏中,请求可能就定义为,射击,移动,逃跑等等,在动作游戏中,请求就会定义成攻击,格挡,跳跃等等。当行为层收到上层的请求后,就会设法去处理该请求的内容,还是以射击游戏为例,当行为层收到射击的指令,就会从射击的动画列表中选择某个射击动画,然后转向目标,播放动画等等工作来处理射击的请求。所以请求相当于就成了决策层和行为层之间的接口。这样,对于决策层和行为层的输入和输出就很明确了:

  • 决策层:输入(游戏世界信息),输出(请求)
  • 行为层:输入(请求),输出(修改游戏世界的相关信息)

layered-ai-architecture-2

由于有请求层作为中间接口层,所以决策和行为部分就很自然的分开了,而且有清晰的输入和输出,AI团队中的人员的工作职责也就很明确了,做为决策层的AI程序员,就只需要关心如何产生请求,而行为层的AI程序员,只需要关心如何处理请求,一旦定义好完备的请求内容,不管在代码还是在工作上都不会产生很大的粘连度了。

另外值得注意的是,这边的请求层用到了类似双缓冲的结构,分成后端和前端,换个词的话,可以说成当前在处理的请求(前端),和下一个要处理的请求(后端),具体的分析可以参考我以前的文章在AI结构中用双缓冲》,这里就不多做介绍了。

这样的层次化结构在AI中有很强的通用性,因为这是用最高的层面来总览AI的架构,而像其他诸如行为树(Behavior Tree),分层状态机(HFSM)等都可以看成是在决策或者行为层中的具体实现方式。所以不管AI代码是如何实现,大部分都可以归到这种层次化的结构中,因此,我想,我们在设计AI结构之初,就可以用这样的方式来思考和架构整个框架,分割决策和行为,定义请求,然后再针对每一层来选择具体的实现方法。

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

Read More