RTS視頻遊戲中的尋路如何工作？

Question

在諸如魔獸爭霸3或帝國時代的遊戲中，AI對手可以在地圖上移動的方式似乎幾乎是無限的。地圖非常龐大，其他玩家的位置也在不斷變化。

這樣的遊戲中的AI路徑查找如何工作？標準的圖形搜索方法（如DFS，BFS或A *）在這樣的設置中似乎是不可能的。

Answer 1

這是一個有點簡單的例子，但它表明，你可以從一個非複雜的規則使AI /深部調尋路的錯覺：Pac-Man Pathfinding

本質上講，它是可能的AI來了解本地（接近）信息並根據這些知識做出決策。

Answer 2

A*是一種常見的尋路算法。這是一個流行的遊戲開發主題 - 你應該能夠找到包含信息的大量書籍和網站。

Answer 3

因爲我沒有第一人稱尋路經驗，所以請加上一點鹽。這就是說，可能有不同的方法，但我認爲標準的圖形搜索方法，尤其是（A *的變體）對策略遊戲來說是完全合理的。我所知道的大多數策略遊戲似乎都基於一個拼貼系統，其中地圖由小方塊組成，這些小方塊很容易映射到圖形上。其中一個例子是星際爭霸II（Screenshot），我將在這個答案的其餘部分繼續使用它作爲例子，因爲我對它很熟悉。

雖然A *可用於即時戰略遊戲，還有一些必須通過調整，以核心算法來克服一些缺點：

1. A *太慢

   由於RTS是通過「實時」定義的，等待計算完成將會使玩家受挫，因爲這些單位會滯後。這可以通過幾種方法來解決。一種是使用Multi-tiered A*，在考慮較小的障礙之前計算一個粗略的過程。另一個顯而易見的優化是將朝向相同目的地的單位歸入一個排，並且只爲它們計算一條路徑。

   除了使圖中的每個瓦片成爲節點的樸素方法之外，人們還可以構建navigation mesh，該節點具有更少的節點並且可以更快地搜索 - 這需要稍微調整搜索算法，但它仍然會以A *爲核心。

2. A *是靜態

   A *適用於靜態圖形，所以做什麼的景觀變化是什麼時候？我不知道這是如何在實際的遊戲中完成的，但我想象路線是一再地完成的，以應付新的障礙或消除障礙。也許他們正在使用incremental version of A*（PDF）。

   要觀看星際爭霸II對付這個問題的演示，請在this video前往7:50。

3. A *擁有完善的信息

   的許多RTS遊戲的一部分是未開發的地形。由於你看不到地形，你的部隊不應該知道在哪裏走路，但他們經常會做。一種方法是懲罰在未開發的地形上行走，因此單位更不願意利用他們的全知，另一種方法是將全知掃除，並假設未探索的地形是可行的。這可能導致單位陷入死衚衕，有時甚至是對玩家來說顯而易見的，直到他們最終探索到目標的路徑。

   戰爭迷霧是這方面的另一個方面。例如，在星際爭霸2中，地圖上有可破壞的障礙物。已經表明，你可以命令一個單位移動到敵方基地，並且如果障礙物已經被你的對手摧毀，它將開始不同的路徑，從而給你提供你實際上不應該擁有的信息。

總結：您可以使用標準算法，但您可能必須巧妙地使用它們。作爲最後的獎勵：我發現Amit’s Game Programming Information關於路徑有趣。它還有進一步討論這個問題的鏈接。

Answer 4

查看可見性圖。我相信這是他們用於尋路的東西。