标签归档:pathfinding

关于星际争霸的寻路猜想

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

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

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

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