游戏算法整理 算法三：寻路算法新思维

目前常用寻路算法是A*方式，原理是通过不断搜索逼近目的地的路点来获得。

 

如果通过图像模拟搜索点，可以发现：非启发式的寻路算法实际上是一种穷举法，通过固定顺序依次搜索人物周围的路点，直到找到目的地，搜索点在图像上的表现为一个不断扩大的矩形。如下：

 很快人们发现如此穷举导致搜索速度过慢，而且不是很符合逻辑，试想：如果要从（0，0）点到达（100，0）点，如果每次向东搜索时能够走通，那么干吗还要搜索其他方向呢？所以，出现了启发式的A*寻路算法，一般通过 已经走过的路程 + 到达目的地的直线距离 代价值作为搜索时的启发条件，每个点建立一个代价值，每次搜索时就从代价低的最先搜索，如下：

 

综上所述，以上的搜索是一种矩阵式的不断逼近终点的搜索做法。优点是比较直观，缺点在于距离越远、搜索时间越长。

 

现在，我提出一种新的AI寻路方式——矢量寻路算法。

 

通过观察，我们可以发现，所有的最优路线，如果是一条折线，那么、其每一个拐弯点一定发生在障碍物的突出边角，而不会在还没有碰到障碍物就拐弯的情况：如下图所示：

 

我们可以发现，所有的红色拐弯点都是在障碍物（可以认为是一个凸多边形）的顶点处，所以，我们搜索路径时，其实只需要搜索这些凸多边形顶点不就可以了吗？如果将各个顶点连接成一条通路就找到了最优路线，而不需要每个点都检索一次，这样就大大减少了搜索次数，不会因为距离的增大而增大搜索时间。

 

这种思路我尚未将其演变为算法，姑且提出一个伪程序给各位参考：

1．                建立各个凸多边形顶点的通路表TAB，表示顶点A到顶点B是否可达，将可达的顶点分组保存下来。如: ( (0,0) (100,0) ),这一步骤在程序刚开始时完成，不要放在搜索过程中空耗时间。

2．              开始搜索A点到B点的路线

3．              检测A点可以直达凸多边形顶点中的哪一些，挑选出最合适的顶点X1。

4．              检测与X1相连（能够接通）的有哪些顶点，挑出最合适的顶点X2。

5．   X2是否是终点B？是的话结束，否则转步骤4（X2代入X1）

 

如此下来，搜索只发生在凸多边形的顶点，节省了大量的搜索时间，而且找到的路线无需再修剪锯齿，保证了路线的最优性。

 

这种方法搜索理论上可以减少大量搜索点、缺点是需要实现用一段程序得出TAB表，从本质上来说是一种空间换时间的方法，而且搜索时A*能够用的启发条件，在矢量搜索时依然可以使用。