尋路

基于NavMesh尋路、漏?尋路、RVO動態避障?創的服務器

?規模尋路+動態避障算法的實現

?、描述

TW項?是?個擁有較?闊野外空間的SLG游戲，玩家的軍隊?陣可以在野外進?長距離?軍、短距離?由?軍、占領要塞、駐扎、形

成戰?陣型戰?等?為。其中，野外的?脈、河流等會產?靜態阻擋；?由玩家遷城、把守要塞、駐扎等?為，會在野外地圖上產?動態阻

擋。

每個服務器活躍軍隊?陣?標5萬個，每天產?的長距離尋路請求可能達??萬或者百萬個，并且都需要在服務器端計算，?常規的

A*尋路、navmesh尋路、ROV避障算法計算量巨?，影響服務器效能。所以我們可以采?兩種解決?案：第?是做?個尋路服務器；第?

是選擇優化算法。本?給出了第?種優化算法?案。

?、需求

1、長、短距離尋路

2、尋路校驗（如果有前端尋路，那么后端需要校驗）

3、動態避障

注：以上所有需求是2D尋路

三、尋路

1、?先?navmesh尋路算法作為第?步，為野外地圖創建靜態尋路??；

2、然后?“?邊剔除”、“凸多邊形合并”的算法盡量合并??（這樣做可以使內存占?最?），如下圖；

左邊的線段BC被剔除，?BE+CE取代。右側HG、GJ線段被剔除，?HJ取代。

KN線段被直接剔除，兩個凸多邊形合并

3、?漏?尋路算法離線計算所有的??到所有其他?相鄰??的最優路徑，并記下途徑??索引、??重?距離邊的垂線的平均長度、路

程距離、權重等參數，形成“路徑數據”保持到?件（最優路徑可以不??條）；

4、后端在計算尋路請求的時候，算法如下：

4.1）起點終點在同?個??內，直接返回；

4.2）起點終點所在??相鄰（沒有途經??），直接返回；

4.3）起點終點所在??途徑?個??，并且有多個這樣的最優路徑，需要分別計算起點、終點到相鄰??交點的長度+途徑??重?

距離邊緣長度，選擇最短的；

4.4）起點終點所在??途徑?個??，并且有多個這樣的最優路徑，需要分別計算起點、終點到相鄰??交點的長度，選擇最短的；

5、后端校驗，只需要看路徑是否在“路徑數據”即可。

6、前端收到后端穿來的路徑后，只需要按“漏?尋路”算法，在需要的時候進?計算即可。

四、避障

由于我們的障礙物是可能突然出現在前?的，我們并不能像ROV那樣預先計算，選擇?個另外路徑，所以我們躲避障礙物的?式為：不會

提前改變路徑，?是到障礙物?前后才改變。

下圖是RVO避障算法，藍點?陣知道障礙物（紅球）的存在，會與紅球相撞的藍點會提前改變路徑

下圖是我們的動態避障算法，本來obj要從C點移動到K點，但是由于有障礙物的出現，于是到快與障礙物相撞的D點時轉向，?D-E-F-H-K

各點，到達?標點與障礙物包圍圓切線位置時?直線奔向?標點

此算法依賴于如下?點前提條件：

1.障礙物都可以被圓包圍，不會?限?，按照圓（折線）躲避不會違和。

2.緊貼著障礙物的周圍是可以?的，也就是障礙物不能連起來形成更?的障礙。

本來要從N?到P點，結果?到O點時發現障礙物A。

1、將A的包圍圓分成12份，每份30度。

2、由于已知A點位置，圓半徑（基本都是固定半徑），AB與AC夾?度數（30度），所以可知B,C,D,E,,,M等12個點的位置

3、由于繞開障礙物只需要繞最多90度，所以最多只需要?3個點。

4、當對象?到O點，發現障礙物時，?先計算A點在直線NP的位置，如果A點在直線下?，則從上?繞；相反如果A點在直線上?，則從下

?繞

5、計算AO夾?如果?于AD?則?折線OD，其他以此類推

6、計算C點在直線DP的上?，則需要?折線DC

7、計算B點在直線CP的上?，則需要?折現CB

8、此時已經?了3個點了，可以直接?BP奔向?的地。如果不滿3個點，則計算下?個點M在直線BP下?，則不需要?M了。

復雜度分析

1.當A已知時，由于包圍圓的半徑是固定值，所以B,,M點通過加減法就可以得到

2.接下來在計算?次AO夾?（兩次浮點數乘法）

3.接下來最多計算3此點與直線的關系（每次是兩次浮點數乘法）

五、總結

尋路的算法有很多，各?應?在不同的場景。通過篩選了??種不同的尋路算法后，本?參考、采?或者部分采?了其中4，5種，也

將?些算法拆解只?其中?部分，然后還?創了?些尋路算法，?創部分是最?化的?空間換取時間，最終達到了后端的長距離?軍粗路徑

尋路CPU消耗很低的優化效果，不需要增加新的硬件就可以?持服務器端?規模尋路。