關于尋路算法的一些思考（1）：A*算法介紹
英文原文： Amit’s Thoughts on Pathfinding
物體的移動算法似乎顯得很簡單，然而尋路規劃問題卻十分復雜。考慮下面這個例子：
這個單位的初始位置在地圖的下方，想要到達地圖的頂部。如果物體所能偵測到的地方（粉色部分所示）并沒有障礙，那么物體就會直接向上走到它的目 標位置。但在距離頂端較近的位置時，物體偵測到了障礙，因而改變了方向。該物體將不得不行進一個“U”形的路徑繞過障礙物（如紅色路徑所示）。通過對比可 知，尋路系統能夠通過搜索一個更大的范圍（如藍色區域所示），并尋找一個更短的路線（如藍色路徑所示），使物體避免繞這條由凹陷障礙物造成的遠路。
當然，可以通過改進物體的移動算法解決上圖所示的陷阱。即要么避免在地圖上創建有凹陷的物體，要么標記整個凹陷物體的整個凸包為危險區域（即除非目標在該區域內，否則避免進入該區域），如下圖所示：
而尋路系統則會讓路徑的決定提前，而不是像上圖一樣，物體直到移動到最后一刻才發現問題所在。對于“改進物體移動算法”和“使用尋路系統規劃路 徑”兩種方式有以下的折中：規劃路徑一般來說更慢，但效果更好；改進移動算法則會快一些，但有時候會卡住。如果游戲地圖經常改變，那么路徑規劃的方式可能 就意義不大了。我建議兩者都使用：在更大的尺度、緩慢變換的地圖和更長的路徑上進行尋路規劃，而對于局部區域、快速更改的地圖和短的路徑則使用改進的物體 移動算法。
算法
普通教科書上的尋路算法往往只應用在數學意義上的“圖”上，即由頂點集合和邊集合互相連接組成的結構。因此我們需要將一個柵格化的游戲地圖轉化為一個“圖”：地圖上的每一格可以作為一個頂點，而相鄰的格子則各有一條邊，如圖所示：
我們只考慮二維網格。如果你沒有關于圖的背景知識，可以參見此鏈接。之后我會討論如何在游戲世界中創建其他類型的圖。
大部分在 AI 和算法領域的尋路算法都是針對作為數學結構的“圖”本身，而并非針對這種網格化游戲地圖。我們希望尋找一種能利用游戲地圖自身特征的方法。其實有些在二維 網格圖中我們認為是常識的事情，一些在普通圖上使用的尋路算法本身可能并沒有考慮到，例如如果兩個物體距離較遠，那么可能從一個物體到另一個物體的移動的 時間和路徑會較長（當然，假設空間中沒有蟲洞存在）。對于方向來說，如果方向是朝東，那么最優路徑的路徑也應當是大體往東走，而不是向西去。在網格中還可 以從對稱中獲取信息，即先向北再向西，大部分情況下和先向西再向北等價。這些額外的信息可以讓尋路算法更加快速。
Dijkstra 算法和最好優先搜索(best-first search)
Dijkstra 算法簡單說來，就是從起始點訪問其他臨近節點，并將該節點加入待檢查節點集合中，使用松弛算法更新待檢查節點的路徑長度值。只要圖不存在負權值的 邊，Dijkstra 算法能夠確保找到最短路徑。在下面的圖中，粉色的方格為起始點，藍紫色的方格為目標點，青綠色的方格則為 Dijkstra 算法所掃描的節點。淡色的節點是距離起始點較遠的節點。
貪心最好優先搜索算法大體與之類似，不同的是該算法對目標點的距離有一個估計值（啟發值）。該算法并不在待檢查節點集合中選取距離起始點近的節 點進行下一步的計算，而是選擇距離目標點近的節點。貪心最好優先搜索算法并不能保證尋找到最優路徑，然而卻能大大提高尋路速度，因為它使用了啟發式方法引 導了路徑的走向。舉例來說，如果目標節點在起始點的南方，那么貪心最好優先搜索算法會將注意力集中在向南的路徑上。下圖中的黃色節點指示了具有高啟發值的 節點（即到目標節點可能花費較大的節點），而黑色則是低啟發值的節點（即到目標節點的花費較小的節點）。下圖說明了相比于 Dijkstra 算法，貪心最好優先算法能夠更加快速地尋路。
然而上述的例子僅僅是最簡單的：即地圖上沒有障礙物。考慮前文中我們曾經提到的凹陷障礙物，Dijkstra 算法仍然能夠尋找到最短路徑：
貪心最好優先算法雖然做了較少的計算，但卻并不能找到一條較好的路徑。
問題在于最好優先搜索算法的貪心屬性。由于算法僅僅考慮從目前節點到最終節點的花費，而忽略之前路徑已經進行的耗費，因此即使在路徑可能錯誤的情況下仍然要移動物體。
1968 年提出的A*算法結合了貪心最好優先搜索算法和 Dijsktra 算法的優點。A*算法不僅擁有發式算法的快速，同時，A*算法建立在啟發式之上，能夠保證在啟發值無法保證最優的情況下，生成確定的最短路徑。
A*算法
下面我們主要討論A*算法。A*是目前最流行的尋路算法，因為它十分靈活，能夠被應用于各種需要尋路的場景中。
與 Dijkstra 算法相似的是，A*算法也能保證找到最短路徑。同時A*算法也像貪心最好優先搜索算法一樣，使用一種啟發值對算法進行引導。在剛才的簡單尋路問題中，它能夠像貪心最好優先搜索算法一樣快：
而在后面的具有凹陷障礙物的地圖中，A*算法也能夠找到與 Dijkstra 算法所找到的相同的最短路徑。
該算法的秘訣在于，它結合了 Dijkstra 算法使用的節點信息（傾向于距離起點較近的節點），以及貪心最好優先搜索算法的信息（傾向于距離目標較近的節點）。之后在討論A*算法時，我們使用 g(n)表示從起點到任意節點n的路徑花費，h(n)表示從節點n到目標節點路徑花費的估計值（啟發值）。在上面的圖中，黃色體現了節點距離目標較遠，而 青色體現了節點距離起點較遠。A*算法在物體移動的同時平衡這兩者的值。定義f(n)=g(n) +h(n)，A*算法將每次檢測具有最小f(n)值的節點。
之后的系列文章將主要探討啟發值設計、具體實現、地圖表示等，并討論與游戲中尋路問題相關的一系列話題。
譯文鏈接： http://blog.jobbole.com/71044/