在AI寻路决策中运用势力图(Influence Map)

最近在程序中遇到一个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
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

(已被阅读9,172次)

5 评论

  1. Hi 博主,前段时间在做游戏AI,也是参考了您的行为树节点库来实现的,十分感谢,现在又遇到一个问题,最近在做一个战斗场景,敌对双方的英雄都是运动的,现在需要AI做一些寻路,比如攻击时的寻路和逃跑时的寻路,看了这篇文章受一些启发,就是想问一下文章后面您提到的类似于“导向性寻路”具体如何实现?还请博主看点一下,博主后期有写这个帖子吗?

NavyKing进行回复 取消回复

邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

Copyright © 2011-2020 AI分享站    登录