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