關于尋路算法的一些思考（1）：A* 算法介紹

物體的移動算法似乎顯得很簡單，然而尋路規劃問題卻十分複雜。考慮下面這個例子：

這個機關的初始位置在地圖的下方，想要到達地圖的頂部。如果物體所能偵測到的地方（粉色部分所示）并沒有障礙，那麼物體就會直接向上走到它的目标位置。但在距離頂端較近的位置時，物體偵測到了障礙，因而改變了方向。該物體将不得不行進一個“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)值的節點。

之後的系列文章将主要探讨啟發值設計、具體實作、地圖表示等，并讨論與遊戲中尋路問題相關的一系列話題。

英文：Amit’s Thoughts on Pathfinding

譯者：伯樂線上 - Lunamos 

連結：http://blog.jobbole.com/71044/