趣說游戲AI開發：曼哈頓街角的A*算法
來自： http://www.cnblogs.com/murongxiaopifu/p/5111514.html
0x00 前言
請叫我標題黨！請叫我標題黨！請叫我標題黨！因為下面的文字既不發生在美國曼哈頓，也不是一個講述美國夢的故事。相反，這可能只是一篇沒有那么枯燥的關于算法的文章。A星算法，這個在游戲尋路開發中難免會用到的算法便是我這篇文章的主角。
0x01 曼哈頓的街道
這是一張美國曼哈頓的俯視圖，放眼望去除了能看到這里高樓林立之外，我們也能發現其另外一個特點，即橫平豎直的街道將一整塊地區整整齊齊的分成了好幾個區塊。人和車流只能行進在橫穿其中的街道上，也只能在街道的交叉口改變自己的前進的方向。例如要找出地圖中A點到B點的最佳路線，事實上就是從A點所在的交叉口沿著街道走到B點所在的交叉口，我們無法從區塊內部穿越過去，除了沿街道走別無選擇。
下面讓我們把曼哈頓的這些街道交叉口當做結點，兩個交叉口之間的街道當做邊，做出一個如下圖所示的二維網格。
那么A點到B點的實際距離是多少呢？考慮到我們只能沿著街道行走，而無法從街道圍成的區塊中穿越，因此在這種情況下A點到B點的實際距離并不是它們之間的直線距離，而是應該如下圖所示的這樣：
轉換成數學語言就是這樣：
dis = abs(A.x - B.x) + abs(A.y - B.y)
對了，這就是 曼哈頓距離 。也就是在A星算法中常常被用來作為啟發函數的家伙。等等，啟發函數是什么？讓我繼續。
0x02 醉漢尋“路”
從A點到B點的這條路徑，顯然包括了以A為起點B為終點的一系列結點，而每個結點也只能從和自己相鄰的結點中選擇下一個行走目標。但是正如現實生活一樣，暢通無阻的街道總是奢求，在路上總會花費一些代價，例如路況不佳，交通擁堵等等原因造成從這條道路行走時會花費更多的時間。因此在尋路中，一條路徑的代價等于在每個路口選擇的道路的代價之和。了解了這些之后，就讓我們來實現一個最粗暴的尋路方式，仿佛一個醉漢，無視每條道路是否已經走過，也不關心每條道路所花費的時間代價，反正只需要在路口閉著眼睛做出一個選擇就好了。
//偽代碼
q = newqueue
q.enqueue(newpath(start))
while q is not empty
p = q.dequeue
if p.lastNode == destination
return p
foreach n in p.lastNode.neighbours
q.enqueue(p.continuepath(n))
//找不到合適路徑
return null
這樣做的后果是什么呢？不錯，就像一個醉漢一樣，從路口的四個方向中隨機選擇一個方向，甚至還有可能走回頭路（因為沒有記錄他已經走過的路口），也許最后的確能夠找到家，但是這個過程中卻不知道消耗了多少時間，走了多少冤枉路。更有甚者，如果實際上并沒有一條能夠到達目的地的路徑，甚至會出現“鬼打墻”的情況，即進入了一個無限的死循環之中無法自拔。所以，讓我們來幫他一下吧，既然醉漢不記得已經走過了哪些路口，那么就讓我們來幫他記住他走過的路口。我們為上面的代碼引入一個closed集合，用來保存已經走過路口。
//偽代碼
//引入一個集合，用來保存已經走過的路口
closed = {}
q = newqueue
q.enqueue(newpath(start))
while q is not empty
p = q.dequeue
//如果下面closed集合中包含了路徑p的最后一個路口
//p.last則忽略
if closed contains p.last
continue
//如果路徑p的最后一個路口即是目的地，則直接返回p
if p.last == destination
return p
//否則將該點p.last加入到closed集合中
closed.add(p.last)
//把點p.last相鄰的點加入到隊列中
foreach n in p.last.neighbours
q.enqueue(p.continuepath(n))
//找不到合適的路
return null
這樣，我們就幫醉漢解決了走回頭路的問題，也消除了“鬼打墻”的隱患。但是，醉漢在選擇道路時仍然沒有一個明確的目標，這也就決定了他在尋找目的地的效率并不高效。因為他仍然會向四面八方尋路，雖然他在我們的幫助下已經不會走回頭路了。顯然，為了盡早讓醉漢回到家，我們需要為他選擇一條最佳的道路。但是，這條最佳的道路到底應該如何選擇（預估）呢？
0x03 給我一個指南針
在考慮如何尋找最佳路徑之前，我們第一步要做的顯然就是為最佳路徑定義一個可以量化的標準。到底以什么為標準來評價一條路徑呢？最簡單的，我們就選擇兩個路口之間的距離作為標準，這里我們將距離長度稱之為路徑的開銷，且一個路口上下左右相鄰的路口的消耗為1，而對角線上的路口消耗則為1.41。而我們評價一條潛在路徑的開銷時，所依據的數據主要來自兩個方面：
- 該路徑到目前的路口為止，已經經過的路口的總消耗。這一點我們是已知的，我們將這個消耗的值記為G。
- 該路徑到目前的路口為止，預估到目的地的消耗。這一點我們是猜測的，我們將這個消耗的值記為H。
而我們所要做的，便是在幫助醉漢不走回頭路的基礎上，再為醉漢指一個回家的方向。醉漢只要按照這個方向走，便能夠很快的找到家。而這個方向又是如何確定的呢？其實十分簡單，我們只需找到總消耗最小的路徑便可以了。這里我們記總消耗為F，那么顯然有如下這樣的等式：
F = G + H
那么具體應該如何操作呢？我們需要一個優先隊列，記錄每條路徑的總消耗以及這條路徑，并且根據路徑的總消耗來對該隊列進行排序，這樣消耗最小的路徑便能輕易地獲取了。所以，我們的代碼拓展成了下面這個樣子：
//偽代碼
//引入一個集合，用來保存已經走過的路口
closed = {}
q = newqueue;
//q為優先隊列，記錄路徑的消耗以及路徑，起始點消耗為0
q.enqueue(0, newpath(start))
while q is not empty
//優先隊列彈出消耗最小的路徑
p = q.dequeueCheapest
if closed contains p.last
continue;
if p.last == destination
return p
closed.add(p.last)
foreach n in p.last.neighbours
//獲得新的路徑
newpath2 = p.continuepath(n)
//將新路徑的總消耗（G+H)，和新路徑分別入隊
q.enqueue(newpath.G + estimateCost(n, destination), newpath2)
return null</pre>
其中，我們可以發現預估到目的地消耗的函數叫“estimateCost”，這便是在A星算法中我們常常提起的啟發函數。它的作用便是估算當前位置到目的地的大概距離，而在本文一開始介紹的曼哈頓距離便是一種常用的啟發函數。即計算當前路口（格子）到目標路口（格子）之間的垂直和水平的路口（格子）數量總和。
</div>
dis = abs(A.x - B.x) + abs(A.y - B.y)
而這個啟發函數，便是我們送給醉漢回家的指南針。當然，借這個醉漢回家的例子說明的僅僅是A星算法最基本的實現原理。而在實際的工程中，它也有更加復雜的使用環境，下面我就簡單的介紹幾種工程中實現A星尋路的工作方式。
0x04 工程中A星算法的實現方式
我們有了算法的實現思路，接下來便是如何在游戲中實現A星算法了。
要在游戲中進行尋路，首先要做的便是借助圖來將游戲地形表示出來，而這個圖便是導航圖。
而最常見的導航圖便是如下三種：
基于單元格的導航圖
如上圖所示，將游戲地圖劃分為許多單元格的形式便是我們所說的基于單元格的導航圖。這種表示方式的結構十分規則，因此最容易理解和使用，且易于動態更新。因此在需要頻繁動態更新場景的游戲中使用這種基于單元格的導航圖便十分的恰當。
但是，為了追求尋路的結果更加精確，單元格的大小就成為了關鍵，過大的單元格顯然和精確無緣，但是如果為了追求精確而使用很小的單元格，卻又不得不面對另一個問題——需要存儲和搜索的結點的數量會十分大。這樣不僅需要大量的消耗內存，同時也會影響搜索效率。
基于路點的導航圖
如果我們通過人工不規則的放置一些用來導航的點來代替剛剛的單元結點，那么是否會有更好的表現呢？因此，基于可視點，或者被稱為路點（The waypoints）的導航圖便出現了。如上圖所示，紅色的結點便是放置的路點，而路點之間的連線是游戲單位可以行走的路徑。
這種基于路點的導航圖的優勢便是可以讓場景設計師按照場景的特點來布置路點，由于可以按照設計師的想法來放置，因此基于路點的導航圖的一大特點便是靈活性很高，且不像基于單元格的導航圖那樣，需要存儲和搜索大量的結點，因此需要的內存和搜索的效率較前者都要優秀。
但是它的缺點也同樣明顯，那就是如果場景過大，放置少量的路點顯然無法滿足需要，但是放置很多路點時，會使得場景設計師的工作變得復雜且容易出錯。而由于游戲單位只能在兩個路點之間的連線上進行移動，因此如果游戲單位不在結點或結點間連線上的時候，會先到離它最近的路點上，之后再次移動，這樣從視覺上看會出現不自然的情況。
導航網格
如圖，導航網格將游戲地形劃分成了大大小小的三角形，而這些三角形也就成為了A星算法中的節點。相鄰的三角形可以直達，換言之，三角形相鄰的其他三角形既其相鄰的結點。
因此，與前兩種導航圖相比，由于其“節點”面積大，因此只需要少量的“節點”即可覆蓋整個游戲區域，從而減少了“節點”的數量。其次，也正是由于節點全部覆蓋了游戲場景，因此不必擔心像基于路點的導航圖那樣由于缺少路點而造成的尋路不精確的問題。
但是，它同樣并非十全十美的，相較前兩者而言，生成導航網格的時間較長，因此推薦在靜態場景中使用，而在地形經常發生變化的場景中減少使用。