实测|A*寻路与JPS寻路同一地图运行效率

学更好的别人，

做更好的自己。

——《微卡智享》

本文长度为1035字，预计阅读3分钟

前言

前面几篇我们把A*算法和JPS的算法都简单介绍了一下，并且展现出来了行动规划，其中A*算法的核心代码我也在《实战|OpenCV结合A*算法实现简单的运动路径规划》中放出来了， 感兴趣的朋友可以连接过去看一下，今天我们就专门对两个算法的运算效果进行一下实测，对比一下看看

对比视频

算法差别

微卡智享

其实在上一篇《实战|JPS跳点寻路实现运行路径规划》介绍JPS算法时，就说到了通过跳点寻路，可以大大地减少了OpenList（开启列表）中的计算点，这样在遍历查找时可以省去大部分的计算量，速度应该是A*的N倍，下面放一下两个算法的流程对比差异，图来自网上找的一篇关于JPS的文章。

其实这张图对我来说真是作用很大，因为开始自已写JPS的算法的时候，总是找不到路径，最后也是因为这张图的启发，发现了问题的所在（当时是找到后直接往OpenList中插入了，后来发现应该是先判断是否存在，如果存在后要修改值）。

好了，别的我就不再费话了，我们直接看看对比效果吧，用了两张图，分别就是前面这几篇我们用到的这几个图。对比图中，用红线画的就是A*计算的路线，用蓝线画的是JPS计算的路线。

简单地图对比

微卡智享

从上图中我们可以看到，两个完成的速度都在一秒内，所以感觉不是很明显，不过从耗时上来看，JPS的算法还是要比A*算法快了很多，当然两个算法的路线有的时候也会有差，这个就是因为从每个点找和从跳点找不同原因造成的。具体的时间差我们可以看下图红框中的，就是A*和JPS所用的时间。

复杂地图对比

微卡智享

从上图中我们可以看出来，前三个我们选择的起点和终点的距离都很近，而且路线比较简单，所以两个差别时间也不大，基本没什么问题，但是后三次我们就选了比较麻烦点的路，明显可以看出，两个算法的耗时差距非常之大。

下图中红色框为简单的路径耗时对比，蓝色框为复杂的路径耗时对比

后三次对比表

结论

从上面的对测试可以看出来，在平面图中路线简单的话两个算法差别不会很大，不过JPS还是要比A*快，但是一到了复杂的计算，A*算法的计算量耗时是成指数级增长（即使通过优化，我们前面有做过，也达不到生产环境可以用到的情况），而JPS算法依然保持的很稳定。所以一般的平面路径规划来说，大部分场景用JPS的算法即可解决问题。

完