基于物理系統(tǒng)的動(dòng)態(tài)尋路方案研究

歐陽鵬程

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

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

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

1.1 算法簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 路徑優(yōu)化

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

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

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

場景中存在不斷運(yùn)動(dòng)的需要避讓的NPC。要求NPC之間相互阻擋，不能互相穿插。

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

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

2.1 物理碰撞模型

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

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

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

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

2.2 盤繞算法

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

對角色A，假設(shè)當(dāng)前行進(jìn)方向初始角度為d=d0設(shè)置盤繞角度a，初始a=10;

（1）計(jì)算d的順時(shí)針盤繞方向d1=d+a，計(jì)算d的逆時(shí)針盤繞方向d2=d-a;

（2）分別沿d1和d2方向進(jìn)行移動(dòng)預(yù)測，判斷是否與角色B碰撞;

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

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

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

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

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

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

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

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

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

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

3.1 對象穿插

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

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

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

3.2 排斥速度

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

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

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

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

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

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

在對物理系統(tǒng)中碰撞與運(yùn)動(dòng)學(xué)部分進(jìn)行簡化和調(diào)整后，也能夠完美解決由于多碰撞點(diǎn)需要積分計(jì)算而導(dǎo)致的不精確性[3]。可以完美的避免角色被大量其他角色推擠時(shí)，可能被擠進(jìn)墻里的現(xiàn)象。

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

4結(jié)束語

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

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

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

參考文獻(xiàn)

[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].北京：科學(xué)出版社，2015：50.