概述

剝除代碼，A* 算法非常簡單。算法維護(hù)兩個集合：OPEN 集和 CLOSED 集。OPEN 集包含待檢測節(jié)點(diǎn)。初始狀態(tài)，OPEN集僅包含一個元素：開始位置。CLOSED集包含已檢測節(jié)點(diǎn)。初始狀態(tài)，CLOSED集為空。從圖形上來看，OPEN集是已訪問區(qū)域的邊界，CLOSED集是已訪問區(qū)域的內(nèi)部。每個節(jié)點(diǎn)還包含一個指向父節(jié)點(diǎn)的指針，以確定追蹤關(guān)系。

算法有一個主循環(huán)，重復(fù)地從OPEN集中取最優(yōu)節(jié)點(diǎn)n（即f值最小的節(jié)點(diǎn)）來檢測。如果n是目標(biāo)節(jié)點(diǎn)，那么算法結(jié)束；否則，將節(jié)點(diǎn)n從OPEN集刪除，并添加到CLOSED集中，然后查看n的所有鄰節(jié)點(diǎn)n’。如果鄰節(jié)點(diǎn)在CLOSED集，它已被檢測過，則無需再檢測（*）；如果鄰節(jié)點(diǎn)在OPEN集，它將會被檢測，則無需此時檢測（*）；否則，將該鄰節(jié)點(diǎn)加入OPEN集，設(shè)置其父節(jié)點(diǎn)為n，到n’的路徑開銷g(n’) = g(n) + movementcost(n, n’)。

這里有更詳細(xì)的介紹，其中包含交互圖。

（*）這里我略過了一個小細(xì)節(jié)。你應(yīng)當(dāng)檢查節(jié)點(diǎn)的g值，如果新計(jì)算得到的路徑開銷比該g值低，那么要重新打開該節(jié)點(diǎn)（即重新放入OPEN集）。
?

OPEN = priority queue containing START

CLOSED = empty set

while lowest rank in OPEN is not the GOAL:

??current = remove lowest rank item from OPEN

??add current to CLOSED

??for neighbors of current:

? ? cost = g(current) + movementcost(current, neighbor)

? ? if neighbor in OPEN and cost less than g(neighbor):

? ?? ?remove neighbor from OPEN, because new path is better

? ? if neighbor in CLOSED and cost less than g(neighbor): **

? ?? ?remove neighbor from CLOSED

? ? if neighbor not in OPEN and neighbor not in CLOSED:

? ?? ?set g(neighbor) to cost

? ?? ?add neighbor to OPEN

? ?? ?set priority queue rank to g(neighbor) + h(neighbor)

? ?? ?set neighbor's parent to current

reconstruct reverse path from goal to start

by following parent pointers

復(fù)制代碼

（**）如果啟發(fā)式函數(shù)值始終是可信的，這種情況就不應(yīng)當(dāng)出現(xiàn)。然而在游戲中，經(jīng)常會得到不可信的啟發(fā)式函數(shù)。

連通性

如果游戲中起點(diǎn)和終點(diǎn)在圖上根本就不連通，此時A*算法會耗時很久，因?yàn)閺钠瘘c(diǎn)開始，它需要查探所有的節(jié)點(diǎn)，直到它意識到根本沒有可行的路徑。因此，我們可以先確定連通分支，僅當(dāng)起點(diǎn)和終點(diǎn)在同一個連通分支時，才使用A*算法。

性能

A*算法的主循環(huán)從一個優(yōu)先級隊(duì)列中讀取節(jié)點(diǎn)，分析該節(jié)點(diǎn)，然后再向優(yōu)先級隊(duì)列插入新的節(jié)點(diǎn)。算法還追蹤哪些節(jié)點(diǎn)被訪問過。要提高算法的性能，考慮以下幾方面：

能縮減圖的大小嗎？這能減少需處理的節(jié)點(diǎn)數(shù)目，包括在最終路徑上和不在最終路徑上的節(jié)點(diǎn)。可以考慮用導(dǎo)航網(wǎng)格（navigation meshes）代替網(wǎng)格（grids），還可以考慮分層地圖表示（hierarchical map representations）。

能提高啟發(fā)式函數(shù)的準(zhǔn)確性嗎？這可以減少不在最終路徑上的節(jié)點(diǎn)數(shù)目。啟發(fā)式函數(shù)值越接近真實(shí)路徑長度（不是距離），A*算法需要檢查的節(jié)點(diǎn)就越少。可以考慮用于網(wǎng)格的啟發(fā)式函數(shù)，也可以考慮用于一般圖形（包括網(wǎng)格）的ALT（A*，路標(biāo)Landmarks，三角不等式Triangle Inequality）。

能讓優(yōu)先級隊(duì)列更快嗎？考慮使用其他數(shù)據(jù)結(jié)構(gòu)來構(gòu)建優(yōu)先級隊(duì)列。也可以參考邊緣搜索的做法，對節(jié)點(diǎn)進(jìn)行批處理。還可以考慮近似排序算法。

能讓啟發(fā)式函數(shù)更快嗎？每個open節(jié)點(diǎn)都要調(diào)用啟發(fā)式函數(shù)，可以考慮緩存函數(shù)的計(jì)算結(jié)果，也可以采用內(nèi)聯(lián)調(diào)用。

關(guān)于網(wǎng)格地圖，我有一些建議。

源代碼和演示

演示（demos）

這些demos運(yùn)行于瀏覽器端：

我為方形網(wǎng)格、六角形網(wǎng)格、三角網(wǎng)格都編了flash演示。這些demos采用Actionscript 3編寫，點(diǎn)此查看源代碼（其中，Pathfinder.as可視作主算法，Graph.as是圖形的抽象接口）。

這里有在公路圖（不是網(wǎng)格）上運(yùn)行的demos，針對如下算法：A*、廣度優(yōu)先搜索、Dijkstra算法、貪婪最佳優(yōu)先搜索。

用Javascript寫的A* demo可以改變道路權(quán)重，源代碼在github，使用MIT的開源代碼許可。Demo中可以中斷計(jì)算，因此可以每幀運(yùn)行幾個迭代。
?

• James Macgill 寫的java applet.
• 可以選擇A*或Dijkstra算法的交互式demo.
• 這個demo很好，而且包含javascript源碼
• 這個demo很好，源碼也是可見的。
• 另一個javascript demo
• 這個頁面介紹跳點(diǎn)搜索，其中有在線demo。
• 采用Actionscript的A* 教程，在接近結(jié)尾的地方有一個demo。
• 這個demo是javascript寫的，代碼可讀，但是我不知道其源代碼許可是什么。
• 這個A* demo和跳點(diǎn)搜索demo用Unity編寫。

代碼

如果你用C++，一定要看看Mikko Mononen的Recast。

如果你計(jì)劃自己實(shí)現(xiàn)圖搜索，這里是我的Python和C++實(shí)現(xiàn)指南。

我收集了一些源代碼鏈接，但是我還沒有仔細(xì)看這些項(xiàng)目，所以也沒有更具體的建議：

集合表示

要表示OPEN集和CLOSED集，你首先能想到什么？如果你像我一樣，可能就會考慮“數(shù)組”。你也可能想到“鏈表。有很多數(shù)據(jù)結(jié)構(gòu)都可以用，我們應(yīng)當(dāng)依據(jù)需要的操作來選擇一個。

對OPEN集主要執(zhí)行三個操作：主循環(huán)重復(fù)地尋找最優(yōu)節(jié)點(diǎn)，然后刪除它；訪問鄰節(jié)點(diǎn)時檢查節(jié)點(diǎn)是否在集合中；訪問鄰節(jié)點(diǎn)時插入新節(jié)點(diǎn)。插入和刪除最優(yōu)都是優(yōu)先級隊(duì)列的典型操作。

數(shù)據(jù)結(jié)構(gòu)的選擇不僅依賴于操作，還與每個操作運(yùn)行的次數(shù)有關(guān)。成員隸屬測試對每個已訪問節(jié)點(diǎn)的每個鄰節(jié)點(diǎn)運(yùn)行一次，插入對每個要考慮的節(jié)點(diǎn)運(yùn)行一次，刪除最優(yōu)對每個已訪問的節(jié)點(diǎn)運(yùn)行一次。大部分考慮的節(jié)點(diǎn)都會被訪問，沒有被訪問的是搜索空間的邊緣節(jié)點(diǎn)。評估各種數(shù)據(jù)結(jié)構(gòu)下操作的開銷時，我們應(yīng)當(dāng)考慮最大邊緣值（F）。

另外還有第四種操作，這種操作相對較少，但仍需要實(shí)現(xiàn)。如果當(dāng)前檢測的節(jié)點(diǎn)已經(jīng)在OPEN集中（經(jīng)常出現(xiàn)的情況），并且其f值低于OPEN集中原來的值（很少見的情況），那么需要調(diào)整OPEN集中的值。調(diào)整操作包括刪除節(jié)點(diǎn)（這個節(jié)點(diǎn)的f值不是最優(yōu)的）以及再插入該節(jié)點(diǎn)。這兩步操作可以優(yōu)化為一步移動節(jié)點(diǎn)的“增加優(yōu)先級”操作（也被稱為“降鍵”）。

我的建議：一般最好的選擇是采用二叉堆。如果有現(xiàn)成的二叉堆庫，直接用就可以了。如果沒有，開始就使用有序數(shù)組或無序數(shù)組，當(dāng)要求更高的性能時，切換到二叉堆。如果OPEN集中的元素超過10,000個，就要考慮使用更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，比如桶系統(tǒng)（bucketing system）。

無序數(shù)組或鏈表

最簡單的數(shù)據(jù)結(jié)構(gòu)就是無序數(shù)組或鏈表了。成員隸屬測試很慢，要掃描整個結(jié)構(gòu)，時間復(fù)雜度為O(F)。插入很快，只需追加到結(jié)尾，時間復(fù)雜度O(1)。查找最優(yōu)元素很慢，要掃描整個結(jié)構(gòu)，時間復(fù)雜度O(F)。刪除最優(yōu)元素，采用數(shù)組的時間復(fù)雜度是O(F)，鏈表是O(1)。“增加優(yōu)先級”操作花費(fèi)O(F)找節(jié)點(diǎn)，然后花費(fèi)O(1)改變其值。

有序數(shù)組

要想刪除最優(yōu)元素更快，可以維護(hù)一個有序數(shù)組。那么可以做二分查找，成員隸屬測試就是O(log F)。插入則很慢，要移動所有元素從而給新元素讓出位置，時間復(fù)雜度O(F)。查找最優(yōu)元素只需取最后一個元素，時間復(fù)雜度O(1)。如果我們確保最優(yōu)元素在數(shù)組末尾，刪除最優(yōu)元素是O(1)。增加優(yōu)先級操作花O(log F)找節(jié)點(diǎn)，花O(F)改變其值或位置。

要確保數(shù)組是有序的，以使最優(yōu)元素在最后。

有序鏈表

有序數(shù)組的插入很慢。如果用鏈表，插入就很快。而成員隸屬測試則很慢，需要掃描鏈表，時間復(fù)雜度O(F)。插入只需O(1)，但是要用O(F)去找到正確的插入位置。查找最優(yōu)元素依然很快，最優(yōu)元素在鏈尾，時間復(fù)雜度O(1)。刪除最優(yōu)元素也是O(1)。增加優(yōu)先級操作花O(F)找節(jié)點(diǎn)，花O(1)改變其值或位置。

二叉堆

二叉堆（不要和內(nèi)存堆搞混了）是樹型結(jié)構(gòu)，存儲在數(shù)組中。大部分樹采用指針指向孩子節(jié)點(diǎn)，二叉堆則使用下標(biāo)確定孩子節(jié)點(diǎn)。

采用二叉堆時，成員隸屬測試需要掃描整個結(jié)構(gòu)，時間復(fù)雜度O(F)。插入和刪除最優(yōu)元素都是O(log F)。

增加優(yōu)先級操作很有技巧性，找節(jié)點(diǎn)用O(F)，而增大其優(yōu)先級竟然只要O(log F)。然而，大部分優(yōu)先級隊(duì)列庫中都沒有該操作。幸運(yùn)的是，這個操作不是絕對必要的。因此我建議，除非特別需要，不用考慮該操作。我們可以通過向優(yōu)先級隊(duì)列插入新元素來代替增加優(yōu)先級操作。雖然最終可能一個節(jié)點(diǎn)要處理兩次，但是相比實(shí)現(xiàn)增加優(yōu)先級操作，這個開銷比較少。

C++中，可以使用優(yōu)先級隊(duì)列（priority_queue）類，這個類沒有增加優(yōu)先級方法，也可以使用支持這個操作的Boost庫可變優(yōu)先級隊(duì)列。Python中使用的是heapq庫。

你可以混合使用多種數(shù)據(jù)結(jié)構(gòu)。采用哈希表或索引數(shù)組做成員隸屬測試，采用優(yōu)先級隊(duì)列管理優(yōu)先級；詳情請看下文的混合部分。

二叉堆的一個變種是d元堆（d-ary heap），其中每個節(jié)點(diǎn)的孩子數(shù)大于2。插入和增加優(yōu)先級操作更快一些，而刪除操作則略慢一點(diǎn)。它們可能有更好的緩存性能。

有序跳躍列表（sorted skip lists）

無序鏈表的查找操作很慢，可以使用跳躍列表加快查找速度。對于跳躍列表，如果有排序鍵，成員隸屬測試只要O(log F)。如果知道插入位置，同鏈表一樣，跳躍列表的插入也是O(1)。如果排序鍵是f，查找最優(yōu)節(jié)點(diǎn)很快，是O(1)。刪除一個節(jié)點(diǎn)是O(1)。增加優(yōu)先級操作包括查找節(jié)點(diǎn)，刪除該節(jié)點(diǎn)，再插入該節(jié)點(diǎn)。

如果將地圖位置作為跳躍列表的鍵，成員隸屬測試是O(log F)；執(zhí)行過成員隸屬測試后，插入是O(1)；查找最優(yōu)節(jié)點(diǎn)是O(F)；刪除一個節(jié)點(diǎn)是O(1)。這比無序鏈表要好，因?yàn)樗某蓡T隸屬測試更快。

如果將f值作為跳躍列表的鍵，成員隸屬測試是O(F)；插入是O(1)；查找最優(yōu)節(jié)點(diǎn)是O(1)；刪除一個節(jié)點(diǎn)是O(1)。這并不比有序鏈表好。

索引數(shù)組（indexed arrays）

如果節(jié)點(diǎn)集合有限，且大小還可以的話，我們可以采用直接索引結(jié)構(gòu)，用一個索引函數(shù)i(n)將每個節(jié)點(diǎn)n映射到數(shù)組的一個下標(biāo)。無序數(shù)組和有序數(shù)組的大小都對應(yīng)于OPEN集的最大尺寸，而索引數(shù)組的數(shù)組大小則始終是max(i(n))。如果函數(shù)是密集的（即不存在未使用的索引），max(i(n))是圖中的節(jié)點(diǎn)數(shù)目。只要地圖是網(wǎng)格結(jié)構(gòu)，函數(shù)就很容易是密集的。

假設(shè)函數(shù)i(n)時間復(fù)雜度是O(1)，成員隸屬測試就是O(1)，因?yàn)橹恍枰獧z測Array[i(n)]有沒有數(shù)據(jù)。插入也是O(1)，因?yàn)橹恍枰O(shè)置Array[i(n)]。查找和刪除最優(yōu)節(jié)點(diǎn)是O(numnodes)，因?yàn)樾枰檎艺麄€數(shù)據(jù)結(jié)構(gòu)。增加優(yōu)先級操作是O(1)。

哈希表

索引數(shù)組占用大量內(nèi)存來存儲所有不在OPEN集中的節(jié)點(diǎn)。還有一種選擇是使用哈希表，其中哈希函數(shù)h(n)將每個節(jié)點(diǎn)n映射到一個哈希碼。保持哈希表大小是N的兩倍，以保證低沖突率。假設(shè)h(n)時間復(fù)雜度是O(1)，成員隸屬測試和插入預(yù)期時間復(fù)雜度是O(1)；刪除最優(yōu)時間復(fù)雜度是O(numnodes)，因?yàn)樾枰阉髡麄€結(jié)構(gòu)；增加優(yōu)先級操作是O(1)。

伸展樹（splay trees）

堆是基于樹的一種結(jié)構(gòu)，它的操作預(yù)期時間復(fù)雜度是O(log F)。然而問題是，在A*算法中，常見的操作是，刪除一個低開銷節(jié)點(diǎn)（引起O(log F)的操作，因?yàn)楸仨殞?shù)值從樹底向上移）后，緊跟著添加多個低開銷節(jié)點(diǎn)（引起O(log F)的操作，因?yàn)檫@些值被插入樹底，然后再向上調(diào)整到樹根）。這種情況下，預(yù)期情況就等價于最壞情況了。如果能找到一種數(shù)據(jù)結(jié)構(gòu)，使預(yù)期情況更好，即使最壞情況沒有變好，A*算法的性能也可以有所提高。

伸展樹是一種自調(diào)整的樹型結(jié)構(gòu)。對樹節(jié)點(diǎn)的任何訪問，都會將那個節(jié)點(diǎn)向樹頂方向移動，最終呈現(xiàn)“緩存”的效果，即不常用節(jié)點(diǎn)在底部，從而不會減慢操作。不管伸展樹多大，結(jié)果都是這樣，因?yàn)椴僮鲀H像“緩存大小”一樣慢。在A*算法中，低開銷節(jié)點(diǎn)很常用，高開銷節(jié)點(diǎn)則不常用，所以可以將那些高開銷節(jié)點(diǎn)移到樹底。

采用伸展樹，成員隸屬測試、插入、刪除最優(yōu)、增加優(yōu)先級的預(yù)期時間復(fù)雜度都是O(log F)，最壞情況時間復(fù)雜度都是O(F)，然而緩存使最壞情況通常不會發(fā)生。然而如果啟發(fā)式函數(shù)低估開銷，由于Dijkstra算法和A*算法的一些奇特特性，手機(jī)游戲轉(zhuǎn)讓伸展樹可能就不是最好的選擇了。特別地，對于節(jié)點(diǎn)n和其鄰節(jié)點(diǎn)n’，如果f(n’) >= f(n)，那么所有的插入可能都發(fā)生在樹的一側(cè)，最終導(dǎo)致樹失衡。我還沒有測試這種情況。

HOT隊(duì)列

還有一種數(shù)據(jù)結(jié)構(gòu)可能比堆要好。通常你可以限制優(yōu)先級隊(duì)列中值的范圍。給定一個范圍限制，往往會有更好的算法。例如，任意值排序時間復(fù)雜度是O(N log N)，但是如果有固定范圍，桶排序或基數(shù)排序可以在O(N)時間內(nèi)完成。

我們可以采用HOT（Heap On Top）隊(duì)列，以有效利用f(n’) >= f(n)的情況，其中n’是n的一個鄰節(jié)點(diǎn)。我們將刪除f(n) 最小的節(jié)點(diǎn)n，然后插入滿足下列情況的鄰節(jié)點(diǎn)n’：f(n) <= f(n’) <= f(n) + delta，其中delta <= C，常量C是從一個節(jié)點(diǎn)到鄰節(jié)點(diǎn)的開銷的最大變化。由于f(n)是OPEN集中的最小f值，且所有插入的節(jié)點(diǎn)其f值都小于等于f(n) + delta，因此OPEN集中的所有f值都在0到delta的范圍內(nèi)。就像桶/基數(shù)排序一樣，我們可以維護(hù)一些“桶”來對OPEN集中的節(jié)點(diǎn)排序。

用K個桶，可以將任何O(N)花費(fèi)降低到其平均值O(N/K)。HOT隊(duì)列中，最前面的桶是一個二叉堆，其他的桶都是無序數(shù)組。對于最前面的桶，成員隸屬測試預(yù)期時間復(fù)雜度是O(F/K)，插入和刪除最優(yōu)時間復(fù)雜度是O(log (F/K))。對于其他桶，成員隸屬測試時間復(fù)雜度是O(F/K)，插入是O(1)，而刪除最優(yōu)元素永遠(yuǎn)不會發(fā)生。如果最前面的桶空了，就要將下一個桶從無序數(shù)組轉(zhuǎn)換為二叉堆。事實(shí)證明，這一操作（”heapify”）運(yùn)行時間是O(F/K)。增加優(yōu)先級操作最好是處理為O(F/K)的刪除和隨后O(log (F/K))或O(1)的插入。

事實(shí)上，A*算法中，大部分放入OPEN集的節(jié)點(diǎn)都不需要。HOT隊(duì)列結(jié)構(gòu)脫穎而出，因?yàn)樗欢鸦?#xff08;heapified）需要的元素（開銷不大），不需要的節(jié)點(diǎn)都在O(1)時間內(nèi)被插入。唯一大于O(1)的操作是從堆中刪除節(jié)點(diǎn)，其時間復(fù)雜度也僅是O(log (F/K))。

此外，如果C小的話，可以設(shè)置K = C，那么最小的桶甚至不需要是堆，因?yàn)橐粋€桶中的所有節(jié)點(diǎn)f值都相同。插入和刪除最優(yōu)都是O(1)！有個人報(bào)告說，當(dāng)OPEN集最多有800個節(jié)點(diǎn)時，HOT隊(duì)列和堆一樣快；當(dāng)最多有1500個節(jié)點(diǎn)時，HOT隊(duì)列比堆快20%。我預(yù)測隨著節(jié)點(diǎn)數(shù)的增加，HOT隊(duì)列會越來越快。

HOT隊(duì)列的一個簡單變種是兩級隊(duì)列：將好節(jié)點(diǎn)放到一種數(shù)據(jù)結(jié)果（堆或數(shù)組），將壞節(jié)點(diǎn)放入另一種數(shù)據(jù)結(jié)構(gòu)（數(shù)組或鏈表）。因?yàn)榇蟛糠址湃隣PEN集的節(jié)點(diǎn)都是壞節(jié)點(diǎn)，所以它們從不被檢測，而且將它們放入大數(shù)組也沒什么壞處。

數(shù)據(jù)結(jié)構(gòu)比較

要記住，我們不僅要確定漸近（”大O”）行為，也要找一個低常數(shù)。要說為什么，我們考慮一個O(log F)的算法和一個O(F)的算法，其中F是堆中的元素個數(shù)。那么在你的機(jī)器上，第一個算法的實(shí)現(xiàn)可能運(yùn)行10,000 * log(F)秒，而第二個算法的實(shí)現(xiàn)可能運(yùn)行2 * F秒。如果F = 256，那么第一個是80,000秒，而第二個僅需512秒。這種情況下，“更快的”算法用時更長。僅當(dāng)F > 200,000時算法才開始變得更快。

你不能只比較兩個算法，還需要比較那些算法的實(shí)現(xiàn)，還需要知道數(shù)據(jù)的大致規(guī)模。上述例子中，當(dāng)F > 200,000，第一種實(shí)現(xiàn)更快。但如果在游戲中，F始終低于30,000，第二種實(shí)現(xiàn)更好。

沒有一種基本數(shù)據(jù)結(jié)構(gòu)是完全令人滿意的。無序的數(shù)組或鏈表，插入代價很低，但成員隸屬測試和刪除代價則很高。有序的數(shù)組或鏈表，成員隸屬測試代價稍微低些，刪除代價很低，而插入代價則很高。二叉堆插入和刪除代價稍微低些，成員隸屬測試代價則很高。伸展樹的所有操作代價都稍微低些。HOT隊(duì)列插入代價低，刪除代價相當(dāng)?shù)?#xff0c;成員隸屬測試稍微低些。索引數(shù)組，成員隸屬測試和插入代價都很低，但刪除代價異常高，而且也會占用大量內(nèi)存。哈希表性能同索引數(shù)組差不多，不過占用內(nèi)存通常要少得多，而且刪除代價僅僅是高，而不是異常高。

參閱Lee Killough的優(yōu)先級隊(duì)列頁面，獲得更多有關(guān)更先進(jìn)的優(yōu)先級隊(duì)列的論文和實(shí)現(xiàn)。

混合表示

要獲得更好的性能，你會采用混合數(shù)據(jù)結(jié)構(gòu)。我的A*代碼中，用一個索引數(shù)組實(shí)現(xiàn)O(1)的成員隸屬測試，用一個二叉堆實(shí)現(xiàn)O(log F)的插入和刪除最優(yōu)元素。至于增加優(yōu)先級，我用索引數(shù)組在O(1)時間內(nèi)測試我是否真的需要改變優(yōu)先級（通過在索引數(shù)組中存儲g值），偶爾地，如果真的需要增加優(yōu)先級，我采用二叉堆實(shí)現(xiàn)O(F)的增加優(yōu)先級操作。你也可以用索引數(shù)組存儲每個節(jié)點(diǎn)在堆中的位置；這樣的話，增加優(yōu)先級操作時間復(fù)雜度是O(log F)。

游戲交互循環(huán)

交互式（特別是實(shí)時）游戲的需求可能會影響計(jì)算最優(yōu)路徑的能力。相比最好的答案，可能更重要的是有答案。盡管如此，其他所有事都還是一樣的，更短的路徑總是更好的。

通常來說，計(jì)算接近起點(diǎn)的路徑比計(jì)算接近目標(biāo)的路徑更為重要。立即開始原理：即使沿一個次優(yōu)路徑，也要盡快移動單元，然后再計(jì)算更好的路徑。實(shí)時游戲中，A*的時延往往比吞吐量更重要。

單元要么跟隨直覺（簡單地移動），要么聽從大腦（預(yù)先計(jì)算路徑）。除非大腦跟他們說不要那樣做，單元都將跟隨直覺行事。（這個方法在大自然中有應(yīng)用，而且Rodney Brook在機(jī)器人架構(gòu)中也用到了。）我們不是一次性計(jì)算所有的路徑，而是每一個或兩個或三個游戲循環(huán)，計(jì)算一次路徑。此后單元按照直覺開始移動（可能僅僅朝目標(biāo)沿直線運(yùn)動），然后重新開始循環(huán)，再為單元計(jì)算路徑。這種方法可以攤平尋路開銷，而不是一次性全做完。

提前退出

通常A*算法找到目標(biāo)節(jié)點(diǎn)后退出主循環(huán)，但也可能提前退出，那么得到的是一段局部路徑。在找到目標(biāo)節(jié)點(diǎn)前任何時刻退出，算法返回到OPEN集當(dāng)前最優(yōu)節(jié)點(diǎn)的路徑。這個節(jié)點(diǎn)最有可能達(dá)到目標(biāo)，因此這是一個合理的去處。

與提前退出類似的情況包括：已經(jīng)檢測了一定數(shù)量的節(jié)點(diǎn)；A*算法已經(jīng)運(yùn)行了數(shù)毫秒；或者檢查的節(jié)點(diǎn)距開始位置已經(jīng)有一段距離。當(dāng)使用路徑拼接時，較之完整路徑，拼接路徑的限制應(yīng)當(dāng)更小。

可中斷算法

如果基本上不需要尋路服務(wù)，或者用于存儲OPEN集和CLOSED集的數(shù)據(jù)結(jié)構(gòu)很小，一種可選的方案是：存儲算法的狀態(tài)，退出游戲循環(huán)，然后再回到A*算法退出的地方繼續(xù)。

群體移動

路徑請求的到達(dá)不是均勻分布的。實(shí)時戰(zhàn)略游戲中，一個常見的情況是，玩家選擇多個單元，并命令它們向同一個目標(biāo)移動。這造成了尋路系統(tǒng)的高負(fù)載。

這時，為某個單元找到的路徑很有可能對其他單元也有用。那么一種想法是，可以找從單元中心點(diǎn)到目標(biāo)中心點(diǎn)的路徑P，然后對所有單元都應(yīng)用這條路徑的大部分，僅僅將前10步和后10步路，替換成為每個單元所找的路。單元i獲得的路徑是：從開始位置到P[10]的路徑，接著是P[10..len(P)-10]的共享路徑，再接著是從P[len(P)-10]到終點(diǎn)的路徑。

另請參閱：將路徑放到一塊叫做路徑拼接，這部分在這些筆記的另一個模塊中有介紹。

為每個單元找的路很短（大概平均10個步驟），長的路都是共享的。大部分路徑只要找一次，然后在所有單元中共享。但如果所有單元都沿同樣的路徑移動，可能無法給用戶留下深刻印象。為了改善系統(tǒng)的這種表象，讓單元沿稍稍不同的路走。一種方法是，單元選擇鄰近位置，自行修改路徑。

另一種方法是，讓單元意識到其它單元的存在（可能隨機(jī)選一個“領(lǐng)頭”單元，或者選那個最清楚現(xiàn)狀的單元），并只為領(lǐng)頭單元尋找一條路徑，然后采用集群算法，將單元作為一個群體移動。

有些A*變種，可以處理移動目標(biāo)，或者對目標(biāo)理解逐漸加深的情況。其中一些適用于處理多個單元向相同目標(biāo)移動的情況，它們將A*反過來用（找從目標(biāo)到單元的路徑）。

改進(jìn)

如果地圖上基本沒有障礙物，取而代之，增加了地形變化的開銷，那么可以降低實(shí)際地形開銷，來計(jì)算初始路徑。例如，如果草原開銷是1，丘陵開銷是2，大山開銷是3，那么A*會為了避免在大山上走1步，考慮在草原走3步。而如果假設(shè)草原開銷是1，丘陵是1.1，大山是1.2，那么A*在計(jì)算最初的路徑時，就不會花很多時間去避免走大山，尋路就更快。（這與精確啟發(fā)式函數(shù)的成效近似。）知道一條路徑后，單元就立刻開始移動，游戲循環(huán)可以繼續(xù)。當(dāng)備用CPU可用時，用真實(shí)的移動開銷計(jì)算一個更好的路徑。

A* 算法的變體


定向搜索

在A*算法的循環(huán)中，OPEN集合用來保存所有用于尋找路徑的被搜索節(jié)點(diǎn)。定向搜索是在A*算法基礎(chǔ)上，通過對OPEN集合大小設(shè)置約束條件而得到的變體算法。當(dāng)集合太大的時候，最不可能出現(xiàn)在最優(yōu)路徑上的節(jié)點(diǎn)將會被剔除。這樣做會帶來一個缺點(diǎn)：由于必須得保持這樣的篩選，所以可選擇的數(shù)據(jù)結(jié)構(gòu)類型會受到限制。

迭代深化（Iterative deepening）

迭代深化是一種很多AI算法采用的方法，開始的時候給一個估計(jì)值，然后通過迭代使它越來越精確。這個名字來源于游戲樹搜索中對接下來幾次操作的提前預(yù)判（例如，在象棋游戲中）。你可以通過向前預(yù)判更多的操作來深化游戲樹。一旦當(dāng)你的結(jié)果不發(fā)生變化或提高很多，就可以認(rèn)為你已經(jīng)得到了一個非常好的結(jié)果，即使讓它更精確，結(jié)果也不會再改善。在迭代深化A*(IDA*)算法中，“深度”是 f 值當(dāng)前的一個截?cái)嘀怠．?dāng) f 值太大的時候，節(jié)點(diǎn)不會被考慮（也就是說，不會被加入到OPEN集中）。第一次循環(huán)時，只需要處理非常少的節(jié)點(diǎn)。隨后的每次循環(huán)，都會增加訪問的節(jié)點(diǎn)數(shù)。如果發(fā)現(xiàn)路徑得到優(yōu)化，就繼續(xù)增加當(dāng)前的截?cái)嘀?#xff0c;否則結(jié)束。更多細(xì)節(jié)，參見鏈接。

我個人并不看好IDA*算法在游戲地圖尋路中的應(yīng)用。迭代深化的算法往往增加了計(jì)算時間，同時降低了內(nèi)存需求。然而，在地圖尋路的場景中，節(jié)點(diǎn)僅僅包含坐標(biāo)信息，所需要的內(nèi)存非常小。所以減少這部分內(nèi)存開銷并不會帶來什么優(yōu)勢。

動態(tài)加權(quán)

在動態(tài)加權(quán)算法中，你假定在搜索開始時快速達(dá)到(任意)一個位置更為重要，在搜索結(jié)束時到達(dá)目標(biāo)位置更為重要。

f(p) = g(p) + w(p) * h(p)

復(fù)制代碼

有一個權(quán)值(w >=??1 )和該啟發(fā)式關(guān)聯(lián)。當(dāng)不斷接近目標(biāo)位置的時候，權(quán)重值也不斷降低。這樣降低了啟發(fā)式函數(shù)的重要性，并增加了路徑實(shí)際代價的相對重要性。

帶寬搜索

帶寬搜索有兩個被認(rèn)為非常有用的特性。這個算法變體假設(shè) h 是一個估計(jì)過高的值，但它的估計(jì)誤差不會超過 e。那么在這樣的條件下，搜索到的路徑代價與最優(yōu)路徑代價的誤差不會超過 e。這里需要再一次強(qiáng)調(diào)，啟發(fā)值設(shè)置得越好，那么得到的結(jié)果也將越好。

另外一個特性是用來判斷你是否可以刪掉OPEN集合中的某些節(jié)點(diǎn)。只要 h+d 大于路徑真實(shí)代價（對于一些 d），那么你可以丟掉任意滿足其 f 值比OPEN集合中最優(yōu)節(jié)點(diǎn) f 值至少大 e+d 的節(jié)點(diǎn)。這是一個很奇異的特性。你相當(dāng)于得到了一個 f 值的帶寬；所有在這個帶寬意外的節(jié)點(diǎn)都可以被丟棄掉，因?yàn)樗麄儽槐ＷC一定不會出現(xiàn)在最優(yōu)路徑中。

有意思地是，對于這兩種特性分別使用不同的啟發(fā)值，仍然可以計(jì)算得到結(jié)果。你可以使用一個啟發(fā)值來保證路徑代價不會太大，另外一個啟發(fā)值來決定丟棄掉OPEN集中的哪些節(jié)點(diǎn)。

雙向搜索

與從頭到尾的搜索不同，你也可以并行地同時進(jìn)行兩個搜索，一個從開始到結(jié)束，一個從結(jié)束到開始。當(dāng)它們相遇的時候，你就會得到一個最優(yōu)路徑。

這個想法在一些情況下非常有用。雙向搜索的主要思想是：搜索結(jié)果會形成一個在地圖上呈扇形展開的樹。而一個大的樹遠(yuǎn)不如兩個小的樹，所以使用兩個小的搜索樹更好。

面對面的變體將兩個搜索結(jié)果鏈接到一起。該算法選擇滿足最佳 g(start,x) + h(x,y) + g(y,goal) 的一對節(jié)點(diǎn)，而不是選擇最佳前向搜索節(jié)點(diǎn) g(start,x) + h(x,goal) 或者最佳后向搜索節(jié)點(diǎn) g(y,goal) + h(start,y)。

重定向算法放棄同時前向和后向的搜索方法。該算法首先進(jìn)行一個短暫的前向搜索，并選出一個最佳的前向候選節(jié)點(diǎn)。接著進(jìn)行后向搜索。此時，后向搜索不是朝向開始節(jié)點(diǎn)，而是朝向剛剛得到的前向候選節(jié)點(diǎn)。后向搜索也會選出一個最佳后向搜索節(jié)點(diǎn)。然后下一步，再運(yùn)行前向搜索，從當(dāng)前的前向候選節(jié)點(diǎn)到后向候選節(jié)點(diǎn)。這個過程將會不斷重復(fù)，直到兩個后選節(jié)點(diǎn)重合。

動態(tài)A*與終身規(guī)劃A*

有一些A*的變體算法允許初始路徑計(jì)算之后地圖發(fā)生改變。動態(tài)A*可以用于在不知道全部地圖信息的情況進(jìn)行尋路。如果沒有全部信息，那么A*算法的計(jì)算可能會出現(xiàn)錯誤，動態(tài)A*的優(yōu)勢在于可以快速改正那些錯誤而不會花費(fèi)很多時間。終身規(guī)劃A*算法可以用于代價發(fā)生改變的情況。當(dāng)?shù)貓D發(fā)生改變的時候，A*計(jì)算得到路徑可能會失效；終身規(guī)劃A*可以重復(fù)利用以前的A*計(jì)算來產(chǎn)生新的路徑。

然而，動態(tài)A*與終身規(guī)劃A*都要求大量的空間——運(yùn)行A*算法時需要保持它的內(nèi)部信息（OPEN/CLOSED集合，路徑樹，g值）。當(dāng)路徑發(fā)生改變的時候，動態(tài)A*或終身規(guī)劃A*算法會告訴你是否需要根據(jù)地圖的變化調(diào)整你的路徑。

對于一個有大量運(yùn)動單元的游戲，通常不會想要保存所有的信息，所以動態(tài)D*和終身規(guī)劃A*可能不適用。這兩種算法主要為機(jī)器人而設(shè)計(jì)。當(dāng)只有一個機(jī)器人的時候，你不需要為了其他機(jī)器人的路徑來重復(fù)使用內(nèi)存。如果你的游戲只有一個或比較少的單元，你能會想要研究一下動態(tài)A*或者終身規(guī)劃A*算法。

提高A*算法計(jì)算速度的大多數(shù)技術(shù)都是采取減少節(jié)點(diǎn)數(shù)量的策略。在統(tǒng)一代價的方格網(wǎng)絡(luò)中，每次單獨(dú)搜索一個獨(dú)立格空間是非常浪費(fèi)的。一個解決辦法是對其中關(guān)鍵節(jié)點(diǎn)（例如拐角）建立一個用來進(jìn)行尋路的圖。但是，沒有人愿意預(yù)先計(jì)算出一個路標(biāo)圖，那就來看看可以在網(wǎng)格圖上向前跳躍的A*變體算法，跳躍點(diǎn)搜索。 考慮到當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)有可能會出現(xiàn)在OPEN集合中，跳躍點(diǎn)搜索直接跳躍到從當(dāng)前點(diǎn)可看到的遙遠(yuǎn)的節(jié)點(diǎn)。隨著OPEN集合中節(jié)點(diǎn)的不斷減少，每一步的代價都會越來越高雖然都很高，但是步數(shù)也會越來越少。

此外，在矩形對稱消減中，有對地圖進(jìn)行分析和圖中嵌入跳躍。這兩種技術(shù)都是應(yīng)用于方格網(wǎng)絡(luò)圖中的。

Theta*

有時網(wǎng)格會用來尋路是因?yàn)榈貓D是用網(wǎng)格來生成，而不是因?yàn)檎娴囊诰W(wǎng)格上移動。如果給定一個關(guān)鍵點(diǎn)的圖（例如拐角）而不是網(wǎng)格的話，A*算法可以運(yùn)行得更快并得到更優(yōu)的路徑。但是，如果你不想預(yù)先計(jì)算那些圖的拐角，你可以通過A*算法的變體Theta*在方格網(wǎng)絡(luò)上進(jìn)行尋路而不必嚴(yán)格遵循那些方格。當(dāng)構(gòu)建父親指針的時候，如果有一個祖先與該節(jié)點(diǎn)間存在邊，那么Theta*算法會直接將該指針指向該祖先而忽略所有的中間節(jié)點(diǎn)。不像路徑光滑那樣將A*找到的路徑變?yōu)橹本€，Theta*可以把那些路徑的分析作為A*算法過程的一部分。這樣的做法可以比后處理方格路徑使之成為任意傾角的路徑的方式，可以得到更短的路徑。

Theta*的思路也可能被應(yīng)用于導(dǎo)航網(wǎng)格。

總結(jié)

以上是生活随笔為你收集整理的游戏中常用的寻路算法的分享（3）：A*算法的实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。