3d 游戲的尋路算法主要還是A* （a-star，A星）使用的比較廣泛，它有快速、路徑短，不成環等優點，在orge，unity等引擎中得到了廣泛的使用。
A*的最初設計是基于2d平面，對于3d 尋路就需要先對場景網格化，生成平面，把3d的問題轉化為2d的問題，然后就可以通過A*進行尋路。
3d 游戲尋路大致分為2部分：navmesh(3d轉2d)、A*算法
網格數據（navmesh）生成：
1、Voxelization – Create a solid heightfield from the source geometry.
2、Generate Regions – Detect the top surface area of the solid heightfield and divide it up into regions of contiguous spans.
3、Generate Contours – Detect the contours of the regions and form them into simple polygons.
4、Generate Polygon Mesh – Sub-divide the contours into convex polygons.
5、Generate Detailed Mesh – Triangulate the polygon mesh and add height detail.
相關概念：
體素化Voxelization
向量空間(vector space) 到 體素空間(voxel space) 的轉換. 用到的是叫保守體素化(Conservative voxelization) 的算法, 它保證了每個多邊形面都能完全被生成的三維象素(voxel)包裹。
體素化后, 生成的都是可尋路的高度場(heightfield)信息, 不可尋路部分被剔除.這一步是從一個固態高度場(solid heightfield) 生成一個開放高度場(open heightfield) 的過程, 一個開放高度場表示在一個固態空間上可能尋路的平面.
區域生成Region Generation
定義,哪部分的面是可以尋路的, 并且把尋路區域分隔成連續的平面以供最后生成簡單尋路多邊形.
最終結果, 墻體,圍欄, 柱子, 桌子底等不可能尋路的平面在這步根據鄰居信息和分水嶺算法(the watershed algorithm) 被剔除, 一些孤立的小局域(比如桌子表面) 也被剔除.
樓梯, 雖然是多級, 也會被當做一個平面(綠色). 樓梯扶手等平面也被剔除.
輪廓生成Contour Generation
完成從體素空間回到向量空間的轉換. 區域(region) 輪廓將被"遍歷(walk)", 形成簡單的多邊形.其中, 有些區域被合并, 多邊形的邊更平滑, 邊長度被優化. 此時，可尋路區域已經被一些簡化的多邊形所表示。
凸多邊形生成Convex Polygon Generation：把多邊形切分為三角形, 而后盡量合并的方式
精細網格生成
Detailed Mesh Generation：
通過"德勞內三角化"(Delaunay triangulation) 算法三角化成包含高度信息的三角形，頂點信息也會在這里補到各個三角形上, 以保證高度信息和模型保持一致.
A* （a-star，A星）大致描述：
1、把起始格添加到開啟列表。
2、尋找開啟列表中F值最低的格子(當前格)，將其切到關閉列表
3、對相鄰的8格最如下處理：如果它不在開啟列表中，把它加進去 ；如果它已經在開啟列表中，用G值為參考檢查新的路徑是否更好。更低的G值意味著更好的路徑。如果這樣，把這一格的父節點改成當前格，并且重新計算這一格的G和F值。如果你保持你的 開啟列表按F值排序，改變之后你可能需要重新對開啟列表排序。
4、當把目標格添加進了關閉列表，這時候路徑被找到；如果沒有找到目標格，開啟列表已經空了，這時候，路徑不存在。
最后，保存路徑，從目標格開始，沿著每一格的父節點移動直到回到起始格。這就是需要的路徑。
(1-4是個循環過程)
附注：
開啟/關閉列表：臨時記錄區，算法中的變量
G值：從起點A，沿著產生的路徑，移動到網格上指定方格的移動耗費。
H值：從網格上那個方格移動到終點B的預估移動耗費。
F值：G + H
父節點：記錄最短路徑
A*（A-Star)算法：公式： f(n)=g(n)+h(n)
f(n) 是節點n從初始點到目標點的估價函數
g(n) 是在狀態空間中從初始節點到n節點的實際代價
h(n)是從n到目標節點最佳路徑的估計代價
最短路徑，關鍵在于估價函數h(n)：
估價值h(n)<= n到目標節點的距離實際值，搜索的點數多，搜索范圍大，效率低。但能得到最優解。
估價值>實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。
估價值與實際值越接近，估價函數取得就越好
對幾何路網來說，取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy- ny)*(dy-ny))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。
算法的搜索過程：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,->算X的估價值。
偽代碼：
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點)
break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小于OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小于CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
并將X插入OPEN表中; //還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
}
關于尋路：可以用開源的 RecastNavigation ，里面就有上述算法的實現和demo，支持unity 3d的尋路。
可以用來做地圖服務器的案例。
https://github.com/memononen/recastnavigation
unity 3d導航數據的導出要將任意的 Mesh 轉換成 rcPolyMes，生成相應的多邊形和鄰邊；這里每個多邊形設置為基礎的三角形，
然后用內建的函數來優化合并多邊形，接著再建立鄰邊即可，這樣就可以得出最優化的 NavMesh 最終數據。
注意：Unity 在導出 NavMesh的數據是包含 NavMesh 中得多邊形 Poly信息，可以利用這個直接建立多邊形，這樣下來數據最接近unity本身的數據。