关于星际争霸的寻路猜想

今天把一个月的翻译成果总算上传了,质量不高,主要还是因为自己英文太次,不过在翻译之后,突然想到自己估计之前的群体动态寻路算法整复杂了,基于矩形网格的动态a星算法完全可以达到灵活度和效率的最大化。

我之前在战天下使用的是基于可见点与矩形网格的方式(参考0.A.D开源项目),但是在大规模动态单位碰撞时,可见点寻路的瓶颈非常明显,因为可见点寻路的寻路图的所有边的数量级与图的数量呈N^2的方式上升,所以寻路效率很低,哪怕我将寻路线程分离也不能有效的处理寻路请求。

完全基于矩形网格的寻路,只要网格的单位足够小,一个单位所占的格子虽然比较多,但是寻路的效率应该还是有所保证的,毕竟A*不会搜索所有的图,而碰撞跟寻路图本身不是完全对应的,碰撞的时候才需要考虑重新寻路的问题,所以特别离散的寻路图设计不会影响到单位碰撞半径的设计。

看了星际争霸制作者的一篇日志,更加印证了我的一些想法,我希望下次有机会实现下这个方案。

关于星际争霸的寻路猜想》上有2条评论

  1. matrix

    你好!我最近也在研究群体寻路的相关问题。我采用的HPA* 的分层寻路思路,但在群体移动的时候,如果大规模的移动避免重叠比较纠结,最初是比较土的方式把控制放在AI逻辑里面,在发生路劲阻塞的时候,等待1s后在尝试,如果还是阻塞,就再次通过其他路劲。后来发现steeringbehavior + fieldflow、rov之类的方法,不知道你是采用怎么样的方案解决群体移动避免互相重叠的反复

    回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注