JPS/JPS+ 尋路算法

Posted on by

目錄

  • 概念
    • 強迫鄰居（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* 算法非常相似，步驟大概如下：

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

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

  1. 若斜方向沒完成搜索，則斜方向前進一步，重複上述過程。

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

  1. 若所有方向已完成搜索，則認為當前節點搜索完畢，將當前節點移除於openlist，加入closelist。
  2. 重複取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，而不再像以前需要迭代三步（還每步都要判斷是否跳點）：

其它過程也是類似的：

總結

可以看到 JPS/JPS+ 算法里只有跳點才會被加入openlist里，排除了大量不必要的點，最後找出來的最短路徑也是由跳點組成。這也是 JPS/JPS+ 高效的主要原因。

JPS ：

  • 絕大部分地圖，使用 JPS 算法都會比 A* 算法更快，內存佔用也更小（openlist里節點少了很多）。
  • JPS 在跳點判斷上，要盡可能避免遞歸的深度過大（或者期待一下以後出現避免遞歸的算法），否則在超大型的地圖裡遞歸判斷跳點可能會造成災難。
  • JPS 也可以用於動態變化的地圖，只是每次地圖改變都需要再進行一次 JPS 搜索。
  • JPS 天生擁有合併節點（亦或者說是在一條直線里移除中間不必要節點）的功能，但是仍存在一些可以繼續合併的地方。
  • JPS 只適用於 網格（grid）節點類型，不支持 Navmesh 或者路徑點(Way Point)。

JPS+ ：

  • JPS+ 相比 JPS 算法又是更快上一個檔次（特別是避免了過多層遞歸判斷跳點），內存佔用則是每個格子需要額外記錄8個方向的距離數據。
  • JPS+ 算法由於包含預處理過程，這讓它面對動態變化的地圖有天生的劣勢（幾乎是不可以接受動態地圖的），因此更適合用於靜態地圖。
  • JPS+ 預處理的複雜度為 \(O(n)\) ，n 代表地圖格子數。
算法 性能 內存佔用 支持動態地圖 預處理 支持節點類型
A* 中等 大 支持 無 網格、Navmesh、路徑點
JPS 快 偏小 支持 無 網格
JPS+ 非常快 中等 不支持 有，\(O(n)\) 網格

綜上，JPS/JPS+ 是A*算法的優秀替代者，絕大部分情況下更快和更小的內存佔用已經足夠誘人。在GDC 2015 關於 JPS+ 算法的演講中，Steve Rabin 給出的數據甚至是比A* 算法快70~350倍。

參考

[1] 從頭理解JPS尋路算法 – 簡書 by ElephantKing

[2] JPS+: Over 100x Faster than A* | GDC 2015

[3] JPS+ with GoalBounding C++實現，和上面GDC2015的演講人是同一個人 Steve Rabin。

[4] 一個在線可視化的JPS實現附說明 A Visual Explanation Of Jump Point Search

[5] JPS 算法原作者論文 github Harabor, Daniel Damir, and Alban Grastien. “Online Graph Pruning for Pathfinding On Grid Maps.” AAAI. 2011.

博主其它相關文章：
遊戲AI 系列文章 – KillerAery – 博客園
遊戲AI之路徑規劃 – KillerAery – 博客園

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※別再煩惱如何寫文案,掌握八大原則!

※教你寫出一流的銷售文案?

※超省錢租車方案

※FB行銷專家,教你從零開始的技巧