NavMesh是目前遊戲中主流的尋路演算法之一，並且在Unity3D/UE4中提供相應的元件。由於牆內目前關於NavMesh原理的資料甚少，同時我也認為多一份講解，可能又會多一個理解角度，故特搬運一些資料回來。

該系列將結合一些論文資料，以及個人的理解進行解說（原文太多太長了，不想翻=。=）。由於個人水平十分有限，難免有不周詳之處，若有紕漏也懇請指正；至於一些具體最佳化實現、高階演算法等，亦不涉足，但求能觀其大略，借鑑思想而已。

另，由於本人沒有什麼學術背景，文中一些術語系憑直覺翻譯，理解和用詞恐多有出入，但也會盡量附上原文，供查詢資料。

本篇內容主要參考：

首先要明確，NavMesh實際上是一個對基於導航網格尋路體系的統稱，它不像A*的指向那麼明確，其具體實現有很多種方法，本篇將針對其中一種最簡實現進行介紹。

NavMesh是一種基於凸多邊形網格的尋路，其整個尋路流程至少分為導航網格構建（Navigation mesh construction）和尋路演算法兩個部分。其中導航網格構建在Unity中大致相當於烘焙（Bake），對一個場景烘焙後大概長這樣：

可以看到，它把可以行走的部分烘焙成為了藍色，由於其中穿插有不能通行的障礙物（高臺旁邊那根棒子），故根據其形狀進行了處理（地上畫的那些黑線），仍保持劃分出的每個區域為一個凸多邊形。事實上，導航網格體的構建演算法非常複雜，這部分留到後面再解讀，我們先來關注最經典的尋路部分。

顯然，一個經過處理的遊戲場景，大致可以抽象成下面這樣：

黑色是不可透過的地塊，黃點是每個地塊的中心點，黃線是將每個可透過地塊的中心點進行了連線。連線條件是：如果兩個可透過地塊有鄰邊，則連線

如圖，如果我們要從紅點走到綠點，應該怎麼尋路？首先更一般化地推廣，若要對任意一對點（起點和終點）尋路，無非以下三種情況：

兩個點在同一個地塊內，走直線；

其中一個點不在合法地塊內，此路不通；

兩個點在不同地塊，需要尋路。

顯然，回到圖中來，我們要解決的是第三種情況，這也是大多數時候我們要解決的、最感興趣的情況。針對處理後的地塊網格，一個最簡單的尋路方法是：

A*尋路

。

A*尋路公式：F = G + H

由上圖，經過計算可得每兩個黃點之間連線的長度，則G值易得；至於H值，一個最簡單的方法是將當前黃點與目標點直接連線，求其長度作為H值。

這樣，一個最簡單的NavMesh尋路部分就寫完了，最後在起點/終點所在地塊中將其與中心點（黃點）連線即可。

也就是說，上圖左一就是該方法得到的最終路徑。就。。。這麼簡單。。。

當然，最終結果也可以進行一些簡單最佳化，比如使用鄰邊中心點作為路徑而非地塊中心點（左二），或者沿著邊緣走（左三）。

清煮白水盅：Navigation Mesh （NavMesh） 原理講解（一） NavMesh概覽 & 一個最簡實現

清煮白水盅：Navigation Mesh （NavMesh） 原理講解（二） 當地塊都是三角形時的路徑最佳化

清煮白水盅：Navigation Mesh （NavMesh） 原理講解（三）A*在NavMesh上的完整流程

清煮白水盅：Navigation Mesh （NavMesh） 原理講解（四）持續規劃的A*（LPA*）和D* Lite