• 
  G＝從起點(diǎn)A沿著已生成的路徑到一個(gè)給定方格的移動(dòng)開(kāi)銷(xiāo)。
• 
  H＝從給定方格到目的方格的估計(jì)移動(dòng)開(kāi)銷(xiāo)。這種方式常叫做試探，有點(diǎn)困惑人吧。其實(shí)之所以叫做試探法是因?yàn)檫@只是一個(gè)猜測(cè)。在找到路徑之前我們實(shí)際上并不知道實(shí)際的距離，因?yàn)槿魏螙|西都有可能出現(xiàn)在半路上（墻啊，水啊什么的）。本文中給出了一種計(jì)算H值的方法，網(wǎng)上還有很多其他文章介紹的不同方法。

?

我們要的路徑是通過(guò)反復(fù)遍歷開(kāi)放列表并選擇具有最小F值的方格來(lái)生成的。本文稍后將詳細(xì)討論這個(gè)過(guò)程。我們先進(jìn)一步看看如何計(jì)算那個(gè)等式。

如前所述，G是從起點(diǎn)A沿著已生成的路徑到一個(gè)給定方格的移動(dòng)開(kāi)銷(xiāo)，在本例中，我們指定每一個(gè)水平或者垂直移動(dòng)的開(kāi)銷(xiāo)為10，對(duì)角線移動(dòng)的開(kāi)銷(xiāo)為14。因?yàn)閷?duì)角線的實(shí)際距離是2的平方根（別嚇到啦），或者說(shuō)水平及垂直移動(dòng)開(kāi)銷(xiāo)的1.414倍。為了簡(jiǎn)單起見(jiàn)我們用了10和14這兩個(gè)值。比例大概對(duì)就好，我們還因此避免了平方根和小數(shù)的計(jì)算。這倒不是因?yàn)槲覀儽炕蛘哒f(shuō)不喜歡數(shù)學(xué)，而是因?yàn)閷?duì)電腦來(lái)說(shuō)，計(jì)算這樣的數(shù)字也要快很多。不然的話你會(huì)發(fā)現(xiàn)尋找路徑會(huì)非常慢。

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

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

G和H相加就得到了F。第一步搜索所得到的結(jié)果如下圖所示。每個(gè)方格里都標(biāo)出了F、G和H值。如起點(diǎn)方格右側(cè)的方格標(biāo)出的，左上角顯示的是F值，左下角是G值，右下角是H值。


[圖三]

我們來(lái)看看這些方格吧。在有字母的方格中，G＝10，這是因?yàn)樗谒椒较蛏想x起點(diǎn)只有一個(gè)方格遠(yuǎn)。起點(diǎn)緊挨著的上下左右都具有相同的G值10。對(duì)角線方向的方塊G值都是14。

H值通過(guò)估算到紅色目標(biāo)方格的曼哈頓距離而得出。用這種方法得出的起點(diǎn)右側(cè)方格到紅色方格有3個(gè)方格遠(yuǎn)，則該方格H值就是30。上面那個(gè)方格有4個(gè)方格遠(yuǎn)（注意只能水平和垂直移動(dòng)），H就是40。你可以大概看看其他方格的H值是怎么計(jì)算出來(lái)的。

每一個(gè)方格的F值，當(dāng)然就不過(guò)是G和H值之和了。

繼續(xù)搜索

為了繼續(xù)搜索，我們簡(jiǎn)單的從開(kāi)放列表中選擇具有最小F值的方格，然后對(duì)選中的方格進(jìn)行如下操作：

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

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


[圖四]

首先，我們將選中的方格從開(kāi)放列表中移除，并加入到封閉列表中（所以用亮藍(lán)色標(biāo)記）。然后再檢驗(yàn)它的相鄰節(jié)點(diǎn)。那么在它緊鄰的右邊的方格都是墻，所以不管它們。左邊挨著的是起始方格，而起始方格已經(jīng)在封閉列表中了，所以我們也不管它。

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

當(dāng)我們按如上過(guò)程依次檢驗(yàn)開(kāi)放列表中的所有四個(gè)方格后，會(huì)發(fā)現(xiàn)經(jīng)由當(dāng)前方格的話不會(huì)形成更好的路徑，那我們就保持目前的狀況不變。現(xiàn)在我們已經(jīng)處理了所有相鄰方格，準(zhǔn)備到下一個(gè)方格吧。

我們?cè)俦闅v一下開(kāi)放列表，目前只有7個(gè)方格了。我們挑個(gè)F值最小的吧。有趣的是，目前這種情況下，有兩個(gè)F值為54的方格。那我們?cè)趺催x擇呢？其實(shí)選哪個(gè)都沒(méi)關(guān)系，要考慮到速度的話，選你最近加到開(kāi)放列表中的那一個(gè)會(huì)更快些。當(dāng)離目的地越來(lái)越近的時(shí)候越偏向于選最后發(fā)現(xiàn)的方格。實(shí)際上這個(gè)真的沒(méi)關(guān)系（對(duì)待這個(gè)的不同造成了兩個(gè)版本的A*算法得到等長(zhǎng)的不同路徑）。

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


[圖五]

這一次，在我們檢驗(yàn)相鄰方格的時(shí)候發(fā)現(xiàn)右邊緊挨的那個(gè)是墻，就不管它了。上面挨著的那個(gè)也同樣忽略。還有右邊墻下面那個(gè)方格我們也不管。為什么呢？因?yàn)槟悴豢赡芮写侵苯拥竭_(dá)那個(gè)格子。實(shí)際上你得先向下走然后再通過(guò)那個(gè)方格。這個(gè)過(guò)程中是繞著墻角走。（注意：穿過(guò)墻角的這個(gè)規(guī)則是可選的，取決于你的節(jié)點(diǎn)是如何放置的。）

那么還剩下其他五個(gè)相鄰方格。當(dāng)前方格的下面那兩個(gè)還不在開(kāi)放列表中，那我們把它們加進(jìn)去并且把當(dāng)前方格作為它們的父方格。其他三個(gè)中有兩個(gè)已經(jīng)在封閉列表中了（兩個(gè)已經(jīng)在圖中用亮藍(lán)色標(biāo)記了，起始方格，上面的方格），所以就不用管了。最后那個(gè)，當(dāng)前方格左邊挨著的，要檢查一下經(jīng)由當(dāng)前節(jié)點(diǎn)到那里會(huì)不會(huì)降低它的G值。結(jié)果不行，所以我們又處理完畢了，然后去檢驗(yàn)開(kāi)放列表中的下一個(gè)格子。

重復(fù)這個(gè)過(guò)程直到我們把目的方格加入到開(kāi)放列表中了，那時(shí)候看起來(lái)會(huì)像下圖這個(gè)樣子。


[圖六]

注意到?jīng)]？起始方格下兩格的位置，那里的格子已經(jīng)和前一張圖不一樣了。之前它的G值是28并且指向右上方的那個(gè)方格。現(xiàn)在它的G值變成了20并且指向了正上方的方格。這個(gè)改變是在搜索過(guò)程中，它的G值被核查時(shí)發(fā)現(xiàn)在某個(gè)新路徑下可以變得更小時(shí)發(fā)生的。然后它的父方格也被重設(shè)并且重新計(jì)算了G值和F值。在本例中這個(gè)改變看起來(lái)好像不是很重要，但是在很多種情況下這種改變會(huì)使到達(dá)目標(biāo)的最佳路徑變得非常不同。

那么我們?cè)鯓觼?lái)自動(dòng)得出實(shí)際路徑的呢?很簡(jiǎn)單，只要從紅色目標(biāo)方格開(kāi)始沿著每一個(gè)方格的指針?lè)较蛞苿?dòng)，依次到達(dá)它們的父方格，最終肯定會(huì)到達(dá)起始方格。那就是你的路徑！如下圖所示。從A方格到B方格的移動(dòng)就差不多是沿著這個(gè)路徑從每個(gè)方格中心（節(jié)點(diǎn)）移動(dòng)到另一個(gè)方格中心，直到抵達(dá)終點(diǎn)。簡(jiǎn)單吧！


[圖七]

A* 算法總結(jié)

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