愛華網(wǎng)AStar尋徑算法小結(jié)
AStar算法是一個非常成熟而且用處極多的一種尋徑算法。
AStar尋徑算法思想是將地圖上所有點(小塊)放到一個2維數(shù)組中，然后以尋徑原點開始各個方向試探，將可走點放入open表中，并計算出此點到目的點的代價（H代價）以及從原點到此點的移動代價（G代價），然后對open表中H和G代價和最小的點標記為close狀態(tài)，并加入到結(jié)果路徑表中，并繼續(xù)各方向試探，直到目的點被放到open表中，結(jié)果路徑表中的點就是尋徑結(jié)果。
AStar尋徑算法步驟(這里是GameRes的帖子的內(nèi)容很步驟很清晰，所以記下來http://data.gameres.com/message.asp?TopicID=25439)：
1，從點A開始，并且把它作為待處理點存入一個“開啟列表”。開啟列表就像一張購物清單。盡管現(xiàn)在列表里只有一個元素，但以后就會多起來。你的路徑可能會通過它包含的方格，也可能不會?；旧?，這是一個待檢查方格的列表。
2，尋找起點周圍所有可到達或者可通過的方格，跳過有墻，水，或其他無法通過地形的方格。也把他們加入開啟列表。為所有這些方格保存點A作為“父方格”。當我們想描述路徑的時候，父方格的資料是十分重要的。后面會解釋它的具體用途。
3，從開啟列表中刪除點A，把它加入到一個“關(guān)閉列表”，列表中保存所有不需要再次檢查的方格。
在這一點，你應(yīng)該形成如圖的結(jié)構(gòu)。在圖中，暗綠色方格是你起始方格的中心。它被用淺藍色描邊，以表示它被加入到關(guān)閉列表中了。所有的相鄰格現(xiàn)在都在開啟列表中，它們被用淺綠色描邊。每個方格都有一個灰色指針反指他們的父方格，也就是開始的方格。
[圖2]
接著，我們選擇開啟列表中的臨近方格，大致重復(fù)前面的過程，如下。但是，哪個方格是我們要選擇的呢？是那個F值最低的。
路徑評分
選擇路徑中經(jīng)過哪個方格的關(guān)鍵是下面這個等式：
F = G + H
這里：
* G = 從起點A，沿著產(chǎn)生的路徑，移動到網(wǎng)格上指定方格的移動耗費。
* H =從網(wǎng)格上那個方格移動到終點B的預(yù)估移動耗費。這經(jīng)常被稱為啟發(fā)式的，可能會讓你有點迷惑。這樣叫的原因是因為它只是個猜測。我們沒辦法事先知道路徑的長度，因為路上可能存在各種障礙(墻，水，等等)。雖然本文只提供了一種計算H的方法，但是你可以在網(wǎng)上找到很多其他的方法。
我們的路徑是通過反復(fù)遍歷開啟列表并且選擇具有最低F值的方格來生成的。文章將對這個過程做更詳細的描述。首先，我們更深入的看看如何計算這個方程。
正如上面所說，G表示沿路徑從起點到當前點的移動耗費。在這個例子里，我們令水平或者垂直移動的耗費為10，對角線方向耗費為14。我們?nèi)∵@些值是因為沿對角線的距離是沿水平或垂直移動耗費的的根號2（別怕），或者約1.414倍。為了簡化，我們用10和14近似。比例基本正確，同時我們避免了求根運算和小數(shù)。這不是只因為我們怕麻煩或者不喜歡數(shù)學(xué)。使用這樣的整數(shù)對計算機來說也更快捷。你不就就會發(fā)現(xiàn)，如果你不使用這些簡化方法，尋路會變得很慢。
既然我們在計算沿特定路徑通往某個方格的G值，求值的方法就是取它父節(jié)點的G值，然后依照它相對父節(jié)點是對角線方向或者直角方向(非對角線)，分別增加14和10。例子中這個方法的需求會變得更多，因為我們從起點方格以外獲取了不止一個方格。
H值可以用不同的方法估算。我們這里使用的方法被稱為曼哈頓方法，它計算從當前格到目的格之間水平和垂直的方格的數(shù)量總和，忽略對角線方向。然后把結(jié)果乘以10。這被成為曼哈頓方法是因為它看起來像計算城市中從一個地方到另外一個地方的街區(qū)數(shù)，在那里你不能沿對角線方向穿過街區(qū)。很重要的一點，我們忽略了一切障礙物。這是對剩余距離的一個估算，而非實際值，這也是這一方法被稱為啟發(fā)式的原因。想知道更多？你可以在這里找到方程和額外的注解。
F的值是G和H的和。第一步搜索的結(jié)果可以在下面的圖表中看到。F,G和H的評分被寫在每個方格里。正如在緊挨起始格右側(cè)的方格所表示的，F(xiàn)被打印在左上角，G在左下角，H則在右下角。
[圖3]
現(xiàn)在我們來看看這些方格。寫字母的方格里，G =10。這是因為它只在水平方向偏離起始格一個格距。緊鄰起始格的上方，下方和左邊的方格的G值都等于10。對角線方向的G值是14。
H值通過求解到紅色目標格的曼哈頓距離得到，其中只在水平和垂直方向移動，并且忽略中間的墻。用這種方法，起點右側(cè)緊鄰的方格離紅色方格有3格距離，H值就是30。這塊方格上方的方格有4格距離(記住，只能在水平和垂直方向移動)，H值是40。你大致應(yīng)該知道如何計算其他方格的H值了～。
每個格子的F值，還是簡單的由G和H相加得到
繼續(xù)搜索
為了繼續(xù)搜索，我們簡單的從開啟列表中選擇F值最低的方格。然后，對選中的方格做如下處理：
4，把它從開啟列表中刪除，然后添加到關(guān)閉列表中。
5，檢查所有相鄰格子。跳過那些已經(jīng)在關(guān)閉列表中的或者不可通過的(有墻，水的地形，或者其他無法通過的地形)，把他們添加進開啟列表，如果他們還不在里面的話。把選中的方格作為新的方格的父節(jié)點。
6，如果某個相鄰格已經(jīng)在開啟列表里了，檢查現(xiàn)在的這條路徑是否更好。換句話說，檢查如果我們用新的路徑到達它的話，G值是否會更低一些。如果不是，那就什么都不做。
另一方面，如果新的G值更低，那就把相鄰方格的父節(jié)點改為目前選中的方格（在上面的圖表中，把箭頭的方向改為指向這個方格）。最后，重新計算F和G的值。如果這看起來不夠清晰，你可以看下面的圖示。
好了，讓我們看看它是怎么運作的。我們最初的9格方格中，在起點被切換到關(guān)閉列表中后，還剩8格留在開啟列表中。這里面，F(xiàn)值最低的那個是起始格右側(cè)緊鄰的格子，它的F值是40。因此我們選擇這一格作為下一個要處理的方格。在緊隨的圖中，它被用藍色突出顯示。
[圖4]
首先，我們把它從開啟列表中取出，放入關(guān)閉列表(這就是他被藍色突出顯示的原因)。然后我們檢查相鄰的格子。哦，右側(cè)的格子是墻，所以我們略過。左側(cè)的格子是起始格。它在關(guān)閉列表里，所以我們也跳過它。
其他4格已經(jīng)在開啟列表里了，于是我們檢查G值來判定，如果通過這一格到達那里，路徑是否更好。我們來看選中格子下面的方格。它的G值是14。如果我們從當前格移動到那里，G值就會等于20(到達當前格的G值是10，移動到上面的格子將使得G值增加10)。因為G值20大于14，所以這不是更好的路徑。如果你看圖，就能理解。與其通過先水平移動一格，再垂直移動一格，還不如直接沿對角線方向移動一格來得簡單。
當我們對已經(jīng)存在于開啟列表中的4個臨近格重復(fù)這一過程的時候，我們發(fā)現(xiàn)沒有一條路徑可以通過使用當前格子得到改善，所以我們不做任何改變。既然我們已經(jīng)檢查過了所有鄰近格，那么就可以移動到下一格了。
于是我們檢索開啟列表，現(xiàn)在里面只有7格了，我們?nèi)匀贿x擇其中F值最低的。有趣的是，這次，有兩個格子的數(shù)值都是54。我們?nèi)绾芜x擇？這并不麻煩。從速度上考慮，選擇最后添加進列表的格子會更快捷。這種導(dǎo)致了尋路過程中，在靠近目標的時候，優(yōu)先使用新找到的格子的偏好。但這無關(guān)緊要。（對相同數(shù)值的不同對待，導(dǎo)致不同版本的A*算法找到等長的不同路徑。）
那我們就選擇起始格右下方的格子，如圖。
[圖5]
這次，當我們檢查相鄰格的時候，發(fā)現(xiàn)右側(cè)是墻，于是略過。上面一格也被略過。我們也略過了墻下面的格子。為什么呢？因為你不能在不穿越墻角的情況下直接到達那個格子。你的確需要先往下走然后到達那一格，按部就班的走過那個拐角。(注解：穿越拐角的規(guī)則是可選的。它取決于你的節(jié)點是如何放置的。)
這樣一來，就剩下了其他5格。當前格下面的另外兩個格子目前不在開啟列表中，于是我們添加他們，并且把當前格指定為他們的父節(jié)點。其余3格，兩個已經(jīng)在開啟列表中（起始格，和當前格上方的格子，在表格中藍色高亮顯示),于是我們略過它們。最后一格，在當前格的左側(cè)，將被檢查通過這條路徑，G值是否更低。不必擔心，我們已經(jīng)準備好檢查開啟列表中的下一格了。
我們重復(fù)這個過程，知道目標格被添加進開啟列表，就如在下面的圖中所看到的。
[圖6]
注意，起始格下方格子的父節(jié)點已經(jīng)和前面不同的。之前它的G值是28，并且指向右上方的格子?，F(xiàn)在它的G值是20，指向它上方的格子。這在尋路過程中的某處發(fā)生，當應(yīng)用新路徑時，G值經(jīng)過檢查變得低了－于是父節(jié)點被重新指定，G和F值被重新計算。盡管這一變化在這個例子中并不重要，在很多場合，這種變化會導(dǎo)致尋路結(jié)果的巨大變化。
那么，我們怎么確定這條路徑呢？很簡單，從紅色的目標格開始，按箭頭的方向朝父節(jié)點移動。這最終會引導(dǎo)你回到起始格，這就是你的路徑！看起來應(yīng)該像圖中那樣。從起始格A移動到目標格B只是簡單的從每個格子（節(jié)點）的中點沿路徑移動到下一個，直到你到達目標點。就這么簡單。
[圖7]
A*方法總結(jié)
1，把起始格添加到開啟列表。
2，重復(fù)如下的工作：
a) 尋找開啟列表中F值最低的格子。我們稱它為當前格。
b) 把它切換到關(guān)閉列表。
c) 對相鄰的8格中的每一個？
* 如果它不可通過或者已經(jīng)在關(guān)閉列表中，略過它。反之如下。
* 如果它不在開啟列表中，把它添加進去。把當前格作為這一格的父節(jié)點。記錄這一格的F,G,和H值。
*如果它已經(jīng)在開啟列表中，用G值為參考檢查新的路徑是否更好。更低的G值意味著更好的路徑。如果是這樣，就把這一格的父節(jié)點改成當前格，并且重新計算這一格的G和F值。如果你保持你的開啟列表按F值排序，改變之后你可能需要重新對開啟列表排序。
d) 停止，當你
* 把目標格添加進了開啟列表，這時候路徑被找到，或者
* 沒有找到目標格，開啟列表已經(jīng)空了。這時候，路徑不存在。
3.保存路徑。從目標格開始，沿著每一格的父節(jié)點移動直到回到起始格。這就是你的路徑。
