你是否在做一款游戲的時候想創造一些怪獸或者游戲主角，讓它們移動到特定的位置，避開墻壁和障礙物呢？

如果是的話，請看這篇教程，我們會展示如何使用A星尋路算法來實現它！

在網上已經有很多篇關于A星尋路算法的文章，但是大部分都是提供給已經了解基本原理的高級開發者的。

本篇教程將從最基本的原理講起。我們會一步步講解A星尋路算法，幷配有很多圖解和例子。

不管你使用的是什么編程語言或者操作平臺，你會發現本篇教程很有幫助，因為它在非編程語言的層面上解釋了算法的原理。稍后，會有一篇教程，展示如何在Cocos2D iPhone 游戲中實現A星算法。

現在找下到達一杯咖啡因飲料和美味的零食的最短路徑，開始吧！:]

一只探路貓

讓我們想象一下，有一款游戲，游戲中一只貓想要找到獲取骨頭的路線。

“為什么會有一只貓想要骨頭？！”你可能會這么想。在本游戲中， 這是一只狡猾的貓，他想撿起骨頭給狗，以防止被咬死！:]

現在想像一下下圖中的貓想找到到達骨頭的最短路徑：

不幸的是，貓不能直接從它當前的位置走到骨頭的位置，因為有面墻擋住了去路，而且它在游戲中不是一只幽靈貓！

游戲中的貓同樣懶惰，它總是想找到最短路徑，這樣當他回家看望它的女朋友時不會太累:-)

但是我們如何編寫一個算法計算出貓要選擇的那條路徑呢？A星算法拯救了我們！

簡化搜索區域

尋路的第一步是簡化成容易控制的搜索區域。

怎么處理要根據游戲來決定了。例如，我們可以將搜索區域劃分成像素點，但是這樣的劃分粒度對于我們這款基于方塊的游戲來說太高了（沒必要）。

作為代替，我們使用方塊（一個正方形）作為尋路算法的單元。其他的形狀類型也是可能的（比如三角形或者六邊形），但是正方形是最簡單并且最適合我們需求的。

像那樣去劃分，我們的搜索區域可以簡單的用一個地圖大小的二維數組去表示。所以如果是25*25方塊大小的地圖，我們的搜索區域將會是一個有625個正方形的數組。如果我們把地圖劃分成像素點，搜索區域就是一個有640，000個正方形的數組了（一個方塊是32*32像素）！

現在讓我們基于目前的區域，把區域劃分成多個方塊來代表搜索空間（在這個簡單的例子中，7*6個方塊 = 42 個方塊）：

Open和Closed列表

既然我們創建了一個簡單的搜索區域，我們來討論下A星算法的工作原理吧。

除了懶惰之外，我們的貓沒有好的記憶力，所以它需要兩個列表：

1. 一個記錄下所有被考慮來尋找最短路徑的方塊（稱為open 列表）
2. 一個記錄下不會再被考慮的方塊（成為closed列表）

貓首先在closed列表中添加當前位置（我們把這個開始點稱為點 “A”）。然后，把所有與它當前位置相鄰的可通行小方塊添加到open列表中。

下圖是貓在某一位置時的情景（綠色代表open列表）:

現在貓需要判斷在這些選項中，哪項才是最短路徑，但是它要如何去選擇呢？

在A星尋路算法中，通過給每一個方塊一個和值，該值被稱為路徑增量。讓我們看下它的工作原理！

路徑增量

我們將會給每個方塊一個G+H 和值：

• G是從開始點A到當前方塊的移動量。所以從開始點A到相鄰小方塊的移動量為1，該值會隨著離開始點越來越遠而增大。
• H是從當前方塊到目標點（我們把它稱為點B，代表骨頭！）的移動量估算值。這個常被稱為探視，因為我們不確定移動量是多少 – 僅僅是一個估算值。

你也許會對“移動量”感興趣。在游戲中，這個概念很簡單 – 僅僅是方塊的數量。

然而，在游戲中你可以對這個值做調整。例如：

• 如果你允許對角線移動，你可以針對對角線移動把移動量調得大一點。
• 如果你有不同的地形，你可以將相應的移動量調整得大一點 – 例如針對一塊沼澤，水，或者貓女海報:-)

這就是大概的意思 – 現在讓我們詳細分析下如何計算出G和H值。

關于G值

G是從開始點A到達當前方塊的移動量（在本游戲中是指方塊的數目）。

為了計算出G的值，我們需要從它的前繼（上一個方塊）獲取，然后加1。所以，每個方塊的G值代表了從點A到該方塊所形成路徑的總移動量。

例如，下圖展示了兩條到達不同骨頭的路徑，每個方塊都標有它的G值：

關于H值

H值是從當前方塊到終點的移動量估算值（在本游戲中是指方塊的數目）。

移動量估算值離真實值越接近，最終的路徑會更加精確。如果估算值停止作用，很可能生成出來的路徑不會是最短的（但是它可能是接近的）。這個題目相對復雜，所以我們不會再本教程中講解，但是我在教程的末尾提供了一個網絡鏈接，對它做了很好的解釋。

為了讓它更簡單，我們將使用“曼哈頓距離方法”（也叫“曼哈頓長”或者“城市街區距離”），它只是計算出距離點B，剩下的水平和垂直的方塊數量，略去了障礙物或者不同陸地類型的數量。

例如，下圖展示了使用“城市街區距離”，從不同的開始點到終點，去估算H的值（黑色字）：

A星算法

既然你知道如何計算每個方塊的和值（我們將它稱為F，等于G+H),  我們來看下A星算法的原理。

貓會重復以下步驟來找到最短路徑：

1. 將方塊添加到open列表中，該列表有最小的和值。且將這個方塊稱為S吧。
2. 將S從open列表移除，然后添加S到closed列表中。
3. 對于與S相鄰的每一塊可通行的方塊T：

1. 如果T在closed列表中：不管它。
2. 如果T不在open列表中：添加它然后計算出它的和值。
3. 如果T已經在open列表中：當我們使用當前生成的路徑到達那里時，檢查F 和值是否更小。如果是，更新它的和值和它的前繼。

如果你對它的工作原理還有點疑惑，不用擔心 – 我們會用例子一步步介紹它的原理！:]

貓的路徑

讓我們看下我們的懶貓到達骨頭的行程例子。

在下圖中，我根據以下內容，列出了公式F = G + H 中的每項值：

• F（方塊的和值）：左上角
• G（從A點到方塊的移動量）：左下角
• H（從方塊到B點的估算移動量): 右下角

同時，箭頭指示了到達相應方塊的移動方向。

最后，在每一步中，紅色方塊表示closed列表，綠色方塊表示open列表。

好的，我們開始吧！

第一步

第一步，貓會確定相對于開始位置（點A）的相鄰方塊，計算出他們的F和值，然后把他們添加到open列表中：

你會看到每個方塊都列出了H值（有兩個是6，一個是4）。我建議根據“城市街區距離”去計算方塊的相關值，確保你理解了它的原理。

同時注意F值（在左上角）是G（左下角）值和H（右下腳）值的和。
第二步

在第二步中，貓選擇了F和值最小的方塊，把它添加到closed列表中，然后檢索它的相鄰方塊的相關數值。

現在你將看到擁有最小增量的是F值為4的方塊。貓嘗試添加所有相鄰的方塊到open列表中（然后計算他們的和值），除了貓自身的方塊不能添加以外（因為它已經被添加到了closed列表中）或者它是墻壁方塊（因為它不能通行）。

注意被添加到open列表的兩個新方塊，他們的G值都增加了1，因為他們現在離開始點有2個方塊遠了。你也許需要再計算下“城市街區距離”以確保你理解了每個新方塊的H值。
第三步

再次，我們選擇了有最小F和值（5）的方塊，繼續重復之前的步驟：

現在，只有一個可能的方塊被添加到open列表中了，因為已經有一個相鄰的方塊在close列表中，其他兩個是墻壁方塊。

第四步

現在我們遇到了一個有趣的情況。正如你之前看到的，有4個方塊的F和值都為7 – 我們要怎么做呢？！

有幾種解決方法可以使用，但是最簡單（快速）的方法是一直跟著最近被添加到open列表中的方塊。現在繼續沿著最近被添加的方塊前進。

這次有兩個可通過的相鄰方塊了，我們還是像之前那樣計算他們的和值。
第五步

接著我們選擇了最小和值（7）的方塊，繼續重復之前的步驟：

我們越來越接近終點了！

第六步

你現在訓練有素了！我打賭你能夠猜出下一步是下面這樣子了：

我們差不多到終點了，但是這次你看到有兩條到達骨頭的最短路徑提供給我們選擇：

在我們的例子中，有兩條最短路徑：

• 1-2-3-4-5-6
• 1-2-3-4-5-7

It doesn’t really matter which of these we choose, it comes down to the actual implementation in code.

選擇哪一條其實沒關系，現在到了真正用代碼實現的時候了。

第七步

讓我們從其中一塊方塊，再重復一遍步驟吧：

啊哈，骨頭在open列表中了！
第八步

現在目標方塊在open列表中了，算法會把它添加到closed列表中：

然后，算法要做的所有事情就是返回，計算出最終的路徑！

一只有遠見的貓

在上面的例子中，我們看到當貓在尋找最短路徑時，它經常選擇更好的方塊（那個在它的未來最短路徑上的方塊）- 好像它是一只有遠見的貓！

但是如果貓是盲目的，并且總是選擇第一個添加到它的列表上的方塊，會發生什么事情？

下圖展示了所有在尋找過程中會被使用到的方塊。你會看到貓在嘗試更多的方塊，但是它仍然找到了最短路徑（不是之前的那條，而是另一條等價的）：

圖中的紅色方塊不代表最短路徑，它們只是代表在某個時候被選擇為“S”的方塊。

我建議你看著上面的圖，并且嘗試過一遍步驟。這次無論你看到哪個相鄰的方塊，都選擇“最壞”的方式去走。你會發現最后還是找到了最短路徑！

所以你可以看到跟隨一個“錯誤的”方塊是沒有問題的，你仍然會在多次重復嘗試后找到最短路徑。

所以在我們的實現中，我們會按照以下的算法添加方塊到open列表中：

• 相鄰的方塊會返回這些順序: 上面/左邊/下面/右邊。
• 當所有的方塊都有相同的和值后，方塊會被添加到open列表中（所以第一個被添加的方塊是第一個被貓挑選的）。

下面是從原路返回的示意圖：

最短的路徑是從終點開始，一步步返回到起點構成的（例子：在終點我們可以看到箭頭指向右邊，所以該方塊的前繼在它的左邊）。

總的來說，我們可以用下面的偽代碼，合成貓的尋找過程。這是Objective-C寫的，但是你可以用任何的語言去實現它：

[openList add:originalSquare]; // start by adding the original position to the open list do { 	currentSquare = [openList squareWithLowestFScore]; // Get the square with the lowest F score   	[closedList add:currentSquare]; // add the current square to the closed list 	[openList remove:currentSquare]; // remove it to the open list   	if ([closedList contains:destinationSquare]) { // if we added the destination to the closed list, we've found a path 		// PATH FOUND 		break; // break the loop 	}   	adjacentSquares = [currentSquare walkableAdjacentSquares]; // Retrieve all its walkable adjacent squares   	foreach (aSquare in adjacentSquares) {   		if ([closedList contains:aSquare]) { // if this adjacent square is already in the closed list ignore it 			continue; // Go to the next adjacent square 		}   		if (![openList contains:aSquare]) { // if its not in the open list   			// compute its score, set the parent 			[openList add:aSquare]; // and add it to the open list   		} else { // if its already in the open list   			// test if using the current G score make the aSquare F score lower, if yes update the parent because it means its a better path   		} 	}   } while(![openList isEmpty]); // Continue until there is no more available square in the open list (which means there is no path)

現在是不是對實現它很興奮了？！在接下來的教程中，我們將會這么做！

現在可以做什么？

恭喜，你現在知道A星尋路算法的基本原理了！如果你想進一步了解它，我建議你閱讀Amit’s A* Pages。