注意
本文轉(zhuǎn)載并翻譯自
網(wǎng)站 Red Blob Games
文章 Introduction to the A* Algorithm
如有侵權(quán), 請聯(lián)系刪除弹囚。
正文
在游戲中我們常會需要找出從一個點到另一個點的路徑肥印。我們不僅需要找出最短路, 有的時候也需要考慮經(jīng)過這條路徑所花費的時間葵诈。
當(dāng)?shù)貓D使用圖來表示的時候脓钾，我們可以使用一種基于圖論的搜索算法來找出我們想要的路徑。A*算法是一種比較受歡迎的圖搜索算法浙宜。但是讓我們先從最簡單的圖搜索算法-廣度優(yōu)先搜索來一步一步探索并接近A*褐鸥。
地圖表示
學(xué)習(xí)一種算法的第一步通常是先理解[數(shù)據(jù)]蝶棋，輸入數(shù)據(jù)是什么？輸出數(shù)據(jù)是什么塑荒？
[輸入數(shù)據(jù)]:
像A*這樣的圖形算法通常會使用"圖"做為輸入, 一個"圖"由"點"和"邊"的集合組成熄赡。
下面是我給A*輸入的一個"圖"的示例:
A*除了輸入給它的"圖"以外不會關(guān)心其他任何數(shù)據(jù)。它并不會知道什么東西在里面或者外面齿税，不會知道這個點是個通道還是個房間, 也不會知道這塊區(qū)域到底有多大, 它只關(guān)心輸入給它的"圖"(點集與邊集之間的關(guān)系)彼硫！
對于它來說，下面這幅地圖和上面那副根本沒什么兩樣凌箕。
[輸出數(shù)據(jù)]:
A*算法所找出的路徑是由點集和邊集組成的拧篮。這里的"邊"是一種抽象的數(shù)學(xué)概念。A*會告訴你需要從一個點移動到另外一個點但是不會告訴你如何移動過去牵舱。記住, 它除了點集與邊集之間的關(guān)系組成的"圖"之外并不知道其他額外的信息, 比如這里是個通道還是個門串绩。你將會需要自己決定A*算法交給你的這條邊是一格一格地移動、走一條直線芜壁、打開一扇門礁凡、游過去亦或是沿著一條曲線移動過去。
[權(quán)衡]:
對于任何一副給出的游戲地圖來說, 有很多種方式去劃分出一份交給A*算法的"圖"慧妄。
最開始我們給出的示例"圖"將許多"點"表示為通道:
那如果我們將通道放在"邊"上表示會是如何呢?
又或者我們使用尋路網(wǎng)格來表示呢?
用于輸入給尋路算法的"圖"不需要與你使用的游戲地圖保持一致顷牌。一個由格子組成的游戲地圖可以使用并不是由格子組成的尋路“圖”， 反之亦然塞淹。對于A*算法來說韧掩，點集中的點越少，運算的速度就越快窖铡。通常疗锐，使用網(wǎng)格來劃分地圖會變得比較容易處理，但是與此同時也會導(dǎo)致點集中的節(jié)點數(shù)量過多费彼。這篇文章只探究A*算法本身而非“圖”劃分的設(shè)計滑臊，如果你想了解更多關(guān)于“圖”設(shè)計的內(nèi)容，可以閱讀我的其他文章箍铲。對于本文章的后文雇卷，若沒有特殊說明，我將默認(rèn)使用格子去劃分地圖以便于將相關(guān)概念以更加直觀的方式表現(xiàn)出來。
算法
基于圖論的算法有很多关划，我將重點探究以下幾種：
廣度優(yōu)先搜索算法對于所有的方向都進(jìn)行等價搜索小染，這是一種不僅對于常規(guī)尋路, 同時也對隨機(jī)地圖生成(procedural map generation)、流場尋路(flow field pathfinding)贮折、距離圖(distance maps)還有其他類型的地圖分析等都非常有效的算法裤翩。
Dijkstra算法(也叫做一致代價搜索UCS)讓我們對于那些路徑需要優(yōu)先搜索給出優(yōu)先級而不是等價地探索所有可能的路徑，在探索過程中调榄，Dijkstra算法更偏愛于代價更低的路徑踊赠。我們可以通過給一些路徑設(shè)置較低的代價(消耗)來是的算法搜索過程中優(yōu)先考慮使用這條路徑，或者是設(shè)置較高的代價(消耗)使得算法盡量避免通過一些類似于叢林每庆、敵人之類的地方筐带。當(dāng)?shù)貓D上的路徑行動消耗不同時, 我們通常會使用Dijkstra算法而非廣度優(yōu)先搜索算法。
A*算法是Dijkstra算法對一個單獨目的地的情況做出針對性優(yōu)化的一個改版缤灵。Dijkstra算法可以找出一個點到“圖”上所有點的路徑伦籍。A*算法只找出一個點到一個特定目的地的所有路徑，或者是到一些點的最短路徑腮出。它會給通往一個目標(biāo)哦的那些看起來更近的路徑排出先后順序鸽斟。
我將會從最簡單的廣度優(yōu)先搜索算法開始，然后逐步添加特性來讓它一步步轉(zhuǎn)變?yōu)锳*算法利诺。
廣度優(yōu)先算法
所有這些算法的中心思想是富蓄，我們跟蹤一個不斷膨脹的、叫做“邊界”的環(huán)慢逾，在網(wǎng)格中立倍，這個過程有時被稱為“洪水式填充”，不過這個技術(shù)同樣也適用于非網(wǎng)格的“圖”侣滩。
我們要怎么樣實現(xiàn)這樣的過程口注？重復(fù)以下過程直至取到的“邊界”為空：
- 在邊界上選擇并移除一個點
- 通過查找周圍的節(jié)點進(jìn)行擴(kuò)展：如果是墻， 則跳過君珠；否則寝志，如果是沒有到達(dá)過的節(jié)點，那么都加入到環(huán)中策添，到達(dá)過的節(jié)點材部，從環(huán)中移除并記錄為已到達(dá)。
演示圖如下唯竹，其中帶數(shù)字的格子表示當(dāng)前演示步驟乐导。
以上步驟的實現(xiàn)只有10行（Python）：
frontier = Queue()
# start指圖中星星所在的起始點
frontier.put(start)
reached = set()
reached.add(start)
while not frontier.empty():
current = frontier.get()
for next in graph.neighbors(current):
if next not in reached:
frontier.put(next)
reached.add(next)
這個循環(huán)是這片文章內(nèi)包括A*在內(nèi)的圖搜索算法的本質(zhì)。但是浸颓，我們要如何才能找到最短路徑呢物臂？這個循環(huán)實際上并沒有在構(gòu)建任何路徑旺拉，它只是告訴我們?nèi)绾稳ケ闅v這張“圖”上的所有節(jié)點。這是因為棵磷，廣度優(yōu)先搜索算法的用途不僅僅是在尋路上蛾狗，在這篇文章中，我演示了這個算法如何應(yīng)用在塔防游戲中仪媒，然而其實它也可以用在距離圖沉桌、生成隨機(jī)地圖和很多其他事情上。
不過這里我們還是想把它應(yīng)用在尋路上规丽，所以我們修改一下這個循環(huán)來使得我們可以追蹤我們是從哪個點去往每一個到達(dá)點的蒲牧，同時撇贺，我們將到達(dá)點集合reached改為一個記錄從哪個點來到當(dāng)前到達(dá)節(jié)點的表came_from（表的鍵為過程中所到達(dá)的點）：
frontier = Queue()
frontier.put(start)
came_from = dict()
came_from[start] = None
while not frontier.empty():
current = frontier.get()
for next in graph.neighbors(current):
if next not in came_from:
frontier.put(next)
came_from[next] = current
這樣處理完畢之后赌莺，得到的came_from表可以用來得到來到某個點之前的點，就像“面包屑”一樣散落在地圖上松嘶。這些信息已經(jīng)足夠讓我們用來構(gòu)建出一整條路徑了艘狭。
用于重建出路徑的代碼就很簡單了：從終點一路跟隨
came_from中所指向的“前一個點”直到起點位置即可。一條路徑是一系列邊組成的序列翠订，但是通常情況下巢音，存儲節(jié)點來表示路徑會更加簡單：
# goal表示上圖叉所在的終點位置
current = goal
path = []
while current != start:
path.append(current)
current = came_from[current]
path.append(start) # optional
path.reverse() # optional
以上就是最簡單的一種尋路算法，它不僅僅對于上面展示的這種格子地圖有效尽超，對其他各種類型的“圖”結(jié)構(gòu)亦是如此官撼。在地牢中，圖上的點可以是各個房間似谁，圖上的邊可以是房間之間的通道傲绣；在一個平臺游戲中，圖上的點可以是每一個位置巩踏，而圖上的邊可以是各種類似于左移秃诵、右移、上跳塞琼、下跳等行為的可能性菠净，大體上說就是把圖想象成是各種狀態(tài)，然后各種行為會改變狀態(tài)彪杉。我在這里有寫更多關(guān)于地圖的表現(xiàn)相關(guān)的內(nèi)容毅往。在這篇文章剩余的部分，我還是會繼續(xù)使用格子來作為示例派近，然后去探索為什么我們可能會需要使用各種廣度優(yōu)先搜索算法的變體煞抬。
提前退出
我們已經(jīng)可以找到從一個點到其他所有點的路徑，通常來說构哺，我們并不需要所有的結(jié)果革答，而是只需要從一個點到另外一個點的一條具體路徑战坤，所以我們可以在找到終點的時候立即停止邊界的擴(kuò)張。
代碼也比較簡單：
frontier = Queue()
# start 起點
frontier.put(start)
came_from = dict()
came_from[start] = None
while not frontier.empty():
current = frontier.get()
# goal 終點
if current == goal:
break
for next in graph.neighbors(current):
if next not in came_from:
frontier.put(next)
came_from[next] = current
你可以通過提前退出條件做出很多有趣的事情残拐。
移動消耗
到目前為止途茫，我們在格子上移動的“消耗”都是相同的，然而在某些尋路場景中不同的移動方式所需要的消耗（代價）是不同的溪食。例如囊卜，在《文明》中，移動經(jīng)過平原或者沙漠將會消耗1個行動點错沃，但是移動經(jīng)過樹林或者山丘就得消耗5個行動點栅组。在這篇文章最初的那個地圖中，走過水地將會花上等價于10倍走過草地的時間枢析，再例如玉掸，某個地圖上的格子斜著走要比直著走消耗更大。我們一般會希望尋路算法在尋路過程中將這些消耗也考慮進(jìn)去醒叁。讓我們比較一下從起點到終點的[步數(shù)]與[距離]：
對于這種情況司浪，我們會希望使用Dijkstra算法（一致代價搜索UCS）。不過這個算法與廣度優(yōu)先搜索相比有什么不同之處呢把沼？
為了追蹤移動的消耗啊易，我們加入一個新的變量
cost_so_far來保持追蹤從起點開始的累計移動消耗。我們想要在評估一個點的時候把移動消耗也納入決策中饮睬。首先讓我們把代碼中的隊列轉(zhuǎn)換成一個優(yōu)先隊列租谈，不太明顯的一點是，我們可能會多次到達(dá)并訪問同一個點捆愁，但是消耗不同割去，所以我們需要稍微改動一點邏輯，如果訪問到了一個沒有到達(dá)過的點牙瓢，我們先不急著將它加入邊界中劫拗，而是在考量這條新路徑比之前所得的最優(yōu)路徑更好之后再把它加入邊界。
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
came_from[start] = None
cost_so_far[start] = 0
while not frontier.empty():
current = frontier.get()
if current == goal:
break
for next in graph.neighbors(current):
new_cost = cost_so_far[current] + graph.cost(current, next)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost
frontier.put(next, priority)
came_from[next] = current
使用優(yōu)先隊列而不是常規(guī)隊列改變了邊界擴(kuò)張的方式矾克。在運行過程中我們會發(fā)現(xiàn)使用Dijkstra算法邊界在擴(kuò)張時页慷，通過中間樹林地形的速度會更慢，并且嘗試在樹林的周圍去尋找最短路徑而不是穿過樹林：
非1的移動消耗讓我們除了格子之外還能探索更多有趣的圖形胁附。在文章開頭的地圖中酒繁，移動消耗是由房間與房間之間的距離來決定的。移動消耗也可以用來根據(jù)鄰近敵人或盟友來規(guī)避或偏好某些區(qū)域控妻。
實現(xiàn)說明：我們想要代碼中的優(yōu)先隊列優(yōu)先返回最小值州袒。在[代碼實現(xiàn)]系列文章中我展示了PriorityQueue在Python中使用heapq來優(yōu)先返回最小值。在C++實現(xiàn)部分中我通過配置std::priority_queue來優(yōu)先返回最小值弓候。同樣的郎哭，我在這篇文章中呈現(xiàn)的Dijkstra算法與A*算法實現(xiàn)有別于算法教材他匪，它們會更加接近于被叫做 一致代價搜索 的算法。我會在實現(xiàn)篇中描述這些區(qū)別夸研。
啟發(fā)式搜索
通過廣度優(yōu)先搜索算法和Dijkstra算法邦蜜，邊界可以向各個方向進(jìn)行擴(kuò)張，如果你想要找出一條通往所有點或者許多點的路徑的話亥至，這的確是一個合理的做法悼沈。不過，通常情況我們是需要尋找到某個特定點的路徑姐扮，不妨讓我們嘗試一下讓邊界相比于其他方向更多地朝著目標(biāo)點擴(kuò)張絮供。首先，我們需要定義一個 啟發(fā)函數(shù) heuristic 來告訴程序我們當(dāng)前距離目的地有多遠(yuǎn)：
def heuristic(a, b):
# 方形格子的曼哈頓距離
return abs(a.x - b.x) + abs(a.y - b.y)
在Dijkstra算法中我們使用從起點開始的實際距離來給優(yōu)先隊列排序茶敏，不過在 貪婪最佳優(yōu)先搜索 中壤靶，我們將會使用到終點的估計距離來進(jìn)行優(yōu)先隊列的排序，最靠近終點的點將會最先被探索睡榆。下面這段代碼沿用了Dijkstra算法的優(yōu)先隊列但是沒有使用cost_so_far字段萍肆。
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
came_from[start] = None
while not frontier.empty():
current = frontier.get()
if current == goal:
break
for next in graph.neighbors(current):
if next not in came_from:
priority = heuristic(goal, next)
frontier.put(next, priority)
came_from[next] = current
讓我們看看運行情況：
喔袍榆！是不是很神奇胀屿？如果換成一張更復(fù)雜的地圖會怎么樣呢？
貪婪最佳優(yōu)先搜索找出的路徑并不是最短路徑包雀，所以這個算法在地圖上沒有太多障礙物的時候運行的非乘拚福快。但是所得的路徑并不是很完美才写，我們還能更進(jìn)一步嗎葡兑？當(dāng)然可以！
A*算法
Dijkstra算法很善于找出最短路徑赞草，但是它在探索各個沒啥用的方向上浪費了太多時間了讹堤。貪婪最佳優(yōu)先搜索始終在嘗試探索最接近目標(biāo)的方向，但是它找到的卻不一定是最短路徑厨疙。A*算法在它的決策中同時考慮了距離起點的實際距離以及距離終點的預(yù)估距離洲守。
代碼方面和Dijkstra算法比較相像：
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
came_from[start] = None
cost_so_far[start] = 0
while not frontier.empty():
current = frontier.get()
if current == goal:
break
for next in graph.neighbors(current):
new_cost = cost_so_far[current] + graph.cost(current, next)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost + heuristic(goal, next)
frontier.put(next, priority)
came_from[next] = current
將幾種算法進(jìn)行比較：Dijkstra算法計算了從起點開始的距離；貪婪最佳優(yōu)先搜索預(yù)估了到終點的距離沾凄；而A*算法使用了兩者之和梗醇。
當(dāng)嘗試隨便在墻上開幾個洞的時候, 我們會發(fā)現(xiàn)如果貪婪最佳優(yōu)先搜索能夠找到最短路徑，那么A*算法可以在和貪婪最佳優(yōu)先搜索探索相同區(qū)域的情況下也找到最短路徑撒蟀。
但是當(dāng)貪婪最佳優(yōu)先搜索不能得到最短路徑的時候叙谨，A*算法卻依然可以做到在比Dijkstra算法探索更少區(qū)域的情況下找到和Dijkstra算法一樣的最短路徑。
A*算法是兩全其美的保屯，只要保證啟發(fā)函數(shù)在距離上不過度預(yù)估手负，A*算法就能像Dijsktra算法一樣找到一條最優(yōu)路徑涤垫。A*使用啟發(fā)函數(shù)去重排節(jié)點來讓目標(biāo)點盡可能快地被探索到。
嗯......這就完事了竟终！以上就是A*算法雹姊。
更多
你準(zhǔn)備好去實現(xiàn)這個算法了嗎?考慮去使用一個現(xiàn)成的庫吧。如果你正在自己實現(xiàn)這個算法衡楞，我在這份指南里展示了如何使用 Python/C++/C# 去一步一步實現(xiàn) 圖吱雏、隊列和尋路算法。
當(dāng)你想在游戲地圖中使用尋路的時候你應(yīng)該選擇哪個算法呢瘾境？
- 如果你想要尋找到所有點的路徑歧杏，就使用廣度優(yōu)先搜索或者Dijkstra算法：如果移動消耗都是等價的話就是用廣度優(yōu)先搜索，如果移動消耗各有不同迷守，那就使用Dijkstra算法犬绒。
- 如果你想尋找到某一個特定點的路徑，或者到某幾個點的最短路徑兑凿，那就使用貪婪最佳優(yōu)先搜索或者A*算法凯力，大部分情況下應(yīng)該優(yōu)先選擇A*，當(dāng)你想要使用貪婪最佳優(yōu)先搜索的時候礼华，可以考慮一下使用一個帶有“非常規(guī)”的啟發(fā)函數(shù)的A*算法咐鹤。
關(guān)于最優(yōu)路徑呢？廣度優(yōu)先搜索和Dijkstra算法保證可以找到給出的圖中的最短路徑圣絮，但是貪婪最佳優(yōu)先搜索無法保證祈惶，A*算法在啟發(fā)值保證不大于從起點開始的真實距離的情況下可以保證找到最短路徑。當(dāng)啟發(fā)值變得越來越小的時候扮匠，A*就逐步變成Dijkstra算法捧请。當(dāng)啟發(fā)值變得越來越大的時候，A*就會逐步變成貪婪最佳優(yōu)先搜索棒搜。
關(guān)于性能呢疹蛉？你最需要做的事情就是一出你圖中的冗余節(jié)點，如果是使用一個格子圖的話力麸，看這里可款。減小圖的規(guī)模可以幫助所有的圖搜算法加快速度末盔，然后筑舅，用你可以用的最簡單的算法，隊列越簡單陨舱，算法運行越快翠拣。貪婪最佳優(yōu)先算法通常比Dijkstra算法運行地更快，但是不能產(chǎn)出最優(yōu)路徑游盲。一般尋路需求下A*算法通常都會是一個比較好的選擇误墓。
關(guān)于沒有地圖的情況呢蛮粮？使用地圖來舉例是因為我認(rèn)為用地圖可以助于理解算法的運行原理。然而谜慌，圖搜算法除了游戲地圖外可以用在各種各樣的圖上然想。我已經(jīng)設(shè)法在不依賴于2D格子的方向上去呈現(xiàn)算法代碼，地圖上的移動消耗可以是圖邊上的任意權(quán)重欣范，啟發(fā)函數(shù)并不能很簡單得翻譯給任意地圖变泄，你必須給不同類型的圖設(shè)計不同的啟發(fā)函數(shù)。對于平面地圖恼琼，使用距離來作為啟發(fā)值是一個好選擇妨蛹，所以我們在這里也是這么用的。
我在這里寫了很多關(guān)于尋路的內(nèi)容晴竞。記住蛙卤，圖搜僅僅是你需要的內(nèi)容的一部分而已，A*算法本身并不會去處理諸如協(xié)同移動噩死、移動障礙物颤难、更改地圖、危險區(qū)域評估已维、編隊行嗤、轉(zhuǎn)彎半徑、對象大小衣摩、動畫昂验、路徑平滑等內(nèi)容捂敌。
