關於凸多邊形網格尋路的理解?

01-30

查了一些資料, 但似乎不同資料的解釋不一樣. 比如使用 A* 尋找最短路徑時, 有說使用多邊形中心點連線計算路徑長度的, 這樣算出來的結果準確性肯定受多邊形密度影響; 還有的只說用頂點尋路, 但這樣拐點之間可以直線連接又該怎麼算? 能推薦個靠譜的資料就行, 謝謝.

A* 尋路是在圖（graph）上做搜尋，所以是離散的，也就是說細分密度會影響結果。而你希望的結果似乎是需要連續空間的搜尋，可能需要 Any-angle path planning，當中有一個演算法稱為 Theta*，可以參考一下 Theta*: Any-Angle Path Planning for Smoother Trajectories in Continuous Environments。

最最簡單、基礎的尋路演算法，都是求解互相連接的（連接關係稱之為邊）點（即頂點）之間的路徑的。A* 演算法就是其中一種求解路徑的簡單方法。而研究點和邊的關係的學科，就是『離散數學』中的『圖論』。

但是，現實世界或是部分遊戲中不同，他們的空間是連續的。

我們怎麼把這種連續空間中的尋路問題轉化為簡單的圖論問題呢？

凸多邊形網格就是一種解決方案，他可以把連續空間的尋路問題抽象成圖論的尋路問題。

原因如下：

對於任何一個『可通行的』『不規則形狀』表面（甚至可以是不平的），用凸多邊形進行剖分，可得到多個凸多邊形。

對於任意一個凸多邊形內，任意兩點都可以以直線連接，直線在兩點間的部分肯定在凸多邊形內，所以我們可以認為凸多邊形內任意兩點間都是可通行的。

而剖分後的相鄰凸多邊形肯定有一條公共邊。根據上面的結論，我們可以知道這條公共邊上任意一點到兩個多邊形內都是可通行的。所以兩個相鄰的多邊形內的任意兩點都是可通行的。

既然這樣我們就可以開始抽象了：

在凸多邊形內以某種方法取一個點，來代表這個凸多邊形。（頂點）

如果兩個凸多邊形相鄰，說明兩個頂點是聯通的（邊）

這樣，就轉化為可以用A*等演算法解決的圖論問題了。

使用圖論的方法得到抽象的頂點和邊的路徑之後，再還原成凸多邊形的經過順序（比如經過凸多邊形1、4、5、7號到達），然後再根據次結果用適當的方法選擇在真實的可通行表面上的路徑。

這就是我們平時說的『凸多邊形網格尋路』。但這其實是思路，並不是具體演算法。

同時做了這種簡化的抽象肯定會影響結果的精確度，每一步的實現細節都對結果的精確度有影響：

首先是剖分，選擇是簡單的全部剖分成三角形，還是複雜凸多邊形，是否限制多邊形的大小？是否限制多邊形最長邊和最短邊的比例？總體上每個多邊形分的越小，邊數越多，多邊形每個邊的邊長越接近，結果越精確。
其次是剖分後的代表凸多邊形的點的位置，是選擇幾何中心，還是路徑經過該凸多邊形時，根據路徑進入和離開凸多邊形公共邊機動選擇，或者使用其他策略？
計算路徑長度時，是使用經過的凸多邊形數量，還是實際路徑的幾何距離？顯然前者實現簡單，但結果不夠精確。
得到圖論上的路徑，轉化為實際路徑時，是簡單的連接凸多邊形中點，還是連接路徑進入邊和離開邊上最近的點？還是在此基礎上加上回溯修正消除路徑的尖刺？

總體上，方案越是接近精確的正確結果，效率（包括開發難度和執行效率）越低。

其中1、2、3的影響較大，選擇簡單的策略在部分情況下甚至只能保證路徑是可通行的，對是否較短完全無法判斷。

4對路徑的的精確度影響比前面稍小，只會使得到的路徑產生毛刺。

所以，這就是一個實現難度、性能與結果精確度的抉擇問題。將問題分解成這些小問題後，基本都是高中幾何知識可以理解的問題。具體每一步的問題使用什麼演算法，請結合工時、性能、精確度需求來抉擇。

感謝觀看。

題主，我在工作中稍微用到過一些，我給幾個資料，希望能夠幫助到你：

CritterAI(Unity的第三方尋路插件，基於RecastNavigation編寫，文檔十分詳細)
CritterAI與Recast Navigation尋路
GitHub - recastnavigation/recastnavigation: Navigation-mesh Toolset for Games(一個非常流行的工業級尋路庫，作者是Unity的LeaderAI程序員)