基于物理系統的動態尋路方案研究

歐陽鵬程

摘 要 在大型多人角色扮演類游戲的服務器世界中存在大量由AI控制的角色，這些角色需要在世界中進行位移尋路的計算。本文介紹了一種在經典尋路算法基礎上，結合物理系統的尋路解決方案，并描述了在實際項目中的實現方式與效果驗證。

關鍵詞 尋路算法;動態尋路;導航網格;物理碰撞;碰撞算法

1靜態尋路算法

1.1 算法簡介

在大型多人角色扮演類游戲的服務器世界中，不但存在著大量由玩家扮演的角色，同時還存在著大量由AI控制的非玩家角色（簡稱：NPC）。這些NPC需要模擬真實的運動行為，在世界各處行走。

圖1展示了在游戲中玩家和NPC分別在客戶端和服務端中的顯示方式。雖然游戲客戶端使用3D圖形技術來表現華麗的視覺效果，但是在服務端的邏輯世界中是基于二維空間進行計算的。

角色在二維空間中表示為一個有一定半徑的圓，同時場景中存在大量不可行走的區域，比如墻、山、房子等。因此，當NPC角色在場景中移動時必須繞開這些區域。如何計算出一條能夠繞開這些不可行走區域的路徑，成為一個需要研究的算法。

由于這些不可行走區域不會變化，因此我們稱這類算法為靜態尋路算法。

1.2 生成導航網格

靜態尋路算法首先需要對場景進行建模，將場景中的可行走區域邊界計算出來。計算出來的可行走區域表達為一個n多邊形。如圖2所示，灰色區域為可行走區域N多邊形。

然后將N多邊形進行三角面剖分，這里可以采用經典的Delaunay三角面剖分算法。如圖3所示，將可行走區域進行三角面剖分后的結果。

這些相連的三角形稱為導航網格，NPC的尋路就依賴導航網格數據進行計算。

1.3 基于導航網格的尋路算法

導航網格中的三角形都是相互連接的，因此需要先建立三角形連接關系的數據，可以用圖數據結構來表示三角形間的連接關系。如圖4所示。

當NPC需要在導航網格中由A點移動到B點時。首先計算出起點A和終點B所在的三角形Ta和Tb。然后根據三角形之間的連通關系計算出起點三角形Ta和終點三角形Tb之間的最短三角形連接通路。最短路徑的計算可以采用經典的A*算法。

獲得最短連通三角形通路后，將所有三角形的中心點連接起來，就獲得了一條在可行走區域中由起點A到終點B的可達路徑。如圖5所示。

由于這條路徑經過各三角形的中心點，因此還不是最優路徑。

1.4 路徑優化

獲得了連通三角形列表后，計算出連通三角形列表之間共享的邊。角色最終的移動路徑必然連續穿越所有共享邊。

然后以起點A到終點B的方向為最優選擇，依次計算路徑在每條共享邊上的最優點。再將這些點相連，就可以獲得起點A到終點B的最優路徑。如圖6所示。

以上介紹了經典靜態尋路算法的計算原理，但是在實際項目中會遇到如下幾個問題：

場景中存在不斷運動的需要避讓的NPC。要求NPC之間相互阻擋，不能互相穿插。

靜態尋路算法并沒有考慮角色的大小。角色體積較大時，在墻角移動時會穿插到墻體內。

2動態碰撞尋路算法

2.1 物理碰撞模型

由于靜態尋路算法，只考慮到場景中靜止不動的物體。因此，需要尋找一種方法能夠解決場景中不斷運動且會相互阻擋的物體。

對于運動的阻擋物，無法事先對其進行靜態分析與建模。因此考慮引入物理系統中的碰撞檢測來解決動態阻擋物的尋路問題。

首先，對場景中所有角色創建二維空間中的物理碰撞模型，如圖7所示。NPC角色可以使用圓來表示碰撞模型，墻體使用三角形來表示碰撞模型。

物理系統以每秒20幀的頻率檢測所有碰撞模型之間的碰撞檢測，由于不存在高速運動的阻擋物，因此當兩個物理碰撞體邊緣相接觸時就可以立刻檢測到。

2.2 盤繞算法

當角色A和角色B相向而行時，在發生碰撞的那一幀，采用如下盤繞算法來處理動態角色間的穿插問題。

對角色A，假設當前行進方向初始角度為d=d0設置盤繞角度a，初始a=10;

（1）計算d的順時針盤繞方向d1=d+a，計算d的逆時針盤繞方向d2=d-a;

（2）分別沿d1和d2方向進行移動預測，判斷是否與角色B碰撞;

（3）如果d1方向可行，則使d=d1;如果d2方向可行，則使d=d2;如果d1和d2方向都不可行a+=10，跳轉1;

（4）移動一幀，使d = d向初始方向d0偏移10;

（5）判斷是否仍然與角色B發生碰撞。是，跳轉1;否，退出盤繞狀態，并重新計算靜態路徑。

圖8展示了算法的流程圖。

采用以上計算方法后，當角色在行進方向遇到阻擋物體時。會先小角度進行移動預判，判斷對當前方向左右偏移是否可以移動;并不斷循環放大嘗試偏移角度，直到找到可以行走的角度。

圖9顯示了角色A在遇到角色B的阻擋后，使用盤繞算法的行進路徑。可以看到角色A的行進路徑不會和B發生穿插，成功繞過B角色。

給角色添加物理碰撞范圍，并且每幀進行物理碰撞檢測，能夠及時檢測到物理模型之間的碰撞和穿插。然后再針對兩物理模型之間的碰撞接觸點，進行盤繞算法，使角色的移動方向避開下一幀可能發生碰撞的方向[1]。

使用這樣的算法，不但很好地解決了NPC角色這種動態對象的尋路問題，針對靜態場景也能夠有明顯的優化效果。

靜態尋路算法的路徑并沒有考慮到角色半徑的問題，因此當角色沿路徑移動到墻角處時會發生明顯的穿插現象。結合了基于物理碰撞的盤繞算法后，角色在經過墻角時能夠動態繞開墻體。圖10左圖顯示了靜態尋路算法的路徑，有明顯的穿插現象;右圖顯示結合了碰撞算法后，可以成功避開與墻體的穿插。

3動態物理尋路算法

3.1 對象穿插

對于相互沒有穿插的對象，以上算法能夠很好地解決對象之間在尋路移動過程中的相互穿插現象。但是在實際項目中，有時會出現兩個對象已經穿插在一起的情況。

比如，一個可以自動開關的門，門打開時NPC站在門中間，然后門自動關上。這時NPC就會仍然站在門中間，NPC和門互相穿插。而且在這種情況下，NPC已經站在了一個不可移動的區域中，即使生成了尋路網格，NPC也會由于起點不在尋路網格的任何一個三角形中而無法找到一條可達路徑。

因此針對這種情況，需要結合物理系統中的運動學部分來優化NPC的尋路系統。

3.2 排斥速度

優化方案希望能夠將已經穿插的兩個對象能夠相互擠開，因此這里引入真實物理系統中的排斥力概念。

真實物理系統中的排斥力會根據兩個物理對象穿插的距離計算排斥力大小，并且涉及復雜的力學計算，但是在尋路系統中這樣的表現并不好。因此我們只使用排斥力的方向，在方向上設定一個固定的移動速度。

圖11顯示了兩個圓形碰撞體穿插時，互相給對方施加一個反向的排斥移動速度。和三個圓形碰撞體穿插時相互施加排斥移動速度。

需要注意的是，在通常的2D物理引擎中（比如box2d），當一個碰撞體與三個及以上的碰撞體發生碰撞時，需要積分計算，而電腦只能通過多次循環計算碰撞點所產生的合力方向來模擬積分過程。這個計算過程非常消耗算力，并且合力計算結果的精確性依賴于循環次數[2]。當循環次數較少且碰撞體較多時，仍然會發生穿插現象。而且較大的計算量對于MMO類游戲的服務器也會造成非常大的性能壓力。

因此在這里的尋路算法中簡化了這種復雜情況的計算。當一個碰撞對象受到3個及以上的碰撞體碰撞時，在計算過程中以任意一個力的方向為x軸，建立笛卡爾坐標系統。只要在x、y軸上出現相反方向的力，則將此方向上的力歸零。如圖12所示，A受到3個方向的力，且3個力在x、y軸上的投影都存在相反的情況。因此就不對A物體施加排斥速度。

采用這種算法上的優化后，大量碰撞物體聚集在一起時，會使邊緣的碰撞對象逐步被擠開;騰出空間后，中間的碰撞對象再逐步疏散開。這樣就能在性能和表現上取得平衡。

在對物理系統中碰撞與運動學部分進行簡化和調整后，也能夠完美解決由于多碰撞點需要積分計算而導致的不精確性[3]。可以完美的避免角色被大量其他角色推擠時，可能被擠進墻里的現象。

圖13顯示了在實際項目中大量角色聚集在一起時的尋路位移情況。其中綠色圈為玩家角色，紅色圈為NPC角色。可以看到雖然大量紅色NPC角色聚集在一起并且相互緊貼，但并沒有發生明顯的穿插現象。而且也完全不會出現穿插到墻體中的情況。

4結束語

經典的靜態尋路算法奠定了尋路算法的基礎，但是針對游戲項目中復雜多變的環境和需求，并不能達到令人滿意的效果。

因此本文闡述了在實際項目中經過實踐摸索后，總結的一種適合大量動態物體的尋路算法，將物理系統中的碰撞系統與運動學部分進行簡化與調整，再結合靜態尋路算法，能夠達到令人滿意的表現效果。對于MMO類服務器計算壓力較大的環境也能很好的適用。

隨著技術的發展，用戶對游戲品質要求的提高，未來對尋路算法的要求會越來越高。本文所闡述的是一種經過實際項目驗證的方法，對于其他類型的項目也有較好的參考價值。

參考文獻

[1] Mark DeLoura.游戲編程精粹1[M].北京：人民郵電出版社，2004： 271-275.

[2] Siu-Wing Cheng.Delaunay Mesh Generation[M]. Chapman and Hall/CRC 2012：26-27.

[3] 陳文登.Box 2D 物理游戲編程[M].北京：科學出版社，2015：50.