歐陽鵬程

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

關(guān)鍵詞 尋路算法;動態(tài)尋路;導航網(wǎng)格;物理碰撞;碰撞算法

1靜態(tài)尋路算法

1.1 算法簡介

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

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

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

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

1.2 生成導航網(wǎng)格

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

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

這些相連的三角形稱為導航網(wǎng)格，NPC的尋路就依賴導航網(wǎng)格數(shù)據(jù)進行計算。

1.3 基于導航網(wǎng)格的尋路算法

導航網(wǎng)格中的三角形都是相互連接的，因此需要先建立三角形連接關(guān)系的數(shù)據(jù)，可以用圖數(shù)據(jù)結(jié)構(gòu)來表示三角形間的連接關(guān)系。如圖4所示。

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

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

由于這條路徑經(jīng)過各三角形的中心點，因此還不是最優(yōu)路徑。

1.4 路徑優(yōu)化

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

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

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

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

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

2動態(tài)碰撞尋路算法

2.1 物理碰撞模型

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

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

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

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

2.2 盤繞算法

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

對角色A，假設(shè)當前行進方向初始角度為d=d0設(shè)置盤繞角度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，跳轉(zhuǎn)1;

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

（5）判斷是否仍然與角色B發(fā)生碰撞。是，跳轉(zhuǎn)1;否，退出盤繞狀態(tài)，并重新計算靜態(tài)路徑。

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

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

圖9顯示了角色A在遇到角色B的阻擋后，使用盤繞算法的行進路徑?？梢钥吹浇巧獳的行進路徑不會和B發(fā)生穿插，成功繞過B角色。

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

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

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

3動態(tài)物理尋路算法

3.1 對象穿插

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

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

因此針對這種情況，需要結(jié)合物理系統(tǒng)中的運動學部分來優(yōu)化NPC的尋路系統(tǒng)。

3.2 排斥速度

優(yōu)化方案希望能夠?qū)⒁呀?jīng)穿插的兩個對象能夠相互擠開，因此這里引入真實物理系統(tǒng)中的排斥力概念。

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

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

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

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

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

在對物理系統(tǒng)中碰撞與運動學部分進行簡化和調(diào)整后，也能夠完美解決由于多碰撞點需要積分計算而導致的不精確性[3]?？梢酝昝赖谋苊饨巧淮罅科渌巧茢D時，可能被擠進墻里的現(xiàn)象。

圖13顯示了在實際項目中大量角色聚集在一起時的尋路位移情況。其中綠色圈為玩家角色，紅色圈為NPC角色?？梢钥吹诫m然大量紅色NPC角色聚集在一起并且相互緊貼，但并沒有發(fā)生明顯的穿插現(xiàn)象。而且也完全不會出現(xiàn)穿插到墻體中的情況。

4結(jié)束語

經(jīng)典的靜態(tài)尋路算法奠定了尋路算法的基礎(chǔ)，但是針對游戲項目中復雜多變的環(huán)境和需求，并不能達到令人滿意的效果。

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

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

參考文獻

[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.