游戏寻路中 A* 算法的改进

Chengsoul

在众多寻路算法中，A* 的确是比较不错的。但在游戏寻路领域，A* 耗时过大，显然需要改进。

改进

我的想法是预先将地图按照一定的规则划分为多个区域，这些区域彼此连通，并且计算好彼此连通的区域之间的来往的消耗（预计算部分，经检测耗时极少）。

从几千个正方形组成的障碍矩阵中构造出一张数据量大大减少的带权连通图。

每次寻路时自动检测起始位置和终点分别在图中的哪两个节点，在很短时间内构造出一条最短路径。

接着，计算进入以及离开每个区域的比较适合的点，再经过路径平滑算法，得到的路径与传统 A* 没有明显区别，但是中间节点减少，耗时大大减少。经过计算，耗时为传统 A* 的 1/800 - 1/1000，取得相当显著的效果。而且对于 A* 其他的改进措施，也可以用在该改进方法上，如双向 A*，在较复杂的图中可以明显加快寻路速度。并且该寻路代码也可以放在非主线程中，影响更是可以忽略不计。

（改进 A* 路径）

（传统 A* 路径）

在障碍图中的信息发生改变时，可以重新进行计算，得出新的带权连通图，并且广播所有已经寻路完成但是还没有达到终点的物体，使其修改路径，耗时同样在可接受范围内。


总结

该 A* 改进算法是典型的以空间换时间的算法（虽然耗费的空间也很少，在游戏领域可以忽略）

接下去我会继续研究比如策略游戏中一个群体单位寻路算法的改进，因为他们无论起始点是否在同个区域，在带权连通图中总会经过相同的节点，这些计算完全可以缓存下来，减轻后面计算的负载。

文/wyj1998
来源：indienova
原文：https://mp.weixin.qq.com/s/JD9bFJvirP-OBR-ZFGbukg