跳点寻路算法（Jump Point Search），是一种在线的高效寻路算法。

其精髓在于“跳过”一些明显不必经过的路，抽象地说，就是在搜索时大量减掉明显无用的分支，使得朴素的搜索过程变得高效。正如刚刚说的那样，Jump Point Search（简称JPS）是一个在线（Online）算法，所以无需预处理，而且运行时不占用空间。最美妙的是，JPS可以和现有的搜索加速技术（启发式，记忆化等）结合，爆发出惊人的威力。

    在拜读了相当的论文，资料后，今天终于尝试着把代码写出来了。。。    
    这篇博文算是对这么多天学习的一个总结和笔记吧。
    如有谬误，欢迎指正。

<!-- more -->

一. 从游戏中引出的问题

（本节以下内容略微有些扯淡。。）

以前老喜欢玩DotA/LoL，现在也喜欢玩。玩着玩着就有了一个问题：

    在DotA/LoL游戏中操作一个英雄，从 泉水处 出发去打 肉山/大龙。英雄是按照什么样的路径行走的呢？最近的路径？还是最安全的路径？当然不是最安全的路径了，鬼知道会不会有一群人 开了雾/蹲草丛 来gank你。
    所以我们假设是一条最近的路径，程序是怎么算出这样一条路径的呢？

二. 抽象化的模型

假设游戏地图是一个m*n的方格，地图中有些地方是障碍，问题就是求一条从A点到B点最近的路径。如图：

有很多经典的算法可以用来处理这样的问题。

广度优先搜索（BFS），朴素的盲目搜索算法，编码难度低，实现简单。
深度优先搜索（DFS），较BFS节省空间，但速度更慢，且非常不稳定（有时会过深地陷入某个错误分支）
Dijkstra算法，图论算法，有建图空间开销，速度不稳定，在数据量小的时候，可能还不如盲目搜索。
双向广度搜索，BFS升级版，空间开销更大，编码难度上一个档次，实现复杂。
A*启发式搜索，BFS的启发式版本，速度相当快。但也会有掉进某个“坑”而浪费时间的情况，就常见情况来说，速度非常理想。
IDA*启发式搜索，DFS的启发式版本，速度相当快。比A*好的是，保证了速度的同时减少了空间开销，且编码难度降低。

由于A搜索和接下来的内容有关，所以这里简单介绍一下A的原理。

A*在朴素BFS之上，添加了启发式。就好比是，BFS就像是一个人在迷宫里寻找出口，他老老实实地挨着挨着找。加上启发式，就像是有其他人在出口处放置了一台大功率的喇叭放着《最炫XX风》，于是这个人就不老老实实地找了，他可以听着声音判断自己是不是离出口越来越近了，然后从最近的开始找。

因为我们知道B点的坐标，不知道A到B的路径。我们完全可以根据当前所在的坐标以及B点坐标来判断一下，当前搜索的节点是不是离B点更近了。引入等式： $$f(x)=g(x)+h(x)$$ g(x) 表示从A点到x点所走过的距离。g值是在搜索时可以记录的。

h(x) 表示当前所在的x点到B点的估算距离。h值需要构造一个估价函数进行计算。

f(x) 表示从A到B的估算距离。

在进行BFS的同时，计算f值，并且在进行状态转移时，选择当前f值最小的，即选估计路径最短的一条分支进行搜索。如果走到一个状态不同f值，以前遇到过并且还没有被扩展，那么选择一个f值最小的更新就行。

虽然看起来好像并没有增加太多的东西，但是实现起来需要讲究的地方很多。

所以，真正实现起来一个正确高效的A*算法还是有一些难度。

三. 让搜索“跳”起来

A寻路已经可以很出色地完成我们提出的问题了。在此之上，JPS算法能够让A寻路更上一个档次。

在搜索中，有部分节点的扩展是无用的。如图：

当前按照箭头方向搜索到了x点，至此所有灰色节点都是无用的，因为总是存在一条最近路径可以从x点的父节点出发，不经过x点，而最终到达灰色节点。

但有一些点比较特殊。如图：

所有灰色节点都是无用的，而图中被红圈圈住的点，是不存在一条不经过x点的最近路径可以从x点的父节点出发而到达。而x点就是一条特殊的点，因为有要到达x点的某些后继节点，必须要经过x点，否则就不是最近路径。

所以，JPS实际上是在搜索中寻找跳点的后继节点（jump point successor）而转移状态，而不是直接从当前节点进行扩展。JPS跳过了部分的无用节点，保留关键的“跳点（jump point）”，令A*在搜索时减少了扩展的节点数， 从而达到加速的效果。

四. 查阅过的资料和代码

代码实现使用c++，功能基本实现。代码地址

为了保证算法正确，随机生成了20组数据，在关键地方输出中间变量，然后与github上这位大神的 js版本进行对拍结果一致。

代码风格不太好，而且没有注释…

如有任何错误，欢迎指正。

电子邮箱：JackieDeng.cn@gmail.com