Recastnavigation解析

一、什麼是Recastnavigation

Recastnavigation是一個用於Mesh導航、尋路方面的底層庫，由Mikko Mononen製作，可以高效、精確地為遊戲、模擬、虛擬現實等領域中的靜態或動態環境生成導航網格。Recastnavigation利用了構建和搜索圖形存儲在網格上的路徑的技術，並具有強大的問題空間分割，自適應代理大小，快速尋路和緩存以及多線程支持。Recastnavigation庫開發始於2006年，目前支持Windows，Mac OSX，Linux和Android。Recastnavigation在遊戲、工程、兵棋推演等領域廣泛應用。

二、Recastnavigation的特點

Recastnavigation有哪些突出和獨特的特性卓越，可以適應需求呢？以下是Recastnavigation的幾個特徵。

1. 三角形網格建模

Recastnavigation可以處理多邊形，但最好使用三角形作為Recastnavigation的輸入。在三角網格上可生成更準確的、沒有分gon的或漏洞的多邊形地形。

2. 智能拼接單元格：

Recastnavigation使用一維線網格，而不是二維網格作為底層數據結構，它有助於Recastnavigation在巨大的網格上解決舒適取出的問題。大規模的單個網格會導致性能問題和內存使用問題，Recastnavigation將代理單元格子分成矩形網格進行處理，從而可以處理大規模世界。Recastnavigation採用粘合Trimmed K-D樹的局部化搜索，以避免在搜索路徑時耗費太多時間。

3. 凸性體積的智能代理縮放

Recastnavigation可以根據需要自動縮放代理，以適應現實世界中的不同類型的代理。Recastnavigation可以自適應改變代理的大小，區分原始數據的地形和代理的大小之間的關係，可以產生更加精確的地圖，並以更快的速度計算出路徑。

4. 快速路徑檢索

Recastnavigation相對Agenta*和其他技術有較快的尋路演算法。Recastnavigation緩存最短路徑，緩存同一個代理請求的路徑，這就降低了尋路時間。

5. 多線程優化:

Recastnavigation被優化了多線程，它的路徑搜索演算法非常可擴展，使Recastnavigation能夠在具有多核心處理器的現代計算機上快速計算路徑。

三、如何使用Recastnavigation

Recastnavigation的使用步驟如下：

1. 獲取Recastnavigation

Recastnavigation可以在網上下載最新的源,當前最新的版本為1.5.1。開發人員需要將源代碼包解壓並將其包含在程序項目中。

2. 載入三角形網格

首先載入三角形網格。Recastnavigation最好處理通過三角形，因此在進行人工建模時，需要確保將建模頂點轉化成三角形。將三角形網格導出為OBJ格式的文件，並在RCA濾芯中使用它。

3. 配置代理

代理有始於延續的過程。Recastnavigation通過代理評估代理的高度、寬度和長度，並為每個代理確定一個縮放半徑。使用單角代理時，需要根據代理尺寸設置縮放環境變數，以保證代理可以在地形上充分運用。

4. 構建導航網格數據

輸入三角形網格和代理尺寸，執行構建導航網格，Recastnavigation將生成和存儲導航網格數據。

BuildContext ctx;
InputGeom inputGeom;
if (!inputGeom.loadMesh(&ctx, sceneFilename)
    return;//導入地形
float* bmin = inputGeom.getMeshBoundsMin();
float* bmax = inputGeom.getMeshBoundsMax();
float* vertices = inputGeom.getMesh()->getVerts();
int nverts = inputGeom.getMesh()->getVertCount();
int* faces = inputGeom.getMesh()->getTris();
int ntris = inputGeom.getMesh()->getTriCount();
rcHeightfield* solid = rcAllocHeightfield();
rcChunkyTriMesh* chunkyMesh = rcAllocChunkyTriMesh();
if (!solid || !chunkyMesh)
    return; //無法正常申請相應大小的內存

5. 搜索路徑

在構建導航網格後，就可以開始在導航網格上執行搜索路徑。根據需求設置起點和終點，調用尋路演算法得到路徑。

rcContext ctx;
rcPolyMesh* m_navMesh = nullptr; //導航網格信息
rcCompactHeightfield* m_chf = nullptr;  //高度圖信息
rcConfig m_cfg;    //方格配置信息
rcPolyMeshDetail* m_pmdtl = nullptr;  //網格細節，用於尋路路徑的偏移量
rcContext m_ctx;   //地形數據信息
dtNavMeshQuery* m_navQuery = nullptr;  //查詢導航網格信息
//設置起始位置和目的地位置
dtPolyRef endPoly;
float endPos[3] = { dest[0], dest[1], dest[2] };
float startPos[3] = { start[0], start[1], start[2] };
dtStatus findStatus = m_navQuery->findNearestPoly(startPos, queryExtents, &filter, &m_startRef, 0);
dtStatus status = m_navQuery->findNearestPoly(endPos, queryExtents, &filter, &endPoly, 0);
//尋找路徑
int npath = 0;
status = m_navQuery->findPath(m_startRef, endPoly, startPos, endPos, &filter, polys, &npath, MAX_POLYS);
if (status != DT_SUCCESS || !(npath > 0))
    return; //尋路失敗

四、Recastnavigation的應用

Recastnavigation可以應用於虛擬現實、遊戲、工程、軍事模擬等眾多領域。以下是Recastnavigation的一些應用示例。

1.遊戲領域

顯然，尋路是遊戲的重要組成部分，Recastnavigation作為一款優秀、可靠的尋路引擎，已被許多遊戲和遊戲引擎所採納。例如：Unreal Engine 4、Unity、Cry Engine等。

2.軍事模擬領域

在軍事模擬領域，Recastnavigation可以用於模擬計算中的路徑搜索，以及部隊、交通工具移動的指揮和控制。Recastnavigation在模擬領域的精度和可靠性更有優勢。

3.虛擬現實領域

在虛擬現實領域，Recastnavigation可以為VR世界的導覽和交互提供導航解決方案。

五、總結

Recastnavigation是一款優秀、高效、可靠的尋路引擎，並具有智能代理縮放、快速路徑檢索、多線程支持等優秀特點。Recastnavigation已廣泛應用於遊戲、工程領域、兵棋推演領域等多個領域。如果你需要一個高效且可擴展的尋路解決方案。那麼，請嘗試適用Recastnavigation。