概念
- 強迫鄰居（Forced Neighbour）
- 跳點（Jump Point）
JPS 尋路演算法（Jump Point Search）
- 實作原理
- 示例程序
JPS+（Jump Point Search Plus）
- 預處理
- 示例程序
總結
參考

概念

JPS（jump point search）演算法實際上是對A* 尋路演算法的一個改進，因此在閱讀本文之前需要先了解A*演算法，A* 演算法在擴展節點時會把節點所有鄰居都考慮進去，這樣openlist中點的數量會很多，搜索效率較慢，

若不了解A*演算法，可以參考博主以前寫的一篇文章 A* 尋路演算法 - KillerAery - 博客園

例如在無遮擋情況下（往往會有多條等價路徑），而我們希望起點到終點實際只取其中一條路徑，而該路徑外其它節點可以沒必要放入openlist（不希望加入沒必要的鄰居），

其次我們還希望直線方向上中途的點不用放入openlist，如果只放入每段直線子路徑的起點和終點，那openlist又可以少放很多沒必要的節點：

可以看到 JPS 演算法搜到的節點總是“跳躍性”的，這是因為這些關鍵性的節點都是需要改變行走方向的拐點，因此這也是 Jump Point 命名的來歷，

在介紹JPS等演算法具體實作前，我們必須先掌握下面的概念，

強迫鄰居（Forced Neighbour）

強迫鄰居：節點 x 的8個鄰居中有障礙，且 x 的父節點 p 經過x 到達 n 的距離代價比不經過 x 到達的 n 的任意路徑的距離代價小，則稱 n 是 x 的強迫鄰居，

看定義也許十分晦澀難懂，直觀來說，實際就是因為前進方向（父節點到 x 節點的方向為前進方向）的某一邊的靠后位置有障礙物，因此想要到該邊靠前的空位有最短的路徑，就必須得經過過 x 節點，

可能的情況見圖示，黑色為障礙，紅圈即為強迫鄰居：

（左圖為直線方向情況下的強迫鄰居，右圖為斜方向情況下的強迫鄰居）

跳點（Jump Point）

跳點：當前點 x 滿足以下三個條件之一：

節點 x 是起點/終點，
節點 x 至少有一個強迫鄰居，
如果父節點在斜方向（意味著這是斜向搜索），節點x的水平或垂直方向上有滿足條件a，b的點，

節點y的水平或垂直方向是斜向向量的拆解，比如向量d=(1,1)，那么水平方向則是(1,0)，并不會往左搜索，只會看右邊，如果向量d=(-1,-1)，那么水平方向是(-1,0)，只會搜索左邊，不看右邊，其他同理，

下圖舉個例子，由于黃色節點的父節點是在斜方向，其對應分解成向上和向右兩個方向，因為在右方向發現一個藍色跳點，因此黃色節點也應被判斷為跳點：

JPS 尋路演算法（Jump Point Search）

實作原理

JPS 演算法和A* 演算法非常相似，步驟大概如下：

openlist取一個權值最低的節點，然后開始搜索，（這些和A*是一樣的）
搜索時，先進行 直線搜索（4/8個方向，跳躍搜索），然后再 斜向搜索（4個方向，只搜索一步），如果期間某個方向搜索到跳點或者碰到障礙（或邊界），則當前方向完成搜索，若有搜到跳點就添加進openlist，

跳躍搜索是指沿直線方向一直搜下去（可能會搜到很多格），直到搜到跳點或者障礙（邊界），一開始從起點搜索，會有4個直線方向（上下左右），要是4個斜方向都前進了一步，此時直線方向會有8個，

若斜方向沒完成搜索，則斜方向前進一步，重復上述程序，

因為直線方向是跳躍式搜索，所以總是能完成搜索，

若所有方向已完成搜索，則認為當前節點搜索完畢，將當前節點移除于openlist，加入closelist，
重復取openlist權值最低節點搜索，直到openlist為慷訓者找到終點，

下面結合圖片更好說明程序2和3：首先我們從openlist取出綠色的節點，作為搜索的開始，先進行直線搜索，再斜向搜索，沒有找到任何跳點，

斜方向前進一步后，重復直線搜索和斜向搜索程序，仍沒發現跳點，

斜方向前進兩步后，重復直線搜索和斜向搜索程序，仍沒發現跳點，

斜方向前進了三步后（假設當前位置為 x），在水平直線搜索上發現了一個跳點（紫色節點為強迫鄰居），

于是 x 也被判斷為跳點，添加進openlist，斜方向結束，綠色節點的搜索程序也就此結束，被移除于openlist，放入closelist，

示例程序

下面展示JPS演算法更加完整的程序：
假設起點為綠色節點，終點為紅色節點，

重復直線搜索和斜向搜索程序，斜方向前進了3步，在第3步判斷出黃色節點為跳點（依據是水平方向有其它跳點），將黃色跳點放入openlist，然后斜方向搜索完成，綠色節點移除于openlist，放入closelist，

對openlist下一個權值最低的節點（即黃色節點）開啟搜索，在直線方向上發現了藍色節點為跳點（依據是紫色節點為強迫鄰居），類似地，放入openlist，

由于斜方向還沒結束，繼續前進一步，最后一次直線搜索和斜向搜索都碰到了邊界，因此黃色節點搜索完成，移除于openlist，放入closelist，

對openlist下一個權值最低的節點（原為藍色節點，下圖變為黃色節點）開啟搜索，直線搜索碰到邊界，斜向搜索無果，斜方繼續前進一步，仍然直線搜索碰到邊界，斜向搜索無果，

由于斜方向還沒結束，繼續前進一步，

最終在直線方向上發現了紅色節點為跳點，因此藍色節點先被判斷為跳點，只添加藍色節點進openlist，斜方向完成，黃色節點搜索完成，

最后openlist取出的藍色節點開啟搜索，在水平方向上發現紅色節點，判斷為終點，演算法完成，

回憶起跳點的第三個判斷條件（如果父節點在斜方向，節點x的水平或垂直方向上有滿足條件a，b的點），會發現這個條件判斷是最復雜的，在尋路程序中，它使尋路多次在水平節點上搜到跳點，也只能先添加它本身，其次，這也是演算法中需要使用到遞回的地方，是JPS演算法性能瓶頸所在，

JPS+（Jump Point Search Plus）

JPS+ 本質上也是 JPS尋路，只是加上了預處理來改進，從而使尋路更加快速，

預處理

我們首先對地圖每個節點進行跳點判斷，找出所有主要跳點：

然后對每個節點進行跳點的直線可達性判斷，并記錄好跳點直線可達性：

若可達還需記錄號跳點直線距離：

類似地，我們對每個節點進行跳點斜向距離的記錄：

剩余各個方向如果不可到達跳點的資料記為0或負數距離，如果在對應的方向上移動1步后碰到障礙（或邊界）則記為0，如果移動n+1步后會碰到障礙（或邊界）的資料記為負數距離-n

最后每個節點的8個方向都記錄完畢，我們便完成了JPS+的預處理程序：

以上預處理程序需要有一個資料結構存盤地圖上每個格子8個方向距離碰撞或跳點的距離，

示例程序

做好了地圖的預處理之后，我們就可以使用JPS+演算法了，大致思路與JPS演算法相同，不過這次有了預處理的資料，我們可以更快的進行直線搜索和斜向搜索，

在某個搜索方向上有：

對于正數距離 n（意味著距離跳點 n 格），我們可以直接將n步遠的節點作為跳點添加進openlist
對于0距離（意味著一步都不可移動），我們無需在該方向搜索；
對于負數距離 -n（意味著距離邊界或障礙 n 格），我們直接將n步遠的節點進行一次跳點判斷（有可能滿足跳點的第三條件，不過得益于預處理的資料，這步也可以很快完成），

如下圖示，起始節點通過已記錄的向上距離，直接將3步遠的跳點添加進openlist，而不再像以前需要迭代三步（還每步都要判斷是否跳點）：