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

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

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

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

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

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

值得注意的是，我这边用了方型的势力靶图，主要是为了简化计算，从效果上来说，和圆形的差别并不是很大，另外，我为势力值定了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
本文欢迎转载和引用，请保留本说明并注明出处
————————————————————————