— AI分享站

Archive
Tag "懒惰问题"

LOD(Level Of Detail)是3D渲染中用到的概念,按照wikipedia上的翻译,可以译为“细节层次”,它是一种根据与观察点的距离,来减低物体或者模型的复杂度来提升渲染效率的优化技术,因为显而易见的是,当一个物体离我们很远的时候,我们不需要用很复杂的多边形来绘制,只要用一个粗略模型或者低精度的贴图即可,所以在3D渲染中,这是一个很常见的优化技术。

对于AI来说,当一个AI对象离我们很远的时候,其实,它做出什么样的决策,做出什么样的行为,我们并不能“感觉的”到,虽然它的行为可能会对游戏世界有影响,但玩家一般只会专注于离自己比较近的AI行为,所以我们在AI的优化中,也可以采用这种“LOD”的技术,来提升AI部分的运行效率。

我在玩真三国无双的时候,对此非常有感触,虽然我并不知道他是否在AI层做了LOD,但类似于这种大场景,超多NPC的游戏,AI层的LOD的优化技术就非常适合。同样的NPC,当他离玩家不同的距离的时候,我们就可以赋予它不同的AI行为,如下表所示:

  1. 近:攻击,防御,追踪,掩护,包围,等待,...
  2. 中:追踪,包围,等待,...
  3. 远:等待,...
一般来说,AI候选的行为越多,它决策所花费的时间也越多,根据这样的假设,我们就可以通过限制AI行为的方式,来起到提升效率的作用。上面说的是一种LOD的方式,还有一种实现方式是减少AI的决策频率,这也是我以前讨论过的AI中的懒惰问题,比如如下表:
 
  1. 近:攻击,防御,追踪,掩护,包围,等待,...(0.1秒决策一次)
  2. 中:攻击,防御,追踪,掩护,包围,等待,...(1秒决策一次)
  3. 远:攻击,防御,追踪,掩护,包围,等待,...(5秒决策一次)

我们可以根据需要来混合使用上面两种方式。说到这里,我想大家脑海中会有一个自己的代码实现框架,我也想了一种,可以用到我经常说的行为树的方式来实现,行为树最好的就是可以任意的添加行为分支,所以可以说,对于第一种的LOD实现是天生支持的,我们只要建立三个行为分支表示近,中,远,并且在这三个分支下,挂上不同的候选行为,这样,我们就建立了一棵带LOD优化功能的行为树,如下图:

 
Lod1
 
对于第二种LOD实现,我们可以创建一种新的控制节点(回忆一下控制节点的概念),可以称之为LazyNode,这是一个一元的节点,它的功能就是维护一个时钟,当时间一到就执行它的子节点。同样的,我们用LazyNode,也建立近,中,远三个行为分支,然后在下面挂上相关的行为子节点,如下图:
 
Lod1 (1)
可以看到,如果我们用行为树,就不需要用什么附加的模块来做LOD优化,而是用行为树强大的扩展能力把这些直接整合进了AI结构中,这种不破坏结构,从架构层面的优化方式,是我相当推崇的。
LOD是一种懒人化的优化方式,无论是概念还是实现都非常简单,当然,所有这些都是以不破坏游戏性为前提的,有时,我们有可能需要远处的AI做一些复杂的决策,比如,在即时战略游戏中,虽然我们AI离我们很远,但它确实需要做一些完整决策,在这种情况下,LOD可能并不是很适用,所以,AI中的一些问题没有一成不变的解决方案,实际情况,实际分析是相当之重要的 :) ,大家对AI优化有什么心得呢,欢迎大家留言讨论。
 
 
————————————————————————
作者: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