趣說遊戲AI開發：曼哈頓街角的A*演算法

01-28

0x00 前言

請叫我標題黨！請叫我標題黨！請叫我標題黨！因為下面的文字既不發生在美國曼哈頓，也不是一個講述美國夢的故事。相反，這可能只是一篇沒有那麼枯燥的關於演算法的文章。A星演算法，這個在遊戲尋路開發中難免會用到的演算法便是我這篇文章的主角。

0x01 曼哈頓的街道

這是一張美國曼哈頓的俯視圖，放眼望去除了能看到這裡高樓林立之外，我們也能發現其另外一個特點，即橫平豎直的街道將一整塊地區整整齊齊的分成了好幾個區n塊。人和車流只能行進在橫穿其中的街道上，也只能在街道的交叉口改變自己的前進的方向。例如要找出地圖中A點到B點的最佳路線，事實上就是從A點所在的交n叉口沿著街道走到B點所在的交叉口，我們無法從區塊內部穿越過去，除了沿街道走別無選擇。

下面讓我們把曼哈頓的這些街道交叉口當做結點，兩個交叉口之間的街道當做邊，做出一個如下圖所示的二維網格。

那麼A點到B點的實際距離是多少呢？考慮到我們只能沿著街道行走，而無法從街道圍成的區塊中穿越，因此在這種情況下A點到B點的實際距離並不是它們之間的直線距離，而是應該如下圖所示的這樣：

轉換成數學語言就是這樣：

dis = abs(A.x - B.x) + abs(A.y - B.y)n

對了，這就是曼哈頓距離。也就是在A星演算法中常常被用來作為啟發函數的傢伙。等等，啟發函數是什麼？讓我繼續。

0x02 醉漢尋「路」

從A點到B點的這條路徑，顯然包括了以A為起點B為終點的一系列結點，而每個結點也只能從和自己相鄰的結點中選擇下一個行走目標。但是正如現實生活n一樣，暢通無阻的街道總是奢求，在路上總會花費一些代價，例如路況不佳，交通擁堵等等原因造成從這條道路行走時會花費更多的時間。因此在尋路中，一條路徑n的代價等於在每個路口選擇的道路的代價之和。

了解了這些之後，就讓我們來實現一個最粗暴的尋路方式，彷彿一個醉漢，無視每條道路是否已經走過，也不關心每條道路所花費的時間代價，反正只需要在路口閉著眼睛做出一個選擇就好了。

//偽代碼nq = newqueuenq.enqueue(newpath(start))nwhile q is not emptyn p = q.dequeuen if p.lastNode == destination n return pn foreach n in p.lastNode.neighboursn q.enqueue(p.continuepath(n))n//找不到合適路徑nreturn nulln

這樣做的後果是什麼呢？不錯，就像一個醉漢一樣，從路口的四個方向中隨機選擇一個方向，甚至還有可能走回頭路（因為沒有記錄他已經走過的路口），也n許最後的確能夠找到家，但是這個過程中卻不知道消耗了多少時間，走了多少冤枉路。更有甚者，如果實際上並沒有一條能夠到達目的地的路徑，甚至會出現「鬼打n牆」的情況，即進入了一個無限的死循環之中無法自拔。

所以，讓我們來幫他一下吧，既然醉漢不記得已經走過了哪些路口，那麼就讓我們來幫他記住他走過的路口。我們為上面的代碼引入一個closed集合，用來保存已經走過路口。

//偽代碼n//引入一個集合，用來保存已經走過的路口nclosed = {}nq = newqueuenq.enqueue(newpath(start))nwhile q is not emptyn p = q.dequeuen //如果下面closed集合中包含了路徑p的最後一個路口n //p.last則忽略n if closed contains p.last n continuen //如果路徑p的最後一個路口即是目的地，則直接返回pn if p.last == destination n return pn //否則將該點p.last加入到closed集合中n closed.add(p.last)n //把點p.last相鄰的點加入到隊列中n foreach n in p.last.neighbours n q.enqueue(p.continuepath(n))n//找不到合適的路nreturn nulln

這樣，我們就幫醉漢解決了走回頭路的問題，也消除了「鬼打牆」的隱患。但是，醉漢在選擇道路時仍然沒有一個明確的目標，這也就決定了他在尋找目的地n的效率並不高效。因為他仍然會向四面八方尋路，雖然他在我們的幫助下已經不會走回頭路了。顯然，為了儘早讓醉漢回到家，我們需要為他選擇一條最佳的道路。n但是，這條最佳的道路到底應該如何選擇（預估）呢？

0x03 給我一個指南針

在考慮如何尋找最佳路徑之前，我們第一步要做的顯然就是為最佳路徑定義一個可以量化的標準。到底以什麼為標準來評價一條路徑呢？最簡單的，我們就選n擇兩個路口之間的距離作為標準，這裡我們將距離長度稱之為路徑的開銷，且一個路口上下左右相鄰的路口的消耗為1，而對角線上的路口消耗則為1.41。

而我們評價一條潛在路徑的開銷時，所依據的數據主要來自兩個方面：

該路徑到目前的路口為止，已經經過的路口的總消耗。這一點我們是已知的，我們將這個消耗的值記為G。
該路徑到目前的路口為止，預估到目的地的消耗。這一點我們是猜測的，我們將這個消耗的值記為H。

而我們所要做的，便是在幫助醉漢不走回頭路的基礎上，再為醉漢指一個回家的方向。醉漢只要按照這個方向走，便能夠很快的找到家。而這個方向又是如何確定的呢？其實十分簡單，我們只需找到總消耗最小的路徑便可以了。這裡我們記總消耗為F，那麼顯然有如下這樣的等式：

F = G + H

那麼具體應該如何操作呢？我們需要一個優先隊列，記錄每條路徑的總消耗以及這條路徑，並且根據路徑的總消耗來對該隊列進行排序，這樣消耗最小的路徑便能輕易地獲取了。所以，我們的代碼拓展成了下面這個樣子：

//偽代碼n//引入一個集合，用來保存已經走過的路口nclosed = {}nq = newqueue;n//q為優先隊列，記錄路徑的消耗以及路徑，起始點消耗為0nq.enqueue(0, newpath(start))nwhile q is not emptyn //優先隊列彈出消耗最小的路徑n p = q.dequeueCheapestn if closed contains p.last n continue;n if p.last == destination n return pn closed.add(p.last)n foreach n in p.last.neighbours n //獲得新的路徑n newpath2 = p.continuepath(n)n //將新路徑的總消耗（G+H)，和新路徑分別入隊n q.enqueue(newpath.G + estimateCost(n, destination), newpath2)n nreturn nulln

其中，我們可以發現預估到目的地消耗的函數叫「estimateCost」，這便是在A星演算法中我們常常提起的啟發函數。它的作用便是估算當前位置n到目的地的大概距離，而在本文一開始介紹的曼哈頓距離便是一種常用的啟發函數。即計算當前路口（格子）到目標路口（格子）之間的垂直和水平的路口（格子）n數量總和。

dis = abs(A.x - B.x) + abs(A.y - B.y)

而這個啟發函數，便是我們送給醉漢回家的指南針。

當然，借這個醉漢回家的例子說明的僅僅是A星演算法最基本的實現原理。而在實際的工程中，它也有更加複雜的使用環境，下面我就簡單的介紹幾種工程中實現A星尋路的工作方式。

0x04 工程中A星演算法的實現方式

我們有了演算法的實現思路，接下來便是如何在遊戲中實現A星演算法了。

要在遊戲中進行尋路，首先要做的便是藉助圖來將遊戲地形表示出來，而這個圖便是導航圖。

而最常見的導航圖便是如下三種：

基於單元格的導航圖

如上圖所示，將遊戲地圖劃分為許多單元格的形式便是我們所說的基於單元格的導航圖。這種表示方式的結構十分規則，因此最容易理解和使用，且易於動態更新。因此在需要頻繁動態更新場景的遊戲中使用這種基於單元格的導航圖便十分的恰當。

但是，為了追求尋路的結果更加精確，單元格的大小就成為了關鍵，過大的單元格顯然和精確無緣，但是如果為了追求精確而使用很小的單元格，卻又不得不面對另一個問題——需要存儲和搜索的結點的數量會十分大。這樣不僅需要大量的消耗內存，同時也會影響搜索效率。

基於路點的導航圖

如果我們通過人工不規則的放置一些用來導航的點來代替剛剛的單元結點，那麼是否會有更好的表現呢？因此，基於可視點，或者被稱為路點（The waypoints）的導航圖便出現了。如上圖所示，紅色的結點便是放置的路點，而路點之間的連線是遊戲單位可以行走的路徑。

這種基於路點的導航圖的優勢便是可以讓場景設計師按照場景的特點來布置路點，由於可以按照設計師的想法來放置，因此基於路點的導航圖的一大特點便是靈活性很高，且不像基於單元格的導航圖那樣，需要存儲和搜索大量的結點，因此需要的內存和搜索的效率較前者都要優秀。

但n是它的缺點也同樣明顯，那就是如果場景過大，放置少量的路點顯然無法滿足需要，但是放置很多路點時，會使得場景設計師的工作變得複雜且容易出錯。而由於游n戲單位只能在兩個路點之間的連線上進行移動，因此如果遊戲單位不在結點或結點間連線上的時候，會先到離它最近的路點上，之後再次移動，這樣從視覺上看會出n現不自然的情況。

導航網格

如圖，導航網格將遊戲地形劃分成了大大小小的三角形，而這些三角形也就成為了A星演算法中的節點。相鄰的三角形可以直達，換言之，三角形相鄰的其他三角形既其相鄰的結點。

因此，與前兩種導航圖相比，由於其「節點」面積大，因此只需要少量的「節點」即可覆蓋整個遊戲區域，從而減少了「節點」的數量。其次，也正是由於節點全部覆蓋了遊戲場景，因此不必擔心像基於路點的導航圖那樣由於缺少路點而造成的尋路不精確的問題。

但是，它同樣並非十全十美的，相較前兩者而言，生成導航網格的時間較長，因此推薦在靜態場景中使用，而在地形經常發生變化的場景中減少使用。