大家好，欢迎大家关注我的知乎专栏- 慢慢悠悠小马车。
- JPS是为了解决A*算法中的路径对称和多余扩展问题，而提出的一种适用于无向归一化代价栅格地图的最优路径搜索算法，一般速度快于A*。（归一化代价指沿不同方向的单位步长的代价相同）
- JPS最初是在《Online Graph Pruning for Pathfinding on Grid Maps》提出的。本文只简述要点。
- JPS特点在于，有选择的只扩展跳点，跳点间的栅格被跳过，不加入OpenList。跳点（Jump Point）就是路径的转折点（Turn Point）。
- 计算跳点的过程，是向2个方向扩展，首先是横平竖直的方向，然后是对角线方向（必须在后）。
- 弄懂这几个重要概念，就可以理解JPS的算法流程了。以下都是基于比较2种路径的长度：parent→center→neighbor VS parent→非center→neighbor。
- 自然邻居：假设中心栅格的8邻域都不被障碍物占据，剪枝后剩余的邻居节点。
- 强迫邻居：8邻域中的非自然邻居，且靠近障碍物。Def1。
- 跳点：满足Def2中的任一条件即可。
- 是终点。
- 有强迫邻居。
- 是路径转折点。（会得到2个跳点）
