即時戰略遊戲中實用的尋路演算法都有哪些，比較如何？

12-28

rts中的尋路系統一般需要滿足有以下幾個條件，
1. 效率高，因為rts普遍地圖大，單位多，所以處理效率很重要
2. 易編輯，以便於level design
3. 效果真實，如能找出最優（或者是看上去合理）
4. 可以應對動態的遊戲世界，例如起建築

如 @王亞暉所說，一般用於尋路的演算法是A Star，
首先是A Star有利用到啟發式函數（Heuristic Function）[1]，和另一個演算法Dijkstra（A Star的無啟發函數版）相比可能會更有效率，因為啟發函數設計得當，可以大大減少計算的數量。
因為啟發函數的估計往往不是精確的，所以A Star [刪：不像Dijkstra，] 不一定能找出人類人之上的最優解，但是對於遊戲來說，看上去合理就行。

然而用A Star作為尋路演算法，僅僅是尋路系統的基本部分。
作為系統，它需要有易編輯的特性。
這就涉及到A Star中每個節點（Node）的表現方式。

最基本的表現方式是方塊（Tile），如下圖 [2]

其中，可以將山洞所佔的的幾個方塊設為「Not Movable」，這樣A Star就會不會考慮到這幾個方塊，系統所生成的路徑就不會碰到山洞。
用方塊作為A Star節點優點是簡單，
不過也有比較多的問題，
第一是，如果地圖很大的話，方塊就會很多，這樣A Star的節點就會大大增加，處理的時間相應地會增大。
第二是，單位的移動只能是上下左右，最多加上斜行，總共八個方向，不夠真實
第三是，單位的體積大小不一樣的話，大單位的圖像可能會覆蓋到「Not Movable」部分。以上面的圖片為例，一條路徑會經過在山洞邊邊，一個佔四個方塊大小的巨人走過的話，就會走在山洞上面。

為了解決上面的一些問題，我們可以使用路經點（Waypoint）來做A Star節點，如下圖 [3]

圖中的紅色的路徑點代替了方塊，成為A Star節點，這樣的好處是我們可以自由地添加路徑點，可以相對地減少A Star節點數目，
同時也單位也可以按照設計師設計的方法去走。
然而，從上圖也可以看出它的問題不少，
第一是，如果是大地圖，路徑點數量太少會顯得生硬。
第二是，需要考慮得面面俱到，不然一條直路忘了加路徑點，單位就會「繞」（看上去）過去。

為了更好地解決以上所述的問題，導航網格（Navmesh or Navigation Mesh）出現了，如下圖所示 [4]

現在，灰白色的多邊形成為了A Star節點。
它解決了上面所出現的所有問題，
第一，從圖中可以看出，節點的數目大大減少，因為多邊形可以覆蓋任意區域，不用限制成方塊或點。除了提升計算速度之外，編輯導航網格的效率也大大增加。
第二，通過計算直線兩點和導航網格的相鄰點（上圖藍色點）的位置關係，可以計算出兩點是不是可以直接行走而沒有阻礙物。例如上圖從A點到B點通過計算可以得出可以直線行走，不用想方塊和導航點那樣繞來繞去。
第三，在轉角位不一定要經過相鄰點，可以加上單位的體積半徑，這樣不同體積的單位都可以合理地通過轉角。

對於建築的考慮
在RTS中的尋路系統，還有一個很重要的話題，就是要可以應對動態的遊戲世界。
一個簡單的例子就是起建築。
在一些需要頻繁修改遊戲世界的場景中，以方塊為節點會更加容易作出修改 [14] ——只需要將建築所佔的方塊的「Not Movable」修改成「Movable」。例如著名的塔防遊戲《Field Runner》，應該是利用這種方法來實現的，而且作為塔防，《Field Runner》可以只在建塔之後尋路一次，緩存起來就行。所以在這一場景中方塊又成為了一個方便快捷的選擇。
然而，導航網格也是可以動態修改的，不過開發難度會更大，而且運行中動態修改可能會造成延遲。有一些方法可以優化，例如動態地修改局部導航網格 [12]，或者是完全不修改，而將建築看作局部的障礙物用另一套機制來應對 [13]。

其實除了A Star演算法之外，還有其他演算法，或者技巧，可以用於RTS的尋路系統，這裡簡單地介紹一下，

例如Potential Field，
它是將地圖用一個矩陣來表示，矩陣儲存著大小不同的電勢（整數）。
例如，正電勢表示吸引，負電勢表示排斥。
而遊戲中的單位本身是一個負電勢，遊戲以一個數組儲存所有單位的電勢和位置 [7]。
這樣，在計算一個單位需要怎麼從A點到B點時，我們可以用一個新的矩陣將目的地B點設成正電勢，並以不同方式（如圓形、四邊形等）輻射開來，離B點越遠電勢越低，直到0。
然後將地圖矩陣，目的地矩陣，和所有單位數組的電勢相加，得出一個新的、反映當前遊戲世界的電勢矩陣，
然後單位再選擇周圍所有電勢點中的最高電勢點去走。
不過這裡坑很多，因為它本質上是Greedy Algorithm，所以它未必能找出解。[5]
然而在某些設定中，例如在沒有過於複雜地形，並且需要單位自動不相互覆蓋的情況下，Potential Field還是可以完成任務 [8]。
因為相比A Star的尋路系統來說，這個方法會比較簡單。

還有Flocking Behavior，
在對於一大群單位的尋路，計算量是很大的，而且往往會有很多的重複，這些都是可以避免的。
如果單位的移動是利用Steering Behavior [9] 來實現的話，
那麼就可以為其中一個單位，稱之為Leader，計算路徑（例如用導航網格），
然後其他單位按照以下Flocking原則來移動：
1. 分離，避開相鄰單位
2. 一致，和整體的移動方向一致，這裡應該是Leader的移動方向
3. 聚合，向整體的平均位置靠攏
這樣的話，就可以降低尋路的計算量，並且得到更加真實的群體單位行進效果。

另外一個技巧和Flocking Behavior類似 [10]，
對於不用Steering Behavior的一大群單位，
可以將他們設為一個組，計算這個組的路徑（並且要考慮到這個組的半徑以便通過轉角位），
然後給每個單位offset一個適當的距離，
如果遇到小的通道，例如門，可以適當調整offset。
《全面戰爭》裡面一個隊伍40人，大概用的就是這種方法 [11]。

還有一個優化技巧是Chunk [15]。
這個技巧和 @王亞暉所提到的「先切分地圖然後分塊去做」應該是一致的。
在規模宏大的地圖中，為了進一步提高尋路速度，可以在編輯地圖時將一些節點處理成一個Chunk，它有入口和出口，並且不同Chunk之間需要連接起來。
從A點移動到B點，首先先在Chunk之間做尋路，得到一系列的Chunk，
在Chunk 1的時候只需要在Chunk 1中尋路，去到Chunk 2的時候就只在Chunk 2中尋路。
它本質上是將地圖分為兩種維度，一種是粗略的Chunk，一種是Chunk裡面的節點（可以是方塊，路徑點，導航網格），並分開進行處理。有種空間分割（Space Partition）的味道在裡面。
這個方法我沒有真正用過，還望大家補充。

還有D Star，它主要運用在機器人領域 [6]，可以在未知環境中尋路，不過我沒接觸過。

--------------Update 1----------------
1. 增加了Potential Field的簡單說明
2. 增加了常用的啟發函數例子
3. 完善了A Star說明，指出它不一定能找出最優解

--------------Update 2----------------
1. 增加了Flocking Behavior在大群單位尋路的應用
2. 增加了Flocking Behavior的替代技巧

--------------Update 3----------------
1. 增加了對於動態地修改遊戲世界的考慮（如建築）

--------------Update 4----------------
1. 增加了Chunk 優化技巧

--------------Update 5----------------
1. 在 @金秉文的幫助下，發現A Star和最優解的一個錯誤，已更正。A Star的啟發函數在單調的情況下是可以找出最優解的，但是這個最優解未必符合人類認知上的最優解，因為啟發函數未必準確。

注釋和資料來源：
[1] 啟發式函數 Heuristic Function：估計路徑所需的資源花費的函數，資源可以是「時間」，「體力」等等。對於精度要求不高的遊戲來說，常用的啟發函數是估算曼哈頓距離。
[2] 圖片來源： Implementing Auto-tiling Functionality in a Tile Map Editor
[3] 圖片來源：http://mgrenier.me/2011/06/pathfinding-concept-the-basics/ （這篇博客也有講述尋路的概念，是一個不錯的學習資源）
[4] 圖片來源：Game/AI: Fixing Pathfinding Once and For All （這篇博客更加全面地講述各種尋路系統的節點代表方式，值得一看）
[5] 推薦參考：Using Potential Fields in a Real-time Strategy Game Scenario (Tutorial)
[6] 參考來源：http://en.wikipedia.org/wiki/D*
[7] 單位可以移動，所以以數組來儲存會比較方便，不用頻繁更新矩陣。
[8] 一個成功的例子：n-created
[9] Steering Behavior，將一個單位考慮成一個受力點，通過增加不同的力，如吸引的，排斥的等等，實現如搜索、逃跑、躲避障礙和Flocking等行為。
[10] [11] 資料來源：Flanking Total War』s AI: 11 Tricks to Conquer for Your Game
[12] 動態地修改局部導航網格：Dynamic Navigation Mesh
[13] RV Obstacles：http://gamma.cs.unc.edu/RVO/
[14] 資料來源：A* Pathfinding Project
[15] 資料來源：RTS尋路系統概要中orange030的補充

本回答想從一個更系統的角度來敘述pathfinding這一系列問題，希望可以成為一個更容易理解的tutorial。這裡所涉及的尋路演算法不限於RTS遊戲，其中一些方法可能更適合靜態的遊戲環境。

這個回答中所包含的topics涉及

1.遊戲地圖的劃分及其優劣性，這裡包括：

Grid (方格)
Navigation Mesh(導航網格)

2.遊戲中常用的搜尋演算法及其優劣性

A Star search
Dijkstra』s algorithm
Floyd-Warshall algorithm

首先假設我們有下面這樣一個遊戲地圖

我們想使我們的小人從地圖任意一個位置出發，都可以順利避過障礙物到達另一個目的地。這時候該怎麼做呢？

假設我們現在只有一張上面的地圖，這時候小人是不能動的，因為我們需要告訴他哪些地方可以走。由此引入了第一個topic，也就是方格grid。

這個方法很簡單，我只需要選擇一個合適的正方形的邊的大小，然後在地圖上沒有障礙物的地方畫square就可以了。然後我們可以選取每一個square的中心，作為小人實際可以走的點，這樣這個地圖就成了下圖模樣（圖中綠色的方格代表每一個grid，方格的中心才是可以走的點）。

有了這些網格，我們只是告訴了小人哪些點是可以走的，但我們還要告訴它在某一個點上有哪些路徑可以選擇。這個很簡單，我們可以選擇某一個點周圍八個點作為可以走的路徑（如果這個方向沒被障礙物擋住的話）。對所有的點重複這一過程，我們就可以生成這個地圖的path networks(路徑網路)了。如下圖，圖中藍色的線代表路徑網路。

此時我們就已經完成了對連續的地圖離散化這一過程，小人也就可以在遊戲世界裡亂走了（注意是亂走~）。這是因為我們還沒有使用搜索演算法來告訴小人如何到達目的的，或者說走哪條路可以到達目的地。

以上就是grid navigation的大致方法了，在此總結一下它的優缺點。

優點：這是一種對地圖離散化的方法。這種方法真的很簡單，非常容易實現而且容易和A star search或者uniform cost search演算法結合起來使用。

缺點：使用這種方法劃分出來的網格，小人的移動其實是不連續的。有時可能看起來並不自然，就如下圖所示的情況。而且可以從上圖看出，網格數灰常的多，可能需要大量的資源來計算和存儲路徑。

在說明常用的搜尋演算法之前，我想詳細說明一種遊戲中更常用的路徑生成方法，這就是navigation mesh（導航網格）。這裡的mesh和grid有區別，mesh可以是很多種形狀的多邊形。下圖中的每一個多邊形都是navigation mesh的組成部分，魔獸世界就用到了這種方法進行地圖的劃分。

請注意這裡的劃分出的每一個多邊形都是凸多邊形。這裡其實是使用到了凸多變形的性質，在凸多邊形邊上的一個點走到另外一點，不管怎麼走都不會走出這個多邊形，如下圖所示(參考Convex Polygon -- from Wolfram MathWorld)。相反凹多邊形就不滿足這一性質。

應用到遊戲世界裡，我們只要在空地上放置凸多邊形，小人在多邊形內怎麼走都不會碰到障礙。

這種方法聽上去挺簡單，實際該怎麼操作呢。我們知道任意一個三角形都是凸多邊形，我們可以先通過地圖的邊界點和障礙物的邊界點，將地圖劃分成很多個三角形，如下圖所示。

我們可以看到，雖然通過這種方法生成的網格相比grid已經大大減少，但是圖上很多相鄰的三角形是可以合併形成新的凸多邊形的。所以我們其實還可以進一步優化，將可以合併成新的凸多邊形的相鄰多邊形合併，並重複這一過程，最終得到下圖。

然後我們可以在每一個網格每一條邊的中點上放置pathnode(路徑點)，然後將每一個網格自己邊上的路徑點連接起來就得到了完整的路徑網路了，如下圖，同上綠色的線代表畫好的navigation mesh，藍色的線代表可以走的路徑網路。

以上就是navigation mesh的大致思想與方法，其優缺點總結如下，參考(http://en.wikipedia.org/wiki/Navigation_mesh#Advantages):

優點：這種方法可以大大減少路徑點和搜尋所需的計算量，同時也使小人的移動更加自然。在這樣的路徑點之間行走，我們其實可以完全無視地圖上的任何障礙物。

缺點：計算三角形和合併相鄰的凸多邊形需要很大的計算量，而且實現起來沒有看上去那麼簡單。不過成熟的遊戲引擎一般是有現成的解決方案的。

在有了path network(路徑網路)後，我們就可以開始考慮如果讓小人從一點走到另外一點，如果尋找最優路線了（即返回一系列路徑點）。

首先大多數人會想到A* search。A*是一種非常經典的搜索演算法，使用到了heuristic和accumulated cost，細節這裡就不贅述了，不太清楚的可以參考（A*_search_algorithm）。值得注意的是，這裡的heuristic一般是admissible的，也就是說在A*中我們對目標的估計必須小於或等於其實際值，不然可能會出現找不到最優路徑或者根本找不到路徑的情況。當然也有很多情況下我們根本不需要找到最優路徑，只要player覺得合理，who cares optimality呢lol~

這裡除去A*的實現細節，我想說明的是，A*是一種single source single destination的演算法，它的時間複雜度是O(|E|), E是地圖上所有路徑點所形成的路徑網路的edge的數目。也就是說A*可以用來計算從一個點到另外一個點的最優路徑。這也就說明A*適合用來對動態環境進行路徑計算，可以實時根據當時的環境立即計算出路徑。相對應的，Dijkstra』s algorithm和Floyd-Warshall適合對於不變的環境來進行計算，下面會說明為什麼。

這裡介紹的第二種尋路演算法就是Dijkstra』s algorithm。說Dijkstra是A*的無heuristic版本，其實並不準確。A*去掉heuristic其實是uniform cost search。而Dijkstra是uniform cost search的multiple destination的變形。也就是說，給出地圖上一個路徑點，使用Dijkstra可以對地圖上所有其他的路徑點一次性計算出最優路徑。Dijkstra的時間複雜度是O(|E|+|V|log|V|)，這時E是edge數，V是vertex的數目(Dijkstra"s_algorithm)。從這裡可以看出，如果需要對地圖上所有的路徑點同時計算左右路徑，Dijkstra會比使用A*更方便。這也就說明了為什麼Dijkstra適合對靜態的環境進行計算，因為靜態的環境是不會變的，我們可以是用Dijkstra對地圖進行preprocess獲得navigation table（後面會說明navigation table如何生成）。我們可以把navigation table記錄下來，這樣在遊戲進行的時候從一個路徑點到另外一個路徑點只需要查表就可以了，這樣一來遊戲實際運行時的尋路的時間複雜度就減少到了O(V)，也就是線性複雜度了，而且對於靜態的環境，我們的navigation table是百分之百可靠的。

另外還想簡要介紹一種尋路演算法Floyd-Warshall。這個演算法是all sources all destinations的，也就是說給出一個地圖，這個演算法可以計算出從所有路徑點到所有其他路徑點的最優路徑，而且可以一邊運行演算法一邊生成navigation table，而Dijkstra需要先跑一遍演算法，然後從一個路徑點backtrack才能生成navigation table。這個演算法的時間複雜度是O(|V|^3)，詳情可以參考Floyd。

至於Navigation table, 它大概是長這樣的，假設地圖上已經通過上述的grid或navigation mesh生成了5個路徑點，表示為0到4。表上的數字代表了從某一點要到另外一個點，應該走哪個相臨的點，再從走到的下一個點繼續查表。

假設我們已經通過運行Dijkstra和Floyd-Warshall生成了這個navigation table。如果我們需要找到從第0個點到第4的點的最優路徑，我們可以查表上第0行的第4列，列上的數字是1，意思是要從0走到4，第一個要走的點是1；再查第一行第四列，下一個要走的點是3；再查第三行第四列，我們就可以通過3走到目的地4了。這一系列0-1-3-4就是之前計算出的最優路徑。這種方法對於靜態的環境十分有效，只要環境不變，通過提前計算navigation table，在遊戲實際運行時只需要O(|V|)的時間複雜度就可以獲得到達目標點的最優路徑了。

總結:

A* search：single source single destination，速度較快但依賴於heuristic函數的設計。適用於動態環境的尋路，因此適合RTS。

Dijkstra"s Algorithm：single souce all destinations，速度也比較快，不需要heuristic函數，但是在建立navigation table的時候需要backtrack。適用於靜態環境的尋路。

Floyd-Warshall Algorithm: all sources all destinations，可以在演算法運行過程中建立navigation table。適用於靜態環境的尋路。

對於即時戰略遊戲，地圖中所涉及的環境多是動態，所以A*可能更適合一些。

參考文獻：

[1] http://en.wikipedia.org/wiki/Navigation_mesh#Advantages

[2]A* search algorithm

[3]Dijkstra"s algorithm

[4] http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html#dijkstras-algorithm-and-best-first-search

[5]Floyd

[6] http://mat.uab.cat/~alseda/MasterOpt/MyL09.pdf

[7] Convex Polygon -- from Wolfram MathWorld

PS: 本人乃graduate student一枚，並無成熟的遊戲開發經驗，本文所敘述的東西多是從上課和學習中積累而來，只是淺談一些自己的理解，不妥的地方還請多指教。

在遊戲開發中，A*是個被說爛的演算法，所以這裡說些別的。
AStar的優勢在於啟發函數，劣勢也在於啟發函數。當搜索演算法使用啟發函數後，就需要對open list中的節點進行排序，這就在演算法的時間複雜度上增加了一個係數N（這是基於往有序隊列中插入，而不是傻乎乎的每次都重排）。所以，最壞情況下，AStar要慢很多，特別是當路徑很遠時，有時候open list中會有幾十萬的節點。
另外，當目標點可以是多個，比如去最近的氣礦，AStar的啟發函數就不好設計了。這時候會使用動態規劃尋路。

我們常說程序=演算法+數據結構，那麼除了尋路演算法，地圖數據結構也在很大程度上影響著尋路的效果。常用的地圖數據結構主要有兩種：格子和凸多邊形。
使用格子的好處是查詢便捷、直觀，一般格子的精度都很高，所以數據量較大，對於數據查詢來說屬於用空間換時間的選擇，對於尋路來說，目標遠的時候需要處理的數據量較大，性能會急劇下降。而凸多邊形正好相反，數據量小很多，尋路就會快很多，但是查詢效率不如格子。有時候會兩種數據都用，用格子查詢，用凸多邊形尋路。

當追一個移動的目標時，由於目標點一直在變，而且距離不遠，這時候每次都求出全路徑就很不合算，就會採用單步尋路演算法，雖然有可能不是最優解，但是能省很多計算量。
（?充下單步尋路的大致思路）
1 只要能直接朝目標方向前進一步，就前進，並離開繞行狀態
2 否則，嘗試從左右兩邊繞過障礙，進入繞行狀態
3 一旦進入繞行狀態，不改變最初選擇的繞行方向
4設定最多繞行多少步，超過則判定尋路失敗，可以換用其它方法

基本的演算法就是A*演算法，不過網路普遍的初級教程都是把A*介紹成了只與網格相關，實際上A*可以普遍利用於圖搜索，而不一定是常見的網格，比如尋路可以沿著邊線走，未必是中心點。
另外在遊戲編程精粹中介紹了一種簡易搜索演算法：可見點尋路，你可參考，利用物體輪廓線進行構造圖，圖搜索依然是利用的A*，不過這種尋路方式大部分是動態的，比較消耗性能，我估計在RTS遊戲中基本還是矩形網格多些，只不過每個物體佔據大小不一樣，3D遊戲應該是導航網格，網格變成了三角形而已。
之前在網路上看到一個開源RTS遊戲（0.A.D），他是可見點尋路及矩形網格結合的，你可以參考其代碼。
另外星際爭霸2等最新遊戲使用了勢場尋路，關於這個可參考Using Potential Fields in a Real-time Strategy Game Scenario (Tutorial)

其實都是a+的，原因就算是即時戰略，能夠出現的情況也就是一兩百單位的尋路要計算，這對於遊戲而言說誇張些現在遊戲裡面貼一個坦克模型的貼圖都比尋路占的時間長。
就我所知，遊戲裡面因為要尋路的單位數量超過開發人員想像而在後發布的補丁中，把同時可以尋路的單位數量進行限制的就橫掃千軍了，當然這其實也不是程序員的問題，原本是設計200個單位上限的，後來，玩家玩多了以後在遊戲裡面就開始造數千個單位來打了，這才出現問題。
所以a+是夠用的

最高指揮官2據說是用了華盛頓大學的研究人流移動規律，能讓大量單位移動時不互相卡位置。
演算法叫流場尋路
視頻：
http://v.youku.com/v_show/id_XMTU0ODM4Njk2.html

看起來真爽，哈哈

大部分都是A*，但有很多優化的方法，很多都是先切分地圖然後分塊去做。針對不同的遊戲方式和地圖也有不同的優化辦法。
即便有人冒出來說別的演算法，那一般也都是A*的變形演算法。

1. a-star
2.路點 + a-star
3.導航網格
4.啟發式探測

A*+預處理，我正常嘗試完成這樣子的結構

SC不知道.
war3包括dota都很簡單.
一般會選擇插眼或者造建築或者掛小精靈的地方都屬於實用的.

說A*的都是沒有開發過RTS的，實際上A*的效率太差了，在RTS里根本沒法用。

最近新被發明的在限定條件下比astar更快的演算法
https://github.com/SteveRabin/JPSPlusWithGoalBounding

CC3車輛加入倒車功能據說是尋路演算法的一個大改進,可以避免單位堵塞.

A*演算法，怎樣還高效實現遊戲中一群兵（同源）分別攻擊多個目標，我現在的思路只能是把多個兵分組，對每個組指定一個目標，這樣分別用A*演算法算出，但感覺效率有點低，有知道更好的辦法沒？
還有就是當多個物體同源同目標的時候，怎樣來這實現這些目標分散到目標也是一個難點，因為如果多個物體擠在一些走向目標，看上去就是一個物體移動了，真實性大打折扣