「遊戲」尋路算法之 A Star 算法原理及實現

前言

常見搜索算法

Dijkstra 算法

舉個例子（後續的所有移動代價皆以此計算）

當玩家向自身 8 個方向中的橫軸以及縱軸進行移動時（即向上、下、左、右），移動代價爲 10（別問爲啥爲 10，拍腦門決定的）。

當玩家向自身八個方向中的對角方向進行移動時（即左上、左下、右上、右下），移動代價爲橫（縱）軸移動的 1.4 倍（因爲正方形的對角線是邊長約 1.4 倍）。

左圖爲 BFS 算法右圖爲 Dijkstra 算法（圖侵刪）

上圖對比了不考慮節點移動代價差異的廣度優先搜索與考慮移動代價的 Dijkstra 算法的運行圖

最佳優先搜索算法（Best-First-Search）

這個算法和 Dijkstra 算法差不多，同樣也使用一個優先隊列，但此時以每個節點的移動代價作爲優先級去比較，每次都選取移動代價最小的，因爲此時距離終點越來越近，所以說這種算法稱之爲最佳優先（Best First）算法。

接下來看一下運行事例：

左側爲 Dijkstra 算法右側爲最佳優先搜索算法

最佳優先搜索算法相對於 Dijkstra 算法的問題在哪裏呢？看一下中途有阻擋的時候的情況：

左側爲 Dijkstra 算法右側爲最佳優先搜索算法

從上圖中可以看出，當地圖中存在障礙物的時候，最佳優先搜索算法並不能找到最短路徑。

A Star 算法

A Star 算法是一種在遊戲開發過程中很常用的自動尋路算法。它有較好的性能和準確度。A * 搜索算法（A* search algorithm）是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的算法。常用於遊戲中的 NPC 的移動計算，或網絡遊戲的 BOT 的移動計算上。該算法綜合了最佳優先搜索和 Dijkstra 算法的優點：在進行啓發式搜索提高算法效率的同時，可以保證找到一條基於啓發函數的最優路徑 [^4]。

啓發公式

解釋下這個公式的各項的含義：

•h(n): 從當前節點 n 到終點的預估的代價。•g(n): 從起始點到達當前節點 n 的代價。•f(n): 爲當前節點 n 的綜合的代價，在選擇下一個節點的時候，其值越低，優先級就越高（因爲代價小）。

關於啓發函數中 * h(n) 公式的的選擇，由於遊戲地圖中大部分都是被分爲網格形式（即整個地圖被拆分爲多個正方形格子），那麼此時就有 3 種可選的啓發函數的 h(n)* 公式可用，分別爲：

曼哈頓距離：出租車幾何或曼哈頓距離（Manhattan Distance）是由十九世紀的赫爾曼 · 閔可夫斯基所創詞彙，是種使用在幾何度量空間的幾何學用語，用以標明兩個點在標準座標系上的絕對軸距總和。

曼哈頓距離一般用在在移動時，只允許朝上下左右四個方向移動的情況下使用。

在平面中 X1 點到 X2 點的距離爲其公式爲：$$ d(i,j)=|X1-X2|+|Y1-Y2| $$ 轉換爲程序語言如下，其中 Cost 爲相鄰兩個節點移動所耗費的代價
1func Manhattan(startX, startY, endX, endY float64) float64 {
2    dx := math.Abs(startX - endX)
3    dy := math.Abs(startY - endY)
4    return Cost * (dx + dy)
5}
6
7

對角線距離：如果你的地圖允許對角線運動，則啓發函數可以使用對角距離。它的計算方法如下：

其中 HVCost 是水平、垂直方向移動代價，SCost 爲傾斜方向移動代價
1func  Diagonal(startX, startY, endX, endY float64) float64 {
2    dx := math.Abs(startX - endX)
3    dy := math.Abs(startY - endY)
4    return HVCost*(dx+dy) + (SCost-2*HVCost)* math.Min(dx, dy)
5}
6
7
8

歐幾里得距離：是一個通常採用的距離定義，指在 m 維空間中兩個點之間的真實距離，或者向量的自然長度（即該點到原點的距離），其公式爲：$$ \sqrt[2]{ (x2−x1)^2+(y2−y1)^2} $$

該公式爲點 (x1,y1) 與點 (x2,y2) 之間的歐氏距離
1func  Euclidean(startX, startY, endX, endY float64) float64 {
2    dx := math.Abs(startX - endX)
3    dy := math.Abs(startY - endY)
4    return D * math.Sqrt(dx * dx + dy * dy)
5}
6
7

在此文章中我們選擇對角距離公式來作爲啓發函數求 * h(n)* 的公式。

啓發函數可能對算法造成的影響 [^5]：

• 在極端情況下，當啓發函數 h(n) 始終爲 0，則將由 g(n) 決定節點的優先級，此時算法就退化成了 Dijkstra 算法。• 如果 h(n) 始終小於等於節點 n 到終點的代價，則 A * 算法保證一定能夠找到最短路徑。但是當 h(n) 的值越小，算法將遍歷越多的節點，也就導致算法越慢。• 如果 h(n) 完全等於節點 n 到終點的代價，則 A * 算法將找到最佳路徑，並且速度很快。可惜的是，並非所有場景下都能做到這一點。因爲在沒有達到終點之前，我們很難確切算出距離終點還有多遠。• 如果 h(n) 的值比節點 n 到終點的代價要大，則 A * 算法不能保證找到最短路徑，不過此時會很快。• 在另外一個極端情況下，如果 h(n) 相較於 g(n) 大很多，則此時只有 h(n) 產生效果，這也就變成了最佳優先搜索。

A Star 算法執行過程

在搜索過程中，A Star 算法需要遍歷周圍 8 方向的 8 個節點，並將之有效的節點（即可通過的節點）計算 **f(n) **後放入一個優先級隊列中，以便下次循環可以直接取出優先級最高的節點繼續遍歷，此時我們把這個優先級隊列稱呼爲 OpenList，另外 A Star 算法中也需要一個容器用來存儲已經遍歷過的節點、以防止重複的遍歷，那麼此時我們把這個容器稱之爲 CloseList。

接下來本文講按照步驟說明 A Star 算法每一步的執行過程：

對 OpenList 和* CloseList* **進行初始化，作者採用小根堆來作爲 ****OpenList**** 的實現數據結構，採用 HashMap 作爲 ****CloseList**** 的數據結構，其中 Key 爲節點座標值 Value 爲空結構體。2. 首先確定 Start 節點以及 End 節點，而後將 Start 節點放入 ****OpenList**** 中。3. 從 ****OpenList**** 中取出一個節點 Cur，如果 Cur 節點爲 End 節點，則回溯當前節點結構中存儲的父節點對象（像鏈表一樣向前回溯）直到父節點對象爲 nil 或者爲 Start 節點，此時得到搜索到的路徑，搜索結束返回。4. 如果 Cur 節點非 End 節點則進行如下邏輯：
將當前 X 節點放入 CloseList 中，如果在取出 Cur 節點時未做刪除操作的話那麼則從* OpenList*** 中刪除。2. 遍歷 Cur 節點其周圍 8 方向的所有額鄰居可用節點、可用節點的條件爲：
是可通過的節點。2. 未處於 CloseList 中。
計算當前的 Cur 節點的鄰居可用節點，計算其 **f(n) **值，設置其父節點爲 Cur 節點，隨後將其加入至 OpenList 中。
循環執行 3-4。直到找不到有效路徑或找到 End 節點。

代碼實現

 1// 優先隊列
 2type PriorityQueue []*Node
 3
 4func (receiver PriorityQueue) Len() int {
 5    return len(receiver)
 6}
 7
 8func (receiver PriorityQueue) Less(i, j int) bool {
 9    return receiver[i].Fn() < receiver[j].Fn()
10}
11
12func (receiver PriorityQueue) Swap(i, j int) {
13    receiver[i], receiver[j] = receiver[j], receiver[i]
14}
15
16func (receiver *PriorityQueue) Push(x interface{}) {
17    *receiver = append(*receiver, x.(*Node))
18}
19
20func (receiver *PriorityQueue) Pop() interface{} {
21    index := len(*receiver)
22    v := (*receiver)[index-1]
23    *receiver = (*receiver)[:index-1]
24    return v
25}
26
27// 傳入的是一個存放搜索路徑的切片
28// *tools.Node 是節點指針
29func (receiver *FindAWay) doAStar(result *[]*tools.Node) {
30   for receiver.OpenQueue.Len() > 0 {
31     // 從 OpenList 裏取出一個節點
32      node := receiver.openGet()
33     // 看看是不是終點
34      if receiver.end.Equal(node.Position()) {
35         receiver.statistics(node, result)
36         return
37      }
38     // 節點放入CloseList
39      receiver.closePut(node)
40     // 進行具體處理
41      receiver.azimuthProcessing(node)
42   }
43}
44
45func (receiver *FindAWay) azimuthProcessing(node *tools.Node) {
46  // 遍歷當前節點的8個方向
47  // tools.NodeFormula 是一個存有 計算8個方向座標的函數數組
48    for azimuth, f := range tools.NodeFormula {
49    // Position 返回一個 存放了 XY字段的結構體代表節點座標
50        nearNode := tools.GlobalMap.GetNode(f(node.Position()))
51    // 返回爲nil代表節點超出邊界
52    // EffectiveCoordinate() 代表當前鄰居節點是否可用，即是否可以通過
53        if nearNode == nil || !nearNode.EffectiveCoordinate() {
54            continue
55        }
56    // 查看當前鄰居節點是否處於 CloseList裏
57        if _, ok := receiver.CloseMap[nearNode.Position()]; ok {
58            continue
59        }
60    // 查看當前鄰居節點是否處於 OpenList裏
61    // 這算是個優化，防止OpenList插入重複節點
62        if _, ok := receiver.OpenMap[nearNode.Position()]; !ok {
63      // 設置當前鄰居節點的父節點爲當前節點
64            nearNode.SetParent(node)
65      // 根據所處方位使用不同的移動代價計算Fn值
66
67      // 此時 HVCost =10 
68      // SCost = HVCost * 1.4
69            switch tools.Azimuth(azimuth) {
70        // 斜方計算
71            case tools.LeftUp, tools.LeftDown, tools.RightUp, tools.RightDown:
72                nearNode.CalcGn(tools.SCost).CalcHn(receiver.end.Position()).CalcFn()
73        // 垂直、水平方向計算
74            default:
75                nearNode.CalcGn(tools.HVCost).CalcHn(receiver.end.Position()).CalcFn()
76            }
77      // 將當前鄰居節點放入OpenList中
78            receiver.openPut(nearNode)
79        }
80    }
81}
82
83
84

結果測試

紫色爲終點

綠色忘記刪了，沒有代表意義

下圖爲原地圖：

下圖爲搜尋完畢的地圖：

總結

A Star 算法算是一個很簡單的用於遊戲中自動尋路的算法，但是其性能還有有些問題，主要問題在於其需要把每個節點的周圍所有可用節點均插入 OpenList 中，因此相對來說性能損耗幾乎都在這個 OpenList*** 中，因此 A Star 算法有很多對其可以優化的算法。

日後作者將會寫一篇關於針對 A Star 的優化算法即：JPS（jump point search）算法，該算法實際上是對 A Star 尋路算法的一個改進，A Star 算法在擴展節點時會把節點所有鄰居都考慮進去，這樣 OpenList 中點的數量會很多，搜索效率較慢。而 JPS 在 A Star 算法模型的基礎之上，優化了搜索後繼節點的操作。A Star 的處理是把周邊能搜索到的格子，加進 OpenList，然後在 OpenList 中彈出最小值。JPS 也是這樣的操作，但相對於 A Star 來說，JPS 操作* OpenList* **的次數很少，它會先用一種更高效的方法來搜索需要加進 ****OpenList**** 的節點，從而減少 ****OpenList**** 中節點的數量。

[^1]: Dijkstra 算法 https://baike.baidu.com/item/%E8%BF%AA%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95/23665989?fromtitle=Dijkstra%E7%AE%97%E6%B3%95&fromid=215612 [^2]: Cormen, Thomas H.[1]; Leiserson, Charles E.[2]; Rivest, Ronald L.[3]; Stein, Clifford[4]. Section 24.3: Dijkstra's algorithm. Introduction to Algorithms[5] Second. MIT Press[6] and McGraw–Hill[7]. 2001: 595–601. ISBN 0-262-03293-7[8]. [^3]: 最佳優先搜索算法（Best-First-Search） https://www.jianshu.com/p/9873372fe4b4 [^4]: A Star 算法 https://zh.wikipedia.org/wiki/A*%E6%90%9C%E5%B0%8B%E6%BC%94%E7%AE%97%E6%B3%95 [^5]: 路徑規劃之 A* 算法 https://paul.pub/a-star-algorithm/#id-dijkstra%E7%AE%97%E6%B3%95

[1] Cormen, Thomas H.: _https://zh.wikipedia.org/w/index.php?title=Thomas_H.Cormen&action=edit&redlink=1
[2] Leiserson, Charles E.: _https://zh.wikipedia.org/w/index.php?title=Charles_E.Leiserson&action=edit&redlink=1
[3] Rivest, Ronald L.: _https://zh.wikipedia.org/wiki/Ronald_L.Rivest
[4] Stein, Clifford: https://zh.wikipedia.org/w/index.php?title=Clifford_Stein&action=edit&redlink=1
[5] Introduction to Algorithms: https://zh.wikipedia.org/wiki / 算法導論
[6] MIT Press: https://zh.wikipedia.org/wiki / 麻省理工學院出版社
[7] McGraw–Hill: https://zh.wikipedia.org/wiki / 標普全球
[8] ISBN 0-262-03293-7: https://zh.wikipedia.org/wiki/Special: 網絡書源 / 0-262-03293-7

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

前言