前言

請叫我標題黨！請叫我標題黨！請叫我標題黨！因為下面的文字既不發(fā)生在美國曼哈頓，也不是一個講述美國夢的故事。相反，這可能只是一篇沒有那么枯燥的關(guān)于算法的文章。A星算法，這個在游戲?qū)ぢ烽_發(fā)中難免會用到的算法便是我這篇文章的主角。

1、曼哈頓的街道
?

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

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

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

轉(zhuǎn)換成數(shù)學語言就是這樣：

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

對了，這就是曼哈頓距離。也就是在A星算法中常常被用來作為啟發(fā)函數(shù)的家伙。等等，啟發(fā)函數(shù)是什么？讓我繼續(xù)。

2、醉漢尋“路”

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

了解了這些之后，就讓我們來實現(xiàn)一個最粗暴的尋路方式，仿佛一個醉漢，無視每條道路是否已經(jīng)走過，也不關(guān)心每條道路所花費的時間代價，反正只需要在路口閉著眼睛做出一個選擇就好了。
這樣做的后果是什么呢？不錯，就像一個醉漢一樣，從路口的四個方向中隨機選擇一個方向，甚至還有可能走回頭路（因為沒有記錄他已經(jīng)走過的路口），也許最后的確能夠找到家，但是這個過程中卻不知道消耗了多少時間，走了多少冤枉路。更有甚者，如果實際上并沒有一條能夠到達目的地的路徑，甚至會出現(xiàn)“鬼打墻”的情況，即進入了一個無限的死循環(huán)之中無法自拔。

所以，讓我們來幫他一下吧，既然醉漢不記得已經(jīng)走過了哪些路口，那么就讓我們來幫他記住他走過的路口。我們?yōu)樯厦娴拇a引入一個closed集合，用來保存已經(jīng)走過路口。
?

//偽代碼

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

復制代碼

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

3、給我一個指南針

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

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

該路徑到目前的路口為止，已經(jīng)經(jīng)過的路口的總消耗。這一點我們是已知的，我們將這個消耗的值記為G。

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

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

F = G + H

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

//偽代碼

//引入一個集合，用來保存已經(jīng)走過的路口

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

復制代碼

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

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

而這個啟發(fā)函數(shù)，便是我們送給醉漢回家的指南針。

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

4、工程中A星算法的實現(xiàn)方式

我們有了算法的實現(xiàn)思路，接下來便是如何在游戲中實現(xiàn)A星算法了。
?

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

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

基于單元格的導航圖
?

如上圖所示，將游戲地圖劃分為許多單元格的形式便是我們所說的基于單元格的導航圖。這種表示方式的結(jié)構(gòu)十分規(guī)則，因此最容易理解和使用，且易于動態(tài)更新。因此在需要頻繁動態(tài)更新場景的游戲中使用這種基于單元格的導航圖便十分的恰當。

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

基于路點的導航圖
?

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

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

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

導航網(wǎng)格
?

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

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

但是，它同樣并非十全十美的，相較前兩者而言，生成導航網(wǎng)格的時間較長，因此推薦在靜態(tài)場景中使用，而在地形經(jīng)常發(fā)生變化的場景中減少使用。

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的趣说游戏AI开发：曼哈顿街角的A*算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。