• 
  G＝從起點A沿著已生成的路徑到一個給定方格的移動開銷。
• 
  H＝從給定方格到目的方格的估計移動開銷。這種方式常叫做試探，有點困惑人吧。其實之所以叫做試探法是因為這只是一個猜測。在找到路徑之前我們實際上并不知道實際的距離，因為任何東西都有可能出現在半路上（墻啊，水啊什么的）。本文中給出了一種計算H值的方法，網上還有很多其他文章介紹的不同方法。

?

我們要的路徑是通過反復遍歷開放列表并選擇具有最小F值的方格來生成的。本文稍后將詳細討論這個過程。我們先進一步看看如何計算那個等式。

如前所述，G是從起點A沿著已生成的路徑到一個給定方格的移動開銷，在本例中，我們指定每一個水平或者垂直移動的開銷為10，對角線移動的開銷為14。因為對角線的實際距離是2的平方根（別嚇到啦），或者說水平及垂直移動開銷的1.414倍。為了簡單起見我們用了10和14這兩個值。比例大概對就好，我們還因此避免了平方根和小數的計算。這倒不是因為我們笨或者說不喜歡數學，而是因為對電腦來說，計算這樣的數字也要快很多。不然的話你會發現尋找路徑會非常慢。

我們要沿特定路徑計算給定方格的G值，辦法就是找出該方格的父方格的G值，并根據與父方格的相對位置（斜角或非斜角方向）來給這個G值加上14或者10。在本例中這個方法將隨著離起點方格越來越遠計算的方格越來越多而用得越來越多。

有很多方法可以用來估計H值。我們用的這個叫做曼哈頓（Manhattan）方法，即計算通過水平和垂直方向的平移到達目的地所經過的方格數乘以10來得到H值。之所以叫Manhattan方法是因為這就像計算從一個地方移動到另一個地方所經過的城市街區數一樣，而通常你是不能斜著穿過街區的。重要的是，在計算H值時并不考慮任何障礙物。因為這是對剩余距離的估計值而不是實際值（通常是要保證估計值不大于實際值――譯者注）。這就是為什么這個方式被叫做試探法的原因了。想要了解更多些嗎？ 這里還有更多式子和關于試探法的額外說明。

G和H相加就得到了F。第一步搜索所得到的結果如下圖所示。每個方格里都標出了F、G和H值。如起點方格右側的方格標出的，左上角顯示的是F值，左下角是G值，右下角是H值。


[圖三]

我們來看看這些方格吧。在有字母的方格中，G＝10，這是因為它在水平方向上離起點只有一個方格遠。起點緊挨著的上下左右都具有相同的G值10。對角線方向的方塊G值都是14。

H值通過估算到紅色目標方格的曼哈頓距離而得出。用這種方法得出的起點右側方格到紅色方格有3個方格遠，則該方格H值就是30。上面那個方格有4個方格遠（注意只能水平和垂直移動），H就是40。你可以大概看看其他方格的H值是怎么計算出來的。

每一個方格的F值，當然就不過是G和H值之和了。

繼續搜索

為了繼續搜索，我們簡單的從開放列表中選擇具有最小F值的方格，然后對選中的方格進行如下操作：

4.
將其從開放列表中移除，并加到封閉列表中。
5.
檢驗所有的相鄰方格，忽略那些不可通過的或者已經在封閉列表里的方格。如果這個相鄰方格不在開放列表中，就把它添加進去。并將當前選定方格設為新添方格的父方格。
6.
如果某個相鄰方格已經在開放列表中了（意味著已經探測過，而且已經設置過父方格――譯者），就看看有沒有到達那個方格的更好的路徑。也就是說，如果從當前選中方格到那個方格，會不會使那個方格的G值更小。如果不能，就不進行任何操作。
相反的，如果新路徑的G值更小，就將該相鄰方格的父方格重設為當前選中方格。（在上圖中是改變其指針的方向為指向選中方格。最后，重新計算那個相鄰方格的F和G值。如果你看糊涂了，下面會有圖解說明。

好啦，咱們來看看具體點的例子。在初始時的9個方塊中，當開始方格被加到封閉列表后，開放列表里還剩8個方格。在這八個方格當中，位于起點方格右邊的那個方格具有最小的F值40。所以我們選擇這個方格作為下一個中心方格。下圖中它以高亮的藍色表示。


[圖四]

首先，我們將選中的方格從開放列表中移除，并加入到封閉列表中（所以用亮藍色標記）。然后再檢驗它的相鄰節點。那么在它緊鄰的右邊的方格都是墻，所以不管它們。左邊挨著的是起始方格，而起始方格已經在封閉列表中了，所以我們也不管它。

其他四個方格已經在開放列表中，那么我們就要檢驗一下如果路徑經由當前選中方格到那些方格的話會不會更好，當然，是用G值作為參考。來看看選中方格右上角的那一個方格，它當前的G值是14，如果我們經由當前節點再到達那個方格的話，G值會是20（到當前方格的G值是10，然后向上移動一格就再加上10）。為20的G值比14大，因此這樣的路徑不會更好。你看看圖就會容易理解些。顯然從起始點沿斜角方向移動到那個方格比先水平移動一格再垂直移動一格更直接。

當我們按如上過程依次檢驗開放列表中的所有四個方格后，會發現經由當前方格的話不會形成更好的路徑，那我們就保持目前的狀況不變。現在我們已經處理了所有相鄰方格，準備到下一個方格吧。

我們再遍歷一下開放列表，目前只有7個方格了。我們挑個F值最小的吧。有趣的是，目前這種情況下，有兩個F值為54的方格。那我們怎么選擇呢？其實選哪個都沒關系，要考慮到速度的話，選你最近加到開放列表中的那一個會更快些。當離目的地越來越近的時候越偏向于選最后發現的方格。實際上這個真的沒關系（對待這個的不同造成了兩個版本的A*算法得到等長的不同路徑）。

那我們選下面的那個好了，就是起始方格右邊的，下圖所示的那個。


[圖五]

這一次，在我們檢驗相鄰方格的時候發現右邊緊挨的那個是墻，就不管它了。上面挨著的那個也同樣忽略。還有右邊墻下面那個方格我們也不管。為什么呢？因為你不可能切穿墻角直接到達那個格子。實際上你得先向下走然后再通過那個方格。這個過程中是繞著墻角走。（注意：穿過墻角的這個規則是可選的，取決于你的節點是如何放置的。）

那么還剩下其他五個相鄰方格。當前方格的下面那兩個還不在開放列表中，那我們把它們加進去并且把當前方格作為它們的父方格。其他三個中有兩個已經在封閉列表中了（兩個已經在圖中用亮藍色標記了，起始方格，上面的方格），所以就不用管了。最后那個，當前方格左邊挨著的，要檢查一下經由當前節點到那里會不會降低它的G值。結果不行，所以我們又處理完畢了，然后去檢驗開放列表中的下一個格子。

重復這個過程直到我們把目的方格加入到開放列表中了，那時候看起來會像下圖這個樣子。


[圖六]

注意到沒？起始方格下兩格的位置，那里的格子已經和前一張圖不一樣了。之前它的G值是28并且指向右上方的那個方格。現在它的G值變成了20并且指向了正上方的方格。這個改變是在搜索過程中，它的G值被核查時發現在某個新路徑下可以變得更小時發生的。然后它的父方格也被重設并且重新計算了G值和F值。在本例中這個改變看起來好像不是很重要，但是在很多種情況下這種改變會使到達目標的最佳路徑變得非常不同。

那么我們怎樣來自動得出實際路徑的呢?很簡單，只要從紅色目標方格開始沿著每一個方格的指針方向移動，依次到達它們的父方格，最終肯定會到達起始方格。那就是你的路徑！如下圖所示。從A方格到B方格的移動就差不多是沿著這個路徑從每個方格中心（節點）移動到另一個方格中心，直到抵達終點。簡單吧！


[圖七]

A* 算法總結

1.
將開始節點放入開放列表(開始節點的F和G值都視為0);
2.
重復一下步驟:
? ?? ?? ?? ?i.
在開放列表中查找具有最小F值的節點,并把查找到的節點作為 當前節點 ;
? ?? ?? ???ii.
把 當前節點 從開放列表刪除, 加入到封閉列表;
? ?? ?? ?iii.
對 當前節點 相鄰的每一個節點依次執行以下步驟:
1.
如果該 相鄰節點 不可通行或者該 相鄰節點 已經在封閉列表中,則什么操作也不執行,繼續檢驗下一個節點;
2.
如果該 相鄰節點 不在開放列表中,則將該節點添加到開放列表中, 并將該 相鄰節點 的父節點設為 當前節點 ,同時保存該 相鄰節點 的G和F值;
3.
如果該 相鄰節點 在開放列表中, 則判斷若經由 當前節點 到達該 相鄰節點 的G值是否小于原來保存的G值,若小于,則將該 相鄰節點 的父節點設為 當前節點 ,并重新設置該 相鄰節點 的G和F值.
? ?? ???iv.
循環結束條件:
當 終點節點 被加入到開放列表作為待檢驗節點時, 表示路徑被找到,此時應終止循環;
或者當開放列表為空,表明已無可以添加的新節點,而已檢驗的節點中沒有終點節點則意味著路徑無法被找到,此時也結束循環;
3.
從 終點節點 開始沿父節點遍歷, 并保存整個遍歷到的節點坐標,遍歷所得的節點就是最后得到的路徑;