A*算法原理圖文詳解
首先了解一下A*算法的基本設計思想，以下是援引百度百科的解釋： IT學習者（www.itxxz.com）
（A-Star)算法是一種靜态路網中求解最短路最有效的直接搜尋方法。
注意是最有效的直接搜尋算法。之後湧現了很多預處理算法（ALT，CH，HL等等），線上查詢效率是A*算法的數千甚至上萬倍。
公式表示為： f(n)=g(n)+h(n),
其中 f(n) 是從初始點經由節點n到目标點的估價函數，
g(n) 是在狀态空間中從初始節點到n節點的實際代價，
h(n) 是從n到目标節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在于估價函數h(n)的選取：
估價值h(n)<= n到目标節點的距離實際值，這種情況下，搜尋的點數多，搜尋範圍大，效率低。但能得到最優解。并且如果h(n)=d(n)，即距離估計h(n)等于最短距離，那麼搜尋将嚴格沿着最短路徑進行， 此時的搜尋效率是最高的。
官網：http://www.itxxz.com
然後我們通過圖文結合的形式來解釋下，如下圖：
圖中有這麼幾個要點先需要了解：
1、類似迷宮圖，分開始節點(start)、障礙物、結束節點(end)，我們需要從start節點探尋一條到end節點的路線
2、對于探尋的每一步，都會以目前節點為基點，掃描其相鄰的八個節點 内容來自www.itxxz.com
3、計算目前節點與start節點及到end的距離
4、計算出最短路徑
如果明白了上面的場景描述，下面就可以進行分析了。
在A*算法中，核心思想是一個公式，上面已經提到過：f(n)=g(n)+h(n)
僅通過文字可能有些朋友不是很了解，下面我們就舉例說明：
以start節點為例，探尋相鄰的八個節點，且隻能上下左右移動，每移動到鄰近的單元格，我們認為行走了一個距離。
比如從start移動到A節點，就移動了兩個距離，從A節點移動到end節點(此時忽略障礙，僅計算距離)。
這時公式中的g(n)就可以了解為g(A)=2，h(n)就了解為h(A)=6,
内容來自www.itxxz.com
f(n)就是start節點到end節點的實際距離，公式描述為：f(A)=g(A)+h(A)=8。
于是就有了A節點的數字描述——f(n)位于左上方，g(n)位于左下方，h(n)位于右下方。
同理，可計算出f(B) = g(B) + h(B) = 1 + 5 = 6
這時start相鄰的其它節點變都可以計算出來了
現在理念明白了，該如何實作呢？
可以通過對相鄰節點的便利及父節點的不斷嵌套來形成一條路徑。
比如我們把start相鄰的所有節點進行便利比較，選出f(n)最小的一個節點(我們稱為X節點)，并設定X節點的父節點為start節點，并以X節點為目前節點，再判斷X節點周圍的有效節點(如障礙物完全可以忽略)，選出f(n)最小的節點後設定X節點為其父節點，依次類推，就形成了一條節點線，這個算法也就完成了。
了解A*尋路算法具體過程 當然尋路算法不止 A* 這一種, 還有遞歸, 非遞歸, 廣度優先, 深度優先, 使用堆棧等等, 有興趣的可以研究研究~~
簡易地圖
如圖所示簡易地圖, 其中綠色方塊的是起點 (用 A 表示), 中間藍色的是障礙物, 紅色的方塊 (用 B 表示) 是目的地. 為了可以用一個二維數組來表示地圖, 我們将地圖劃分成一個個的小方塊.
二維數組在遊戲中的應用是很多的, 比如貪吃蛇和俄羅斯方塊基本原理就是移動方塊而已. 而大型遊戲的地圖, 則是将各種"地貌"鋪在這樣的小方塊上.
尋路步驟
1. 從起點A開始, 把它作為待處理的方格存入一個"開啟清單", 開啟清單就是一個等待檢查方格的清單.
2. 尋找起點A周圍可以到達的方格, 将它們放入"開啟清單", 并設定它們的"父方格"為A.
3. 從"開啟清單"中删除起點 A, 并将起點 A 加入"關閉清單", "關閉清單"中存放的都是不需要再次檢查的方格
圖中淺綠色描邊的方塊表示已經加入 "開啟清單" 等待檢查. 淡藍色描邊的起點 A 表示已經放入 "關閉清單" , 它不需要再執行檢查.
從 "開啟清單" 中找出相對最靠譜的方塊, 什麼是最靠譜? 它們通過公式 F=G+H 來計算.
F = G + H
G 表示從起點 A 移動到網格上指定方格的移動耗費 (可沿斜方向移動).
H 表示從指定的方格移動到終點 B 的預計耗費 (H 有很多計算方法, 這裡我們設定隻可以上下左右移動).
我們假設橫向移動一個格子的耗費為10, 為了便于計算, 沿斜方向移動一個格子耗費是14. 為了更直覺的展示如何運算 FGH, 圖中方塊的左上角數字表示 F, 左下角表示 G, 右下角表示 H. 看看是否跟你心裡想的結果一樣?
從 "開啟清單" 中選擇 F 值最低的方格 C (綠色起始方塊 A 右邊的方塊), 然後對它進行如下處理:
4. 把它從 "開啟清單" 中删除, 并放到 "關閉清單" 中.
5. 檢查它所有相鄰并且可以到達 (障礙物和 "關閉清單" 的方格都不考慮) 的方格. 如果這些方格還不在 "開啟清單" 裡的話, 将它們加入 "開啟清單", 計算這些方格的 G, H 和 F 值各是多少, 并設定它們的 "父方格" 為 C.
6. 如果某個相鄰方格 D 已經在 "開啟清單" 裡了, 檢查如果用新的路徑 (就是經過C 的路徑) 到達它的話, G值是否會更低一些, 如果新的G值更低, 那就把它的 "父方格" 改為目前選中的方格 C, 然後重新計算它的 F 值和 G 值 (H 值不需要重新計算, 因為對于每個方塊, H 值是不變的). 如果新的 G 值比較高, 就說明經過 C 再到達 D 不是一個明智的選擇, 因為它需要更遠的路, 這時我們什麼也不做.
如圖, 我們選中了 C 因為它的 F 值最小, 我們把它從 "開啟清單" 中删除, 并把它加入 "關閉清單". 它右邊上下三個都是牆, 是以不考慮它們. 它左邊是起始方塊, 已經加入到 "關閉清單" 了, 也不考慮. 是以它周圍的候選方塊就隻剩下 4 個. 讓我們來看看 C 下面的那個格子, 它目前的 G 是14, 如果通過 C 到達它的話, G将會是 10 + 10, 這比 14 要大, 是以我們什麼也不做.
然後我們繼續從 "開啟清單" 中找出 F 值最小的, 但我們發現 C 上面的和下面的同時為 54, 這時怎麼辦呢? 這時随便取哪一個都行, 比如我們選擇了 C 下面的那個方塊 D.
D 右邊已經右上方的都是牆, 是以不考慮, 但為什麼右下角的沒有被加進 "開啟清單" 呢? 因為如果 C 下面的那塊也不可以走, 想要到達 C 右下角的方塊就需要從 "方塊的角" 走了, 在程式中設定是否允許這樣走. (圖中的示例不允許這樣走)
就這樣, 我們從 "開啟清單" 找出 F 值最小的, 将它從 "開啟清單" 中移掉, 添加到 "關閉清單". 再繼續找出它周圍可以到達的方塊, 如此循環下去...
那麼什麼時候停止呢? —— 當我們發現 "開始清單" 裡出現了目标終點方塊的時候, 說明路徑已經被找到.
如何找回路徑
如上圖所示, 除了起始方塊, 每一個曾經或者現在還在 "開啟清單" 裡的方塊, 它都有一個 "父方塊", 通過 "父方塊" 可以索引到最初的 "起始方塊", 這就是路徑.
将整個過程抽象
把起始格添加到 "開啟清單"
do
{
尋找開啟清單中F值最低的格子, 我們稱它為目前格.
把它切換到關閉清單.
對目前格相鄰的8格中的每一個
if (它不可通過 || 已經在 "關閉清單" 中)
{
什麼也不做.
}
if (它不在開啟清單中)
{
把它添加進 "開啟清單", 把目前格作為這一格的父節點, 計算這一格的 FGH
if (它已經在開啟清單中)
{
if (用G值為參考檢查新的路徑是否更好, 更低的G值意味着更好的路徑)
{
把這一格的父節點改成目前格, 并且重新計算這一格的 GF 值.
}
} while( 目标格已經在 "開啟清單", 這時候路徑被找到)
如果開啟清單已經空了, 說明路徑不存在.
最後從目标格開始, 沿着每一格的父節點移動直到回到起始格, 這就是路徑.
主要代碼
程式中的 "開啟清單" 和 "關閉清單"
| 1 | |
Point 類
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |
尋路過程
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | |
下載下傳代碼
本文連結: http://www.cnblogs.com/technology/archive/2011/05/26/2058842.html