Unity寻路插件A* pathfinding project中使用influence map机制
发表于2018-09-21
这篇文章主要给大家介绍如何将influence map的机制融入到当前较火的unity寻路插件A* pathfinding project里。加强大家对influence map的认知。
Influence Map基本概念：
influence map中文名：势力图或影响图。以下称势力图。 势力图是基于空间的，某些空间归属A，另外一些空间归属B，等等。
把问题规模缩小到一场游戏战役，每个兵种单位都占据并影响着一定的空间，且相同势力的单位对同一空间的影响可以叠加，影响值随传播距离递减。
势力图除了告诉我们某块空间的归属之外，还传达了什么信息？
1、进攻方，可以根据势力图选择率先攻击敌人薄弱的地方。防御方，可以根据势力图选择一个较为安全的撤退地点。
2、进一步，统计分析，比如采取某种战略之后，观察势力图变化，可以分析之前战略效果。
3、更进一步，通过对一段时间的势力图进行对比，可以大致预测敌军的部署动向。
实现InfluenceMap的要点
1、定义各单位的势力值传播范围，形状，特性（这是Gameplay）由于每个兵种的特性和能力值不同，故每个兵种单位的影响半径与程度不尽相同。
比如：一个坦克可以影响3km之内空间，3km之内都保持较高的影响。而一个机枪兵只能影响1km以内的空间，并且超出500m之后，士兵的影响十分微弱。
坦克相比机枪兵更具影响力，所以想要抵消掉坦克的影响，我们可能需要更多的机枪兵与之对抗。这些数值根据具体的游戏逻辑来设定。
2、实现传播算法，以什么样的方式传播，各势力影响值得叠加逻辑。
3、实现衰减算法，以什么样的方式衰减，常见如影响随距离线性衰减。
本文使用的算法
1、确定传播区域，获取传播区域内node，从center node开始以广度优先遍历区域内node，更新influence值。
2、influence值随传播距离线性衰减。
这是最简单的方法，还有一些提高性能的方法，有兴趣同学可以google之。
寻路与InfluenceMap结合
通过以上的总结，我们已经知道了势力图对于战略的作用。那么对于一般的游戏，我们是否用的上呢？
我现在的想法是，Influence map可以和寻路系统进行融合。比如，NPC在寻路的时候，不是选择一条最短的路径，而是选择一条最安全的路径。
只需想象一下即可，我们需要到达A点，但最短路径上有一个敌方炮塔，我们无法对抗炮塔的攻击，那么我们需要舍近求远，绕道一个炮塔无法攻击的地点，最终到达A点。
截图体现了我们之前总结出的规律：
1、影响的传播，红色区域乃是影响的传播范围。
2、影响的衰减，随着远离中心区域，红色逐渐变浅。
3、障碍物会阻碍影响的传播。
4、寻路小机器人，寻路时试图躲避高危的红色区域。
最后的大体效果：
寻路机器人会躲避敌方静止的机器人，并且双方相互影响。
相关修改文件，有兴趣朋友可以继续研究
编辑器扩展涉及到的文件如下：
Base.cs AStarPath.cs AStarPathEditor.cs astarclassess.cs 核心代码 Color NodeColor (GraphNode node, PathHandler data)
势力图的逻辑涉及到的文件如下：
| astarclassess.cs | InfluenceUpdateObject这是一个新的类，表示那部分导航图需要更新。 可参考 GraphUpdateObject |
| GridNode.cs | / GraphNode.cs 添加node的influence信息。 |
| GridGenerator.cs | 添加node的influence信息更新逻辑。 |
| Seeker.cs | 添加使用AInfluencePath寻路的逻辑。 |
| AInfluencePath.cs | AInfluencePath：ABPath这是一个新的类，用A*算法求取的influence路径。 |
需要重定义public override uint GetTraversalCost (GraphNode node)
最近更新了一些细节：
主要优化了性能。因为A* pathfinding project 使用多线程。所以，在更新graph的Influence信息时，需要block pathfinding thread.否则会出现寻路异常。
在更新完地图后 unblock pathfinding thread，为了防止频繁的block and unblock pathfinding thread，新建一个更新队列，批处理多个agent的更新请求。
如果有需要更新的Influence请求，就会请求block pathfinding thread，但该函数不会一直等待而是立即返回，下一帧查看pathfinding thread是否block。
如果后面某一帧 pathfinding thread block 那么立即批处理更新队列中的请求。 我们可以设置每帧更新请求数量的最大值，以免导致某帧会耗时过长。
没有位置和信息变化的agent不需要请求刷新Influence信息，并且同一个agent新的Influence信息会覆盖后面的信息。这样可以保证queue不会过度膨胀。