关于博客上AI技术文章的问与答 – 第二回


这段时间又收到一些朋友的来信,询问一些关于AI和行为树方面的问题,整理在这里,供更多的朋友参考,欢迎继续来信或者在博客上留言讨论,我的邮箱是finneytang@gmail.com,我的新浪微博是@imFinney,欢迎关注~

 

Q: 您好,我找到你的博客,看了一系列文章,开始给自己的游戏用行为树实现AI。An Architecture for Game Behavior AI: Behavior Multi-Queues Proceedings of the Fifth Artificial Intelligence and Interactive Digital Entertainment Conference,看到这篇文章提到了AI的4个特性,包括了中断和可重入。中断就是你在干A的时候, 新的BT决策判断你需要干B了, 需要中断A。可重入是可能有些事情在中断之后需要重新继续执行。比如B干完后,继续去做干到一半的A。
我想实现后应该是游戏一个线程,BT决策一个线程。这就带来很多困惑了,

1. 比如我满足hp>100时干一系列事,顺序干下来 A完了B再C。那么BT决策后执行Action 是否要同步阻塞执行? 如果同步阻塞执行,就没法实现中断了,action执行完前无法进入bt决策。好像也没法异步执行,比如决策当前要执行ActionA 后,给出命令没等ActionA执行完就返回。也不能马上就要对象执行ActionB(A还没执行完呢,也就没返回值了)
这样就也没法进入下一轮BT决策了。

2. 如我采用异步的做法,发出的指令压入游戏对象的队列。 那可能命令队列还没完,执行第2轮BT决策出来了。是清空队列呢?还是把新命令,继续往里面压?可能会想要通过优先级来选择,考虑BT本身selectornode的子节点就是按优先级排列了,所以应该不需要另外再加优先级了。事实上第二轮决策给出的结论即使是优先级比上一轮决策低的,也应该要马上执行,因为是根据当前新的所有状态做出的判断。 那只有进入同一个决策节点的才是不清空命令队列的。如何判断是同一个决策节点又是个问题,初步想法是跟当前执行节点有同一祖先seq节点,不知是否正确?

貌似讲的还是有点乱。。希望能听一下你的建议和做法

A:谢谢你对博客的关注~~,AI的可重入是个很高的要求,我现在做的行为树中,还没有办法做到这一点,而且我从现在实践下来的角度看,重入并不是必须的,因为当我行为切换的时候,就是表示,我上一个在做的行为已经不需要再做的,以后再满足做这个行为的条件,重头开始就可以了。当然,也不排除可能需要有重入的情况,不过要支持重入,会给实现带来一些挑战。

对于问题1:在我对序列的实现中,我是会每帧都判断当前行为的前提的,如果不满足,就中断当前序列的。下一次再进入的话,是从头开始的。

对于问题2:如何处理这些指令,不是在你上层的BT决策中考虑的,而是取决于你下层处理这些指令的做法,如果下层的处理还是用行为树的话,你就不需要为这些指令排定优先级,可以看我在博客上,对于分层次的AI架构的讨论,还有是一篇关于被动请求的讨论。我在这个架构中,上下层都用到了行为树,中间用“请求”链接,和你的情况很像,你可以参考下。

希望我的回答对你有所帮助。

Q: 你好,最近在网上看到你的博客(http://www.aisharing.com/)里面的一些文章,收益匪浅,想与你探讨下NPC的AI机制的设计实现。我是在校大四的计算机专业学生,目前正在做毕业设计,是关于情感化和社会化NPC行为模型的实现,目前我正在研究该模型的决策机制。想采用行为树/有限状态机/决策树分别实现一个决策机制,然后进行比较。对于这三种模型的区别,优劣,我有以下几点看法:

决策树模型最原始,也最容易理解,但是每一次决策过程都要自顶向下找到叶子节点,比较耗时;

有限状态机模型对于决策树是一个改良,存储了当前的状态信息,以空间换时间,所以时间效率高。但是随着AI复杂程度增加,状态和状态转移越来越复杂(HFSM在一定程度上减少了状态转移),而且重用行不好。

行为树模型,最大的优势在于对于游戏AI设计人员可以有直观的工具来操控。但是其时间效率不如有限状态机。

以上只是读了一点相关文章的感受。想请教您作为游戏AI专业人士的见解。

另外,我在比较AI模型的时候目前想到比较它们的时间和空间的复杂度,不知道还有没有其他的可以反映出模型特性的评判标准?谢谢您的耐心

A:你好,感谢你对博客的关注~

决策树,按照我的理解,就是一颗if-else的树,它的主要目的,是要根据输入条件,找到一个结果,从应用上来说,算术的意味比较强。

状态机,首先它是一个图状结构,状态机中的两个重要的概念就是“状态”和”跳转“,状态是可以维持的(这个和决策树很不一样,决策树只是一个算术过程),跳转可以发生在任意的状态间,状态与状态间会有相互的关联。但就如你说的,当状态一多的时候,就会很乱,用HFSM会稍稍好一点。好处是,状态机比较直观。

行为树,改善了状态机的问题,将跳转从状态里剥离了出来(在状态机中,状态和跳转是写在一起的),并用了树状的结构,更好的描述了行为与行为间的关系,行为树上的节点分为”控制节点“和”行为节点“,控制节点负责行为间的转换,它是可以复用的(比状态机好很多),这样就灵活了很多。

总的来说,决策树是一个算术过程,没有状态的维持,而状态机和行为树都是有状态的概念的,行为树较之状态机更灵活和易于维护。所以现在越来越多的游戏AI都用了行为树结构(或者类行为树结构)。

效率上来说的话,这三者的决策过程,都差不多,没有明显的数量级上的差别,都是一些条件判断,至于空间和时间的复杂度,我个人觉得,因为他们并不是一种什么算法(可能决策树更像算法一点),仅仅是架构上的不同,所以这并不是讨论着三者优劣区别的一个很重要的地方。

由于本人并不是专业计算机系毕业的,以上回答仅基于我个人的一些理解,希望对你有所帮助:)

Q1: 你好,我出于个人兴趣想尝试做一个游戏,已经完成的部分AI是用比较原始的FSM来写的,非常难以维护、扩展和编辑,在网上查阅关于Behavior Tree的一些资料时发现了你的blog,觉得写的非常精彩,对我有极大的启发。读完你的博文,有一两个疑问想冒昧求教一下。

第一个问题是,行为树怎么处理角色自身的一些状态,比如死亡,角色如果在执行BT中的一个行为时,进入了死亡状态,是把死亡本身作为BT中的一个行为吗?还是BT外的一种角色状态,强行中断BT行为,而进入死亡状态呢?

第二个问题是,行为树怎么处理游戏世界中引发的事件呢?比如由BT控制的角色正在执行BT中的idle行为,而角色之间出于协作的目的有互相发送消息的功能(对于收消息的角色来说类似于触发了一个事件),此时是中断当前BT行为重新决策一次?还是每一个Action都要有一个处理事件的过程,由Action自身判断是否需要退出当前Action而重新决策?

感谢你阅读我冗长而冒昧的来信,非常希望在探索AI这方面丰富知识的过程中得到你的一些提示吧,非常谢谢!

A: 谢谢对于博客的关注!

1. 玩家本身的状态可以作为一个状态变量存在玩家身上,如果你要在玩家死亡的时候做一些行为相关的事情,那就可以在bt中加一个“死亡”的行为节点,他的进入条件就是玩家的状态是死亡,当条件满足,行为树就是执行这个行为。

2. 行为树永远是自顶向下,靠控制节点进入前提来寻找可以运行的节点的,行为树每个行为节点自身是不处理行为切换的(要不就和FSM一样了),所以,对于外部触发的事件,可以先存贮在任意的数据结构里,然后把这个数据结构作为行为树的输入,让行为树根据这个输入来进行决策。

可以看看我写的一个小的行为树的例子, http://www.aisharing.com/archives/530

Q2: 还请教一下,这样的行为树是整棵树都在不停的Tick的吧?自上而下,除了前提条件已经不满足的节点的子节点以外,所有的节点都会每次Tick都检查条件,满足就调用一次具体行为节点,是吗?

A:对,行为树每次tick都会遍历一遍所有的节点的前提,寻找可以运行的节点,如果没有并行节点,每次只会有一个节点被运行,如果有并行节点,就可能有多个节点被运行。因为行为树需要遍历所有来寻找可运行的节点,一个优化就是用不带优先级的选择节点,他会优先判断上一次运行的节点分支,如果满足就直接运行了。还有就是现在国外有人提出了第二代的行为树解决方案,能改进遍历的问题,我也会分享在博客上的。

其实,AI做法千变万化,有一些是通用的东西,比如状态机,行为树,A*寻路等等,但很多还是和具体游戏相关的,不同的游戏,AI的实现方法会完全不同,这也是AI比较有意思的地方,每次都能有新的挑战。很高兴我的文章能给到你帮助,有问题,欢迎一起讨论~

Q: Finney您好,想请问您可否推荐一些AI的中英文书。看了您的BLOG想了解更多有关AI方面的东西,请问是否有这类相关的书籍呢?谢谢

A: 专门的介绍游戏人工智能的经典书不是很多,有一套游戏编程精粹(现在出到第八本了吧),它里面收录了很多游戏编程各个方面的文章,其中包含一些人工智能方面的部分,可以一看。还有一个专门的英文网站很值得一去aigamedev.com,里面有很多很好的文章和视频,希望能对你有所帮助。除了看书以外,可以的话,自己做个带AI的小游戏,会学到更多的东西,我平时就是看到了一些东西,就会写点代码,实验一下,感觉收获更大谢谢你对博客的关注:)

Q:你好,我是游戏开发人员,对AI很感兴趣,之前对AI的处理一般是用有限状态机,在阅读你的博客时候看到了行为树,请问下:在行为树中,如果行为节点A状态为完成,这时一般是行为树本身遍历所有节点的状态来判断是否执行另一个行为节点,还是行为节点A抛出事件通知行为树执行下一个节点?

A:您好,是否要执行另一个节点,控制权都在它的父节点,如果父节点是序列节点或者并行节点,那么就有可能会继续执行下一个兄弟节点行为树外部一般不需要管行为树的控制逻辑的。

比如,有一棵树,根节点是序列节点A,它有两个子节点,B,C,按照序列节点的控制逻辑,当B完成时,就会执行C

比如再有一棵树,根节点是选择节点A,它也有两个子节点,B,C,按照 选择 节点的控制逻辑,当B完成时,C不会被执行,当下一帧再进来的时候,就会重新判断是要执行B,还是执行C,然后选择一个执行

所以,行为树的执行逻辑都是由控制节点来控制的

Q:你好, 我是一名AI程序员, 当前在使用行为树时碰到这样的一个实现问题。我希望在行为树上实现目标仲裁的机制, 这样的功能在行为树的构架上该用什么组织方法来支持? 不知道你有什么想法或者建议么?另外这里说的目标仲裁是指,当前我们的AI有多个子目标需要选择, 如:攻击, 寻找合适的武器, 寻找HP,探索等。但这些目标的选择是基于一个规则的, 如: 寻找武器的行为时候AI会综合考虑当前AI的血量, 武器的强度, 武器离玩家的距离等因素, 最终形成一个执行这个行为的期望。而行为选择时则选择综合期望最高的行为。

A:你好,感谢对博客的关注!对于你这个问题,可以分两个方面考虑

1. 如果你指的行为的期望,是一个静态逻辑的话,换句话说是可以用逻辑表达式来表示的,比如if 血量 < 10 or ( 血量  < 20 and 武器强度为0)  then 逃跑,那就可以用行为树来表示,把这些静态逻辑移到行为树行为节点的前提中,并配上选择节点就可以了

2. 如果行为期望是一个模糊逻辑,也就是说需要根据某个算法,综合考虑一些因素得到一个值的话,比如if 期望值<10 then 逃跑, 那可以把这个值作为行为树的输入,并且把对这个值的判断逻辑作为行为树行为节点的前提,并配上选择节点来实现。不推荐把行为树用在模糊逻辑上面,一方面是没有必要,一方面也是行为树本身的结构所决定的,它善于表示的是确定的逻辑和流程控制

对于模糊逻辑的AI心得,我在上个项目中也实现了一个分数系统用来实现在足球游戏中,带球队员的AI决策,在博客上也有简单的分享,可以查看

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



(已被阅读1,500次)

1 评论

  1. 您好,看了您的博客受益良多,我现在是用lua脚本写逻辑,参考了您分享的行为树节点库,并把它迁移到纯lua上面来,但是效率不高,我想应该是lua执行没有C++高效,就想像cocos2dx一样,将这个行为树节点库向lua暴露接口,问一下你有没有做过类似的工作,也请指点一下~

发表评论

电子邮件地址不会被公开。

Copyright © 2011-2017 AI分享站    登录