和论文： http://www.doc88.com/p-6099778647749.html 的启发和借鉴。
JPS(jump point search)算法实际上是对A 寻路算法的一个改进，即在扩展搜索节点时，提出了更优化的策略，A 在扩展节点时会把节点所有邻居都考虑进去，这样openlist中点的数量会很多，搜索效率较慢。JPS算法通过寻找跳点的方式，排除了大量不感兴趣的点，减少了openlist中搜索的点的数量，速度大大提高。
水平(垂直)搜索：如图右边部分描述，点1和4如果经过x到达，还不如从点p(x)到达，所以不用考虑点1,4，同理继续向右搜索时，点2,5和点3,6，都是类似的情况，直到遇到黑色的障碍，没有发现感兴趣的点，x处水平方向搜索完成，垂直方向搜索类似。如图左边部分描述，在点x处向右搜索至点y时，点y有一个强迫邻居(点7)，因此y是从点x处沿水平方向搜索的一个跳点，需要将y加入到openlist中。水平搜索结束。
对角搜索：斜向搜索时，需要先在当前点的水平和垂直方向搜索一下，看能否找到感兴趣的点，如果找到，则将当前点加到openlist，结束斜向搜索，如果找不到，则继续斜向多走一步，继续，直到找到感兴趣的点或者斜向方向遇到障碍。
一条完整路线的搜索过程：
搜索算法：
下面两张对比图，摘自上面的论文，可以看出，JPS算法实在优秀。
github链接
上图中红色块为节点x，基于前节点为P(x)的情况下的自然邻居节点。而被迫邻居则是图中绿色的方块（其对称情况未画出）。x被迫邻居包含三层隐藏含义：首先被迫邻居的位置是基于P(x)、x、阻挡块的相对关系定的，如第三个图所示，如果第三个图中，P(x)的位置在节点6的位置，那么绿色方块就不是x的被迫邻居了。其次，被迫邻居一点是考察非自然邻居的节点。最后被迫邻居一定是P(x)经过x到达才能取得最短路径的点。
起点S，终点T，黑色块为阻挡黄色块为跳点，红色箭头是搜索方向，但是没有找到跳点，绿色箭头表示找到跳点。横坐标A-N，纵坐标1-10。
起始位置S，将A10加入openlist里，开始算法流程。
从openlist里取出代价最小的节点(现在为S)，当前节点没有方向，所以需要搜索8个方向，只有右上方B9点是跳点。因为根据跳点定义iii，斜向搜索时，需要在两个分量方向查找跳点，右方是墙壁，略过，上方B8点有强迫邻居点C7，所以B8是跳点（根据跳点定义ii），所以B9是跳点。将B9加入openlist里。A10处理完后，将其从openlist中移除，加入closelist里。
从openlist中取出B9点，该点的父亲是S，所以搜索方向为右斜上，需要在右斜上，右方，上方搜索跳点，只有B8满足要求，将B8加入openlist。处理完B9点将其移到closelist。
从openlist取出B8点，该点搜索方向为上，B8有被邻居C7点，在斜上方搜索跳点，可以看出D8是C7的被迫邻居，所以C7是跳点，B8处继续向上搜索结束。
从openlist中取出C7点。需要搜索右上，右，上三个方向。水平搜索时发现被迫邻居D8，加入openlist。右上搜索时发现跳点G3（因其在上方搜索时发现具有被迫邻居节点的G2），将G3加入openlist。C7点处理结束。
取出G3点（为啥是G3，而不是D8点呢，因为从总代价来说G3比D8更小，总代价=已经走过的距离 + 估值，估值可采用曼哈顿距离或者高斯距离），需要搜索右上，右，上三个方向。向上搜索到跳点G2。
其余点路径在图上标注，就不再重复了。
(1) 若current方向是直线
i. 如果current左后方不可走且左方可走，则沿current左前方和左方寻找跳点。
ii. 如果current当前方向可走，则沿current方向寻找跳点。
iii. 如果current右后方不可走且右方可走，则沿current右前方和右方寻找跳点。
(2) 若current方向是斜线
i. 如果当前方向的水平分量可走，则沿current方向的水平分量方向寻找跳点。
ii. 如果当前方向可走，沿current方向寻找跳点。
iii. 如果当前方向的垂直分量可走，则沿current方向的垂直分量方向寻找跳点。
上述算法流程是建立在斜向不可穿过阻挡基础上。
这是一个近年来发现的高效寻路算法。不过有一个限制就是只能在规则的网格地图上寻路，而且图上的点或边不能带权重，也就是不能有复杂的地形，只支持平坦和障碍两种地形。其
思想就是跳过矩形平坦区域的大量对称路径，只寻找所谓的跳跃点，作为搜索的节点。这样做的好处是裁剪了矩形区域内大量的节点，使open
list中的节点数相对较少。要知道，通常启发式搜索算法如A*，大量时间耗费在对open
list的操作上。实现得好的A*算法会使用优先队列，甚至HOT(heap on top）来对操作进行优化。但当open
list中的节点过多，这些操作还是会变得很昂贵。不过JPS有个缺点是每生成一个节点，也就是要找到一个跳跃点，相比较A*算法，是比较昂贵的。幸好通
常来说，得到的收益更多些。所以，在适用的情况下，还是推荐使用JPS的。
具体的实现，主要有两部分。第一部分，从open list中取一个最佳节点，然后从几个特定方向展开搜索，把每个方向得到的跳跃点，加入open list里。第二部分，就是找到一个跳跃点。
对于起始点，可以向所有方向展开搜索。对于其他节点，要看父节点指向本节点的方向，向所有自然邻居和被迫邻居节点方向进行搜索。
例如下图的例子，对于节点n和父节点p和障碍x，+是n的自然邻居，也就是说从p到n到+是最佳路径。如果x不是障碍，从p到n到-不是最佳路径，因为从p到x到-最近。但是如果x是障碍，那么从p到n到-就是最佳路径了，所以这时候称-为被迫邻居。
- + +
x n +
p x -
以上是n和p对角的例子。还有种情况是n和p是直线：
x x -
p n +
x x -
搜
寻跳跃点是递归进行的。首先判断一个节点是否是跳跃点。如果这个点有被迫邻居，那么这个节点就是跳跃点。第二种情况，如果这个节点是目的地节点那么也当作
跳跃点。如果不是，那么就递归地沿本来方向继续搜寻下去。对于对角方向要额外多做两步，即先对其相应的（左右两个）直线方向进行搜索，如果找到跳跃点，就
把自身也当作跳跃点返回。如果直线没找到，那么就一样继续按对角方向递归寻找跳跃点，并返回那个跳跃点。
先看看leetcode上的几道题目，关键字 层序遍历 ，其实就是把一棵树一层一层地遍历，取出每一个节点。当然从根节点到叶子节点，从叶子节点到根节点，每层从左到右，从右到左……都可以衍生成不同的题目。
102. 二叉树的层序遍历
107. 二叉树的层序遍历 II
429. N 叉树的层序遍历
这一类的题目，被归纳在leetcode的 广度优先搜索 标签下
这一类的题目，总结起来可以套用模板来解决，我们需要借用一下数据结构的知识：
队列 ：先进先出，后进后出
在JavaScript中，我们会使用 数组Array 来模拟队列：
先初始化一个 二叉树
先看看102的题目
解题：
从以上例子，只要步骤是：
有一个细节要注意：
这里用的是 pop() 和 unshift() ，是因为队列先进先出的特点，pop()从最后面弹出一个元素，unshift()把新元素放到最前面。 push() 和 shift() 搭配也有相同效果。
107的题目稍微改变了一下，要求输出是[[15,7], [9,20], [3]]，可以看出，就是把102的从上到下输出每一层节点，改成从下到上输出，首先想到的就是把102的数组反转就可以了。
但是，我们可能直接在保存结果数组的时候处理一下：
102中，我们使用 push() 把每一层的节点放入结果数组
107中，结果数组和102的反转了，所以，我们可以把 push() 改成 unshift() 即可，最后得到的结果就是，树的要节点那层在结果数组的最后，叶子节点在最前面。
429题中把二叉树改成了N叉树，树的结构发生了变化
但是可以看到，和二叉树的数据结构相比，就是把left和right合成children，那么在我们的模板中，也只需要修改一下
改成
这样就可以得到结果了。
想一下，如果再改一下：如何从右到左遍历每一层节点？层数是单数时从左到右，层数是双数时从右到左？
再扩展一下，这个算法能做什么呢？
当我们玩游戏，特别是走迷宫之类的游戏，是不是会从一个点出发，然后判断下一步能不能走，直到找出终点？BFS也是寻路方案的基础。
推荐一下leetcode上的总结：
二叉树层序遍历登场：我要打十个！
