— AI分享站

Archive
2011-08 Monthly archive

前段时间,谈到了一种层次化的AI架构,通过“请求”来隔离出“决策层”和“行为层”,这种架构的核心是通过“请求”来起到承上启下的作用,并由此得出当前AI所应当有的行为,所以可以称之为“请求导向(Request-Oriented)”的结构。这种结构比较适用于需要频繁做AI决策的游戏场合,比如体育类游戏等,一旦变换了请求之后,行为层就可以迅速的找到相应的行为来完成请求的内容。

这次我们换一种思路,来讨论一种“目标导向(Goal-Oriented)”的AI结构,这种结构对于一些持续性相对较长的AI策略来说,是非常适用的。还是先举个例子吧,我平时很喜欢玩星际(没玩过的同学,可以看我下面的描述),那假设我用单个农民(SCV)造一个人族的重工厂(Factory),造重工厂的前提是需要200水晶(Mineral)资源,100气体(Gas)资源,而且必须要先造好兵营(Barrack),兵营是150水晶资源,还有在采集气体资源前,需要造一个气矿(Refinery),气矿也需要100水晶资源,具体流程图如下:

GoalOrientedExample

在这个流程里,我们为这个农民设定的“目标”就是“造一个重工厂”,由于在游戏中,要完成这个目标前,需要有其他一系列的预备行为,如果我们为这个农民写AI的话,它就需要根据上面的流程一步步的来完成我们要求它的“造一个重工厂”的目标。由于所有的AI行为决策都是由指定的目标引起的,所以我们把它称之为“目标导向(Goal-Oriented)”的AI架构。

由上面的例子我们可以看到,一个目标之后,必然会有一系列的行为与之对应,而这些行为就是为了最终完成这个目标,那这些行为是如何串联的呢?或者说,我们如何来做这样的行为计划呢?在“目标导向(Goal-Oriented)”的AI架构中,一般都会存在一个称之为“计划器(Planner)”的模块,由这个模块负责生成这样的行为序列,计划器有两种工作方式,一种是静态的,一种是动态的。

静态的计划器是在游戏设计时,对于所有已定义的可用目标,预先设计好计划流程,就像我们上面这个例子,我们就对“造一个重工厂”这个目标预先设计了一套计划流程,当游戏中的农民收到这个目标后,就会按照我们定义的这个流程来做。

动态的计划器是在游戏运行时,实时的根据目标来计划行为,因为我们看到,计划中每一个单步的行为都存在“前提(Precondition)”和“效果(Effect)”两个部分,“前提”就是做这个行为需要满足的条件,“效果”就是这个行为对于游戏世界的影响。还是用上面这个例子,像“造兵营”这个行为,它的前提就是“需要有150水晶资源”,它的效果就是“当前存在一个兵营”,再如“造重工厂”,它的前提就是“需要200水晶资源”,“需要100气体资源”,“当前存在一个兵营”,它的效果就是“当前存在一个重工厂”,可以看到,前一个行为的效果会成为了下一个行为的前提,所以有了这样的定义,我们就可以通过一些算法,来把可用的行为串联起来,形成一个计划,这样最后一个行为的效果,就是我们所定义的目标。

除了核心的计划器模块,我们还需要目标选择(Goal Selector)模块,来选择我们当前要完成的目标(相当于更高层的决策层),还有一个就是计划实施(Plan Stepper)模块(相当于行为层),用来按部就班的完成计划中各个行为,这两个模块比较好理解,就不多说了,有了上面几个部分的定义,我就可以画出这样的“目标导向(Goal-Oriented)”的AI架构图:

GoalOrientedArchitecture

由上图可以看到这种架构也是相当清晰的,核心的计划器部分在具体实现的时候,还有各种各样值得讨论的地方,本文作为抛砖引玉的作用就不多提了,以后可以继续讨论。现在的游戏AI中,这种Goal-Planner架构的也占了相当大的比例,在动态的计划器的驱动下,可以呈现出多样和逼真的AI行为,希望这篇文章对大家了解这种架构起到一些帮助。

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

Read More

游戏AI和游戏设计紧密相关,我也经常说,一个好的游戏AI,不在于算法的艰深和行为的完全拟真,而在于和整体游戏性的契合,在平时工作中,也是和游戏设计师打交道的最多,有这样一句话,一个好的AI程序员相当于半个游戏设计师 :) ,所以这次就来谈谈关于AI难度的设计问题。

谈到游戏设计,有些人觉得可能是灵光乍现的东西,只可意会不可言传,我以前也是这么认为的,但去年以AI程序员身份参加了一个为期两周的设计培训课程,感到收获颇丰,原来游戏设计通过总结前人对于游戏设计的实践,是可以形成一系列科学有效的方法的,好的游戏都有一些共性在里面,所以像《愤怒的小鸟》,《植物大战僵尸》这种游戏的成功,也绝不是偶然的。虽然在分工上,设计大部分都是游戏设计师的职责,但作为AI程序员,有时需要给出一些技术上的建议,并能提供一些技术上的支持。这次提到的关于AI难度的设计,也是我最近遇到的一个问题,我想如果运用一些科学的方法,就可以在设计时明确AI的方向和做法,这样对开发是有相当的益处的。

先假设一个场景,如下图所示(P代表玩家,E代表敌人,黑色的块代表障碍,黄色的圈代表目标),这是一个潜行类的游戏,游戏目的是控制游戏内的主人公拿到敌人基地内的情报图,而敌人会在基地内不停的巡逻,如果被发现就会Game Over。假设我们要做成关卡类的游戏,每一关都会比前一关难一点,关卡中的AI行为也要有难易之分。那作为AI程序员,自然就要去思考如何来AI的难度变化,来符合游戏设计人员的需要。

DifficultyOfAIs

当我们设计敌人的AI的时候,会先考察有多少因素会影响到敌人的AI难度,这些因素也是我们可以提供给关卡设计师的,值得说明的是,我们只考量AI层面的难度,不考察由关卡本身带来的难度,因为显而易见的一些因素,诸如敌人数量,敌人出生位置,障碍的位置等等,也是可以增加或者减少关卡难度的,虽然说我们在这里不考虑这些因素,但这些因素也是可以用我接下去的设计方法来设计的。

好,继续我们的AI难度设计,我们仔细分析问题之后,会列出如下可能影响到AI难度的因素

  • 巡逻方式:静止的,可预判的,不可预判的
  • 巡逻范围(用巡逻路线长度衡量):0,4米,8米,12米,无穷
  • 视野角度:0度,30度,60度,90度,120度,360度
  • 视野范围:0米,1米,3米,5米,7米,无穷
  • 移动速度:0米/秒,2米/秒,4米/秒,6米/秒,10米/秒
  • 声音感知范围:0米,1米,3米,5米,无穷

上面的这些因素后面的取值,都是由简单至难依次递增的,特别值得注意的一点是,每一个因素的第一个值都是最简单的情况,可以称之为“空值”,最后一个值是最不可能的情况,一般称之为“无穷值”,在空值和无穷值之间的值,是根据需求,按经验定义的,一般情况下(除巡逻方式外),我们不会取空值和无穷值。就拿“视野角度”这个因素来说,它的空值就是0度,表示这个敌人没有视野,它的无穷值是360度,表示这个敌人能看到周围所有的东西,在这之间的值都是比较合理的视野角度,可以任意取用。

有了这些因素,我们就可以用一张二维的表格来定义各种难度下的AI设置了,如下面这个表格

  巡逻方式 巡逻范围 视野角度 视野范围 移动速度 声音感知范围
AI1(新手) 静止 4米 30度 1米 2米/秒 1米
AI2(简单) 可预判 8米 60度 3米 2米/秒 1米
AI3(中等) 可预判 8米 90度 5米 4米/秒 3米
AI4(困难) 可预判 8米 120度 7米 6米/秒 3米
AI5(超神) 不可预判 12米 120度 7米 6米/秒 5米

这里我们通过设置不同的因素值,定义出了5种难度的AI设置,当把这些AI放入关卡中后,就会对关卡的难度产生影响,也帮助了关卡设计师来更好的设计和调整关卡的难度。

当然,作为AI程序员,可能我们并不需要参与到最后的关卡难度设计,但这样的设计方式,我觉得,是值得我们学习的,也可以帮助我们在实现AI的过程中,辅助游戏设计师,定义出可控的参数来,做到参数化的AI控制。我在现在的项目中,经常听到玩家的一些抱怨,什么AI太难啦,AI太简单啦什么的,而且有时游戏测试人员也需要一种“傻AI”模式来帮助他们测试,所以,如果我们能在实现AI初期,就把一些能够控制AI难度的因素定义出来,那也可以更好的来使我们的AI行为更可控,何乐而不为呢?

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

Read More

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

我们知道状态机是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
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

前段日子,和以前大学的同窗们聚会,很多人都是好久未见,有些人也是难得从国外回来一次,大家相聊甚欢,说说近况如何云云。

正巧,有个人现在在美国某著名大学读PHD,而且主要研究的是人工智能相关,那我作为一个AI程序员,对她研究的东西自然也就要打听一番。聊了一点之后,发现学术的东西还真是学术,和我现在在做的非常的不同,不仅偏向于理论,而且门类非常的窄。虽然,这也是在我的预料之中的,虽然,我在游戏行业里对AI技术摸爬滚打了几年,但还是不得不感叹:此AI非彼AI。

游戏中用到的AI技术,不管从架构还是实现上,较之于学术上的AI研究来说,都是相当简单的东西了。当然,不是说游戏AI不追求前沿,这也是有原因的,首先游戏AI技术的发展,和其他游戏技术一样,也是依赖于硬件的发展,在红白机时代,受硬件所限很难处理复杂的AI逻辑,所以看以前的游戏,AI大多是简单的if-else逻辑,或者简单的脚本化的逻辑为主。随着游戏硬件的处理速度越来越快,AI才可以越来越多的用到一些稍稍复杂或者高级的技术。

其次就是游戏对于处理速度的要求是相当之追求的,如果一个60帧的游戏,那一帧的处理时间就是16毫秒左右,在这之中分给AI的时间一般也就是6~8毫秒(视具体要求和如何划分AI而定)。所以游戏的AI很难选用一些,虽然很强劲,但很费时的算法,而我们知道,学术上的一些人工智能的研究,它的一些算法是很费时间的,这也就导致了很多学术上的研究并不能直接给游戏AI所用。

还有,就是可控性和灵活性。人工智能的极致就是极度的拟真,让人感觉不出这个是由程序算出来的结果,对于学术研究来说,这个是他们所最求的目标,但游戏的AI不同,拟真只是一个方面,游戏的AI是为游戏服务的,拥有一个拟真的AI的游戏,并不一定是一个好玩的游戏。所以有时,游戏的AI会作假,会不断的根据设计的要求调整,所以,游戏AI技术一般是注重于模块化的,灵活的架构,而不是拟真的算法。就拿神经网络来说,20世纪40年代就提出了神经网络的基本概念和雏形,做为一种学习型的算法和结构,可以说非常吸引人。但直到现在,我还是很少看到游戏中用神经网络作为主要的AI架构的,归根结底,就是它并不符合我提到的可控性和灵活性的要求。作为一个游戏的AI架构来说,太难以掌控和调式了。在游戏中,我所看到的一些运用到神经网络的地方,还是在一些语音识别的处理上。当然,可能以后会有更多的发展和运用,但就我现在的感觉来说,游戏AI还是需要具备可控性和灵活性的特点。

当然,不少游戏AI技术,也是取自于从学术研究。比如现在很多游戏用到的HTN(Hierarchical task network),中文翻译应该叫“层次化的任务网络”,就是一种实时的做计划(Plan)的系统,类似的学术研究其实从20世纪70年代就开始了,现在经过各种发展,慢慢的也应用到了游戏中了,而且不管从性能,还是最后的效果来看,还是很不错的。随便说一句,类Planner的AI系统,这也是我将来会重点学习和研究的地方。

游戏AI和游戏中的3D技术很不一样,3D技术经常是能把一些最新的研究带入进来,呈现出极其真实的画面,但游戏AI,就像我前面所说的那样,一方面要考虑的计算量的问题,更重要的是,它是为游戏服务的,所以好的游戏AI可能被学院派所不屑(因为并没有艰深的理论和算法),但它确实常常能表现出极佳的游戏性,这不是正是我们做游戏的人来说,最追求的吗? :)

所以,此AI非彼AI,不过多接触和了解一些前沿的AI研究,对于拓宽思路还是很有益的,最后,推荐一本书,《人工智能的未来》,记得当初读的时候,是通宵读完的,而且兴奋的满脑子都是里面的字句。真是非常有意思的书,我想,大家看完也会有种豁然和不一样的感觉。

————————————————————————
作者: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

我们在学习程序的时候,都会提到一些逻辑计算方面的事情,像与(and),或(or),非(not)等,在编程语言层面也提供了相关的符号来表述逻辑的计算。我们都知道,对于AI来说,逻辑是非常重要的,一些简单的AI系统,就是由if-else搭起来的一个庞大的逻辑网,里面包含了各种预设好的可能性,最后得到一个决策结果,这样的系统还有一个名字,叫基于规则的AI系统(Rule based AI System),当然随着游戏逻辑越来越复杂,这样简单的靠分支的系统已经不能满足要求了,所以出现了各种AI架构,像有限状态机(FSM),行为树(Behavior Tree),计划器(Planner)等等。但不管架构如何变化,我们在AI中还是充斥着各种逻辑的计算。

那为什么我们要用类来表示逻辑计算呢?这就要牵扯到我们一直在聊的行为树的问题了,我们知道行为树在每个节点上都需要一个称之“前提”(Precondition)的部分,用来帮助我们来决定此节点是否能被执行,所以这个“前提”就会包含一个逻辑表达式,要么返回False,要么返回True,对于不同的节点来说,它的“前提”基本上都不会相同,那自然的,我们就会从程序设计的角度来思考,如何去实现它。当然,方法有很多,不过如果从以下两个方面来考量的话,可以考虑用类的方式来做。

  1. 模块化(目的复用逻辑项)
  2. 为行为树的编辑器做准备(目的可视化的逻辑表达)

说到类的实现方式之前,我们可以先来看一下,一般代码中的逻辑表示,以c/c++为例:

 1: bool a = IsAOk();
 2: bool b = IsBOk();
 3: bool c = IsCOk();
 4: if(a && (b || c))
 5:     //do sth
 6: else
 7:     //do other things

这样的方式很直接,很简单,作为“前提”的实现也是很好的,比如我们可以提供这样一个类,然后让用户继承这个类,自己在isTrue的方法里写需要的逻辑计算。

 1: class Precondition
 2: {
 3: public:
 4:     virutal bool isTrue() const = 0;
 5: };

但考虑到我上面的两点需求,这样的实现就显得不够模块化,因为我们并不能复用上面的任何一个逻辑项,而且更重要的是,我们也没有办法在编辑器中“看到”它的逻辑表达。基于这样的原因,我们再来看看用如何用类来表示逻辑计算,还是用上面这个纯虚类,我们定义几个称之为类逻辑操作符的新类

  • PreconditionAND
  • PreconditionOR
  • PreconditionNOT
  • PreconditionXOR

这些类继承自上面的Precondition,并重写了isTrue方法,我们用PreconditionAND举例:

 1: class PreconditionAND : public Precondition
 2: {
 3: public:
 4:     PreconditionAND(Precondition* lhs, Precondition* rhs)
 5:         : m_Lhs(lhs),m_Rhs(rhs)
 6:     {}
 7:     virtual bool isTrue() const
 8:     {
 9:         return m_Lhs->isTrue() && m_Rhs->isTrue();
 10:     }
 11: protected:
 12:     Precondition* m_Lhs;
 13:     Precondition* m_Rhs;
 14: };

可以看到,这个类很简单,它接受两个Precondition的实例,然后在isTrue里再调用这两个实例的isTrue方法,并返回它们的And结果。对于其余的逻辑符号类,我们也用同样的方式来定义,值得注意的是,对于PreconditionNOT来说,它只接受一个Precondition的实例,因为Not是一元的操作符。

有了逻辑操作符,我们就可以复用Precondition的逻辑项了,比如

 1: Precondition* precon = new PreconditionNOT(
 2:                             new PreconditionAND(
 3:                                 new PreconditionA(), new PreconditionB()
 4:                             )
 5:                         );
 6: //ret means !(A && B)
 7: bool ret = precon->isTrue();

我们用类逻辑操作符链接了逻辑项,使之达到了复用和模块化的效果。对于这种方式,我们需要不断的整理和提炼,并预先定义一些我经常用到的一些单个的逻辑项,就像上面所示的A,B一样,然后通过类逻辑操作符,组合成我们需要的逻辑计算结果。对于这些单个的逻辑项,因为需要被复用的关系,所以要尽量保持内部的逻辑是简单的。

就我们想要的行为树编辑器来说,我们可以将这些预先定义好的单个逻辑项导出到编辑器,然后在编辑器里,我们通过类逻辑操作符,来组成出我们需要“前提”,这样,我们就可以在编辑器里直观的“看到”逻辑的表达式,也方便我们检查逻辑的正确性。

当然,这种方式比起第一种直接在代码中书写逻辑的方式,相对复杂,在开发过程中,team对于这种理念的坚持程度也有待验证(因为需要不断的优化逻辑表达式),但对于一种用类实现逻辑的方式,我觉得还是有必要在这里介绍一下。我在实践中,两种方式都用到过,各有利弊,对于极度追求模块化的设计理念,并且想做行为树的可视化编辑器的朋友来说,用类的方式还是非常值得一试的。

好,今天就聊到这里,希望对大家有所帮助。

————————————————————————
作者: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