「遊戲」尋路算法之 JPS 原理和實現

前言

之前的文章講解了關於尋路算法中常見的算法以及 AStar 尋路算法的原理以及其實現方式，但是對於 AStar 尋路算法來說，其也有一定的缺點。

A Star 算法的問題在於其在進行節點搜索的時候，會把周圍 8 個方向所有的可用鄰居節點全部存儲於，這樣 openlist 中點的數量會很多，搜索效率較慢，並且佔用內存也會很高。

如圖所示，在無遮擋情況下，可能這種情況會有很多條路徑，對於我們來說只需要一條從起點到終點的路徑就夠了，下圖中綠色爲放入 OpenList 中的節點，由圖中看出往往這些節點並沒有必要放進去，如果我們把這個圖拆分成幾段，那麼就只需要把每段的起始點放入 OpenList 中就可以了。

JPS 算法

綜述

跳點搜索（JPS Jump point search）是對 A Star 搜索算法的優化。它通過圖修剪來減少搜索過程中的對稱性，只要滿足與網格有關的某些條件，就可以基於關於當前節點鄰居的假設來消除網格中的某些節點。該算法可以考慮沿網格中的水平，垂直和對角線的 “跳躍”（即一次性跳過幾個格子），而不是普通 A Star 算法考慮的從一個網格位置到下一個網格位置的每個格子。JPS 保留了 A Star 的最優性，同時有可能將其運行時間減少一個數量級 [^1]。

如圖所示，上圖爲 JPS 算法搜索相同路徑的結果，從圖中可以看出，只有一個藍色的點被加入到了 OpenList 中，不同於 A Star 算法中直接獲取當前節點可用鄰居節點來進行拓展搜索的策略，JPS 根據當前節點的前進方向、符合條件的跳點等方式，來進行後續放入 OpenList 節點的篩選。

強迫鄰居（Forced Neighbour）

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

這段概念很難理解，作者在學習的時候也很懵😓，我們直接拿圖來解釋更好一些。

首先要明確一個問題：當前自動尋路的行走方向有 8 個，如圖所示：

當前節點 X 有 8 種前進方向，分別爲左上、上、右上、左、右、左下、下、右下，那麼對於 X 來說，其父節點可能在其垂直或者水平方向（上、下、左、右），也有可能在其斜方（左上、右上、左下、右下），如圖所示：

上圖所示，紫色方塊爲節點 X 的父節點，上圖爲節點 X 在其父節點斜方，下圖節點 X 在其父節點的垂直方向，此時我們可以說節點 X 的前進方向爲斜方前進或垂直（水平）前進。

接下來我們分別來講解在斜方前進或垂直（水平）前進時，強迫鄰居的概念（或者可以說如何確定強迫鄰居）。

垂直、水平方向強迫鄰居的查找

首先來講一下垂直、水平方向強迫鄰居的查找方式，如圖所示，深綠色爲當前節點位置，黃色的線代表行走方向，紅色的點代表終點，當前行走方向爲右方，那麼此時當前節點位置上方、下方均有阻擋，此時要進行以下邏輯：

**如果當前節點上方有阻擋，且下一個要到達的節點以及當前節點右上方節點是可用節點（即無阻擋）那麼其強迫鄰居爲當前節點右上方的節點。**2. **如果當前節點下方有阻擋，且下一個要到達的節點以及當前節點右下方節點是可用節點，那麼其強迫鄰居爲當前節點右下方的節點。**3. 如果均符合 1、2 兩個條件，那麼該節點有兩個強迫鄰居。

由上述的條件可以舉一反三，分別分析出餘下三個方向（上、左、下）的強迫鄰居條件，即：

**當前進方向爲上（下）方時，判斷當前節點左（右）側是否有阻擋，如有且當前節點前進方向的下一個節點以及當前節點前進方向的左（右）前方均爲可用節點時，其當前節點的左（右）前方的節點爲強迫鄰居。**2. 當前進方向爲左（右）方時，判斷當前節點的上（下）側是否有阻擋，如有則當前節點的前進方向的下一個節點以及當前節點前進方向的上（下）前方均爲可用節點時，其當前節點的上（下）前方的節點爲強迫鄰居。

其實上面的條件簡而言之可以理解爲，當前節點水平（垂直）側有阻擋且當前節點的下一個節點和阻擋側的下一個節點均可用，那麼阻擋側的下一個節點爲當前節點的強迫鄰居。

斜方強迫鄰居的查找

如果當前前進方向爲右上方，強迫鄰居的尋找方式如圖所示（忽略那條線），如圖所示，紅色點爲深綠色點（當前點）的父節點，兩個黑色的方塊爲阻擋，那麼強迫鄰居的條件如下：

**如果當前節點左側有阻擋，且其上方與左上方均爲可用節點（即無阻擋），則當前節點的左上方爲強迫鄰居。**2. **如果當前節點下方有阻擋，且其右側與右下方均爲可用節點（即無阻擋），則當前節點的右下方爲強迫鄰居。**3. 如果 1、2 條件均符合，則左上方、右下方均爲強迫鄰居

由上述的條件可以舉一反三，分別分析出餘下三個方向（左上、左下、右下）的強迫鄰居條件，即：

當前進方向爲左上方時、若其父節點的上方（左方）有阻擋時，且當前節點的右上方與上方（左方與左下方）均爲可用節點時，強迫鄰居爲右上方（左下方）。按照下圖來看。強迫鄰居爲藍色節點。

當前進方向爲左下方時、若其父節點的左側（下方）有阻擋時，且當前節點的左上方與左方（下方與右下方）均爲可用節點時，強迫鄰居爲左上方（右下方）。按照下圖來看，強迫鄰居爲藍色節點。

當前進方向爲右下方時、若其父節點的下方（右側）有阻擋時，且當前節點的下方與左下方（右上方與右方）均爲可用節點時，強迫鄰居爲左下方（右上方）。按照下圖來看，強迫鄰居爲藍色節點。

跳躍點（Jump Point）

所謂的跳點搜索算法，就是在一次尋路過程中主動尋找障礙，通過障礙的位置計算出：經過障礙代價最小的一些關鍵位置，並將這些位置中代價最小的點作爲下一次尋路過程的起點 [^3]。

那麼如何確定當前節點是否是跳躍點那麼就是一件很重要的事情，如何確定跳點，有以下三個規則：

當前節點是終（起）點。

當前節點至少有一個強迫鄰居。

如果父節點在斜方，那麼當前節點的水平或垂直方向上有滿足條件 a，b 的點。

舉個🌰

上圖中綠色點爲起點，紅色爲終點，黑色爲障礙，藍（淺綠）色點爲跳點，圖中可以看出由多個跳點均可以看出符合上述三個條件的跳點。

搜索過程

講完了強迫鄰居和跳躍點兩個重要的概念，那麼接下來說一下搜索過程：

將開始節點的周圍 8 個可用節點加入 OpenList（和 AStar 一樣）。2. 在 OpenList 裏取出一個代價最低的節點，進行如下邏輯判斷：
如果是終點，則回溯，返回結果。2. 如果不是，判斷當前行進方向：
如果行進方向爲水平、垂直方向那麼則繼續根據其前進方向進行遞歸搜索，直到遇到以下三個條件後，終止遞歸搜索
當前遞歸到的節點是不可用節點。2. 當前節點超出地圖編輯邊界。3. 當前節點爲跳點，此時將當前節點加入到 OpenList 中並記錄其強迫鄰居的方向。
如果行進方向爲斜方，如果當前節點是跳點則搜索結束，否則進行下述操作：
如果前進方向爲右上方，則根據水平、垂直方向的搜索方式，搜索當前節點的上方以及右方尋找跳點，接着向行進方向遞歸搜索。搜索方式也爲先水平、垂直方向，再斜方。2. 如果前進方向爲左上方，則根據水平、垂直方向的搜索方式，搜索當前節點的上方以及左方尋找跳點，接着向行進方向遞歸搜索。搜索方式也爲先水平、垂直方向，再斜方。3. 如果前進方向爲左下方，則根據水平、垂直方向的搜索方式，搜索當前節點的下方以及左方尋找跳點，接着向行進方向遞歸搜索。搜索方式也爲先水平、垂直方向，再斜方。4. 如果前進方向爲右下方，則根據水平、垂直方向的搜索方式，搜索當前節點的下方以及右方尋找跳點，接着向行進方向遞歸搜索。搜索方式也爲先水平、垂直方向，再斜方。
根據當前行進方向搜索完畢後，如果當前節點是跳點，則按照 2 的方式搜索當前節點的強迫鄰居。4. 當按照 2 的方式搜索時，每次遞歸需要將上一節點當作下一節點的父節點保存起來，以便找到終點的時候方便回溯（這點和 A Star 是一樣的），同時也要計算其 Fn 值。

網上找了個搜索系列的圖，可以作爲演示（圖侵刪）[^2]。

假設起點爲綠色節點，終點爲紅色節點。

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

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

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

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

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

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

最後 openlist 取出的藍色節點開啓搜索，在水平方向上發現紅色節點，判斷爲終點，算法完成。

源代碼

接下來看一下具體實現，由於沒有做優化，僅僅是考慮實現，因此代碼可能有一些不合理之處，望見諒。

  1// 當前進方向爲斜方時，要搜索的水平、垂直方位
  2var diagonalLine = map[tools.Azimuth][2]tools.Azimuth{
  3   tools.RightUp:   {tools.Up, tools.Right},
  4   tools.RightDown: {tools.Down, tools.Right},
  5   tools.LeftUp:    {tools.Up, tools.Left},
  6   tools.LeftDown:  {tools.Down, tools.Left},
  7}
  8
  9func (receiver *FindAWay) doJPS(result *[]*tools.Node) {
 10   for {
 11      if receiver.OpenQueue.Len() <= 0 {
 12         break
 13      }
 14     // 在OpenList裏獲取損耗最低的節點
 15      curNode := receiver.openGet()
 16     // 判斷是否是終點
 17      if receiver.end.Equal(curNode.Position()) {
 18        // 是的話回溯
 19         receiver.statistics(curNode, result)
 20         return
 21      }
 22     // 判斷是否在CloseList
 23      if _, ok := receiver.CloseMap[curNode.Position()]; ok {
 24         continue
 25      }
 26     // 加入Close List 防止重複掃描
 27      receiver.closePut(curNode)
 28     // 尋找跳點
 29      receiver.findJumpPoint(curNode)
 30   }
 31
 32}
 33
 34func (receiver *FindAWay) findJumpPoint(cur *tools.Node) {
 35   switch cur.ParentAzimuth() {
 36   case tools.LeftUp, tools.RightUp, tools.LeftDown, tools.RightDown:
 37     // 前進方向爲斜方則進行斜方搜索
 38      receiver.sSearch(cur)
 39     // 搜索當前節點的強迫鄰居
 40      receiver.rangeForcedNeighbours(cur)
 41   default:
 42     // 水平、垂直方向來的直接拿到其下一個節點
 43      nextNode := tools.GlobalMap.GetNode(tools.NodeFormula[cur.ParentAzimuth()](cur.Position()))
 44      if nextNode == nil {
 45         return
 46      }
 47      nextNode.SetParent(cur)
 48      nextNode.SetParentAzimuth(cur.ParentAzimuth())
 49      nextNode.CalcHn(receiver.end.Position()).CalcGn(tools.HVCost).CalcFn()
 50     // 水平垂直搜索
 51      receiver.hvSearch(nextNode)
 52     // 搜索當前節點的強迫鄰居
 53      receiver.rangeForcedNeighbours(cur)
 54   }
 55}
 56
 57func (receiver *FindAWay) rangeForcedNeighbours(cur *tools.Node) {
 58  // 這個切片存儲的是如果當前節點有強迫鄰居，則存儲其強迫鄰居的方位
 59   if len(cur.ForcedNeighbourAzimuth()) > 0 {
 60      for _, azimuth := range cur.ForcedNeighbourAzimuth() {
 61         nextNode := tools.GlobalMap.GetNode(tools.NodeFormula[azimuth](cur.Position()))
 62         if nextNode == nil {
 63            return
 64         }
 65         nextNode.SetParent(cur)
 66         nextNode.SetParentAzimuth(azimuth)
 67         nextNode.CalcHn(receiver.end.Position()).CalcGn(tools.SCost).CalcFn()
 68        // 搜索其強迫鄰居
 69         receiver.sSearch(nextNode)
 70      }
 71   }
 72}
 73// 水平、垂直搜索
 74func (receiver *FindAWay) hvSearch(cur *tools.Node) {
 75  // 節點無效。終止
 76   if !cur.EffectiveCoordinate() {
 77      return
 78   }
 79  // 判斷是否是跳點
 80   have := receiver.isJumpPoint(cur)
 81   if _, ok := receiver.CloseMap[cur.Position()]; !ok && have {
 82     // 放入OpenList
 83      receiver.openPut(cur)
 84      return
 85   }
 86
 87   nextNode := tools.GlobalMap.GetNode(tools.NodeFormula[cur.ParentAzimuth()](cur.Position()))
 88   if nextNode == nil {
 89      return
 90   }
 91   nextNode.SetParent(cur)
 92   nextNode.SetParentAzimuth(cur.ParentAzimuth())
 93   nextNode.CalcHn(receiver.end.Position()).CalcGn(tools.HVCost).CalcFn()
 94  // 遞歸
 95   receiver.hvSearch(nextNode)
 96}
 97// 斜方搜索
 98func (receiver *FindAWay) sSearch(cur *tools.Node) {
 99   if !cur.EffectiveCoordinate() {
100      return
101   }
102   have := receiver.isJumpPoint(cur)
103   if _, ok := receiver.CloseMap[cur.Position()]; !ok && have {
104      receiver.openPut(cur)
105      return
106   }
107   oldA := cur.ParentAzimuth()
108   defer cur.SetParentAzimuth(oldA)
109   azimuths := diagonalLine[cur.ParentAzimuth()]
110
111  // 先垂直搜索
112   cur.SetParentAzimuth(azimuths[0])
113   receiver.hvSearch(cur)
114    //再水平搜索
115   cur.SetParentAzimuth(azimuths[1])
116   receiver.hvSearch(cur)
117
118   nextNode := tools.GlobalMap.GetNode(tools.NodeFormula[oldA](cur.Position()))
119   if nextNode == nil {
120      return
121   }
122   nextNode.SetParent(cur)
123   nextNode.SetParentAzimuth(oldA)
124   nextNode.CalcHn(receiver.end.Position()).CalcGn(tools.SCost).CalcFn()
125  // 再斜方遞歸下去
126   receiver.sSearch(nextNode)
127}
128
129func (receiver *FindAWay) isJumpPoint(cur *tools.Node) bool {
130   // 當前點爲end 則是跳點
131   if receiver.end.Equal(cur.Position()) {
132      return true
133   }
134
135   switch cur.ParentAzimuth() {
136   // 斜方過來的 則看看垂直、水平方有沒有跳點
137   case tools.LeftUp, tools.RightUp, tools.LeftDown, tools.RightDown:
138      oldA := cur.ParentAzimuth()
139      azimuths := diagonalLine[cur.ParentAzimuth()]
140      cur.SetParentAzimuth(azimuths[0])
141      haveJp := receiver.findForcedNeighbour(cur)
142      cur.SetParentAzimuth(azimuths[1])
143      haveJp = receiver.findForcedNeighbour(cur)
144      cur.SetParentAzimuth(oldA)
145      return haveJp
146   default:
147      return receiver.findForcedNeighbour(cur)
148   }
149
150}
151
152
153func (receiver *FindAWay) findForcedNeighbour(node *tools.Node) bool {
154   // 如果前進方向側方沒有阻擋則必定無強迫鄰居
155   // 前進方向爲上、下時，側方爲左、右
156   // 前進方向爲左、右時，側方爲上、下
157   switch node.ParentAzimuth() {
158   case tools.Up, tools.Down:
159      if tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.Left](node.Position())) &&
160         tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.Right](node.Position())) {
161         return false
162      }
163   case tools.Left, tools.Right:
164      if tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.Up](node.Position())) &&
165         tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.Down](node.Position())) {
166         return false
167      }
168   default:
169      return false
170   }
171
172   have := false
173   switch node.ParentAzimuth() {
174   case tools.Right:
175      // 1：上側有阻擋且右上側可走
176      // 2：下側有阻擋 右下側可走
177      // 3: 右上、右下其中一點爲終點
178      // 二者符合其一則代表有強迫鄰居
179      if (!tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.Up](node.Position())) &&
180         tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.RightUp](node.Position()))) ||
181         receiver.end.EqualIJ(tools.NodeFormula[tools.RightUp](node.Position())) {
182         node.AddForcedNeighbourAzimuth(tools.RightUp)
183         have = true
184      }
185      if (!tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.Down](node.Position())) &&
186         tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.RightDown](node.Position()))) ||
187         receiver.end.EqualIJ(tools.NodeFormula[tools.RightDown](node.Position())) {
188         node.AddForcedNeighbourAzimuth(tools.RightDown)
189         have = true
190      }
191
192   case tools.Left:
193      // 1：上側有阻擋且左上側可走
194      // 2：下側有阻擋且左下側可走
195      // 3: 左上、左下其中一點爲終點
196      // 二者符合其一則代表有強迫鄰居
197      if (!tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.Up](node.Position())) &&
198         tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.LeftUp](node.Position()))) ||
199         receiver.end.EqualIJ(tools.NodeFormula[tools.LeftUp](node.Position())) {
200         node.AddForcedNeighbourAzimuth(tools.LeftUp)
201         have = true
202      }
203      if (!tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.Down](node.Position())) &&
204         tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.LeftDown](node.Position()))) ||
205         receiver.end.EqualIJ(tools.NodeFormula[tools.LeftDown](node.Position())) {
206         node.AddForcedNeighbourAzimuth(tools.LeftDown)
207         have = true
208      }
209
210   case tools.Up:
211      // 1：左側有阻擋且左上側可走
212      // 2：右側有阻擋且右上側可走
213      // 3: 左上、右上其中一點爲終點
214      // 二者符合其一則代表有強迫鄰居
215      if (!tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.Left](node.Position())) &&
216         tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.LeftUp](node.Position()))) ||
217         receiver.end.EqualIJ(tools.NodeFormula[tools.LeftUp](node.Position())) {
218         node.AddForcedNeighbourAzimuth(tools.LeftUp)
219         have = true
220      }
221      if (!tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.Right](node.Position())) &&
222         tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.RightUp](node.Position()))) ||
223         receiver.end.EqualIJ(tools.NodeFormula[tools.RightUp](node.Position())) {
224         node.AddForcedNeighbourAzimuth(tools.RightUp)
225         have = true
226      }
227   case tools.Down:
228      // 1：左側有阻擋且左下側可走
229      // 2：右側有阻擋且右下側可走
230      // 3: 左下、右下其中一點爲終點
231      // 二者符合其一則代表有強迫鄰居
232      if (!tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.Left](node.Position())) &&
233         tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.LeftDown](node.Position()))) ||
234         receiver.end.EqualIJ(tools.NodeFormula[tools.LeftDown](node.Position())) {
235         node.AddForcedNeighbourAzimuth(tools.LeftDown)
236         have = true
237      }
238      if (!tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.Right](node.Position())) &&
239         tools.GlobalMap.EffectiveCoordinate(tools.NodeFormula[tools.RightDown](node.Position()))) ||
240         receiver.end.EqualIJ(tools.NodeFormula[tools.RightDown](node.Position())) {
241         node.AddForcedNeighbourAzimuth(tools.RightDown)
242         have = true
243      }
244   default:
245   }
246   return have
247}
248
249

總結

和 A Star 算法相比，JPS 的優缺點爲：

使用 JPS 算法比 A * 更快（絕大部分地圖），內存佔用更小，因爲 OpenList 少了很多節點（最差的情況和 A Star 一樣，最差的是每個障礙都不連續，中間都有縫隙，這樣所有地方都是跳點了）2. 只適用於網格節點類型，不支持 Navmesh 或者路徑點尋路方式。3. 當地圖很大時，水平、垂直方向的遞歸深度會很深。參考資料

[^1]: Jump point search https://en.wikipedia.org/wiki/Jump_point_search

[^2]: JPS/JPS+ 尋路算法 https://www.cnblogs.com/KillerAery/archive/2020/06/17/12242445.html

[^3]: JPS 尋路算法 https://www.jianshu.com/p/9335dddb04b4

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/X6WZvbzw_CnTshbGiYSLSg

前言