— AI分享站

Archive
2011-07 Monthly archive

自从开博以来,每天都会关心一下博客的访问情况,看到一些朋友的订阅或者访问,不胜欣喜,也促使我去写一些更好的博文,来和大家分享和交流,从访问统计来看,有相当一部分是来自于搜索引擎的流量,关键字以“行为树”,或者“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结构,最近在整理一些东西的时候,发现这样的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

最近在程序中遇到一个AI决策问题,简要描述和图示如下:

在一张开阔的地图上(几乎没有障碍物),有一些会任意移动的“敌人”,我们要实现一个NPC的AI,使他在做接近目标点的移动决策的时候,能避开这些“敌人”所在的危险区域,而选择相对安全的方向去移动。

im_pic_1

这有点类似于一个寻路算法,不过,和一般的A*算法问题有点不一样的是,在这张开阔的地图上并没有预先设置的路点(Way Point)帮助寻路,而且所有的“障碍物”在这里都是动态的,这样就造成预先计算一条路径的意义并不是很大,正所谓计划赶不上变化嘛。所以我们需要另一种方案来处理,在这里,我用到势力图(Influence Map)来辅助AI寻路。

所谓势力图(Influence Map),也就是一种对于世界信息的预处理,计算和存储地图上的势力数据。比如说,我站在地图的某个点上,那我所站的这个位置,我就对它产生了最大的“势”,因为别人不可能再占据这个点了,由我这个点向外越远的地方,我对其的影响力就越小,也就是我所产生的势越小,用图画出来的话,就像一个靶子一样,所以可以称之为势力靶图如果我们用分数来表示的话,中心就是10分(最大值),然后随着离中心点距离的增大,造成的势力值越来越小。

im_pic_2

另外,势力靶图是可以叠加的,如下图阴影处的势力值,就是4(2+2),叠加后如果超过最大值(10),就按最大值来取,比如多个势力值叠加后为12,超过了10,那这个点的势力值还是取最大值10。

im_pic_3

如果我们对每一个地图上的物体(不管静态还是动态的),计算势力值的话,我就可以得到当前时刻该地图的势力图。当然,为了更好的表示势力图,我们可以先为地图做网格化,然后在每一个格子中存入该格的势力值。我们回到上面这个问题,假设当前这个时刻,NPC和三个敌人的分布就如图片1所示,那我们就可以根据这样的分布,计算出当前的势力图:

im_pic_4

值得注意的是,我这边用了方型的势力靶图,主要是为了简化计算,从效果上来说,和圆形的差别并不是很大,另外,我为势力值定了4级的标准(10,7,4,1),势力值的级数一般是看具体的需要,可多可少,自行权衡既可,有了这样的势力图,我就知道哪些地方是“相对安全”的地方,比如,0,1的格子,在往目标点寻路的时候,就可以尽量往安全的地方选择了。

一般AI决策前,我们需要很多对于世界数据的收集和抽象,势力图作为其中的一种,可以看到,提供了对当前时刻,当前地图中物体的大致分布情况的抽象,可以很好用来帮助我们做AI寻路的决策,其实不光是寻路,其他AI决策问题,如果需要,也可以用势力图做参考数据,比如足球游戏中,如果我们要选择传球给一个处在空档的球员,我们就可以用势力图,来寻找哪一个球员处在空档的位置,等等。

对于势力图,还有几点需要补充一下:

  1. 对于势力图的更新,大可不必每帧计算,因为对于一个场景来说,就算是有运动的物体,一帧的时间里,其变化还是很小的,所以,可以根据需要把更新的周期拉长,以优化势力图的计算
  2. 方型的势力靶图一般可以满足需求,比起圆形的来说,势力图计算的性能上更有优势
  3. 可以把势力靶图做成运动方向凸起的形状,因为如果是需要转向的物体,他背后的势力值应该是衰减的很快的,或者说延伸的很近的,而在其当前运动方向上的势力值,则延伸的比较远
  4. 需要将势力图画出来(无论是在屏幕上,还是在另一个工具中,见我以前的关于AI调试的文章),以帮助调试。

这次对于一开始的那个问题,我们引出了势力图的介绍,至于具体如何基于势力图来寻路,我用到了类似于“导向性寻路”(Steering Behavior)来实现,以后有机会再写吧。

好,这次就这些了,希望对大家有所帮助。

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

Read More

在上次博文《关于调试AI的闲话(1)》中,提到一个利用共享内存实现的参数调试模块,我整理了一下代码,现在放出来,给大家参考,

下载地址:

GoogleCode下载点

也可用svn通过以下地址来得:

http://tsiu.googlecode.com/svn/branches/blogver/

编译方法:

用VS2005以上打开,选择Debug NoDx或者Release NoDx, 在AITest工程,ATInit.cpp中,有一个宏

#define APP_ONE

打开这个宏,编译一次生成一个可执行文件AITest.exe(在exe\aitest\中),重命名后(比如,AITestA.exe),再关闭这个宏,重新编译一次。

测试方式:

打开编译好的两个exe文件,在其中一个窗口中(有文字提示),按住鼠标左键移动鼠标,就可以看到在另一个窗口中有一个红色的圈在同时移动,另外绿色的圈也是通过这个模块来通信的。

参数调试模块:这次提到的模块代码主要是这两个文件,

TAI_RefValue.h
TAI_RefValue.cpp

说明:

  1. 使用方法可以参考AITest中的例子,注意,需要每帧调用Flush来刷新。
  2. 删除后内存回收的功能还没做,这个需要改变内存的组织方式来做,现在是用数组的方式,可能需要改成链表的方式来组织
  3. 不建议将RefValue用在临时变量里,因为观察一个临时变量的某个值没有什么意义

顺便说一下,整个分享出来的代码是基于一个叫“TsiU”的框架来做的,它是我一直在维护的一个自己用的小型的框架,我平时做的一些AI的sample,或者一些工具,都会基于这个框架,TsiU有一些基本的UI控件库,网络模块库,GDI绘图模块,D3D绘图模块等等,可以快速的做成一个小型的示例程序,很方便(具体可参考AITest),并且整个架构是用Object的方式来组织,非常容易理解和扩展。整个框架很轻量化,基本就是做了一些底层的基本的功能,这样我在平时做东西的时候,就不需要重新写底层了,把精力都放在高层的实现了。以后分享代码都会基于这个框架,大家也可以通过svn来随时update到我最新的改动。下图就是TsiU里的几个工程介绍,代码不多,大家想看的也可以自己看一下 :)

tsiu-project

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

Read More

接第一篇的话题,这次来说说AI bug不可重现的问题。确实,对于AI调试来说,很多bug(或者说行为异常),很难找到一个切实的重现的方法,经常是看到后,加好断点,想刻意再玩一下却很难再玩出来了。所以,如何抓住现场,是在AI调试中的一个很值得去考虑问题。

我们很自然的会想到一个解决方案,那就是“回放”。当看到问题时,马上“录像”,然后把这个场景再回放一遍,甚至是可以回放任意遍。这确实是一个自然而完美的方法。一般来说,游戏中的回放分两种:

  1. 逻辑回放(logical playback)
  2. 结果回放(result playback)/ 画面回放(screen playback)

逻辑回放是指,能回到过去的任意时刻,运行游戏的整个逻辑,保证相同的输出结果。结果回放(画面回放)是指,能回到过去的任意时刻,将逻辑运行的结果重新显示出来。简单来说,逻辑回放中所记录的游戏的数据是输入,而结果回放(画面回放)记录的数据是输出,见下图:

ai_debug_1

这两种的回放的实现都依赖于引擎的结构,和引擎实现的耦合度很高,很难做到独立和通用的模块,对于AI调试来说,显然逻辑回放是最好的,因为它能让我们再运行一次游戏逻辑,这样就可以通过设置断点来调试了,但是,现在的引擎一般都是多线程引擎,既然是多线程,就存在一定的时序问题,要做到同样的输入和上下文,两次结果完全一致会相当的困难,除非引擎从设计之初就考虑逻辑回放的问题,如果是改造这样的多线程引擎,工作量会比较大。如果是单线程的引擎,实现起来会容易很多,一般而言,逻辑回放主要记录几个内容:

  1. 时间信息
  2. 设备输入信息(比如,手柄,键盘,鼠标等)
  3. 随机数信息
  4. 当时的游戏世界上下文

对于第4点是针对从任意点回放而言的,如果当前的上下文信息不是很容易获取,可以考虑不支持任意点回放,而是每次都从头开始回放,这样实现起来更容易一点。

就如我前面所说,对于多线程引擎来说,逻辑回放的实现比较困难,那退而求其次,我们可以选择结果回放,结果回放记录的信息就比较“单纯”,就是每次画面需要画的那些Object信息,比如位置等等,回放时,我们只需把记录的结果再重新给渲染器,让它画出来即可。也许大家会问,我们没法重新调试AI的逻辑,这样的回放有什么意义呢?当然,如果只是单纯的把画面重画一遍,是没什么意义,结果回放需要结合另一个AI调试的方法一起来使用。那就是“调试信息”(Debug Draw)。一般引擎都提供一套可以在屏幕上画点圈,画点叉,写点字的接口,AI的调试,就是可以使用这样的接口在屏幕上打印出关键的信息,来帮助我们查看逻辑的“走向”,举个例子来说,我以前写过一篇博文,介绍用分数系统来做AI,如果要调试这样的AI,我们就可以利用调试信息,在屏幕上,将分数的情况都打印出来。由于结果回放是将所有输出到渲染器的信息都保存了下来,所以我们就可以通过回放来观察这些分数的变化,以此来调试AI的行为。结果回放的另一个优势是,它可以轻松的实现任意点的回放,包括后退,前进,暂停等等,因为结果数据和上下文是无关。

不管有没有回放的机制,很多时候AI的调试,都需要调试信息的帮助,可以让我们不用设置断点就知道逻辑的计算,我们甚至需要制作一些工具来获取当前AI的相关状态,比如前几篇说到的那个观察器。这也就是AI调试比较难的地方,一个字,“猜”,当然是有依据的猜,更准确的说,应该是推测吧, :)

不知不觉,写了3篇了,总结下吧,要有好的AI调试体验,我们需要有好的AI架构,这是一切的基础,比如脚本,比如回放,其次要有好的配套工具,来辅助那个“猜”,并能形成独立可复用的模块,然后就是对于标准的遵守,比如不要用“魔数”的问题,当然,还有很多值得我们去想的,这一系列也希望能抛砖引玉,引起大家的思考吧。

相关:

---> 关于调试AI的闲话(1)

---> 关于调试AI的闲话(2)

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

Read More

在《关于调试AI的闲话(1)》,我谈到了一个AI参数的编辑/观察器,用来实时的修改和查看参数,重新审视那篇博文的时候,我发现我还有些需要补充的地方。

首先,我遗漏了一点,就是需要把调试后的参数信息保存下来,然后当游戏中的那些导出的变量初始化的时候,需要把那下存下来的值作为初始值赋给相应的变量,当然,这样一个文件的保存,载入包括赋值的过程,没有很大的技术难点,作为补充,记录在这个地方。另外,我说的这样一个调试器,是一个相当轻量化的解决方式,很独立,可以很容易作为额外的工具,嵌入已有的引擎,当然,正如我在前一篇文章里所说的,它存在这样或者那样的缺点,所以,如果复杂一点话,可以做的更好,比如用反射(Reflection)的解决方案,将AI中用到的物件(Object)或者类整个导出,现在很多引擎都或多或少用到了反射,并提供了强大的可视化编辑器来支持。这样的解决方案和引擎的契合度会很大,挺难独立的剥离出来(当然,也不是不可能)。

好,前面说的是对AI参数方面的调试,另外一种比较流行的方式,是实时的远程命令。通过向游戏引擎发送指令,来使其运行一段预定义的代码,不知道大家有没有玩过CS,CS里面有一个命令控制台,它预定义了一系列可以使用的命令,比如,addbot,votemap等等,这种以控制命令来调整的方式,其实可以非常好的用在AI调试中,而且也是一个非常独立,和轻量化的模块,同样,也是可以用同进程(如CS),或者不同进程的方式来实现,对于不同进程,用网络传输的方式传递命令字串,是一个很方便也很好的办法,因为网络的关系,甚至可以做到跨机器调试。技术上来说,这样的远程命令难点也不是很大,无非是对命令字串的解析,将函数导出成命令的封装。

AI的调试的麻烦之处,很多时候在于编译的速度(如果你有i7+8g内存,那你很幸运),所以上面说的两种方案,都是为了最大化的减少编译次数,但是,在改变AI逻辑的时候,还是不得不重新编译和link游戏,所以,我觉得,作为一个AI程序员,如果在项目起初,如果拿到引擎很“干净”(没有任何游戏逻辑代码),如果引擎没有提供脚本支持,一定要强烈建议做一套脚本化的AI引擎(不一定是全脚本化,但一定要考虑内嵌脚本),原则上来说核心引擎和AI是可以完全分开的,核心引擎部分,在某种程度上,对于AI程序员来说,可以是完全透明的,只要给我一个tick入口,我就能写AI。 :) 。随便说一句,暴雪在脚本化方面做的很好,玩过星际,魔兽的人应该都会有这样感觉,他里面的AI都可以通过外部的方式来改变,确实很强大。其实仔细想想,我们为什么不可以呢?也许我们有时缺少的就是这种对于标准,规范的坚持吧。所以经常我会想,如果有幸我能面试新人,我不会要求你了解多少,知道多少,或者会多少诡异的算法,我会很看重他/她写代码的规范程度,清晰程度,这是会对整个team有益的。

有点扯远了, :) ,总结下,对于影响AI调试的原因一(见前一篇),我想有以下几点能够考虑

  1. 使用脚本化的AI引擎,将AI逻辑与核心引擎分离
  2. 将需要调整或者观察的参数导出,做成一个运行时的参数编译/观察器
  3. 添加远程命令调用
  4. 升级你的电脑到i7+8g内存

好,先写到这里了,下次聊聊对于原因二的一些可以考虑的事情

相关:

--->关于调试AI的闲话(1)

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

Read More

项目进行到后期,越来越多是在修复一些AI的错误和调整AI的行为,但不得不承认,AI有时候很难调试,我想主要是有两个原因,一是现在的引擎越来越复杂,改一点点地方,编译都会等很久,时间上效率不高(所以对于AI程序员来说,真的是非常欢迎那种引擎核心和游戏逻辑分开的架构);二是如果出现问题的话,情况不可重现,或者很难重现。由于以上原因的存在,我一直在考虑如何来改善AI的调试环境,并且使之模块化,以便在不同的引擎上可以重用。

就我上面的第一个原因,如果要提高调试AI的时间上的效率,减少编译次数是一个关键,最近听到有同事抱怨,说他们用的那个引擎,一编译就超过20分钟,不能忍啊!而AI代码里,除了逻辑部分,很多地方是一些可调整的参数,这些参数如果写死在代码里,每次调整,都要重新编译链接,那一天基本上干不了什么活了。所以有一个可以在运行时,动态调整AI参数的编辑器就很重要了。这种参数编辑器的实现方法有很多种,可以实现在同一进程中(随游戏弹一个编辑器出来),也可以通过进程间通信的各种方式,用另一个独立的编辑器来实现。

更进一步,这样参数编辑器的另一个作用,就是查看AI中的各种值的变化,也就是说这个编辑器变成了一个动态的观察器,可以实时的观察那些我们关心的数据变化,举个例子,比如在一般的RPG游戏中,有些技能会提高人物的属性,当这些属性是隐藏的,不会在UI中显示的,或者说UI显示部分还没完成的时候,就需要用到这样的观察器来观测这些属性是否正常的变化。

是编辑器,还是观察器,其实就是对AI中导出变量,哪方是只读,哪方是只写的问题(对于单个变量,不存在两方面都是只写的情况,要不就乱了 :) ),如果用代码来表示的话,我希望是这样的:

class AIExampleClass
{
EXPORT READONLY m_RDValue;
EXPORT WRITABLE m_WRValue;
}

我实现过一个用共享内存作为通信方式的模块,可以方便的在类中导出变量,并且在一个对应的编辑器里修改和观察。基本原理是,在游戏程序启动的时候开了一块共享内存,然后将内存分为头区域和数据区域,头区域存有所有导出变量的信息,数据区存真正的变量数据,当变量发生变化的时候(不管是从游戏端修改,还是从编辑器端修改),会将数据同步更新到共享内存中,保证两边的结果一致。

这样的做的好处是,由于是内存拷贝,所以同步的速度很快,变化很迅速,而且我封装了对于导出变量的声明,几乎可以做到和不导出时,对变量的使用方式是一致的,以实现对代码的改变的最小化,当然,这样的实现有一个缺点,由于对于编辑器而言,它看到的只是内存,所以需要对内存解析有个类似“协议”的声明,以保证正确地解析出变量的值,这个“协议”就需要和游戏的导出变量同步改变了。另外,对于“小型变量”,比如一个bool,这样的导出成本有点高,因为都需要有额外的头部信息。

有了这样的参数编辑/观察器,可以大大的提高调试AI的效率,当然,前提是,要积极使用!,以前我写过一篇叫《AI程序员的痛苦》,因为我们经常可以看到在AI代码中充斥着不知所谓的“魔数”(magical number),这样写起来是简单了,但对以后的调试,别人甚至是自己以后的维护,都是有百害而无一利的。现在,我很推崇这种对于AI参数的管理,希望对大家有所帮助!

先这些,以后再聊~

PS:关于上面说的那个共享内存的模块,我整理一下再放出,写的不好,仅供参考,如果有同学能帮着一起完善,就更是感激不尽了~~

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

Read More

上次提出了关于AI懒惰问题的解决方案(见上一篇),一种称为计时器法,就是通过人为的延时来平滑AI的行为抖动,还有一种称为交叉边界法,通过平滑边际值来解决AI在边际上的行为问题。在讨论的最后,我们看到对于交叉边界法,在结果上看来,稍稍有点不是很符合一开始的对AI的行为定义。

再来看一下这个问题,当红圈从A区域移动到图示中新位置的时候,由于虚拟区域的存在,蓝圈不会移动到D的中心

lazy-1-3

解决这个问题有多种不同的方案,本来嘛,AI的代码基本上没有什么标准答案,我在这里提出我的一个方案,原本我们定义的虚拟区域是静态的,也就是说,大小是固定不变,如果我们改用一个会随时间变化渐渐缩小的虚拟区域,那就可以很好的解决上面的问题,我们对以前的算法做一个补充:

当红圈从B区域进入A区域时,建一个A的虚拟区域,然后随时间,A的虚拟区域渐渐减小直到和A区域一样大
当红圈从A区域进入B区域时,建一个B的虚拟区域,然后随时间,B的虚拟区域渐渐减小直到和B区域一样大
当红圈在A区域,并且不在B的虚拟区域中时,蓝圈的目标点在C的中心
当红圈在B区域,并且不在A的虚拟区域中时,蓝圈的目标点在D的中心

由于虚拟区域随着时间最终会和原来的区域一样大,所以就不存在以前不符合AI预期行为的问题了。 :)

另外,用计时器来控制某些值得变化,是在实践中经常碰到的一个问题,以前经常是用下面的这种方式来做:

if 计时器超时 then
计时器重置
a = 新的值
else
a = 旧的值
end

对于一些有规律,或者重复的东西,自然的就想到是否可以封装一下,用类把一些值定义成所谓的懒惰值(Lazy Value),比如,原本我们对一个布尔值赋值,它的值的变化是“立即的”

bool instantValue = true;
print instantValue;  //输出"true"

而现在我们希望对于懒惰值而言,我们可以延迟某个时间来改变他的值

float updateInterval = 20.f;
LazyBool lazyValue(updateInterval, false); //20秒才会更新一次, 默认值是false
...
lazyValue.Set(curGameTime, true); //赋值,传入当前游戏时间
print lazyValue //如果离上一次更改还没到20秒,输出上一次的值,如果超过20秒,输出"true"

有了这样的概念,这个类应该是比较容易实现的,我在我们的AI系统中用模板的的方式实现了这样一个懒惰值类,作为AI经常会用到的工具类收藏在个人的小本本中, :)

相关:

---> AI中的懒惰(Lazy)问题(1)

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

Read More

最近在路上一直在思考AI中的懒惰问题,为什么会突然想到这个,实在是因为这个问题十分常见,它非常简单,但是又非常难以漂亮的解决。先从一个问题引入吧。看下面这张图

假设我们有一个开阔的战场,这个战场被划分成了4个小区域,A~D来表示,实心小红圈表示进攻方,也是我们控制的人。实心小蓝圈表示防守方,是电脑AI控制的人。防守方为了不让进攻方突破,它有一个很简单的AI算法,当进攻方在A的时候,防守方就跑到C区域的中心(空心圈表示),当在B的时候,防守方就跑到D区域的中心(空心圈表示)。

这个算法看似很完美,但看下面一张图

lazy-1-1

当我们控制小红圈在A和B的边界快速来回移动的时候,试想一下蓝圈的行为,它就会不停在两个目标点转换,如果是带朝向的真实物体,就会发现,蓝圈一直在做180度的大转身,显得非常的傻。这就是AI程序中经常碰到的边界问题,也就是,当判断条件出现边界值的话,在边界附近会出现行为抖动的现象。解决边界问题的一个主要方法就是为AI引入“懒惰”的机制。

所谓“懒惰”,就是通过人为的为AI加入延迟机制,来使AI的行为更为真实。在这里,我们就需要调整我们的算法,既然觉得AI太快,我们就让他慢一点,加入一个计时器,这是非常直观的一种解决方案,我称之为计时器法。描述如下:

当蓝圈根据红圈位置得到一个新的目标点时,我们设定计时器为n秒,这样表示,n秒内目标点不允许被变更,然后计时器开始倒计时,当计时器倒计时结束时,我们再为蓝圈得到一个新的目标点,再次设定计时器,依次类推。

这样当我们在边界点快速移动的时候,蓝圈就不会随之快速的改变目标点了,相当于变得懒惰了,这种做法很简单。在AI中,计时器一直是一个好东西,有时我们不需要AI决策的太频繁,一方面为了真实,一方面也为了优化,这样我们就可以用计时器来控制AI决策的频度。引申一点说,这里设定延迟n,可以每次是一个随机值,随机值的好处就是,当有很多AI需要同时决策的时候,可以避免AI在一帧里集中计算,而其他帧空闲,造成AI决策的峰值。

还有一种Lazy的方法,我称之为交叉边界法,看下面这张图

lazy-1-2

我们为每个区域创建一个虚拟的区域,图中用粉框表示,虚拟区域比原来的区域要大一圈,这就使得A,B的虚拟区域的边界有一部分是重叠的。我们新的算法描述如下:

当红圈在A区域,并且不在B的虚拟区域中时,蓝圈的目标点在C的中心
当红圈在B区域,并且不在A的虚拟区域中时,蓝圈的目标点在D的中心

比较一下原来的算法,多了两个额外的条件,由于虚拟区域的存在,使得边界处不再是,A和B的二元差别,而是变成了A,A&B,B三个值,这样边界的跳变也就被平滑掉了,这种是专为解决边界问题而引入的Lazy机制,它会在边界处存在一定的决策延迟。

针对这个问题,使用上述的算法,会存在一个问题,如下图:

lazy-1-3

当红圈从A区域移动到图示中新位置的时候,由于虚拟区域的存在,蓝圈不会移动到D的中心,这会使得此处的AI行为不符合我们的预期。一个改进的做法是........,下次公布一下我的想法,留给大家可以思考一下。 :)

这两种就是非常常用的使AI懒惰的方法,它们有一些很好的优点,简单,易于实现。但却存在的一个致命的问题,就是需要修改原本的AI代码,而且这两种方法都会使得代码比较丑陋,不宜维护。我一直在想,有没有一个比较通用的解决方案或者代码片段,使得这样的问题得到解决,而不用修改原有的AI算法。欢迎大家留言和我讨论。

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

Read More

接上篇,我们接着聊。

分数系统的打分公式,是根据情况自己定义的,但也有一些方式来帮助构建出比较合理的公式来,公式的推导就是一个函数的拟合过程,我们可以先取几个样点,然后试着找到一条函数曲线,尽可能的去使样点落在我们的这条函数曲线上。在中学的时候的实验课上,大家应该都做过这种事情。在AI中,我们的打分公式,一般不会很复杂,可能是简单的直线,或者分段的折线,有时也会是二次,或三次的曲线。有了这样一个基本曲线,接着再用测试样例去修正,一般就可以得到一个比较符合需求的打分公式了。

在分数系统中,如果有多个因素需要考量,比如我们上个例子中的EC和HP,这就引出了分数如何组合的问题。就像我们先前对Retreat和Shoot的打分方式。常用的做法是,针对每个因素单独引入打分公式,并且归到[min, max]的分数区间中,然后再对所有的得分组合后,得到一个最终得分。对每个因素单独打分的好处是,我们可以跟专注于单个因素的影响,方便我们构建打分公式,并且可以方便的移除和添加新的因素,而且也能更好的复用我们的打分公式。分数的组合一般可以有两种:

1. 加权平均,s = (k1*s1 + k2 * s2 + ... + kn * sn)/(k1 + k2 + ... + kn)
2. 因子连乘,s = s1 * s2 * ... * sn ( 0 <= si <= 1.0 )

这两种方式有各自的适用范围,第一种方式,我们除了对打分公式要细心调整外,还需要对加权因子加以调整。第二种方式必须保证每个因子被归到[0,1]之间,因为用到了乘法的原因,所以体现了一种并且的关系,一旦有一个因子为0,则整个分数就会是0。

分数系统是一种模糊逻辑,他不像基于规则的系统那样逻辑非常清楚,所以,在分数系统中,有时会出现一种“意外点”,但对AI来说,出现一些意外点,也不是不可接受,有时这样也更显得AI很真实,AI也会犯错的嘛。一旦使用了分数系统,debug的过程就变成了不断调整公式和数值的过程。如果设计的好的话,AI程序员可以提供出一套调节分数的接口,这样design也可以参与其中了。

当然,有时分数系统是会和规则系统联合使用的,用来处理一些意外情况。我常觉得,在AI中,规则系统就是用来修bug的。

好了,就聊到这儿,欢迎大家留言

相关:

---> 基于分数系统(Scoring System)的AI设计(1)

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

Read More