將網格轉換爲圖形進行導航

旁註：我不確定此問題是否屬於遊戲開發堆棧交換站點 - 但是，我覺得它屬於這裏，因爲雖然上下文是遊戲，但算法本身我期待的實現是相當應用程序不可知論的。此外，我並不是在尋找高級技術，因爲我覺得我已經建立了一個技術，但是我正在尋求針對某個問題的更具體的幫助。無論如何，對於這個問題：將網格轉換爲圖形進行導航

嘿大家好！

我正在開發一款多人遊戲，要求服務器可以爲服務器控制的實體執行尋路。服務器是一個直接的C＃應用程序，客戶端使用Unity遊戲引擎。在服務器上使用Unity不是一種選擇。此外，我想完全避免本地圖書館。

我已經檢查了Detour for pathfinding，雖然他們有C＃端口，但我寧願自己實現實際尋路位;因爲這個過程足夠直接，我希望它能夠滿足我的需求，以便與服務器上的現有組件配合良好。

Unity帶有對Recast/Detour的內置支持。這很好，因爲我可以在Unity中使用Recast來生成導航網格;然後使用我自己的路徑查找在服務器上使用它。問題是，我似乎無法找到一種基於Unity/Recast創建的網格生成圖形的正確方法。

我需要做的是在內存中創建一個圖形，其中每個節點都是網格中的一個三角形，並且圖形的每個邊連接兩個彼此相鄰的三角形。

我能夠從Unity的API中提取的唯一數據是生成的網格的頂點和三角形索引，因此我需要重新構建自己的圖。我的第一個實現只是爲每個三角形創建一個節點，如果該三角形與另一個三角形共享另外兩個點，則在它們之間創建鏈接 - 形成圖形的邊緣。

雖然這對於大多數網格很有用，但它並不盡如人意，因爲Unity似乎正在吐出可以在區域（多邊形）之間建立連接（邊）的網格，即使它們不共享兩個頂點。下面是統一覆蓋一個例子其導航網格生成到我的水平幾何結構（統一做合併三角形成凸多邊形，而我的代碼不 - 然而，問題仍然在任一情況下存在）

Unity Navmesh

在這種例如，我生成的圖需要連接由白線分隔的多邊形（我找不到任何說明爲什麼它在Unity中呈現爲白色的文檔），但由於它們只共享一個頂點，所以無法這樣做。

我想知道是否有一個有效的算法來檢測這些情況。我在想什麼做的是有它，這樣的多邊形被認爲是連接：

if (sharedVertexCount == 2) 
    connectPolygons() 
else if (sharedVertexCount == 1) 
    Vector3[] parallelLine = findParallelLineSharedByBothPolygons() 
    if (parallelLine != null) 
     Vector3 otherPoint = getUnsharedPointInLine(parallelLine) 
     if (isPointInLine(parallelLine, otherPoint)) 
      connectPolygons()

我認爲這應該工作，但是我沒有找到一種方法來有效地做到這一點。另外，我在「isPointInLine」實現方面遇到了一些麻煩，因爲顯然我的數學技能比我想象的更加生疏。

無論哪種方式，有是一個更簡單的解決方案;但我沒有發現任何網上的內容，指出我朝那個方向發展。這就是爲什麼我問你好人如果有什麼我可以做的，以有效地將生成的導航網格變成連接多邊形的圖形。無論是幫助我實現isPointInLine還是將我指向一個更明智的算法，都會受到無以倫比的讚賞。

來源

2014-02-08 LittlePip

當談到尋路時，大多數方法都提出了一個專用於導航的預製數據結構，它更易於使用（除非您的圖形數據結構足夠簡單 - 在這裏不是這樣）。

我建議你幾個解決方案：

基於體素的導航系統：實施與布爾的3D陣列（罐/'噸通）的體素系統，以及應用和星空或D Star算法就可以了。
知道AI可以通過的路徑向量。
兩個系統的合併（主要路徑使用已知路徑矢量，而網籤素它與假相交- 這可能是你正在尋找的解決方案

來源

2014-02-08 11:59:49

。那麼，我當然可以拒絕Unity使用Recast並編寫我自己的自動導航網格生成器;但是從Unity的導航網格導出的三角形，我非常接近使用它作爲我的尋路系統的輸入的工作實現，基本上，重新提示這種方法不值得麻煩嗎？ – LittlePip

這種方法是密封的，對於大多數應用程序（遊戲等），您不需要密封解決方案，您需要一個簡單易維護的解決方案。而我是軟件基礎設施設計師，我喜歡密封解決方案lol ... –

D \ *已經過時，如果您確實需要它，您應該使用D \ * - Lite代替。但是，即使D \ * - Lite對於遊戲來說也相當罕見，因爲它比A \ *複雜得多。請參閱[這裏]（http://cstheory.stackexchange.com/questions/11855）瞭解更多信息。 –

將網格轉換爲圖形進行導航

回答

相關問題