|
最近花了幾個月的時(shí)間實(shí)現(xiàn)了導(dǎo)航網(wǎng)格尋路和導(dǎo)航網(wǎng)格自動生成。 □導(dǎo)航網(wǎng)格數(shù)據(jù)結(jié)構(gòu)定義 由于數(shù)據(jù)之間有著層級關(guān)系，所以采用XML進(jìn)行定義。 □導(dǎo)航網(wǎng)格尋路 1.以凸多邊形為節(jié)點(diǎn)，以可走邊為relation，進(jìn)行A星尋路。 2.尋路結(jié)果使用LOS算法進(jìn)行路徑平滑，其中視線采用Z軸橫切面而不是直線來實(shí)現(xiàn)。 3.尋找凸多邊形。先使用八叉樹進(jìn)行空間劃分，然后根據(jù)點(diǎn)跟AABB盒相交進(jìn)行查找。 □導(dǎo)航網(wǎng)格自動生成 主要是提供 1.Cleaner：合并重復(fù)的頂點(diǎn)（即焊接頂點(diǎn)）、刪除共線情況、刪除沒有用到的頂點(diǎn)、刪除沒有的poly（即刪除不規(guī)范、刪除面積過?。?、重置頂點(diǎn)ID和Poly ID。 2.MergingPolys:合并多邊形，包含對相同邊進(jìn)行合并和32合并。 3.PolygonClipping:多邊形剪切，地形數(shù)據(jù)必須是三角網(wǎng)格（若不是，可以使用Triangulate三角化）。輸入障礙物后，使用包裹法（Jarvis步進(jìn)法）進(jìn)行構(gòu)造凸多邊形，然后再對各個三角網(wǎng)格進(jìn)行剪切操作。 4.Triangulate:三角化。 5.GeneratingEdges:生成邊操作。 6.Deleter：刪除指定頂點(diǎn)、刪除指定poly、刪除指定Edge 7.BoudingBoxCreater:障礙物的輸入可以使用AABB盒，但只對有連接關(guān)系的三角網(wǎng)格進(jìn)行生成包圍盒，如一座橋上的兩個柵欄，必須為它生成2個AABB盒，而不能只生成一個。 8、NavMesh：導(dǎo)入、導(dǎo)出、遍歷操作等
截圖： 1、（未路徑平滑）
2.路徑平滑后
所花時(shí)間：0.412872 ms（跟網(wǎng)格數(shù)量有關(guān)）
參考資料： 1. 焊接頂點(diǎn),《3d數(shù)學(xué)基礎(chǔ)：圖形與游戲開發(fā)》14.4.2節(jié) 2. 32合并， 《人工智能游戲編程真言》里面有一篇 “4.3 建立接近最優(yōu)的導(dǎo)航網(wǎng)格”專門介紹如何建立 基于導(dǎo)航網(wǎng)格的3d尋路，4.3.6節(jié)。 3. http://www./archives/000152.html 4.生成邊： http://www./code/edges.php 5.根據(jù)點(diǎn)生成三角網(wǎng)格，delaunay算法， http://www./tmp/delaunay.htm http://local.wasp./~pbourke/papers/triangulate/ 6.幾何操作：《計(jì)算機(jī)圖形學(xué)幾何工具算法詳解》 7. 。。。。。 |
|
|
