寻路和避障算法

最近需要实现一个后端控制逻辑的多人多兵种的自动战斗机器人。其中就需要涉及到寻路和避障的问题。这里简单记录一下遇到的问题和解决方案。

寻路

说到寻路，首先想到星寻路算法，我们把地图抽象成了格子就像图中所示
星寻路算法
至于星寻路算法算法如何编写已经他的原理就不再赘述。我一开始对多物体寻路的做法是，把所有物体也看做障碍物，这样多物体之间就不会发生碰撞。这样的好处是代码逻辑非常简单，缺点是增加了地图的复杂度，即使在小地图上星寻路算法的成本也很高。用性能诊断工具在一个40*45的地图上，200个战斗单位每个物体每次寻路需要耗费1000多微秒（虽然开启了性能诊断工具检测性能程序会比平时运行慢很多）也就是1毫秒左右，这样如果50毫秒为1帧，每帧只能寻路50个单位，这样是不满足需求的。所以把所有物体也看做障碍物这样是不不可行的。

避障

如果不允许把单位看成障碍物，那物体之间就要用到避障算法，由于之前没有接触过这个话题，所以只能在网上查找到好的做法。一番查找后我选择了避障算法，这种算法把物体抽象成圆形物体，有半径和速度，通过速度和半径预判两物体是否相撞，如果相撞就转变方向,从而实现避障。用了避障算法后就不用把物体看做障碍了。经过我的测试每次避障的消耗在14微秒左右，效率不错！并且这个算法的官方示例中也可以支持同时避障移动圆形物体和静态的矩形障碍物，我认为如果游戏中如果只存在少量的方块形障碍物的时候，不使用其他寻路算法直接采用边避障边寻路的方式也是可行的。