在3D MMO或者其他類型的遊戲中，通常需要進行尋路處理，地圖針對尋路有多種方案，比如劃分格子，凸多邊形等，本篇介紹一種比較常用的navigation mesh的方式來進行尋路。不過整套navmesh的算法比較複雜，沒有深入的研究寫不出來，我們使用網上開源的解決方案，google的recast方案。我們使用的開發環境是win7 + vs2013.
一、伺服器端recast的安裝和使用
1、先從github上面下載下傳recast的源代碼
2. 源代碼下載下傳下來之後，需要我們自己進行編譯，recast使用預編譯工具premake，需要premake.lua。先下載下傳lua，然後單獨下載下傳premake5，否則premake5.lua不能使用。将下載下傳好的premake.exe放到和premake5.lua的同一目錄下，然後在控制台運作premake.exe vs2013(根據自己的IDE版本号)，就會生成vs2013的解決方案sln檔案。
2. recast的測試程式中，用到了SDL的相關庫，這個比較簡單，下載下傳一個SDL-devel的庫就可以了，然後看下RecastDemo裡面的配置目錄，copy進去就可以編譯通過了。中間編譯的時候，可能由于vs2013版本，會提示min，max這些函數沒有定義，隻要#include對應的STL庫頭檔案就可以了
3. 成功編譯了recast相關的庫，Detour，Recast等，我們一開始對于如何使用recast可能一點概念都沒有，不過recast已經考慮到了這一點，工程中有一個RecastDemo程式，是用來示例如何使用recast的。
4. 使用recastDemo，我們可以根據場景的.obj檔案，來生成navmesh，和導入我們自己生成的navmesh，不過這都是我們通過recast開源工具生成的。實際的遊戲中，我們需要的是從用戶端生成的navmesh，然後導入到伺服器中進行解析。
二、Unity3D用戶端的navmesh生成
unity3D是自帶navmesh agent的，可以自己生成navmesh，并且導出navmesh，不過它的導出navmesh，我查下來是需要自己寫代碼的，而且navmesh agent是修改過導出navmesh檔案格式的，也就是說我們recast C++代碼是不能直接使用的。後來我又搜尋了一下recast for Unity這個插件，這個插件是有源代碼的，不過如果正常購買需要＄50。
對于這個插件當時研究了比較長的時間，一開始導出了一下它的navmesh格式，然後用C++recast導入試了一下，發現格式肯定是不一樣的了。然後就仔細研究了一下兩邊生成navmesh時的格式差異，針對TileMesh存儲的時候，兩邊是不一緻的，本來想直接修改C#代碼來達到兩邊一緻，不過由于對C#的序列化不夠熟悉，就放棄了。不過應該可以直接改成一緻，這個後面有時間可以再深入研究一下。
後來使用了KBEngine修改過的CritterAI，它導出來的navmesh檔案，在KBEngine中是能直接使用的。然後把我們伺服器中解析navmesh的格式，改成和KBEngine一緻就可以了。代碼還是非常簡單的，代碼如下：
bool NavMeshLoader::load_cai(const char*path) {
FILE* fp = fopen(path, "rb");if (!fp) return false;//Read header.
NavMeshSetHeader_CAI header;
size_t readLen= fread(&header, sizeof(NavMeshSetHeader_CAI), 1, fp);if (readLen != 1)
{
fclose(fp);return false;
}if (header.version !=NAVMESHSET_VERSION)
{
fclose(fp);return false;
}
dtNavMesh* mesh =dtAllocNavMesh();if (!mesh)
{
fclose(fp);return false;
}
dtStatus status= mesh->init(&header.params);if(dtStatusFailed(status))
{
fclose(fp);return false;
}//Read tiles.
for (int i = 0; i < header.tileCount; ++i)
{
NavMeshTileHeader tileHeader;
readLen= fread(&tileHeader, sizeof(tileHeader), 1, fp);if (readLen != 1)
{
fclose(fp);return false;
}if (!tileHeader.tileRef || !tileHeader.dataSize)break;
unsignedchar* data = (unsigned char*)dtAlloc(tileHeader.dataSize, DT_ALLOC_PERM);if (!data) break;
memset(data,0, tileHeader.dataSize);
readLen= fread(data, tileHeader.dataSize, 1, fp);if (readLen != 1)
{
fclose(fp);return false;
}
mesh->addTile(data, tileHeader.dataSize, DT_TILE_FREE_DATA, tileHeader.tileRef, 0);
}
fclose(fp);
m_navMesh=mesh;
m_navQuery=dtAllocNavMeshQuery();
status= m_navQuery->init(m_navMesh, 2048);if(dtStatusFailed(status))
{return false;
}return true;
}
KBEngine中和RecastDemo中解析navmesh主要就是NavMeshSetHeader頭結構不一緻，其他的都一樣，是以還是比較簡單的。
能正常解析navmesh檔案之後，就是對地圖進行尋路了，在這裡主要使用了RecastDemo中尋路的代碼，進行了本地化的修改。
三、 使用recast navigation遇到的問題
1、其中有段時間，我對于用戶端生成的navmesh，和伺服器生成的navmesh在坐标系上不一緻，感覺很困惑，甚至想要不要自己用3DMax之類的工具重新導入地圖模型，然後修改坐标系，這現在看來很可笑，主要還是對于navmesh的生成原理不是很懂。其實用戶端生成的navmesh是帶有自身坐标系和相對坐标的。之前之是以有那種困惑，是因為伺服器用的是recastDemo中生成的navmesh，用戶端生成了自己的，根本就是兩種世界，兩種坐标，當然不一緻了！！
2、其實CritterAI的底層是C++寫的dll，通過unity導入進工程，然後生成navmesh的，隻要符合unity使用dll的規則，我們其實也可以使用recast的源碼，然後改成unity能夠使用的dll來導出navmesh。這個後面可以試試