遊戲中的尋路演算法

電子遊戲發展至今已經成為一個熱門、體系成熟的高收益產業 。大大小小的遊戲型別中，地圖、角色、 AI 、迷宮等等元素都已被玩家們習以為常，而尋路演算法在它們的邏輯和規則中又起著至關重要的作用。如果你想知道《王者榮耀》裡迷失在野區草叢的炮車要如何找回前進的方向，或者你想搞明白為什麼《生化危機 2 重製版》裡面的暴君能如此噁心地繞著警署三層樓追的你死去活來，那就跟著我一起系統的瞭解一下游戲中常用的尋路演算法吧。

• 地圖和圖

尋路演算法要解決的問題是，如何釐清地圖上各個位置之間的關係，如何選取關鍵位置以及制定在不同位置之間移動的策略。所以我們無法離開地圖來談尋路演算法，而任何型別的遊戲地圖都可以被抽象為經典的資料結構 —— 圖（ Graph ）。 圖的正式表示式是 G=(V,E) ， V 是代表頂點的集合， E 和 V 是一種二元關係，可以理解為邊，比如有條邊從頂點 U 到頂點 V 結束，那麼 E 可以用 (u,v) 來表示這條邊。具體的有向圖和無向圖，也是根據邊是否有方向來區分。為了方便理解，本文中大多數的資料演示都是基於 2D 網格地圖來進行講解，以下是幾種關係梳理，以 A 為頂點， BCDE 為子頂點，我們可以把每個格子也看是一個頂點。

圖中的邊也可以帶有權重或花費值 (weight/cost) ：

• 深度優先搜尋（ DFS ）

深度優先搜尋是搜尋和遍歷圖的一種演算法，與樹的深度優先搜尋類似（其實樹形結構可以理解成一種特殊的圖），選取一個深度規則，然後按照這個規則，從一個起點不斷的向遠端搜尋。比如二叉樹的深度搜索規則可以是：對於當前的節點，優先搜尋它的左子，然後再搜尋它的右子。方形網格圖的一個深度搜索規則可以是：對於當前的節點，按照上 -> 右 -> 下 -> 左的優先順序順序去搜索與它臨接的節點（ 這將是本文的幾乎所有演算法中應用的搜尋規則 ）。   

圖中灰色格子表示正常聯通的路面，紅色格子表示無法通過的障礙，黃色表示尋路過程中搜索過的格子，綠色格子表示最終生成的路徑（另外感謝 Leo 的傾情出演 ）。我們可以看到， DFS 是遍歷地圖的演算法，所以一定可以幫我們找到一條通往目標位置的路徑（如果目標位置可到達），但是這條路徑顯然不太符合我們通常意義上的尋路需求，它既不是最短的也不是很快就可以找到。但 DFS 仍然是一個非常有用的探索演算法，如果你玩過經典遊戲《惡魔城》，你一定面臨過這樣的靈魂抉擇：當前場景的所有內容都探索完後，開啟了左右兩個門，每個門後面都是一個未知的新場景，到底應該進哪個？作為一個追求 100% 探索率的 “ 強迫症玩家 ” ，我的選擇是：見門一律進左，一直到走投無路再回來進右。這樣的策略通常可以保證在未知的探索過程中少走一些冤枉路。

• 廣度優先搜尋（ BFS ）

與 DFS“ 一條路走到黑，不撞南牆不回頭 ” 的策略不同， BFS 演算法的思想是：先搜尋附近的，然後再逐漸往外層擴

雖然搜尋的優先順序順序仍是上 -> 右 -> 下 -> 左，但 BFS 會先搜尋完一個節點的四個方向上直接相臨的節點後，再去逐個搜尋這些新發現的節點的相鄰節點，從而形成層層擴散式的效果，可以看到，當我們搜尋到目標點時就已經確定了從起始點和目標點之間 “ 移動步數最少 ” 的路徑。然而由於搜尋具有盲目性，導致 BFS 作為 “ 尋找最短路徑 ” 的演算法效率著實比較低下（遍歷了過多與目標方向 “ 背道而馳 ” 的節點）。相比之下 BFS 其實更加適合這樣的遊戲場景：《過山車大亨》中的一位遊客，突然感覺到肚子餓了，於是他以自己為中心，通過 BFS 確定第一個搜尋到的餐廳或食品攤位，然後沿著路徑去那裡吃東西。

• Dijkstra 演算法

到目前為止，我們已經可以解決如何在聯通的區域中，幫 Leo 找到一條通往寶箱的步數最少的路徑的問題。但有沒有發現，我們其實默認了，每兩個格子之間 “ 移動的代價 ” 都是一樣。而在實際問題中的地圖環境可能要複雜得多，我們要考慮的就不單單是步數這一個因素了。假設我們在花園裡散步，我們要從花園的入口到花園中心的池塘邊上去。我們肯定會沿著花園中已經鋪好的石子路走過去，而不會沿直線穿過各種花叢、草叢和泥坑 “ 跋涉 ” 到目的地。這就是因為綜合了 “ 弄髒鞋子 ” 、 “ 蚊蟲叮咬 ” 、 “ 猛獸出沒 ” 等很多因素後，我們認為石子路比 “ 跋涉 ” 路線的 “ 代價 ” 要低得多（儘管前者的路程可能要比後者要長）。

將 “ 代價 ” 抽象成圖的資料結構的話，我們用節點與節點之間的邊的 cost 來表示。 Dijkstra 演算法便是經典的求解到目標點最小 cost 路徑的演算法。演算法的步驟如下：

1. 將起始點作為第一個 “ 已探索點 ” 。

2. 發現所有通過 “ 已探索點 ” 可以到達的新的節點，計算並更新要到達它們所需的最小 cost 。

3. 選取所有新發現的點中 cost 最小的標記為 “ 已探索點 ” 。

4. 重複 23 直到目標點被標記為 “ 已探索點” 。

假設灰色格子表示正常路面，藍色格子表示水坑，黃色格子則表示 “ 已探索點 ” 。 Leo 在路面上移動一個格子的 cost 是 1 ； Leo 從路面進入水坑，或從水坑游到另一個水坑，或者從水坑上岸的 cost 都是 5 。則 Dijkstra 演算法的過程可以表示為：

可以看到，我們在找到目標格子的最小 cost 路徑後仍然沒有停止搜尋，這是因為該演算法很大的一個優點在於，可以一次性計算出從該起點格子出發到達地圖上任意一個格子的最小 cost 值和對應的路徑。一個典型的遊戲應用場景是：《主題醫院》中，科室房間和其他的功能區域一旦建成，便可以以醫院大門或者分診諮詢臺為起點，計算一次到達所有這些區域或房間的位置的尋路路徑。只要醫院的佈局不變化，路徑就一直有效，當病人進入醫院後就可以根據他要去的地方直接提取路徑資料進行移動控制，不必再為每個病人單獨進行一次尋路。

• A* 演算法（ AStar ）

你可能已經發現，在上面所描述的演算法中， Leo 其實並不知道地圖上的寶箱在哪，他甚至都不知道地圖上是不是真的有寶箱，只是在不斷的盲目探索中碰巧發現了寶箱。但在遊戲設計開發中，許多時候， Leo 手裡其實是有這張藏寶地圖的，他跟我們一樣是上帝視角。這種前提下，他自然不會眼睜睜的看著寶箱在自己的東方，自己卻偏偏先往西方去探索，從而做出很多 “ 無用功 ” 。鼎鼎大名的啟發式尋路演算法 A* 演算法就是被賦予了這樣一點點 “ 智慧 ” ，卻在很大程度上提高了尋路的效率，使得它幾乎成為了遊戲開發中最常見的尋路演算法，以至於程式設計師們經常開玩笑道： “ 沒寫過 A 星尋路，都不好意思說自己是遊戲開發者。 ”

A* 演算法的整體思路步驟與 Dijkstra 演算法大致相同，只是在計算每個節點的 cost 時，將其拆分成兩部分之和，記作 F(i)=G(i)+H(i) ， G(i) 表示從起點到 i 點的移動 cost ， H(i) 表示 i 點到目的地的估計 cost ， F(i) 則表示從起點要移動到 i 點的最終 cost ，每一輪演算法中都選擇 F 值最小的節點標記為 “ 已探索點 ” 。我們假設 G 函式的計算方式與上一例子中的 cost 計算方式相同，為相鄰格子的移動 cost 的累加。假設 H 函式為 “ 要計算的格子到終點格子在 x 方向和 y 方向上要走的步數之和 ” ，即 “ 曼哈頓距離 ” 。那麼演算法的過程將如下所示：

與之前的演算法相比，該演算法不管在演算法步驟次數和探索的節點個數上都有相當大的效率提升，這得益於 G 和 H 兩個函式為演算法提供了 “ 可定製的目的性 ” 。將上面我們選取的 G 和 H 函式所表達的規則翻譯**話就是： “ 朝著靠近寶箱的方向，找一條好走的路。 ”G 和 H 選取的靈活性使得 A* 演算法在五花八門的尋路問題中都可以提供有效的解決方案。同時 G 和 H 的選取會直接影響到演算法的效能，比如上例中如果 H 選取的定義為 “ 要計算的格子到終點格子的直線距離 ” ，即 “ 歐幾里得距離 ” ，那麼尋路過程還會進一步得到簡化，起點正下方相鄰的格子甚至不會被標記為 “ 已探索點 ” 。

至此，我們終於掌握了一個真正好用的求解 “ 最短路徑 ” 的演算法。至於它在遊戲中的應用，就太顯而易見了：各種網路和單機遊戲中玩家通過點選目標位置使角色向其移動的實現、 roguelike 型別遊戲中怪物的仇恨追蹤等等。

• NavMesh 導航網格尋路

在之前所有的例子中，為了方便演算法說明，我們都選取了正方形網格地圖作為我們地圖的抽象模型。但是這種地圖模型有幾個致命問題：

1 、地圖規模很大時，比如要開發這幾年流行的開放世界無縫銜接的地圖型別，格子的尺寸如果選取太小，數量就會太多從而直接導致尋路演算法效率跌入谷底；格子的尺寸如果選取的太大，小物體的座標描述成本會增加，角色尋路位置的精確性也會降低。

2 、角色在正方形格子上基本只能實現四個方向或八個方向的移動，在除畫素風格以外的遊戲型別中會顯得不真實、不自然。畢竟如果能走直線，誰會非要去走個 90 度的大拐角呢？

3 、將格子當作節點來尋路，很難根據角色的身體特徵來對尋路進行調整，比如某些狹窄的空間只允許體型較瘦的角色通過。

作為另一個在遊戲開發中經常使用到的地圖模型和演算法， NavMesh 導航網格很好的解決了上面的問題，使角色的移動線路看起來更真實、更符合直覺。

地圖生成

我們要對地圖進行預處理，根據地圖上不同區域特徵將其劃分成許多鄰接的凸多邊形（通常是三角形），即 NavMesh ，如下圖所示，其中深紅色為障礙區域，粉色為可移動區域。

至於如何定義和生成這樣的地圖格式，有興趣可自行搜尋 NavMesh 生成演算法、 Delaunay 三角網格演算法、 Weiler-Atherton 多邊形裁剪演算法等關鍵字，涉及比較複雜的數學知識，這裡先不多贅述了。

尋路演算法

假設我們要從 A 點尋路到 B 點。首先我們把地圖上的所有三角形看成尋路演算法中的節點（類似於之前我們把一個正方形看成演算法中的一個節點），那麼三角形與三角形之間有公共邊就說明這兩個節點間是聯通的或有邊的（當然肯定必須是兩個非障礙三角形區域）。然後確定了 A 、 B 所在的三角形節點，我們就可以使用 A* 演算法來確定一片 “ 最短三角形聯通域 ” ，即圖中紫**域。 A* 演算法中的 G 函式可以選取為：相鄰三角形中心點（三個頂點的座標平均值）之間的直線距離。 H 函式可以選取為：三角形的中心點到 B 點的直線距離。

具體路徑確定

經過尋路演算法，我們確實找到了包含 A 、 B 兩個點在內的一條最短聯通域，聯通域的邊界內實際上都是可以任意移動的。但我們怎麼確定一條從 A 點到 B 點的最短移動路徑呢（即找到上圖中的黃色折線路徑）？通常我們使用 Funnel Algorithm ， Funnel 中文裡是漏斗的意思，這個詞比較形象的概括了這個演算法。如圖：

首先把漏斗的出口設定為起始點（圖 A ）。對於要穿過的每條邊，依次不斷縮小開口張角（圖 B-E ）。如果張角閉合了，那麼找到當前邊的拐點，並重新設定為漏斗的起始點（圖 F-G ）。重複該過程直到終點出現在開口中。依次連線起點、各個拐點以及終點，就形成了該次尋路的具體路徑。

導航網格尋路在大型 3d 遊戲中應用較多，比較成熟的遊戲引擎如 Unity 和 Unreal 甚至提供了可以直接使用的 api 介面，可見該演算法在效率、平滑度、真實性上的綜合優勢使其成為了行業內的主流選擇。而它帶給我更多的感受則是，優秀的演算法在很大程度上依賴於優秀的資料結構設計，當遇到瓶頸時，不妨跳出原有的模型架構進行思考，說不定問題會迎刃而解。

• 結語

至此，遊戲中比較經典的尋路演算法就介紹完了。本文只對演算法的大致思路進行說明，並沒有涉及實際編碼。實際上，這些演算法在面臨各種實際問題時都有相當大的優化空間，比如我們可以使用二叉堆來儲存 A* 演算法中的已經計算過 cost 值的節點，以降低最小 cost 選取的效能消耗；或者我們在計算導航網格的 A* 之前，直接對起點和終點進行射線檢測，如果射線沒有穿過障礙，則可將兩者直接連線作為最終路徑 。最後，希望各位大佬以後在遊戲中被怪物追殺到罵娘時、在對自動尋路無腦做任務的網路遊戲大翻白眼時，能順道感受一下游戲開發者在其背後所付出的汗水和傳遞的智慧。

戳“閱讀原文”get 流利說工作機會噢