最快速的尋路演算法 Jump Point Search

作者：runzhiwang，騰訊 TEG 后臺開發工程師

本文介紹一種跳點搜索演算法 JPS 以及其四個優化演算法，其尋路速度最快可是 A*演算法的 273 倍，文中的 JPS-Bit 和 JPS-BitPrune 都支持動態阻擋，

1.引言

尋路演算法用途眾多，例如在游戲和地圖中，A*演算法已經眾所周知，對于其優化也是層出不窮，然而性能并沒有取得突破性進展，本文介紹 JPS 的效率、多執行緒、記憶體、路徑優化演算法，為了測驗搜索演算法的優化性能，實驗中設定游戲場景使得起點和終點差距 200 個格子，需要尋路 10000 次，

結果發現，A*尋路總時間約 2.6074x1011 納秒（一秒為 109 納秒）；基礎版 JPS 尋路總時間 1.7037x1010 納秒；利用位運算優化的 JPS（下文稱 JPS-Bit）尋路總時間 3.2364x109 納秒；利用位運算和剪枝優化的 JPS（下文稱 JPS-BitPrune）尋路總時間 2.3703x109 納秒；利用位運算和預處理的 JPS（下文稱 JPS-BitPre）尋路總時間 2.0043x109 納秒；利用位運算、剪枝和預處理三個優化的 JPS（下文稱 JPS-BitPrunePre）尋路總時間 9.5434x108 納秒，

其中的預處理在一些文章被稱為 JPS+，本文的 JPS-Bit 和 JPS-BitPrune 都支持動態阻擋，本文解決了絕大部分開源 JPS 存在的潛在 BUG：穿越阻擋，在圖 2.2.1 中，從 H 走到 K 時，穿越 H 右邊阻擋，

上述結果表明，尋路 200 個格子的路徑，JPS 的五個版本，平均消耗時間分別為 1.7 毫秒、0.32 毫秒、0.23 毫秒、0.02 毫秒、0.095 毫秒，尋路速度分別為 A*演算法的 15 倍、81 倍、110 倍、130 倍、273 倍，大幅度超越 A*演算法，標志著尋路已經不會成為性能的瓶頸，

事實上，在 2012 到 2014 年舉辦的三屆（目前為止只有三屆）基于 Grid 網格尋路的比賽 GPPC（The Grid-Based Path Planning Competition）中，JPS 已經被證明是基于無權重格子，在沒有預處理的情況下尋路最快的演算法，

本文接下來介紹 JPS 基礎版本以及四個優化演算法；然后解讀 GPPC2014 的比賽，介紹 GPPC 的比賽地圖資料，并從尋路時間、路徑長度、消耗記憶體、失敗率等方面比較 22 個參賽尋路演算法的優劣，

2.JPS 演算法

2.1 演算法介紹

JPS 又名跳點搜索演算法（Jump Point Search），是由澳大利亞兩位教授于 2011 年提出的基于 Grid 格子的尋路演算法，JPS 演算法在保留 A*演算法的框架的同時，進一步優化了 A*演算法尋找后繼節點的操作，為了說明 JPS 在 A*基礎上的具體優化策略，我們在圖 2.1.1 中給出 A*和 JPS 的演算法流程圖對比，由圖 2.1.1 看出，JPS 與 A*演算法主要區別在后繼節點拓展策略上，不同于 A*演算法中直接獲取當前節點所有非關閉的可達鄰居節點來進行拓展的策略，JPS 根據當前結點 current 的方向、并基于搜索跳點的策略來擴展后繼節點，遵循“兩個定義、三個規則”，

定義一，強迫鄰居（forced neighbour）：如果節點 n 是 x 的鄰居，并且節點 n 的鄰居有阻擋（不可行走的格子），并且從 parent(x)、x、n 的路徑長度比其他任何從 parent(x)到 n 且不經過 x 的路徑短，其中 parent(x)為路徑中 x 的前一個點，則 n 為 x 的強迫鄰居，x 為 n 的跳點，例如圖 2.2.1 中，尋找從 S 到 E 的路徑時，K 為 I 的強迫鄰居（I 為 K 的跳點），這里不認為從 H 到 K 能走，因為對角線有阻擋（這點和論文不一致，但和代碼一致，因為如果 H 到 K 能直接到達，會走進 H 右邊的阻擋區，大部分的 JPS 開源代碼根據論文都認為 H 到 K 能直接到達，所以存在穿越阻擋的情況），如果需要 H 到 K 可走，則 K 為 H 的強迫鄰居（H 為 K 的跳點），

定義二，跳點（jump point）：（1）如果點 y 是起點或目標點，則 y 是跳點，例如圖 2.2.1 中，S 是起點也是跳點，E 是目標點也是跳點；

（2）如果 y 有強迫鄰居則 y 是跳點， 例如 I 是跳點，請注意此類跳點和強迫鄰居是伴生關系，從定義一強迫鄰居的定義來看 n 是強迫鄰居，x 是跳點，二者的關系是伴生的，例如圖 2.2.1 中 K 的鄰居只有 I 是跳點，M 雖然也是 K 的鄰居，但 M 不是跳點，因為 K 不是 M 的強迫鄰居；

（3）如果 parent(y)到 y 是對角線移動，并且 y 經過水平或垂直方向移動可以到達跳點，則 y 是跳點，例如圖 2.2.1 中 G 是跳點，因為 parent(G)為 S，S 到 G 為對角線移動，從 G 到跳點 I 為垂直方向移動，I 是跳點，所以 G 也是跳點，

規則一：JPS 搜索跳點的程序中，如果直線方向（為了和對角線區分，直線方向代表水平方向和垂直方向，且不包括對角線等斜線方向，下文所說的直線均為水平方向和垂直方向）、對角線方向都可以移動，則首先在直線方向搜索跳點，再在對角線方向搜索跳點，規則二：（1）如果從 parent(x)到 x 是直線移動，n 是 x 的鄰居，若有從 parent(x)到 n 的路徑不經過 x 且路徑長度小于或等于從 parent(x)經過 x 到 n 的路徑，則走到 x 后下一個點不會走到 n；

（2）如果從 parent(x)到 x 是對角線移動，n 是 x 的鄰居，若有從 parent(x)到 n 的路徑不經過 x 且路徑長度小于從 parent(x)經過 x 到 n 的路徑，則走到 x 后下一個點不會走到 n（相關證明見論文），

規則三：只有跳點才會加入 openset，因為跳點會改變行走方向，而非跳點不會改變行走方向，最后尋找出來的路徑點也都是跳點，尋路具體流程如下：

一，若 current 當前方向是直線方向：（1）如果 current 左后方不可走且左方可走（即左方是強迫鄰居），則沿 current 左前方和左方尋找不在 closedset 的跳點；（2）如果 current 當前方向可走，則沿 current 當前方向尋找不在 closedset 的跳點；（3）如果 current 右后方不可走且右方可走（右方是強迫鄰居），則沿 current 右前方和右方尋找不在 closedset 的跳點；

二，若 current 當前方向為對角線方向：（1）如果 current 當前方向的水平分量可走（例如 current 當前為東北方向，則水平分量為東，垂直分量為北），則沿 current 當前方向的水平分量尋找不在 closedset 的跳點；（2）如果 current 當前方向可走，則沿 current 當前方向尋找不在 closedset 的跳點；（3）如果 current 當前方向的垂直分量可走（例如 current 當前為東北方向，則水平分量為東，垂直分量為北），則沿 current 當前方向的垂直分量尋找不在 closedset 的跳點，JPS 尋找跳點的程序有三種優化：一，位運算；二；預處理；三；剪枝中間跳點，

2.2 JPS 演算法舉例

下面舉例說明 JPS 具體的尋路流程，示例如圖 2.2.1 所示，5*5 的網格，黑色代表阻擋區，S 為起點，E 為終點，

JPS 要尋找從 S 到 E 的最短路徑，首先初始化將起點 S 加入 openset，從 openset 取出 F 值最小的點 S，并從 openset 洗掉，加入 closedset，S 的當前方向為空，則沿八個方向尋找跳點，在該圖中從 S 出發只有下、右、右下三個方向可走，但向下搜索到 D 遇到邊界，向右搜索到 F 遇到阻擋，因此都沒有找到跳點，然后沿右下方向尋找跳點，在 G 點，根據上文定義二的第（3）條，parent(G)為 S，praent(G)到 S 為對角線移動，并且 G 經過垂直方向移動（向下移動）可以到達跳點 I，因此 G 為跳點 ，

將 G 加入 openset，從 openset 取出 F 值最小的點 G，并從 openset 洗掉，加入 closedset，因為 G 當前方向為對角線方向（從 S 到 G 的方向），因此在右（當前方向水平分量）、下（當前方向垂直分量）、右下（當前方向）三個方向尋找跳點，在該圖中從 G 出發只有向下可走，因此向下尋找跳點，根據上文定義二的第（2）條找到跳點 I，將 I 加入 openset，從 openset 取出 F 值最小的點 I，并從 openset 洗掉，加入 closedset，因為 I 的當前方向為直線方向（從 G 到 I 的方向），在 I 點時 I 的左后方不可走且左方、前方可走，因此沿左、左前、前尋找跳點，但左前、前都遇到邊界，只有向左尋找到跳點 Q（根據上文定義二的第（2）條）），因此將 Q 加入 openset，

從 openset 取出 F 值最小的點 Q，并從 openset 洗掉，加入 closedset，因為 Q 的當前方向為直線方向，Q 的左后方不可走且左方、前方可走，因此沿左、左前、前尋找跳點，但左前、前都遇到邊界，只有向左尋找到跳點 E（根據上文定義二的第（1）條）），因此將 E 加入 openset，從 openset 取出 F 值最小的點 E，因為 E 是目標點，因此尋路結束，路徑是 S、G、I、Q、E，

注意，本文不考慮從 H 能走到 K 的情況，因為對角線有阻擋，如果需要 H 到 K 能直接到達，則路徑是 S、G、H、K、M、P、E，修改跳點的計算方法即可，但在游戲中如果 H 到 K 能直接到達，則會穿越 H 右邊的阻擋，

上述的 JPS 尋路效率是明顯快于 A*的，原因在于：在從 S 到 A 沿垂直方向尋路時，在 A 點，如果是 A*演算法，會將 F、G、B、H 都加入 openset，但是在 JPS 中這四個點都不會加入 openset，對 F、G、H 三點而言，因為從 S、A、F 的路徑長度比 S、F 長，所以從 S 到 F 的最短路徑不是 S、A、F 路徑，同理 S、A、G 也不是最短路徑，根據上文規則二的第（1）條，走到 A 后不會走到 F、G，所以 F、G 不會加入 openset，雖然 S、A、H 是 S 到 H 的最短路徑，但因為存在 S、G、H 的最短路徑且不經過 A，據上文規則二的第（1）條，從 S 走到 A 后，下一個走的點不會是 H，因此 H 也不會加入 openset；對 B 點而言，根據上文規則三，B 不是跳點，也不會加入 openset，直接走到 C 即可，

表 2.2.1 所示為 A*和 JPS 在尋路消耗中的對比，D. Age: Origins、D. Age 2、StarCraft 為三個游戲龍騰世紀：起源、、龍騰世紀 2、星際爭霸的場景圖集合，M.Time 表示操作 openset 和 closedset 的時間，G.Time 表示搜索后繼節點的時間，可見 A*大約有 58%的時間在操作 openset 和 closedset，42%時間在搜索后繼節點；而 JPS 大約 14%時間在操作 openset 和 closedset，86%時間在搜索后繼節點，避免在 openset 中加入太多點，從而避免過多的維護最小堆是 JPS 比 A*快的原因（最小堆插入新元素時間復雜度 log(n)，洗掉最小元素后調整堆，時間復雜度也為 log(n)），實際上在從 S 到 E 的尋路程序中，進入 openset 的只有 S、G、I、Q、E，

3.JPS 優化

3.1 JPS 演算法的五個效率優化演算法

3.1.1 JPS 效率優化之一 JPS-Bit：位運算優化

利用位運算優化的 JPS-Bit 的關鍵優化思路在于利用位運算來優化 JPS 中節點拓展的效率，JPS-Bit 和下文介紹的 JPS-BitPrune 支持動態阻擋，當動態阻擋出現時，將格子標記為阻擋，當動態阻擋消失時，將格子標記為非阻擋，如果動態阻擋占據 k 個格子，則時間復雜度為 O(k)，下面以圖 3.1.1.1 中的場景示例說明如何將位運算融合于 JPS 演算法中，其中黑色部分為阻擋，假設當前位置為 I（標藍位置），當前方向為右，位運算中使用 1 代表不可走，0 代表可走，則 I 當前行 B 的八位可以用八個 bit：00000100 表示，I 上一行 B-的八位可以用八個 bit：00000000 表示，I 的下一行 B+的八位可以用八個 bit：00110000 表示，在當前行尋找阻擋的位置可以用 CPU 的指令__builtin_clz(B)（回傳前導 0 的個數），即當前阻擋在第 5 個位置（從 0 開始），

尋找當前行的跳點可以用__builtin_clz(((B->>1) && !B-) ||((B+>>1) && !B+)) 尋找，例如本例中(B+>>1) && !B+為：(00110000 >> 1) && 11001111，即 00001000，而(B->>1) &&!B 為 00000000，所以__builtin_clz(((B->>1) && !B-) ||((B+>>1) && !B+))為__builtin_clz(00001000)為 4，所以跳點為第 4 個位置 M（從 0 開始），注意論文中使用_builtin_ffs(((B-<<1) && !B-) ||((B+<<1) && !B+))，__builtin_ffs(x)回傳 x 的最后一位 1 是從后向前第幾位，比如 7368（1110011001000）回傳 4，因為論文對格子的 bit 編碼采用小端模式，而這里對格子的 bit 編碼采用大端模式，

由于 JPS-Bit 使用運算效率更高的位運算和 CPU 指令運算來優化原始 JPS 節點擴展程序中的遍歷操作，JPS-Bit 的演算法效率高于原始的 JPS，實測中 JPS-Bit 的尋路時間比 JPS 縮短 5 倍左右，

3.1.2 JPS 效率優化之二 JPS-BitPrune：位運算與剪枝優化

利用位運算和剪枝優化的 JPS-BitPrune 在 JPS-Bit 的基礎上進一步進行剪枝優化，剪掉不必要的中間跳點（定義二第(3)條定義），根據定義二，中間跳點在節點拓展程序中只具有簡單的“承接”作用，不具備拓展價值，將中間跳點放入 openset 會增大擴展的次數，因此 JPS-BitPrune 將中間跳點全部洗掉，將中間跳點后繼跳點中的非中間跳點的父跳點改為中間跳點的父跳點，可以有效避免冗余的節點拓展運算，

拐點獲取：值得一提的是，JPS-BitPrune 由于洗掉了中間跳點，因此 JPS-BitPrune 需要在搜索到完整的路徑之后以一定的策略在最后尋得的路徑中加入中間拐點，使得每兩個相鄰的路徑節點之間都是垂直、水平、對角線方向可達的，對此，JPS-BitPrune 采用的具體方法如下：

假設目前搜索到的路徑為 start(jp1)、jp2、jp3...jpk..end(jpn)，對每兩個相鄰的跳點 jpi、jpi+1，一，如果 jpi、jpi+1 的 x 坐標或者 y 坐標相等，說明這兩個跳點在同一個水平方向或垂直方向，可以直線到達，無需在這兩個跳點之間加入拐點；二，如果 jpi、jpi+1 的 x 坐標和 y 坐標都不相等，（1）如果 x 坐標的差 dx（即 jpi 的 x 坐標減去 jpi+1 的 x 坐標）和 y 坐標的差 dy 的絕對值相等，說明這兩個跳點在對角線方向，也可以直線到達，無需在這兩個跳點之間加入拐點；（2）如果 x 坐標的差 dx 和 y 坐標的差 dy 的絕對值不相等，說明這兩個跳點不在對角線方向，并且有可能不能直線到達（因為跳點附近有阻擋），此時 jpi、jpi+1 之間只需要加入一個從 jpi 出發離 jpi+1 最近的對角線上的點即可（jpi、jpi+1 不能水平、垂直、對角線到達，說明 jpi、jpi+1 之間一定存在被剪枝的中間跳點，只需要補上離 jpi+1 最近的一個中間跳點充當拐點即可，該拐點即為 jpi 沿對角線方向走 min(dx,dy)步到達的點），

下面以圖 3.1.2.1 的問題場景示例 JPS-BitPrune 如何在剪枝的同時進行尋路，起點為 S（坐標為(1,1)，即 S(1,1)），節點 1、4、6 均為中間跳點：因為節點 2、3 是滿足定義二第(2)條的跳點，所以節點 1 是為了到達節點 2、3 的中間跳點，同理節點 4、6 也為中間跳點，在剪枝中間跳點之前，要將中間跳點的后繼節點的父節點調整為該中間跳點的父節點，例如圖 3.1.2.1 中，節點 1 的后繼跳點為節點 2、3、4，其中節點 4 也為中間跳點，刪掉中間跳點中的節點 1 后，節點 2、3 的父跳點由節點 1 改為節點 S，洗掉中間跳點中的節點 4 后，節點 4 的后繼跳點 5 的父跳點由節點 4 改為節點 S（節點 4 的父跳點為節點 1，但節點 1 已經被刪掉，因此回溯到節點 S），洗掉中間跳點中的節點 6 后，節點 6 的后繼跳點 7 的父跳點由節點 6 改為節點 S（節點 6 的父跳點為節點 4，但節點 4 被刪，節點 4 的父跳點節點 1 也被刪，因此回溯到節點 S），

上述程序是簡化的邏輯描述，實際運行中的做法是從節點 S 尋找跳點，首先找到中間跳點節點 1，然后在水平方向和垂直方向尋找到跳點節點 2、3，將節點 2、3 的父跳點設為節點 S；繼續沿對角線方向尋找跳點，走到節點 4 后，沿水平方向和垂直方向尋找到跳點節點 5，將節點 5 的父跳點設為節點 S；繼續沿對角線方向尋找跳點，走到節點 6 后，沿水平方向和垂直方向尋找到跳點 7，將跳點 7 的父跳點設為節點 S，因此 JPS-BitPrune 獲得路徑 S(1,1) 、節點 7(4,6)，因為路徑中 S(1,1)無法垂直、水平、對角線方向走到節點 7(4,6)，需要加入中間拐點，根據上述的拐點添加策略，有 dx 為 3，dy 為 5，需要從 S 沿對角線走 3 步，即節點 6(4,4)可作為中間拐點，因此，在圖 3.1.2.1 的示例中，JPS-BitPrune 最后構建的完整路徑為 S(1,1) 、節點 6(4,4) 、節點 7(4,6)，

3.1.2.1 剪枝的優化效率

下面通過對比剪枝前后的 JPS 節點拓展的情況來說明剪枝操作的優化效率：

場景一（無剪枝）如果不對中間跳點進行剪枝，那么從節點 S 尋路到節點 7 將經歷如下程序：(1)從節點 S 搜索跳點，找到跳點節點 1，openset 此時只有節點 1；

(2)從 openset 取出 F 值最小跳點節點 1，并搜索節點 1 的后繼跳點，水平方向和垂直方向找到跳點節點 2、3，對角線方向找到跳點節點 4，此時 openset 有節點 2、3、4；

(3)從 openset 取出 F 值最小跳點節點 4，并搜索節點 4 的后繼跳點，水平和垂直方向找到跳點節點 5，對角線方向找到跳點 6，此時 openset 有節點 2、3、5、6；

(4)從 openset 取出 F 值最小跳點節點 6，垂直方向找到跳點 7，此時 openset 有節點 2、3、5、7；

(5)從 openset 取出 F 值最小的跳點節點 7，為目的點，搜索結束，因此完整路徑為節點 S(1,1)、節點 1(2,2) 、節點 4(3,3) 、節點 6(4,4) 、節點 7(4,6)，JPS 在到達目的節點 7 之前，需要接連拓展中間跳點 1，4，6，

場景二（剪枝中間跳點）在剪枝中間跳點之后，從節點 S 尋路到節點 7 的流程得到了明顯簡化：

(1)從節點 S 尋找跳點，首先找到中間跳點節點 1，然后在水平方向和垂直方向尋找到跳點節點 2、3，將節點 2、3 的父跳點設為節點 S；繼續沿對角線方向尋找跳點，走到節點 4 后，沿水平方向和垂直方向尋找到跳點節點 5，將節點 5 的父跳點設為節點 S；繼續沿對角線方向尋找跳點，走到節點 6 后，沿水平方向和垂直方向尋找到跳點 7，將跳點 7 的父跳點設為節點 S；繼續沿對角線方向尋找跳點，遇到阻擋，搜索終止，此時 openset 有節點 2、3、5、7；

(2)從 openset 取出 F 值最小的跳點節點 7，為目的點，搜索結束，此時獲得的路徑為 S(1,1)、節點 7(4,6)，不同于無剪枝的 JPS 需要拓展中間跳點 1、4、6，在 JPS-BitPrune 中，節點 1、4、6 作為中間跳點均被剪枝，有效避免了冗余的節點拓展，尋路效率得到大大提升，

3.1.3 JPS 效率優化之三 JPS-BitPre：位運算與預處理

本優化中的預處理在一些文章被稱為 JPS+，JPS-BitPre 和 JPS-BitPrunePre 都不支持動態阻擋，因為動態阻擋的出現會導致八個方向最多能走的步數發生變化，從而導致預處理的結果不再準確，利用位運算和預處理的 JPS-BitPre 依舊采用 JPS-Bit 中的位運算，而其中的預處理則是對每個點存盤八個方向最多能走的步數 step，這個 step 值將影響 JPS 中節點的拓展順序和拓展“跨度”，加快尋路效率，

step 值由跳點、阻擋、邊界等決定，如果遇到跳點，則 step 為走到跳點的步數；否則 step 為走到阻擋或邊界的步數，例如對圖 3.1.3.1 中的 N 點，向北最多走到節點 8，即 2 步；向南最多走到節點 4，即 4 步；向西最多走到節點 6，即 3 步；向東最多走到節點 2（節點 2 是滿足定義二第（2）條的跳點），即 5 步；西北最多走到節點 7，即 2 步；東北最多走到節點 1（節點為 1 是上文定義二第（3）條定義的跳點），即 1 步；西南最多走到節點 5，即 3 步；東南最多走到節點 3（節點 3 是上文定義二第（3）條定義的跳點），即 3 步，

以圖 3.1.3.1 中的場景為例，要尋找從節點 N 到節點 T 的路徑，JPS-BitPre 的尋路流程如下：

(1)從 openset 取出節點 N， 從 N 沿八個方向尋找跳點，根據預處理得到的各方向最遠可走的 step 值，可以快速確定八個方向最遠能到達的節點{1，2，3，4，5，6，7，8}，如圖 3.1.3.1 所示，其中，節點 1、2、3 均為滿足定義二的跳點，直接加入 openset，對于節點 4、5、6、7、8，首先判斷終點 T 位于以 N 為中心的南、西南、西、西北、北的哪部分，因為 T 位于西南方向，只有節點 5 位于西南方向，因此節點 4、6、7、8 直接略過，在從 N 到 5 的方向上，N 可走 3 步，而 N 和 T 的 x 坐標差絕對值 dx 為 1，y 坐標差絕對值 dy 為 2，因此將從節點 N 到節點 5 方向上走 min(dx,dy)步即節點 11，加入 openset；

(2)從 openset 取出 F 值最小節點 11，垂直方向找到跳點 T，加入 openset；

(3)從 openset 取出 F 值最小節點 T，為目的點，搜索結束，此時獲得的路徑為 N(4,5)、節點 11(3,4) 、節點 T(3,3)，

為了說明 JPS-BitPre 尋路的準確性與高效率，這里給出原始 JPS-Bit 從 N 到 T 的尋路流程作為對比：

(1)從 openset 取出節點 N 后，需要沿八個方向尋找跳點，節點 1、3、11 為上文定義二第（3）條定義的跳點，加入 openset，節點 2 為上文定義二的第（2）條定義的跳點，加入 openset；

(2)從 openset 取出 F 值最小節點 11，垂直方向找到跳點 T，加入 openset；

(3)從 openset 取出 F 值最小跳點 T，為目的點，搜索結束，此時獲得的路徑也為 N(4,5)、節點 11(3,4) 、節點 T(3,3)，對比發現，經過預處理的 JPS-BitPre 和只使用位運算的 JPS-Bit 最后尋得的路徑是一樣的，然而，由于 JPS-BitPre 無需在每一步節點拓展程序中沿各方向尋找跳點，其可以根據預處理得到的 step 值快速確定 openset 的備選節點，從而大大提升尋路效率，

3.1.4 JPS 效率優化之五：空間換時間

openset 采用最小堆實作，最小堆的底層資料結構是一個陣列，從最小堆中插入、洗掉時間復雜度為 O(logn)，除了洗掉還需要查找操作，每次找到一個跳點，都需要判斷在最小堆中是否有，如果有，則判斷是否更新 G 值、F 值、父跳點等，如果沒有，則加入 openset，在最小堆的中查找操作時間復雜度 O(n)，因此需要優化，closedset 存的是已經從 openset 中彈出的跳點，實際只需要對每個跳點加個標記即可，如果跳點打上標記，則表示是 closedset 中跳點，否則不是，

綜合上述需求，針對 1km*1km 的地圖，構建 2k*2k 的二維陣列 matrix，陣列每個元素 pnode 均為一個指標，指標的物件型別包括節點 id、是否擴展過 expanded(即是否在 closedset 中)、G 值、F 值、父跳點指標 parent、在最小堆中的索引 index 等 12 個 byte，

如果地圖(x,y)處是搜索到的跳點，首先檢查在二維陣列 matrix 對應的(x,y)處指標 pnode 是否為空，如果為空，表示該跳點之前未搜索過，從記憶體池 new 出一個跳點，將指標加到最小堆 openset 中，并在執行 shift up、shift down 操作之后，記錄在最小堆中的索引 index；如果不為空，則表示該跳點之前搜索過，首先檢查 expand 標記，如果為真，則表示在 closedset 中，直接跳過該跳點；否則表示在 openset 中，通過 matrix(x,y)記錄的在 openset 中的索引 index 找到對應的指標，檢查 matrix(x,y)和 openset(index)的指標是否相等進行二次確認，然后檢查判斷是否需要更新 G 值、F 值、父跳點等，采用空間換時間的方法可以將 openset 和 closedset 中查找操作降為 O(1)，游戲中有很多場景，無需為每個場景構建一個 matrix，以最大的場景的大小構建一個 matrix 即可，

3.2 多執行緒支持

游戲服務器普遍采用單行程多執行緒架構，多執行緒下，不能對 JPS 尋路加鎖，否則尋路串行化，失去了多執行緒的優勢，為了支持多執行緒 JPS 尋路，需要將一些變數宣告為執行緒獨有 thread_local，例如上文提到的為了優化 openset 和 closedset 的查找速度，構建的二維跳點指標陣列 matrix，該陣列必須為執行緒獨有，否則，不同執行緒在尋路時，都修改 matrix 元素指向的跳點資料，例如 A 執行緒在擴展完跳點后，將 expanded 標記為真，B 執行緒再試圖擴展該跳點時，發現已經擴展過，就直接跳過，導致尋路錯誤，

3.3 JPS 記憶體優化

3.3.1 分層

JPS 的地圖格子粒度如果采用 0.5m*0.5m，每個格子占 1bit，則 1km*1km 的地圖占用記憶體 2k*2k/8 個 byte，即 0.5M；為了向上、向下也能通過取 32 位數獲得向上、向下的 32 個格子阻擋資訊，需要存將地圖旋轉 90 度后的阻擋資訊；上文 JPS 優化之四：不可達兩點提前判斷，需要存連通資訊，假設連通區數目最多 15 個，則需記憶體 2k*2k/2 個 byte，即 2m，則記憶體為：原地圖阻擋資訊 0.5m、旋轉地圖阻擋資訊 0.5m、連通區資訊 2m，即 3m，另外，上文提到用空間換時間的方法，為了優化 openset 和 closedset 的查找速度，構建二維跳點指標陣列 matrix，1km*1km 的地圖，格子粒度為 0.5m*0.5m，構建出的 matrix 指標陣列大小為 2k2k4byte 即為 8m，為了支持多執行緒，該 matrix 陣列必須為 thread_local，即執行緒獨有，16 個執行緒共需記憶體 16*8m 即為 128m，記憶體空間太大，因此需要優化這部分記憶體，

首先將 2k*2k 分成 100*100 的塊，即 20*20 個塊，20*20 個塊為第一層陣列 firLayerMatrix，100*100 為第二層陣列 secLayerMatrix，firLayerMatrix 的 400 個元素為 400 個指標，每個指標初始化為空，當遍歷到的跳點屬于 firLayerMatrix 中(x,y)的塊時，則從記憶體池 new 出 100*100*4byte 的 secLayerMatrix，secLayerMatrix 每個元素也是一個指標，指向一個從記憶體池 new 出來的跳點，例如，搜索 2k*2k 的地圖時，在(231,671)位置找到一個跳點，首先檢查 firLayerMatrix 的(2,6)位置指標是否為空，如果為空，則 new 出 100*100*4byte 的 secLayerMatrix，繼續在 secLayerMatrix 查找(31,71)位置檢查跳點的指標是否為空，如果為空，則從記憶體池 new 出來跳點，加入 openset，否則檢查跳點的 expanded 標記，如果標記為真，表示在 closedset 中，直接跳過該點，否則表示在 openset 中，判斷是否更新 G 值、F 值、父節點等，

因為游戲中 NPC 尋路均為短距離尋路，JPS 尋路區域最大為 80*80，一個 secLayerMatrix 是 100*100，因此只需要一個 secLayerMatrix，則兩層 matrix 大小為：20*20*4byte+100*100*4byte 即為 0.04m，所以 16 個執行緒下，總記憶體為：原地圖阻擋資訊 0.5m、旋轉地圖阻擋資訊 0.5m、連通區資訊 2m、兩層 matrix0.04m*16，共 3.64M，游戲中場景最多不到 20 個，所有場景 JPS 總記憶體為 72.8M，

3.3.2 記憶體池

在搜索程序中，每次將一個跳點加入 openset，都需要 new 出對應的節點物件，節點物件中存節點 id、父節點、尋路消耗等共 12 個 byte，為了減少記憶體碎片，以及頻繁 new 的時間消耗，需要自行管理記憶體池，每次 new 節點物件時，均從記憶體池中申請，為了防止記憶體池增長過大，需要限制搜索步數，

記憶體池是在真正使用記憶體之前，先申請分配一定數量的、大小相等(一般情況下)的記憶體塊留作備用，當有新的記憶體需求時，就從記憶體池中分出一部分記憶體塊，若記憶體塊不夠再繼續申請新的記憶體，

本文的記憶體池共有兩個：一，跳點的記憶體池，初始大小為 800 個跳點，當 new 的跳點數目超出 800 個，即停止尋路，因為服務器用 JPS 進行 NPC 的尋路，NPC 不會進行長距離尋路，假設 NPC 尋路上限距離是 20m，則尋路區域面積是 40m40m，格子數 8080 即 6400，經統計跳點數目占所有格子數目的比例不到 1/10， 即跳點數目少于 640，因此 800 個跳點足夠使用，800 個跳點共占記憶體 800byte*12，即為 9.6k，忽略不計；二，secLayerMatrix 指向的 100*100*4byte 的記憶體池，因為每次尋路都需要至少一個 secLayerMatrix，如果每次尋路都重新申請，尋路完后再釋放，會造成開銷，因此 secLayerMatrix 指向的 1001004byte 的空間也在記憶體池中，申請時，從記憶體池拿出，釋放時，放回記憶體池即可，secLayerMatrix 記憶體池占記憶體 0.04m，

3.4 路徑優化

如圖 3.4.1 所示，綠色格子為起點，紅色格子為終點，灰色格子為跳點，藍線為 JPS 搜出來的路徑，灰色虛線為搜索程序，可以看出，從綠色格子到紅色格子可以直線到達，而 JPS 搜索出來的路徑卻需要轉折一次，在游戲表現上，會顯得比較奇怪，因此在 JPS 搜索出來路徑后，需要對路徑進行后處理，

比如 JPS 搜出來的路徑有 A、B、C、D、E、F、G、H 八個點，走到 A 時，需要采樣檢查 A、C 是否直線可達，如果 A、C 直線可達，再檢查 A、D 是否直線可達，如果 A、D 直線可達，繼續檢查 A、E，如果 A、E 直線不可達，則路徑優化為 A、D、E、F、G、H，走到 D 時，再檢查 D、F 是否直線可達，如果 D、F 直線可達，繼續檢查 D、G，如果 D、G 直線不可達，則路徑優化為 A、D、F、G、H，依此類推，直到走到 H，因為采樣檢查的速度很快，大約占 JPS 尋路時間的 1/5，而且只有當走到一個路點后，才采樣檢查該路點之后的路點是否可以合并，將采樣的消耗平攤在行走的程序中，因此采樣的消耗可以忽略，

4.GPPC 競賽解讀

4.1 GPPC 競賽與地圖資料集

基于格子的尋路一直是被廣泛研究的熱點問題，也有很多已經發表的演算法，但是這些演算法沒有相互比較過，因此也難辨優劣，使用者如何選擇演算法也有很大的困難，為了解決這個問題，美國丹佛大學的 Nathan R. Sturtevant 教授創辦了基于 Grid 格子的尋路比賽：The Grid-Based Path Planning Competition，簡稱 GPPC，目前已經在 2012、2013、2014 舉辦過三次，下文主要討論 GPPC2014，

GPPC 比賽用的地圖集如表 4.1.1 所示，地圖資料主要分為游戲場景圖和人造地圖，其中來自游戲場景圖的資料有三類：Starcraft（星際爭霸）、Dragon Age2（龍騰世紀 2）、Dragon Age:origins（龍騰世紀：起源），三個游戲分別提供地圖 11、57、27 張，提供尋路問題 29970、54360、44414 個，來自人造地圖有三類：迷宮、隨機、房間，三類資料分別提供地圖 18、18、18 張，提供尋路問題 145976、32228、27130 個，六類資料共提供地圖 132 張，尋路問題 347868 個，圖 4.1.1 中給出三個游戲的場景圖示例，圖 4.1.2 中給出三類人造地圖示例，其中黑色代表阻擋區，白色代表可行走區，地圖大小從 100*100 到 1550*1550，六個地圖集的大小分布如圖 4.1.3 所示，橫坐標是格子數，縱坐標是地圖數目，最小的地圖來自 Dragon Age:origins（龍騰世紀：起源），最大的地圖來自 Starcraft（星際爭霸）和人造資料，

4.2 GPPC 的評價體系

GPPC 在相同的配置下運行參賽演算法，其中 CPU 的配置是 Xeon E5620，四核處理器、2.4Ghz 主頻，12G 記憶體，為了消除誤差，GPPC 要求對每個參賽的尋路方法在 34868 個尋路問題上運行 5 遍，共尋路 34868*5，即 174340 次，所以下文介紹的總運行時間等指標都是尋路 174340 次的結果匯總，其中運行時間包括：加載預處理資料和尋路時間，而預處理時間并不計算在運行時間內，

GPPC 定義如下 13 個指標來評價尋路演算法（其中，路徑表示從起點到終點的完整路徑）：

1. Total (秒)：尋路 174340 次所花費的總時間，

2. Avg(毫秒)：尋路 174340 次的平均時間，

3. 20 Step(毫秒)：尋找到路徑的前 20 步所花費的平均時間，該指標衡量最快多久可以跟隨路徑，在實時互動例如游戲中，該指標很重要，

4. Max Segment(毫秒)：每條路徑最長段的尋路平均時間，該指標衡量在實時互動中，尋路方法最差情況下的表現，

5. Avg Len：路徑的平均長度，如果 A 尋路演算法在長路徑上表現好，在短路徑上表現不好；B 尋路演算法在長路徑上表現不好，在短路徑上表現好，則 A 的該指標優于 B 的指標，因為 Avg Len 的增加主要來自長路徑，該指標偏向于在長路徑上表現好的尋路方法，

6. Avg Sub-Opt：尋到的路徑長度/最優路徑長度 的平均值，如果 A 尋路方法在長路徑上表現好，在短路徑上表現不好；B 路徑尋路方法在長路徑上表現不好，在短路徑上表現好，則 B 的該指標優于 A 的指標，因為 174340 次尋路大多數的路徑都是短路徑，該指標偏向于在短路徑上表現好的尋路方法，

7. Num Solved：在 174340 次尋路中，成功的數目，

8. Num Invalid：在 174340 次尋路中，回傳錯誤路徑的數目，錯誤路徑：路徑的相鄰路點無法直線到達，

9. Num UnSolved：在 174340 次尋路中，沒有尋找到路徑的數目，

10. RAM(before)(兆)：尋路演算法在加載預處理資料后，尋路之前占用的記憶體，

11. RAM(after)(兆)：尋路 174340 次后占用的記憶體，包括所有尋路結果占用的記憶體，

12. Storage：預處理的資料占用的硬碟大小，

13. Pre-cmpt(分鐘)：預處理資料花費的時間，表 3 中該列數字之前的“+”表示采用并行計算進行預處理，

4.3 GPPC 參賽演算法及其比較

目前為止參加 GPPC 競賽的演算法共有 22 個，其中參加 GPPC2014 的有 14 個，可大致分為如下 4 類：一，對 A*的改進，例如 Relaxed A*(RA*)和 A* Bucket；二，利用格子特點的演算法，例如 Jump Point Search(JPS)和 SubGoal Graphs；三，預先生成任意兩點第一個路點的壓縮資料庫，例如 SRC；四，基于節點優先級的演算法，例如 Contraction Hierarchy(CH)，

表 4.3.1 給出參加 GPPC2012、2013、2014 的共 22 個演算法的結果對比，其中前 14 個為參與 GPPC2014 的演算法，其中第一列（Entry 列）為演算法名，其后 13 列給出每個演算法在 13 個指標下的表現，第一列被黑體加粗的演算法表示該演算法在某些指標（帕累托最優的指標）達到帕累托最優，該演算法所在的行被加粗的指標，表示帕累托最優的指標，帕累托最優表示：沒有其他演算法在帕累托最優的指標上均優于當前演算法，例如 JPS(2012)帕累托最優的指標：第 6 個指標 Avg Sub-Opt 和第 12 個指標 Storage，達到帕累托最優，表示沒有其他演算法在 6 個指標 Avg Sub-Opt 和第 12 個指標 Storage 上均優于 JPS(2012)，22 種演算法沒有嚴格的優劣關系，只是在不同指標下的表現各有側重，演算法的使用者可基于對不同指標的具體需求來選擇自己適用的演算法，

下面給出所有在 GPPC 中獲得帕累托最優的演算法，本文介紹的 JPS 演算法位列其中，

1.RA*(2014)：第 10 個指標 RAM(before)和第 12 個指標 Storage 帕累托最優，

2.BLJPS(2014)：第 2 個指標 Avg、第 6 個指標 Avg Sub-Opt 和第 12 個指標 Storage 帕累托最優，

3.BLJPS2(2014)：第 2 個指標 Avg、第 6 個指標 Avg Sub-Opt 和第 12 個指標 Storage 帕累托最優，

4.RA-Subgoal(2014)：第 2 個指標 Avg 和第 12 個指標 Storage 帕累托最優，

5.NSubgoal(2014)：第 2 個指標 Avg、第 6 個指標 Avg Sub-Opt 和第 12 個指標 Storage 帕累托最優，

6.CH(2014)：第 2 個指標 Avg、第 6 個指標 Avg Sub-Opt 和第 12 個指標 Storage 帕累托最優，

7.SRC-dfs-i(2014)：第 3 個指標 20 Step 和第 4 個指標 Max Segment 帕累托最優，8.SRC-dfs(2014)：第 2 個指標 Avg 和第 6 個指標 Avg Sub-Opt 帕累托最優，

9.JPS(2012)：第 6 個指標 Avg Sub-Opt 和第 12 個指標 Storage 帕累托最優，本文的主角 JPS 在未使用預處理的演算法中 Avg Sub-Opt 表現最優，

10.PDH(2012)：第 3 個指標 20 Step 和第 12 個指標 Storage 帕累托最優，11.Tree(2013)：第 2 個指標 Avg 帕累托最優，

歡迎關注我們的視頻號：騰訊程式員

最新視頻：鵝廠程式員用代碼畫企鵝

騰訊技術官方交流微信群已經開放

進群添加微信：journeylife1900

（備注：騰訊技術）