Unity寻路插件A* pathfinding project中使用influence map机制

发表于2018-09-21
评论0 613浏览

想免费获取内部独家PPT资料库?观看行业大牛直播?点击加入腾讯游戏学院游戏程序行业精英群

711501594
这篇文章主要给大家介绍如何将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.csInfluenceUpdateObject这是一个新的类,表示那部分导航图需要更新。 可参考 GraphUpdateObject
GridNode.cs/ GraphNode.cs  添加node的influence信息。
GridGenerator.cs添加node的influence信息更新逻辑。
Seeker.cs添加使用AInfluencePath寻路的逻辑。
AInfluencePath.csAInfluencePath: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不会过度膨胀。

原文链接

著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引

游戏学院公众号二维码
腾讯游戏学院
微信公众号

提供更专业的游戏知识学习平台