转：跳点搜索算法JPS及其优化（万字长文）
歡迎關注作者git博客
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格子的尋路算法。A*算法整體流程如表2.1.1所示，JPS算法在保留A*算法的框架的同時，進一步優化了A*算法尋找后繼節點的操作。為了說明JPS在A*基礎上的具體優化策略，我們在圖2.1.1中給出A*和JPS的算法流程圖對比。由圖2.1.1看出，JPS與A*算法主要區別在后繼節點拓展策略上，不同于A*算法中直接獲取當前節點所有非關閉的可達鄰居節點來進行拓展的策略，JPS根據當前結點current的方向、并基于搜索跳點的策略來擴展后繼節點，遵循“兩個定義、三個規則”（見表2.1.2，兩個定義確定強迫鄰居、跳點，三個規則確定節點的拓展策略），具體流程如下：
??一，若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.1.1 A*和JPS的算法流程圖對比
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?表2.1.1 A*算法流程
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
Step 1. 將起始點start加入開啟集合openset
Step 2. 重復以下工作：
? ? 一、當openset為空，則結束程序，此時沒有路徑。
? ? 二、尋找openset中F值最小的節點，設為當前點current
? ? 三、從openset中移出當前點current
? ? 四、關閉集合closedset中加入當前點current
? ? 五、若current為目標點goal，則結束程序，此時有路徑生成，此時由goal節點開始逐級追溯路徑上每一個節點x的父節點parent(x)，
? ? ? ? 直至回溯到開始節點start，此時回溯的各節點即為路徑。
? ? 六、對current的八個方向的每一個相鄰點neighbor
? ? ? ? 1．如果neighbor不可通過或者已經在closedset中，略過。
? ? ? ? 2．如果neighbor不在openset中，加入openset中
? ? ? ? 3．如果neighbor在openset中，G值判定，若此路徑G值比之前路徑小，則neighbor的父節點為current，同時更新G與F值。
? ? ? ? ? ?反之，則保持neighbor和原父節點的關系與G、F值。G值表示從起點到當前點路徑耗費；H值表示不考慮不可通過區域，當前點到終點的理論路徑耗費；F=G+H。
術語參考：
? ? current?? ?當前節點
? ? openset?? ?開啟節點集合，集合內節點有待進一步拓展
? ? closedset?? ?關閉節點結合，集合內節點不再拓展
? ? neighbor?? ?鄰居，與當前節點相鄰的節點
? ? parent(x)?? ?節點x的父節點，即算法尋得的路徑中節點parent(x)的下一節點為x
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 表2.1.2 JPS算法的“兩個定義、三個規則”
定義一，強迫鄰居（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，因為跳點會改變行走方向，而非跳點不會改變行走方向，最后尋找出來的路徑點也都是跳點。
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右邊的阻擋。
圖2.2.1
表2-2-1.png 表2.2.1 A*和JPS的尋路消耗對比
??上述的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.1.1
3.1.2 JPS效率優化之二JPS-BitPrune：位運算與剪枝優化
??利用位運算和剪枝優化的JPS-BitPrune在JPS-Bit的基礎上進一步進行剪枝優化，剪掉不必要的中間跳點（見表2.1.2，定義二第(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的剪枝優化示例
??下面以圖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。
1
2
3
4
5
6
7
8
場景二（剪枝中間跳點） 在剪枝中間跳點之后，從節點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中節點的拓展順序和拓展“跨度”，加快尋路效率。由于預處理版本的JPS需要存儲八個方向最多能走多少步，如果地圖大小是N*N，每個方向最多能走的步數用16位數表示，則需要存儲空間N*N*8*16bit，如果N為1024，則大概需要存儲空間為16M，存儲空間占用較大，使用該版本JPS時需要權衡是否以空間換時間。為降低預處理數據占用的內存，本項目也提供每個方向最多能走的步數用8位數表示的源碼，尋路速度和步數用16位數表示的源碼差異1%左右，但內存減少一半。另外預處理的時間對小于1024*1024個格子的圖可以在1秒內處理完，但對于2048*2048個格子的圖需要一小時左右處理完，建議提前預處理完并存到文件中，程序啟動時讀文件即可。
??其中，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 JPS-BitPre尋路的場景示例
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 以圖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；三，從openset取出F值最小節點T，為目的點，搜索結束，
? ? 此時獲得的路徑為N(4,5)、節點11(3,4) 、節點T(3,3)。
1
2
3
4
5
6
7
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 為了說明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)。
1
2
3
4
5
??對比發現，經過預處理的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，而且只有當走到一個路點后，才采樣檢查該路點之后的路點是否可以合并，將采樣的消耗平攤在行走的過程中，因此采樣的消耗可以忽略。
圖3.4.1
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.1.1 GPPC比賽用的地圖集
圖4.1.1 GPPC的三類游戲場景地圖示例
圖4.1.2 GPPC的三類人造場景地圖示例
圖4.1.3 GPPC的六類地圖大小分布
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中該列數字之前的“+”表示采用并行計算進行預處理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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種算法沒有嚴格的優劣關系，只是在不同指標下的表現各有側重，算法的使用者可基于對不同指標的具體需求來選擇自己適用的算法。
表4.3.1 GPPC2014的比賽結果
下面給出所有在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帕累托最優。
---------------------?
作者：runzhiwang.github.io?
來源：CSDN?
原文：https://blog.csdn.net/yjxxtd/article/details/93506231?
版權聲明：本文為博主原創文章，轉載請附上博文鏈接！
總結
以上是生活随笔為你收集整理的转：跳点搜索算法JPS及其优化（万字长文）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： [Redis6]常用数据类型_List列
- 下一篇： [Redis6]常用数据结构_Hash哈