作者：銳亞教育（www.insideria.cn）
本文為銳亞教育原創文章，轉載請注明轉載自銳亞教育
A*尋路
A*算法基本原理
A*(念作A星)算法對初學者來說的确有些難度。本文并不試圖對這個話題作權威性的陳述，取而代之的是描述算法的原理，使你可以在進一步的閱讀中了解其他相關的資料。下面我們就利用圖文并茂的方式向大家展示它的基本原理。
簡化搜尋區域
如圖1所示，假設有人想從A點移動到一牆之隔的B點，如下圖，綠色的是起點A，紅色是終點B，藍色方塊是中間的牆。
圖1
首先注意到，搜尋區域被我們劃分成了方形網格。像這樣，簡化搜尋區域，是尋路的第一步。這一方法把搜尋區域簡化成了一個二維數組。數組的每一個元素是網格的一個方塊，方塊被标記為可通過和不可通過兩種。路徑被描述為從A到B我們經過的方塊的集合。一旦路徑被找到，我們的人就從一個方格的中心走向另一個，直到到達目的地。
這些中間點被稱為“節點”。當你閱讀其他的尋路資料時，你将經常會看到人們讨論節點。為什麼不把他們描述為方格呢？因為有可能你的路徑被分割成其他不是方格的結構。他們完全可以是矩形，六角形，或者其他任意形狀。節點能夠被放置在形狀的任意位置，可以在中心，也可以沿着邊界，又或者在其他任何地方。我們使用這種系統，歸根結底是由于它最簡單。
開始搜尋
正如我們處理圖1中網格的方法，一旦搜尋區域被轉化為容易處理的節點，下一步就是去引導一次找到最短路徑的搜尋。在A*尋路算法中，我們通過從點A開始，檢查相鄰方格的方式，向外擴充直到找到目标。
我們做如下操作開始搜尋：
從點A開始，并且把它作為待處理點存入一個“開啟清單”。開啟清單就像一張購物清單。盡管現在清單裡隻有一個元素，但以後就會多起來。你的路徑可能會通過它包含的方格，也可能不會。基本上，這是一個待檢查方格的清單。
尋找起點周圍所有可到達或者可通過的方格，跳過有牆，水，或其他無法通過地形的方格。也把他們加入開啟清單。為所有這些方格儲存點A作為“父方格”。當我們想描述路徑的時候，父方格的資料是十分重要的。後面會解釋它的具體用途。
從開啟清單中删除點A，把它加入到一個“關閉清單”，清單中儲存所有不需要再次檢查的方格。
在這一步驟中，會形成如圖2所示的結構。在圖2中，暗綠色方格是你起始方格的中心。它被用淺藍色描邊，以表示它被加入到關閉清單中了。所有的相鄰格現在都在開啟清單中，它們被用淺綠色描邊。每個方格都有一個灰色指針反指他們的父方格，也就是開始的方格。
圖2
接着，我們選擇開啟清單中的臨近方格，大緻重複前面的過程，示範如下步驟所示。但是，哪個方格是我們要選擇的呢？我們會選取F值最低方格作為下一次的起點。
路徑評分
選擇路徑中經過哪個方格的關鍵是下面這個等式：
F = G + H
G = 從起點A，沿着産生的路徑，移動到網格上指定方格的移動耗費。
H = 從指定方格移動到終點B的預估移動耗費。這經常被稱為啟發式的，可能會讓你有點迷惑。這樣叫的原因是因為它隻是個猜測。我們沒辦法事先知道路徑的長度，因為路上可能存在各種障礙(牆，水，等等)。雖然本文隻提供了一種計算H的方法，但是你可以在網上找到很多其他的方法。
我們的路徑是通過反複周遊開啟清單并且選擇具有最低F值的方格來生成的。本文将對這個過程做更詳細的描述。首先，我們需要深入的學習如何計算這個公式。
正如上面所說，G表示沿路徑從起點到目前點的移動耗費。在這個例子裡，我們令水準或者垂直移動的耗費為10，對角線方向耗費為14。我們取這些值是因為沿對角線的距離是沿水準或垂直移動耗費的的根号2，或者約1.414倍。為了簡化，我們用10和14近似。比例基本正确，同時我們避免了求根運算和小數。這不是隻因為我們怕麻煩或者不喜歡數學而是使用這樣的整數對計算機來說也更快捷。之後就會發現，如果不使用這些簡化方法，尋路會變得很慢。
既然我們在計算沿特定路徑通往某個方格的G值，求值的方法就是取它父節點的G值，然後依照它相對父節點是對角線方向或者直角方向(非對角線)，分别增加14和10。例子中這個方法的需求會變得更多，因為我們從起點方格以外擷取了不止一個方格。
H值可以用不同的方法估算。我們這裡使用的方法被稱為曼哈頓方法，它計算從目前格到目的格之間水準和垂直的方格的數量總和，忽略對角線方向，然後把結果乘以10，這被稱為曼哈頓方法。因為它看起來像計算城市中從一個地方到另外一個地方的街區數，在那裡你不能沿對角線方向穿過街區。很重要的一點，我們忽略了一切障礙物。這是對剩餘距離的一個估算，而非實際值，這也是這一方法被稱為啟發式的原因。
F的值是G和H的和。第一步搜尋的結果可以在下面的圖3中看到。F,G和H的評分被寫在每個方格裡。正如在緊挨起始格右側的方格所表示的，F被列印在左上角，G在左下角，H則在右下角。
圖3
現在我們來看看這些方格。寫字母的方格裡，G = 10。這是因為它隻在水準方向偏離起始格一個格距。緊鄰起始格的上方，下方和左邊的方格的G值都等于10。對角線方向的G值是14。
H值通過求解到紅色目标格的曼哈頓距離得到，其中隻在水準和垂直方向移動，并且忽略中間的牆。用這種方法，起點右側緊鄰的方格離紅色方格有3格距離，H值就是30。這塊方格上方的方格有4格距離(記住，隻能在水準和垂直方向移動)，H值是40。
每個格子的F值，還是簡單的由G和H相加得到。
繼續搜尋
為了繼續搜尋，我們簡單的從開啟清單中選擇F值最低的方格。然後，對選中的方格做如下處理：
1. 把它從開啟清單中删除，然後添加到關閉清單中。
- 檢查所有相鄰格子。跳過那些已經在關閉清單中的或者不可通過的(有牆，水的地形，或者其他無法通過的地形)，把他們添加到開啟清單中，如果他們還不在裡面的話，把選中的方格作為新的方格的父節點。
-
如果某個相鄰格已經在開啟清單裡了，檢查現在的這條路徑是否更好。換句話說，檢查如果我們用新的路徑到達它的話，G值是否會更低一些。如果不是，那就什麼都不做。
另一方面，如果新的G值更低，那就把相鄰方格的父節點改為目前選中的方格（在上面的圖表中，把箭頭的方向改為指向這個方格）。最後，重新計算F和G的值。如果這看起來不夠清晰，你可以看下面的圖示。
好了，讓我們看看它是怎麼運作的。我們最初的9格方格中，在起點被切換到關閉清單中後，還剩8格留在開啟清單中。這裡面，F值最低的那個是起始格右側緊鄰的格子，它的F值是40。是以我們選擇這一格作為下一個要處理的方格。在圖4中，它被用藍色邊框突出顯示。
圖4
首先，我們把它從開啟清單中取出，放入關閉清單(這就是他被藍色邊框突出顯示的原因)。然後我們檢查相鄰的格子。右側的格子是牆，是以我們略過。左側的格子是起始格。它在關閉清單裡，是以我們也跳過它。
其他4格已經在開啟清單裡了，于是我們通過檢查G值來判定，通過這一格到達那裡，路徑是否更好。我們來看選中格子下面的方格。它的G值是14。如果我們從目前格移動到那裡，G值就會等于20(到達目前格的G值是10，移動到上面的格子将使得G值增加10)。因為G值20大于14，是以這不是更好的路徑。如果你看圖，就能了解。與其通過先水準移動一格，再垂直移動一格，還不如直接沿對角線方向移動一格來得簡單。
當我們對已經存在于開啟清單中的4個臨近格重複這一過程的時候，我們發現沒有一條路徑可以通過使用目前格子得到改善，是以我們不做任何改變。既然我們已經檢查過了所有鄰近格，那麼就可以移動到下一格了。
于是我們檢索開啟清單，現在裡面隻有7格了，我們仍然選擇其中F值最低的。有趣的是，這次，有兩個格子的數值都是54。我們如何選擇？這并不麻煩，從速度上考慮，選擇最後添加進清單的格子會更快捷。這種導緻了尋路過程中，在靠近目标的時候，優先使用新找到的格子的偏好。
那我們就選擇起始格右下方的格子，如圖5所示。
a *算法
圖5
這次，當我們檢查相鄰格的時候，發現右側是牆，于是略過。上面一格也被略過。我們也略過了牆下面的格子。為什麼呢？因為你不能在不穿越牆角的情況下直接到達那個格子。你的确需要先往下走然後到達那一格，按部就班的走過那個拐角。(穿越拐角的規則是可選的。它取決于你的節點是如何放置的。)
這樣一來，就剩下了其他5格。目前格下面的另外兩個格子目前不在開啟清單中，于是我們添加他們，并且把目前格指定為他們的父節點。其餘3格，兩個已經在關閉清單中（起始格，和目前格上方的格子，在表格中藍色高亮顯示),于是我們略過它們。最後一格，在目前格的左側，将被檢查通過這條路徑，G值是否更低。不必擔心，我們已經準備好檢查開啟清單中的下一格了。
我們重複這個過程，直到目标格被添加進關閉清單，如圖6所示。
a *算法
圖6
注意，起始格下方格子的父節點已經和前面不同的。之前它的G值是28，并且指向右上方的格子。現在它的G值是20，指向它上方的格子。這在尋路過程中的某處發生，當應用新路徑時，G值經過檢查變得低了，于是父節點被重新指定，G和F值被重新計算。盡管這一變化在這個例子中并不重要，在很多場合，這種變化會導緻尋路結果的巨大變化。
那麼，我們怎麼确定這條路徑呢？很簡單，從紅色的目标格開始，按箭頭的方向朝父節點移動。這最終會引導你回到起始格，這就是你的路徑！看起來應該像圖中那樣。從起始格A移動到目标格B隻是簡單的從每個格子（節點）的中點沿路徑移動到下一個，直到你到達目标點。就這麼簡單。
a *算法
圖7
A*算法總結
學完了整個尋路過程之後，現在我們把每一步的操作整理如下：
1. 把起始格添加到開啟清單。
2. 重複如下的工作：
a) 尋找開啟清單中F值最低的格子。我們稱它為目前格。
b) 把它切換到關閉清單。
c) 對相鄰的8格中的每一個格進行如下判斷：
如果它不可通過或者已經在關閉清單中，略過它。反之如下。
如果它不在開啟清單中，把它添加進去。把目前格作為這一格的父節點。記錄這一格的F,G,和H值。
如果它已經在開啟清單中，用G值為參考檢查新的路徑是否更好。更低的G值意味着更好的路徑。如果是這樣，就把這一格的父節點改成目前格，并且重新計算這一格的G和F值。如果你保持你的開啟清單按F值排序，改變之後你可能需要重新對開啟清單排序。
d) 停止，當你把目标格添加進了關閉清單(注解)，這時候路徑被找到，或者沒有找到目标格，開啟清單已經空了。這時候，路徑不存在。
3. 儲存路徑。從目标格開始，沿着每一格的父節點移動直到回到起始格。這就是你的路徑。