遊戲的尋路導航 1：導航網格

這篇文章，首先會介紹什麼是導航網格，它在 3D 遊戲中起到了什麼樣的作用。然後會介紹目前導航尋路最常用的第三方開源庫 RecastNavigation。接下來，就是重點講怎樣利用 RecastNavigation 來生成導航網格，並且利用這些導航網格來進行尋路。最後，會講到 RecastNavigation 的局限性。

什麼是導航網格？

導航網格（Navigation Mesh），也俗稱行走面，是一種用於在複雜空間中導航尋路、標記哪些地方可行走的多邊形網格數據結構。很多時候，它會被用於承載更多的功能，比如標識該位置的地形、該位置角色應該採用什麼動作（行走、游泳、攀爬）。

一個導航網格是由多個凸多邊形（Convex Polygon, Poly Mesh）組成的。為了避免混淆，下文這種專屬名詞都會用英文單詞代替。Poly Mesh 有些時候也會簡稱為 Poly，即上圖中的一個個色塊部分。注意，這裡的 Poly 專門指的是導航網格的組成單位。在導航網格中的尋路是以 Poly 為單位的。在同個 Poly 中的兩點，在忽略地形高度的情況下， 是可以直線到達的；如果兩個點位於不同的 Poly，那麼就會利用導航網格 + 尋路演算法（比如A*演算法）算出需要經過的 Poly，再算出具體路徑。

在 Unity 中，有提供專門的工具集 NavMesh 用於尋路導航。但這套工具有個最大的問題就是演算法、數據格式不開源，導致了遊戲服務端是無法使用，無法和客戶端保持一致的導航尋路邏輯。因此，在實際 MMORPG 開發中，一般會使用其他尋路方案。

RecastNavigation

目前遊戲最常用的導航尋路開源庫應該就是 RecastNavigation 了。坊間傳說 Unity、Unreal 底層其實也是用的這個庫。最初版的作者 Mikko Mononen 多年前曾經是 Crytek工作室 的 AI 工程師。大名鼎鼎的 CryEngine、孤島驚魂 就都是 Crytek 工作室開發的。出了 RecastNavigation 之後，這哥們後來又被 Unity 招安了。

RecastNavigation 是一個的導航尋路工具集，它包括了幾個子集：

1. Recast：負責根據提供的模型生成導航網格。
2. Detour：利用導航網格做尋路操作。這裡的導航網格可以是 Recast 生成的，也可以是其他工具生成的。
3. DetourCrowd：提供了群體尋路行為的功能。
4. Recast Demo：一個很完善的 Demo，基本上將 Recast 、 Detour 提供的功能都很好地展現了出來。弄懂了這個 Demo 的功能，基本也就了解了 RecastNavigation 究竟可以幹什麼事。

接下來，會重點講導航網格的生成和如何利用導航網格進行尋路。

導航網格的生成

導航網格的生成依賴於場景模型的設計，有手動生成，有自動生成，有兩種方式相結合的方式。如果場景簡單，那麼可以由場景設計師在構造場景模型時，手動拉一個場景的導航網格。但對於大規模複雜的場景，一般會讓設計師剔除大量不可能到達的建築、裝飾物，做出一個簡化的邏輯面模型，再根據這個模型去自動化生成導航網格。

Recast 庫就是專門用於自動化生成導航網格的。有一個文章系列 Study: Navigation Mesh Generation，圖文並茂詳細地介紹了 Recast 生成導航網格的過程，非常推薦閱讀。我在這裡就根據這個系列，簡要地羅列一下導航網格生成的相關概念和流程。

導航網格的生成會分為下面幾個步驟：

1. 場景模型體素化（Voxelization），或者叫「柵格化」（Rasterization）。
2. 過濾出可行走面（Walkable Suface）
3. 生成 Region
4. 生成 Contour（邊緣）
5. 生成 Poly Mesh
6. 生成 Detailed Mesh

第一步，體素化。顧名思義，就是將整個場景模型，都轉化為體素（Voxel）。

這一步處理和 GPU 渲染管線的光柵化流程概念是一樣的，都是將矢量的模型信息（三角形），轉化為點陣信息（像素或者體素）。開個腦洞， 假設將來有個全息顯示器，可以在一個空間內渲染出制定的模型內容，渲染的最基本單位是體素而不是像素。那麼到時的「顯卡」很可能就是採取類似的模型體素化過程。

第二步，根據哪些體素頂部有足夠的空間可供行走，以及根據設置的參數，剔除過濾掉一些不符合要求的體素，初步計算出行走面。

第三步，生成 Region。根據計算出來的行走面，使用特定演算法，將這些可行走面切分為一個個盡量大的、連續的、不重疊的、中間沒有「洞」的「區域」，這個區域就叫 Region。由於不重疊，也就不再需要高度信息，因此在這一步就把問題從三維空間轉換到了二維空間。這一步的演算法，Recast 提供了三種演算法：

• 分水嶺演算法（Watershed partitioning）：最經典、效果最好，但處理比較慢，一般用於離線處理。
• Monotone partioning：最快且可以保證生成的是不重疊、沒有洞的 Region，但是生成的 Region 可能會又細又長，效果不好。
• [Layer partitoining][Layer partitoining]：速度、效果都介乎分水嶺演算法和 Monotone partioning 之間，比較依賴於初始數據。

Region 雖然是不重疊且沒有洞的區域，但仍然有可能是凹多邊形，無法保證 Region 內任意兩點在二維平面可以直線到達。因此，接下來的步驟，就是為了將每個 Region 拆分為多個凸多邊形。

第四步，生成 Contour。

在這一步中，根據體素化信息和 Region，首先構建出描繪 Region 的 Detailed Contours（精確輪廓）。由於 Detailed Contour 以體素為單位構建邊緣的，因此是鋸齒狀的。

第五步，生成 Polygon Mesh。

由於大多數演算法處理需要基於凸多邊形，因此這一步就是將 Simplified Contours 切分為多個凸多邊形。凸多邊形在代碼中會簡稱為 Polygon 或 Poly。

在一個 Polygon 中，任意兩個點在二維平面內都是可以直線到達的。因此，Polygon 是 Detour 的基本尋路單元。

第六步，就是把 Polygon 繼續做三角形化，生成了 Detailed Mesh。

如果把場景的拓撲結構看成一個無向圖，其中每個 Polygon 是一個頂點。那麼 Polygon 只是在拓撲結構上解決了尋路問題，但是為了在具體尋路過程中，讓角色更加貼合地面地行走，需要一些更精確的地形信息（比如高度）。因此還需要將 Polygon 拆分為更貼近地表形狀的 Detailed Mesh。

至此，導航網格的生成就結束了，Poly Mesh 和 Detailed Mesh 是最終需要的數據，需要存檔。其他都是屬於中間數據，是可以被釋放掉的。在實際應用中，可能會保存某些中間數據（比如體素化數據），做其它的用途。

利用導航網格做尋路

有了 Poly Mesh 和 Detailed Mesh 之後，使用 Detour 尋路就變得很簡單了。構建一個 dtNavMeshQuery 實例，既可支持在 Poly Mesh 顆粒度的尋路，返回結果是路徑途徑的 Poly 數組；也可以支持在 Detailed Mesh 尋路，返回的是一個坐標點數組形式的路徑。

RecastNavigation 的局限性

在 RecastNavigation 中，一個用於尋路的單位稱為 Agent（代理）。 作者 Mikko Mononen 曾經在 RecastNavigation 的 Google 討論組中提到項目的一些設計前提：

1. 假設 Agent 都是在地面行走且收到重力影響的。
2. 假設 Agent 始終保持直立姿態的，即平行於重力方向。

Agent 不能飛，甚至不能跳。即使「走」在一些斜坡上，也始終應該是直立姿態，而不能是垂直於地表（即地表法線方向）。有了這些設計前提，才可以更方便地簡化體素化時的數據結構，簡化 Walking Surface 的計算生成。

因此，現在國產武俠類 MMORPG 里大行其道的輕功、甚至御劍飛行，是無法只單純依賴 RecastNavigation 的數據去實現的。特別是對於某些具有層次錯落結構的地形，就非常容易出現掉到兩片導航網格的夾縫裡的情況。這類機制的實現需要其他場景數據的支持。

而像《塞爾達傳說：曠野之息》的爬山、《忍者龍劍傳》的踩牆這種機制，則會在生成導航網格的階段就會遇到麻煩。因為設計前提2的存在，RecastNavigation 是無法對與地面夾角小於或等於90°的牆面生成導航網格的。因此需要從另外的機制、設計上去規避或處理。不過，貌似 Unity 2017 已經可以支持了在各種角度的牆面生成導航網格了：Ceiling and Wall Navigation in Unity3D。

RecastNavigation 的另外的一個局限性則是，對於開放地圖並不友好。如果需要判斷遠距離的兩個點是否互相可到達，則需要將這個範圍內的所有導航網格載入完，才可計算出路徑，才可以判斷是否可達到。即，「計算A點是否可走到B點」 和 「計算從A點到B點的具體路徑」，這兩個問題是等價的。因此，當長距離尋路時，玩家如果中途取消，則後續路徑的計算量就會被浪費。

基於這一點，下一篇我們就來聊聊《遊戲的尋路導航2：開放地圖的導航》。