— AI分享站

Archive
Tag "Decision"

记得以前我在博客中,提到过一种层次化的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

自从开博以来,每天都会关心一下博客的访问情况,看到一些朋友的订阅或者访问,不胜欣喜,也促使我去写一些更好的博文,来和大家分享和交流,从访问统计来看,有相当一部分是来自于搜索引擎的流量,关键字以“行为树”,或者“Behavior Tree”居首位,我想大家对此可能有些兴趣,加上,这几年反反复复一直在AI中研究和运用行为树,所以这次就来谈谈关于行为树(Behavior Tree)的一些东西,以前也写过一些文章(123)来讨论行为树,不过已经是一两年前的事情了,较之以前,这次会更为系统,也会添加一些我新的思考和感悟。所谓行为树实践,其实在我脑海里就是Practice in Behavior Tree,没法子,受英文教材影响太多了 :)

我想通过一个例子来介绍一下行为树的基本概念,会比较容易理解,看下图:

bv-tree-1

这是我们为一个士兵定义的一颗行为树(可以先不管这些绿圈和红圈是干吗的),首先,可以看到这是一个树形结构的图,有根节点,有分支,而且子节点个数可以任意,然后有三个分支,分别是巡逻(Patrol),攻击(Attack),逃跑(Retreat),这个三个分支可以看成是我们为这个士兵定义的三个大的行为(Behavior),当然,如果有更多的行为,我们可以继续在根节点中添加新的分支。当我们要决策当前这个士兵要做什么样的行为的时候,我们就会自顶向下的,通过一些条件来搜索这颗树,最终确定需要做的行为(叶节点),并且执行它,这就是行为树的基本原理。

值得注意的是,我们标识的三大行为其实并不是真正的决策的结果,它只是一个类型,来帮助我们了解这个分支的一些行为是属于这类的,真正的行为树的行为都是在叶节点上,一般称之为行为节点(Action Node),如下图红圈表示的

bv-tree-action-node

这些叶节点才是我们真正通过行为树决策出来的结果,如果用我以前提到的那个层次化的AI结构来描述的话,这些行为结果,相当于就是一个个定义好的“请求”(Request),比如移动(Move),无所事事(Idle),射击(Shoot)等等。所以行为树是一种决策树,来帮助我们搜寻到我们想要的某个行为。

行为节点是游戏相关的,因不同的游戏,我们需要定义不同的行为节点,但对于某个游戏来说,在行为树上行为节点是可以复用的,比如移动,在巡逻的分支上,需要用到,在逃跑分支上,也会用到,这种情况下,我们就可以复用这个节点。行为节点一般分为两种运行状态:

  1. 运行中(Executing):该行为还在处理中
  2. 完成(Completed):该行为处理完成,成功或者失败

除了行为节点,其余一般称之为控制节点(Control Node),用树的“学名”的话,就是那些父节点,如下图绿圈表示

bv-tree-control-node

控制节点其实是行为树的精髓所在,我们要搜索一个行为,如何搜索?其实就是通过这些控制节点来定义的,从控制节点上,我们就可以看出整个行为树的逻辑走向,所以,行为树的特点之一就是其逻辑的可见性。

我们可以为行为树定义各种各样的控制节点(这也是行为树有意思的地方之一),一般来说,常用的控制节点有以下三种

  1. 选择(Selector):选择其子节点的某一个执行
  2. 序列(Sequence):将其所有子节点依次执行,也就是说当前一个返回“完成”状态后,再运行先一个子节点
  3. 并行(Parallel):将其所有子节点都运行一遍

用图来表示的话,就是这样,依次为选择,序列和并行

bv-tree-sel

bv-tree-seq

bv-tree-pal

可以看到,控制节点其实就是“控制”其子节点(子节点可以是叶节点,也可以是控制节点,所谓“执行控制节点”,就是执行其定义的控制逻辑)如何被执行,所以,我们可以扩展出很多其他的控制节点,比如循环(Loop)等,与行为节点不同的是,控制节点是与游戏无关的,因为他只负责行为树逻辑的控制,而不牵涉到任何的游戏代码。如果是作为一个行为树的库的话,其中就一定会包含定义好的控制节点库。

如果我们继续考察选择节点,会产生一个问题,如何从子节点中选择呢?选择的依据是什么呢?这里就要引入另一个概念,一般称之为前提(Precondition),每一个节点,不管是行为节点还是控制节点,都会包含一个前提的部分,如下图

bv-tree-precondition

前提就提供了“选择”的依据,它包含了进入,或者说选择这个节点的条件,当我们用到选择节点的时候,它就是去依次测试每一个子节点的前提,如果满足,则选择此节点。由于我们最终返回的是某个行为节点(叶节点),所以,当前行为的“总”前提就可以看成是:

当前行为节点的前提 And 父节点的前提 And 父节点的父节点的前提 And....And 根节点的前提(一般是不设,直接返回True)

行为树就是通过行为节点,控制节点,以及每个节点上的前提,把整个AI的决策逻辑描述了出来,对于每次的Tick,可以用如下的流程来描述:

action = root.FindNextAction(input);
if action is not empty then
action.Execute(request,  input)  //request是输出的请求
else
print "no action is available"

从概念上来说,行为树还是比较简单的,但对AI程序员来说,却是充满了吸引力,它的一些特性,比如可视化的决策逻辑,可复用的控制节点,逻辑和实现的低耦合等,较之传统的状态机,都是可以大大帮助我们迅速而便捷的组织我们的行为决策。希望这次简单的介绍,对大家有所帮助,能力有限,不一定能表述的很清楚,有问题,或者有指教的,都请和我多多交流,最后,我对这个士兵的巡逻分支画了一个示意图,供大家参考:

S -- 选择节点   Se -- 序列节点

bv-tree-patrol-example

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

Read More

在我的概念里,AI应该分为两层,决策(Decision)行为(Behavior),当然这个是从狭义的AI角度来说的,广义上来说,AI还会包括一些其他要件,比如物理,动画等等。现在这个项目里在做Behaviour模块的一些东西,从做结构开始就参与其中,期间经过了几次大的重构。

behaivour-1-1

可能Behaviour在不同文章里的含义会有些不同,我这里的行为层从某种程度上可以说是一个中间件,上层是AI的决策逻辑,下层是动画资源,工作目标就是把AI的请求转换成真正的动画播放请求。行为的定义是比较关键的一点,比如一个小狗,它可以有走,跑,睡觉,撒尿,吃饭,喝水等等。这些就可以认为是他的一系列Behaviour,或者叫逻辑动作(Logical Action)。这些预定义好的行为就组成了一个集合,可以称作行为池(Behavior Pool)

如何组织起这些行为?Behaviour在组织过程中可以分为两种:
1. 单一行为(Simple Behavior)
2.复合行为(Composite Behavior)
在上面Pool里定义的就是单一行为,复合行为可以看成把单一行为组合后形成的新的行为,拿小狗为例,比如我们定义一个复合行为,“ 边吃饭边喝水”,这个复合的行为可以看成是“吃饭""喝水”两个单一行为并行后的结果。常用的复合方式有几种:
behariour-1-2
1. 序列(Sequenece):一个个行为接着做
2. 并行(Parallel):两个或多个行为同时进行
3. 选择(Selector):从候选行为中选择一个执行,包括脚本选择,和随机选择
这就牵涉到实现的相关问题,如何定义各层之间的接口,如何定义统一的结构,下篇再说吧
————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————
Read More