status
date
slug
tags
category
type
password
icon
Paper:
- JPS: Jump Point Search
A* vs. JPS
ㅤ | A* | JPS | JPS-Bit | JPS-BitPrune | JPS-BitPre | JPS-BitPrunePre |
耗時 | 25.5ms | 1.7ms | 320us | 230us | 200us | 95us |
速度 | 1x | 15x | 81x | 110x | 130x | 273x |
基於 A* 的優化
JPS 基於當前節點 的方向，遵循”兩個定義，三個規則”決定 Forced Neighbour(FN)
- 定義一 FN
- 如果節點 是 的鄰居，並且節點 的鄰居有障礙物，並且從 , , 的路徑長度比其他任何從 到 且不經過 的路徑更短 ⇒ 則 為 的 FN， 為 的跳點。(圖1中， 為 的FN， 為 的跳點 )
- 定義二 跳點
- 如果節點 是起點或目標點，則 是跳點。(圖1中的 與 )
- 如果 有 FN ⇒ 則 是跳點 (圖1中的 )
- 如果 到 是對角線移動，並且 經過水平或垂直方向可以到達跳點 ⇒ 則 是跳點 (圖1中的 )
- 規則一
- 在搜尋跳點的過程中，優先搜尋直線方向，再搜尋對角線方向
- 規則二
- 如果從 到 是直線移動，且 是 的鄰居，若存在 到 的路徑不經過 且路徑長度小於等於 經過 到 的路徑，則走到 以後下一個點不會走到
- 如果從 到 是對角線移動，且 是 的鄰居，若存在 到 的路徑不經過 且路徑長度小於從 經過 到 的路徑，則走到 以後下一個點不會走到
- 規則三
- 只有跳點才會加入 openset，因為跳點會改變行走方向(非跳點無法改變方向)，最後尋找出來的路徑點都是跳點
根據當前方向來決定下一個跳點
- Case 1. 當前方向是直線
- Case 1.1 目前左後方不可走且左方可走 ⇒ 沿左前方與左方找不在 closedset 的跳點
- Case 1.2 目前當前方向可走 ⇒ 沿著當前方向尋找不在 closedset 的跳點
- Case 1.3 目前右後方不可走且右方可走 ⇒ 沿右前方與右方找不在 closedset 的跳點
- Case 2. 當前方向是對角線
- Case 2.1 目前的水平分量可走 ⇒ 沿水平分量方向尋找不在 closedset 的跳點
- Case 2.2 目前當前方向可走 ⇒ 沿著當前方向尋找不在 closedset 的跳點
- Case 2.3 目前的垂直分量可走 ⇒ 沿垂直方量方向尋找不在 closedset 的跳點
JSP 的三種優化
- Bit Operation
- Preprocessing
- Prune
算法流程圖
圖一
來看個例子
- 圖請見圖一
- 目標: 尋找從 到 的最短路徑，且不能經過黑色區域
- 螢幕參考座標系(上下左右)、人物參考坐標系(前後左右)
- 將 加入 openset
- 從 openset 中取出 值最小的節點 ⇒
- 將 從 openset 中刪除，加入 closedset
- 當前方向為空，往八個方向擴散，三個選項為右、下、右下
- 往右 ⇒ 撞到牆
- 往下 ⇒ 撞到邊界
- 往右下 ⇒ 根據定義二第三條， 為 S，右下是對角線移動，並且 透過垂直移動可以到達跳點 ⇒ 為跳點，將 加入 openset
- 從 openset 中取出 值最小的節點 ⇒
- 將 從 openset 中刪除，加入 closedset
- 當前方向( 看向 )為右下，往右、下、右下三個方向擴散(Case 2)
- 往右 ⇒ 撞到牆
- 往右下 ⇒ 撞到牆
- 往下 ⇒ 根據定義二第二條，找到跳點 ，將 加入 openset
- 從 openset 中取出 值最小的節點 ⇒
- 當前方向( 看向 )為向下，往右、右下(Case1.1中的左與左前)與下(Case1.2)擴散
- 往下 ⇒ 撞到邊界
- 往右下 ⇒ 撞到邊界
- 往右 ⇒ 根據定義二第二條，透過 FN 找到跳點 ，將 加入 openset
- 從 openset 中取出 值最小的節點 ⇒
- 當前方向( 看向牆壁)為向右，往上、右上(Case 1.1)與右(Case 1.2)擴散
- 往右 ⇒ 撞到邊界
- 往右上 ⇒ 撞到邊界
- 往上 ⇒ 根據定義二第一條，找到跳點 ，將 加入 openset
- 從 openset 中取出 值最小的節點 ⇒
- 找到目標點，尋路結束，路徑為
JPS 快在哪
- A* 在從 到 時，會將 加入到 openset 中，才能走出 或是
- JPS 只用到
- 對 heap 來說，插入與刪除節點(更新openset與closedset)的複雜度為
JPS-Bit
- 使用 bit operation 來優化
- 使用 0 表示可走的節點，1表示不可走的節點
圖二
__builtin_clz(B): 返回前導 0 的個數
- 尋找當前的跳點:
__builtin_clz(((B->>1) && !B-) || ((B+>>1) && !B+))
- 本例中
__builtin_clz(((00000000) && 11111111) || ((00011000) && (11001111)))=00001000= 4，從 往當前方向(向右)數四格的 即為下一個跳點
JPS-BitPrune
- 基於 JPS-Bit 之上進行剪枝，刪除不必要的中間跳點，尋訪到完整路徑之後以拐點替代
- 增加拐點
- 假設節點 的 座標為
- 如果 或 ⇒ 與 在同一個直線上 ⇒ 走直線就好，不用加拐點
- 如果 ⇒ 與 在對角線方向上 ⇒ 直線到達即可，不用加拐點
- 除此之外的情況，說明兩個點不在同一個對角線上，並且中間可能存在障礙物，需要加上一個中間跳點作為拐點
- 選擇拐點的策略: 離 點最近的中間跳點(從 沿對角線走 步的點)
再看個例子
- 起點: ，目標:
- 節點 是為了到達結點 或結點 的中間跳點
- 節點 是為了達到節點 的中間跳點
- 從 開始尋找跳點 ⇒
- 在 的直線方向找到跳點 與 ，將兩個跳點的父跳點設為
- 繼續從 的對角線找跳點 ⇒
- 往 的直線方向找到跳點 ，將跳點 的父跳點設為
- 繼續從 的對角線找跳點 ⇒
- 往 的直線方向找到跳點 ，將跳點 的父跳點設為
- 得到路徑 ，因兩者無法走直線及對角線 ⇒ 需要加入中間拐點
- ， ，
- 從 往對角線走 3 步，將節點 設為中間拐點
- 最終路徑為
- 未剪枝 vs. 剪枝
- 未剪枝:
- 剪枝:
JPS-BitPre
- 不支援動態阻擋
- 空間換取時間
- 前處理的內容: 每個點儲存八個方向分別可以走幾步
最後一個例子
- 取出節點
- 取出八個方向最多走幾步，將該方向最遠可抵達的節點找出來
- 滿足定義二第三條，加入 openset
- 滿足定義二第二條，加入 openset
- 剩下的節點中，因為終點 位於 的左下方，因此只考慮方向同為左下角的
- 從 到 的對角線走 步，即節點 ，加入 openset
- 從 openset 中取出 值最小的節點 ，垂直方向找到跳點 ，加入 openset
- 從 openset 中取出 值最小的節點 ，搜索結束
- 路徑為
- Author:Zixu
- URL:https://zixu.us.kg/article/JPS_學習筆記
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
