readme.md

寻路算法整理，自己使用java实现完整代码及性能测试

主要整理格子地图的寻路算法，包括主流的A*和JPS及JPS+

测试地图数据使用项目中maps/maze-100-1.map

性能测试结果

A*寻路

• 性能测试：

次数	G距离公式	H启发函数	耗时ms	close大小	备注
10000	直接获得	manhattan	6000	1641	[1,39]->[99,65] 大概纵100*横25的距离，地形非常复杂，寻路节点80个。

JPS寻路

• 性能测试：

次数	G距离公式	H启发函数	耗时ms	close大小	备注
10000	octile	manhattan	1600	419	[1,39]->[99,65] 大概纵100*横25的距离，地形非常复杂，寻路节点80个。

JPS算法简介

核心思路，定义一些特征点为跳点，寻找跳点，同样和A类似使用open和close处理。 和A相比，增加了周围点的查找和判断，但是大大减少了点进入open和close列表， 而open表的操作是有一定代价的，正是基于这样的特性才将性能得到了优化。同时JPS也有自己的缺点， 在我用java实现的JPS中，查找跳点的jump方法里有用到递归， 而递归深度会增加jvm的方法栈调用，但是任何递归其实也都是可以消除的，下一步优化就是把递归消除。

JPS和A*对比，在下面一些情况下更适合使用：

• 1.地图取格子的信息代价低 （绝大多数的地图格子信息都是预存好的，取格子信息的代价也就是在数组中获取值， 代价非常低。这里举一个特殊的例子：我们的游戏中设计是不预存格子信息的， 所以取格子信息的代价就不能忽略，这样的情况可能就不适合使用jps了）。
• 2.地图格子数不是很大（也就是地图很大的情况下，而且地图大部分点都是可行走的情况下， jps查找跳点时会经常需要遍历到地图的边缘，这样的情况jps会遍历格子的信息比较多。 但是真正对性能产生的影响可能也是有限的，因为取格子的代价非常低。 注意：格子地图不管在什么情况下都不建议太大，无论在内存还是在A或者JPS上都非常不友好。 如果使用A来处理这样的大地图，对于一个没有路径的两点寻路时，不进行特殊优化的情况下，需要检测的格子数几乎也会遍历整个地图）。
• 3.jps的寻路结果天然最优解并且达到合并节点的效果，这点A*是不具备的，需要最后生成路径的时候，自己动手合并节点。

综上：大部分地图取格子的代价非常低，地图也不会设计的非常大，这样在性能和内存使用方面，JPS都是优于A*的。