astar pathfinding 縫隙阻擋方案

我們上一個項目是RTS項目，剛開始尋路問題解決方案過程遇到過跟你相似的疑惑，修改探索和調教了很長時間，分享幾點僅供參考下吧。

先上結論：采用了兩層結構 A Start Pathfinding Project Pro + Unity NavMesh。

1.主體尋路方案使用 A Start Pathfinding Project Pro 這個插件中傳統的網格形式，并進行了深度修改擴充，主要是滿足尋路過程的通路性需要考慮到機關半徑大小，這樣尋路精度高；

2.使用 Unity NavMesh 系統作為尋路過程中的碰撞系統，因為你說的很對，這個尋路插件的碰撞有問題，稍後解釋。

以上兩部分組成“尋路算法+精确碰撞”。

說下以上方案的原因和細節。

1.1 NavMesh 尋路速度快但不夠精确，rts還是适合使用傳統的四方形 NavGrid 格子尋路，而且現有的任何尋路算法預設都是不支援考慮尋路機關半徑大小對尋路過程的影響，但我們策劃絕不允許1米寬的縫隙被一個兩米寬的胖子擠過去，如果使用 navmesh 并且動态生成阻擋會出現尋路路徑是有了，可是由于碰撞問題大的機關會卡在縫隙這裡來回“發抖”；這個隻能自己動手修改，是以我們買了該插件然後自己從裡到外修改，具體修改算法原理和修改後的示意圖，你可以參考這裡：http://www.cnblogs.com/yaukey/p/rts_unit_traverse_size_based_path_finding.html。 修改完後，每次尋路會将機關的直徑大小當做尋路參數之一傳入進行尋路。

1.2 使用這個插件開啟兩個線程左右來尋路是我後來調教後一個比較理想的結果，然後是地圖中各種機關會出生和死亡，當機關站定不動，需要生成阻擋；移動了需要移除阻擋恢複此處的通路性，通過再修改下插件中的 DynamicObscule 這個元件（原生功能太簡單）來實作；我們具體是，每個機關都有一個對應的大小的 CapsuleCollider 空對象挂上這個腳本，機關站定将該物體放置到機關的位置并激活它，機關移動隐藏該空物體即可，這個腳本會引起地圖通路性的更新，這個更新是多線程的，這一點是要注意的，通過回調事件來做響應的事情，切記不要在同一幀或者下一幀去做，不能保證。這樣就能讓整個地圖一直根據機關來更新通路性。

2.尋路的通路性問題解決了，現在來解決碰撞問題，這個插件自帶了碰撞算法，使用的 rvo 算法，但是據我當初各種調教實驗，它的碰撞都達不到我們的要求，機關多了擁擠的時候，總是會有些機關站立後變得重疊了，最不能接受的是兩個機關完全重疊。在這裡我花了相當多的時間都不能調教修改的滿意。後來想起來 recastnavigation 作者親口說過雖然 Unity 的 NavMesh 基于此，但是 Detour 系統經過深度的改寫，Detour 包含了巡航和碰撞，而實際使用也發現 NavMeshAgent 之間的碰撞是很精确的，于是我想了個取巧的辦法，給地表再鋪一層跟AStar 插件的尋路面積一樣大的 NavMesh，但是沒有任何的阻擋（了解為一片純藍色），同時給尋路機關添加一個 NavMeshAgent，然而這個東西隻用它的碰撞，而不使用尋路（沒有阻擋，任何尋路都是兩點直線，可以考慮幾乎無開銷），這樣最後實際的碰撞效果才算達到我們滿意的效果。

以上就是我所說的兩層含義，我再說下坑和問題。

1.當初開發Unity版本是5.3.7-5.3.8，插件版本5.x，尋路插件中底層會有 Physics.CheckCapsule調用，但是多線程大量調用，會導緻底層 PhysX 實體引擎崩潰，遊戲閃退，不必現但是大量的話很容易一下就挂，插件官方論壇也有這個 bug 讨論，後來我将此換成了兩個 Physics.CheckSphere 調用，目前 2017版本沒有測試過；

2.我在1.2中使用的方法，在 uwa 測試中每次都是 Dynamic Collider 超标，這個需要自己取舍了，但是總體我們遊戲的瓶頸不在尋路一塊，消耗在這些測試中看來比較理想；

3.插件中由于是多線程更新，有很多的完成事件回調，基本都是利用這些連結遊戲系統中，不夠了自己加，否則依然是容易在未更新完成時得到錯誤的結果；

4.有可能的話再優化下内部的一些堆記憶體配置設定，并且和遊戲系統結合後注意釋放和斷開引用，否則容易記憶體洩漏，造成尋路插件被引用以至于後面引用很長一串對象都不得釋放。

5.尋路精度和碰撞精度在遊戲中的表現，需要花比較多的時間去調教參數，有時候表現不好未必是方案不好，然後如果你們對實時同步性要求較高，這個方案還必須再進一步完善和擴充下。

我們使用這個尋路方案的項目是：《戰地指揮官》，你可以下載下傳看看尋路是否符合你的要求，蘋果安卓各平台都有：）

以上是我暫時想起來的一些心得，希望對你有幫助。