# PathFinding

**Repository Path**: Aping-Fo/PathFinding

## Basic Information

- **Project Name**: PathFinding
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-05-08
- **Last Updated**: 2024-05-08

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 寻路算法整理，自己使用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*的。