虛擬場(chǎng)景中有寬度物體移動(dòng)路徑的優(yōu)化方法

吳擁民,張 斌

(1.閩江學(xué)院計(jì)算機(jī)科學(xué)系,福州350108;2.網(wǎng)龍網(wǎng)絡(luò)有限公司程序研發(fā)部,福州350003)

虛擬場(chǎng)景中有寬度物體移動(dòng)路徑的優(yōu)化方法

吳擁民1,2,張 斌2

(1.閩江學(xué)院計(jì)算機(jī)科學(xué)系,福州350108;2.網(wǎng)龍網(wǎng)絡(luò)有限公司程序研發(fā)部,福州350003)

提出一種虛擬場(chǎng)景中有寬度物體移動(dòng)路徑的優(yōu)化方法,在地圖掩碼數(shù)據(jù)經(jīng)過(guò)尋路算法搜索后,得到一組連續(xù)路徑節(jié)點(diǎn)組成的節(jié)點(diǎn)集,從起始節(jié)點(diǎn)出發(fā),沿著路徑節(jié)點(diǎn)找出離起始節(jié)點(diǎn)最遠(yuǎn)且沒(méi)有障礙物遮擋的可見(jiàn)節(jié)點(diǎn),作為下一個(gè)起點(diǎn),循環(huán)往復(fù)直至節(jié)點(diǎn)集的終止節(jié)點(diǎn),并順序連接這些可見(jiàn)節(jié)點(diǎn),即可得到優(yōu)化路徑。通過(guò)合并節(jié)點(diǎn)集中的多余節(jié)點(diǎn),使路徑更平滑,從而減少物體移動(dòng)過(guò)程中改變方向的次數(shù),解決有寬度物體無(wú)法通過(guò)狹窄通道后,須重新計(jì)算路徑的問(wèn)題,達(dá)到了更好的用戶體驗(yàn)效果。

虛擬場(chǎng)景;尋路算法;優(yōu)化方法;有寬度物體;最遠(yuǎn)可見(jiàn)節(jié)點(diǎn);節(jié)點(diǎn)合并

1 概述

隨著電子游戲的不斷發(fā)展,在虛擬的游戲場(chǎng)景中,經(jīng)常需要實(shí)現(xiàn)虛擬物體從一點(diǎn)向另一點(diǎn)移動(dòng)的功能。在該過(guò)程中,要判斷是否有可行路線,以及最優(yōu)路線選擇等,這便是尋路過(guò)程。尋路算法的基本思路就是圖的遍歷算法與最短路徑算法,遍歷算法分為廣度優(yōu)先搜索[1]與深度優(yōu)先搜索[2],最短路徑算法分為非啟發(fā)式的Dijkstra搜索[3]與啟發(fā)式的A*搜索[4]。

啟發(fā)式的A*搜索算法被廣泛用于電子游戲中。文獻(xiàn)[5]介紹了該算法在網(wǎng)絡(luò)游戲中的具體實(shí)現(xiàn)方法。文獻(xiàn)[6]在啟發(fā)式的A*搜索算法基礎(chǔ)上,以Bresenham算法獲取直線路徑的節(jié)點(diǎn)集合,對(duì)A*搜索算法的尋路效率提高極為有限。文獻(xiàn)[7]在啟發(fā)式的A*搜索算法基礎(chǔ)上,以二叉堆優(yōu)化A*的開(kāi)啟列表提高了查找速度,并針對(duì)大地圖采用低密度網(wǎng)格的宏觀尋路與高密度網(wǎng)格的微觀尋路的分層尋路思路。文獻(xiàn)[8]基于分層尋路思路,給出了雙層 A*尋路的具體實(shí)現(xiàn)方法。文獻(xiàn)[9]提出一種基于定位點(diǎn)和路徑復(fù)用的尋路算法,是在給定的約束條件(靜態(tài)障礙物環(huán)境下)對(duì)啟發(fā)式的A*搜索算法的一種優(yōu)化,針對(duì)游戲中大量移動(dòng)的角色也可成為障礙物的情形下,則該算法無(wú)效。

在游戲場(chǎng)景中,尋路效果的好壞不僅僅是個(gè)算法問(wèn)題,其本質(zhì)是一種以玩家為中心的體驗(yàn)服務(wù)。游戲中具有AI的NPC角色,應(yīng)該按照玩家意想的狀態(tài)進(jìn)行運(yùn)動(dòng),而不是漫無(wú)目的地自由運(yùn)動(dòng),尤其是在運(yùn)動(dòng)到某個(gè)既定的目的地時(shí),不走直線而是不停地變換方向,就會(huì)導(dǎo)致玩家感覺(jué)失去對(duì)NPC的控制能力,整個(gè)游戲的用戶體驗(yàn)就會(huì)受到極大的削弱。

文獻(xiàn)[10]試圖以一種用戶調(diào)查的方法理解、審視、定義用戶體驗(yàn),同時(shí)提出了很難給出一種通用的用戶體驗(yàn)定義。文獻(xiàn)[11]從游戲可玩性為切入點(diǎn)來(lái)研究MMORPG的用戶體驗(yàn)問(wèn)題。少有文獻(xiàn)研究具有良好用戶體驗(yàn)的虛擬角色的行為,長(zhǎng)期以來(lái)高度依賴游戲設(shè)計(jì)師的理念,改善虛擬角色行為的用戶體驗(yàn)。文獻(xiàn)[12]為了描述如何創(chuàng)建和解析不舒適的驚險(xiǎn)和難忘的體驗(yàn),從4種基本形式:本能,文化,控制,隱私,研究了不舒適的交互體驗(yàn)。其中控制強(qiáng)調(diào):人機(jī)交互準(zhǔn)則早就主張,軌跡的控制應(yīng)回歸于用戶;也就是說(shuō),好的設(shè)計(jì)是:人控制界面,而不是界面控制人。玩家感覺(jué)失去對(duì)NPC的控制能力,就是一種典型的用戶放棄了控制機(jī)器而產(chǎn)生的不適感。因此,減少智能物體在移動(dòng)過(guò)程中的轉(zhuǎn)向次數(shù),不但能提高移動(dòng)速度,而且能改善用戶體驗(yàn)。

文獻(xiàn)[1-9]提出的方法都只是以降低時(shí)間復(fù)雜度為目標(biāo),但無(wú)法解決游戲場(chǎng)景中,跟玩家高度互動(dòng)且具有AI的NPC角色,在移動(dòng)過(guò)程出現(xiàn)頻繁轉(zhuǎn)向或因通路狹窄而重新計(jì)算路徑,給玩家?guī)?lái)不好的用戶體驗(yàn)的問(wèn)題。同時(shí),移動(dòng)路徑的重新計(jì)算會(huì)導(dǎo)致內(nèi)存占用不規(guī)則的漲落,系統(tǒng)空間復(fù)雜度變得極為不穩(wěn)定。為解決這個(gè)問(wèn)題,本文提出一種虛擬場(chǎng)景中有寬度物體移動(dòng)路徑的優(yōu)化方法。

2 移動(dòng)路徑方法的問(wèn)題

啟發(fā)式的A*搜索算法及其各種優(yōu)化搜索算法都需要一種與地圖相關(guān)的數(shù)據(jù),稱為地圖數(shù)據(jù)。地圖數(shù)據(jù)中有一種是將場(chǎng)景劃分成多個(gè)相同大小的平面方格,每個(gè)方格代表一個(gè)區(qū)域,也稱為一個(gè)路徑節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)有自己的屬性,比如是否為障礙物節(jié)點(diǎn)等。每個(gè)節(jié)點(diǎn)有個(gè)中心點(diǎn),即該平面方格的中心點(diǎn)。稱這種地圖數(shù)據(jù)為掩碼數(shù)據(jù)。每個(gè)區(qū)域可以根據(jù)區(qū)域編號(hào)得到該區(qū)域的鄰近區(qū)域節(jié)點(diǎn)。在路徑搜索時(shí),尋路算法搜索起始節(jié)點(diǎn)的相鄰節(jié)點(diǎn),再搜索相鄰節(jié)點(diǎn)的相鄰節(jié)點(diǎn),直至搜索到終止節(jié)點(diǎn),從而得到從起始節(jié)點(diǎn)到終止節(jié)點(diǎn)的完整路徑。這種方式簡(jiǎn)單實(shí)用,被大量運(yùn)用于2D場(chǎng)景,也適用于較簡(jiǎn)單且不包含層次關(guān)系的3D場(chǎng)景。如圖1為含掩碼數(shù)據(jù)的地圖,陰影部分格子為不可走區(qū)域,即屬于障礙物節(jié)點(diǎn),其他格子為可走區(qū)域。

圖1 含掩碼數(shù)據(jù)的地圖

由上文的介紹可以看出,若使用的是掩碼地圖數(shù)據(jù),經(jīng)過(guò)尋路算法搜索之后,將獲得一組連續(xù)的路徑節(jié)點(diǎn),其中,首尾分別為起始節(jié)點(diǎn)S和終止節(jié)點(diǎn)E,以下簡(jiǎn)稱為節(jié)點(diǎn)集。如圖2所示,2個(gè)中心有正方形的節(jié)點(diǎn)分別為起始節(jié)點(diǎn)和終止節(jié)點(diǎn),中心有圓點(diǎn)的節(jié)點(diǎn)為搜索后獲得的節(jié)點(diǎn)。理論上,虛擬物體只需沿著這些路徑節(jié)點(diǎn)的中心點(diǎn)行進(jìn)就可以到達(dá)目的地。

圖2 A*尋路算法獲得的一組連續(xù)路徑節(jié)點(diǎn)

如果這一組節(jié)點(diǎn)數(shù)量太多,路徑不夠平滑,會(huì)導(dǎo)致物體在移動(dòng)過(guò)程中頻繁變換移動(dòng)方向,降低移動(dòng)速度還占用額外存儲(chǔ)空間,從而給玩家?guī)?lái)不好的用戶體驗(yàn)。

另一方面,游戲中的虛擬物體一般具有寬度屬性。若物體有寬度屬性,說(shuō)明該物體有抽象外圍輪廓,則該物體在與其他物體相互作用時(shí),在空間中會(huì)受該輪廓的影響。若經(jīng)過(guò)一個(gè)狹縫區(qū)域時(shí),對(duì)于無(wú)寬度物體,理論上只要有一個(gè)無(wú)限小的縫隙就可以通過(guò),但對(duì)于有寬度物體,狹縫的大小必須滿足物體外圍輪廓的尺寸才可通過(guò)。由于有寬度物體的約束,會(huì)導(dǎo)致有寬度物體在不能通過(guò)狹縫通路時(shí)重新尋路,加劇了不良的用戶體驗(yàn)。

3 移動(dòng)路徑的優(yōu)化方法

虛擬場(chǎng)景中有寬度物體移動(dòng)路徑的優(yōu)化方法基本思路是:通過(guò)合并節(jié)點(diǎn)集中的多余節(jié)點(diǎn),讓路徑更平滑,就可以減少物體移動(dòng)過(guò)程中改變方向的次數(shù),以達(dá)到路徑優(yōu)化的效果。具體流程如圖3所示。

圖3 移動(dòng)路徑優(yōu)化方法的執(zhí)行流程

執(zhí)行流程的步驟如下:

步驟1使用地圖掩碼數(shù)據(jù),經(jīng)過(guò)尋路算法搜索后,得到一個(gè)由一組連續(xù)路徑節(jié)點(diǎn)組成的節(jié)點(diǎn)集,節(jié)點(diǎn)集首尾分別為路徑的起始節(jié)點(diǎn)S和終止節(jié)點(diǎn)E;并檢查節(jié)點(diǎn)集的數(shù)據(jù)是否有效。所謂有效是指:節(jié)點(diǎn)集首尾分別為路徑的起始和終止節(jié)點(diǎn),并且除了起始節(jié)點(diǎn)外所有的路徑節(jié)點(diǎn)與自己的前一個(gè)節(jié)點(diǎn)在邏輯位置上是相鄰的,如圖4所示。

圖4 節(jié)點(diǎn)集中各節(jié)點(diǎn)在邏輯上的相鄰關(guān)系

步驟2先將起始節(jié)點(diǎn)S作為判斷起點(diǎn),在所有剩余節(jié)點(diǎn)中查找起始節(jié)點(diǎn)S可見(jiàn)的最遠(yuǎn)節(jié)點(diǎn),該最遠(yuǎn)節(jié)點(diǎn)為第一最遠(yuǎn)節(jié)點(diǎn)T1,再將第一最遠(yuǎn)節(jié)點(diǎn)T1作為判斷起點(diǎn)查找可見(jiàn)的最遠(yuǎn)節(jié)點(diǎn),得到第二最遠(yuǎn)的節(jié)點(diǎn)T2,再由第二最遠(yuǎn)節(jié)點(diǎn)T2作為判斷起點(diǎn)查找可見(jiàn)的最遠(yuǎn)節(jié)點(diǎn),得到第三最遠(yuǎn)節(jié)點(diǎn)T3,然后按此規(guī)律一直查找下去,直到可見(jiàn)的最遠(yuǎn)節(jié)點(diǎn)為終止節(jié)點(diǎn)E為止。所述可見(jiàn)是指有寬度物體在從判斷起點(diǎn)到目標(biāo)節(jié)點(diǎn)的途中不會(huì)有障礙物;所述可見(jiàn)的最遠(yuǎn)節(jié)點(diǎn)是指離判斷起點(diǎn)最遠(yuǎn)的目標(biāo)節(jié)點(diǎn)。

步驟3將起始節(jié)點(diǎn)S,第一最遠(yuǎn)節(jié)點(diǎn)T1,第二最遠(yuǎn)節(jié)點(diǎn)T2,第三最遠(yuǎn)節(jié)點(diǎn)T3,……,終止節(jié)點(diǎn)E的中心點(diǎn)順次連接起來(lái),所得到的連線即為優(yōu)化路徑,如圖5所示。

圖5 移動(dòng)路徑優(yōu)化后的最終路徑

在步驟2中,查找可見(jiàn)的最遠(yuǎn)節(jié)點(diǎn)采用二分法查找:即先判斷離判斷起點(diǎn)最遠(yuǎn)處的節(jié)點(diǎn)是否可見(jiàn),若不可見(jiàn),則判斷該判斷起點(diǎn)與該最遠(yuǎn)處的節(jié)點(diǎn)的中間位置節(jié)點(diǎn)是否可見(jiàn),以此規(guī)律遍歷下去,直到找到該判斷起點(diǎn)的可見(jiàn)的最遠(yuǎn)節(jié)點(diǎn)。具體步驟如下:

假設(shè)節(jié)點(diǎn)集為P,終止節(jié)點(diǎn)為Pn,要查找節(jié)點(diǎn)Pi(0≤i≤n)能看到的最遠(yuǎn)節(jié)點(diǎn);

查找開(kāi)始前,設(shè)置t,pass和block3個(gè)臨時(shí)變量:Ppass為當(dāng)前Pi能看到的最遠(yuǎn)節(jié)點(diǎn),pass初始值i;Pblock為不能看到的最近節(jié)點(diǎn),block初始值n;Pt為當(dāng)前要判斷能否可見(jiàn)的節(jié)點(diǎn),t初始值n;

判斷(Pi,Pt)兩點(diǎn)是否可見(jiàn):若不可見(jiàn),則block=t,t=pass+(block-pass)/2,返回重新判斷(Pi,Pt)兩點(diǎn)是否可見(jiàn);若可見(jiàn),則當(dāng)t==n或者t==block-1時(shí),節(jié)點(diǎn)Pt為Pi能看到的最遠(yuǎn)節(jié)點(diǎn);

否則pass=t,t=pass+(block-pass)/2,然后返回判斷(Pi,Pt)兩點(diǎn)是否可見(jiàn);

如此反復(fù)判斷,最終找到Pi能看到的最遠(yuǎn)節(jié)點(diǎn)Pt,如圖6所示。

圖6 查找可見(jiàn)最遠(yuǎn)節(jié)點(diǎn)的二分查找法流程

在步驟2中,判定可見(jiàn)最遠(yuǎn)節(jié)點(diǎn)的方法是:計(jì)算有寬度物體從判斷起點(diǎn)到目標(biāo)節(jié)點(diǎn)的移動(dòng)過(guò)程的矩形區(qū)域外圍,所有位于該矩形區(qū)域內(nèi)的完整節(jié)點(diǎn)和部分節(jié)點(diǎn)即為掃描節(jié)點(diǎn)集,判斷該掃描節(jié)點(diǎn)集中是否有障礙物節(jié)點(diǎn),若有則不可見(jiàn),若無(wú)則可見(jiàn),如圖7所示。

圖7 可見(jiàn)最遠(yuǎn)節(jié)點(diǎn)的判定流程

具體過(guò)程如下:

(1)假設(shè)物體占地區(qū)域長(zhǎng)度為橫向節(jié)點(diǎn)數(shù)L,寬度為豎向節(jié)點(diǎn)數(shù)W,判斷起點(diǎn)為節(jié)點(diǎn)A,目標(biāo)節(jié)點(diǎn)為節(jié)點(diǎn)B。

(2)定位所述有寬度物體的重心節(jié)點(diǎn),計(jì)算重心節(jié)點(diǎn)的規(guī)則,如圖8所示,從4個(gè)方向到達(dá)物體邊緣的距離left,top,right,bottom,得到以下數(shù)據(jù):

圖8 物體重心節(jié)點(diǎn)的計(jì)算規(guī)則

(3)計(jì)算有寬度物體移動(dòng)過(guò)程的矩形區(qū)域外圍,如圖9所示,得出該矩形區(qū)域的2個(gè)對(duì)角線頂點(diǎn)所在節(jié)點(diǎn)的坐標(biāo)分別為(minX,minY),(maxX,maxY),其中:

圖9 有寬度物體移動(dòng)過(guò)程的矩形區(qū)域外圍

(4)根據(jù)物體上下邊緣點(diǎn)軌跡獲取掃描節(jié)點(diǎn)集,假設(shè)節(jié)點(diǎn)A與節(jié)點(diǎn)B的中心點(diǎn)連接起來(lái)直線的方程式為f(x):y=ax+b,在二維空間下,直線形態(tài)歸納為以下4種情況:

1)x=b,表示有寬度物體朝水平方向移動(dòng),所述矩形區(qū)域中的所有節(jié)點(diǎn)就是掃描節(jié)點(diǎn)集,如圖10左邊矩形。

2)y=b,a=0,有寬度物體朝垂直方向移動(dòng),所述矩形區(qū)域中的所有節(jié)點(diǎn)就是掃描節(jié)點(diǎn)集,如圖10右邊矩形。

圖10 物體水平或垂直移動(dòng)時(shí)的掃描節(jié)點(diǎn)集

3)y=ax+b,a＞0,有寬度物體正向傾斜移動(dòng),通過(guò)A,B兩節(jié)點(diǎn)的坐標(biāo)求出a,b的值,設(shè)上、下邊緣點(diǎn)的軌跡直線分別為ft(x):y=ax+bt,fb(x):y=ax+bb;根據(jù)二維數(shù)學(xué)幾何知識(shí)可得:bt=b+m,bb=b-n。

根據(jù)重心節(jié)點(diǎn)在物體中的位置固定,計(jì)算得出m與n的值分別為:

通過(guò)以上計(jì)算,求出直線fb(x)與ft(x)的方程式:

兩直線fb(x)與ft(x)中間的區(qū)域與步驟2.3中獲得的矩形區(qū)域的重疊部分即為掃描節(jié)點(diǎn)集所在區(qū)域,只要橫坐標(biāo)x從minX開(kāi)始遍歷至maxX,依次計(jì)算直線fb(x)和ft(x)在該橫坐標(biāo)下的縱坐標(biāo)為掃描起始縱坐標(biāo)和掃描終止縱坐標(biāo),即可獲得所有掃描節(jié)點(diǎn)集中的節(jié)點(diǎn),如圖11所示。

圖11 物體正向傾斜移動(dòng)時(shí)獲取的起止縱坐標(biāo)

4)y=ax+b,a＜0,有寬度物體反向傾斜移動(dòng),通過(guò)A、B兩節(jié)點(diǎn)的坐標(biāo)求出a,b的值,設(shè)上、下邊緣點(diǎn)的軌跡直線分別為ft(x):y=ax+bt,fb(x):y=ax+bb;根據(jù)二維數(shù)學(xué)幾何知識(shí)可得:bt=b+m,bb=b-n。

根據(jù)重心節(jié)點(diǎn)在物體中的位置固定,計(jì)算得出m與n的值分別為:m=|a|×(right+0.5)+top+ 0.5,n=|a|×(left+0.5)+bottom+0.5。

通過(guò)以上計(jì)算,求出直線fb(x)與ft(x)的方程式:

兩直線ft(x)與fb(x)中間的區(qū)域與步驟2.3中獲得的矩形區(qū)域的重疊部分即為掃描節(jié)點(diǎn)集所在區(qū)域,只要橫坐標(biāo)x從minX開(kāi)始遍歷至maxX,依次計(jì)算直線fb(x)和ft(x)在該橫坐標(biāo)下的縱坐標(biāo)為掃描起始縱坐標(biāo)和掃描終止縱坐標(biāo),即可獲得所有掃描節(jié)點(diǎn)集中的節(jié)點(diǎn),如圖12所示。

圖12 物體反向傾斜移動(dòng)時(shí)獲取的起止縱坐標(biāo)

(5)對(duì)所獲得的掃描節(jié)點(diǎn)集中的每個(gè)節(jié)點(diǎn)進(jìn)行屬性判斷,只要有一個(gè)節(jié)點(diǎn)是障礙物節(jié)點(diǎn),則A,B兩節(jié)點(diǎn)不可見(jiàn),否則A,B兩節(jié)點(diǎn)可見(jiàn)。

4 優(yōu)化方法的評(píng)測(cè)

優(yōu)化方法具有如下優(yōu)點(diǎn):

(1)基于兩點(diǎn)之間線段最短[13]的公理,合并無(wú)障礙路徑中多余節(jié)點(diǎn)的方法是一種高效的最優(yōu)化方法。

(2)減少了路徑節(jié)點(diǎn)的數(shù)量,從而節(jié)省了移動(dòng)路徑節(jié)點(diǎn)的內(nèi)存空間。對(duì)比圖4與圖5可知,優(yōu)化前的路徑節(jié)點(diǎn)數(shù)量為19,優(yōu)化后的路徑節(jié)點(diǎn)數(shù)量為5,優(yōu)化比為4∶1。當(dāng)虛擬場(chǎng)景中有數(shù)萬(wàn)個(gè)智能物體在移動(dòng)時(shí),節(jié)省的移動(dòng)路徑節(jié)點(diǎn)的內(nèi)存空間將相當(dāng)可觀。

(3)減少了物體在移動(dòng)過(guò)程中的轉(zhuǎn)向次數(shù),可以提高移動(dòng)速度。物體每次轉(zhuǎn)向,都會(huì)向服務(wù)器發(fā)送驗(yàn)證信息,根據(jù)統(tǒng)計(jì)經(jīng)驗(yàn),國(guó)內(nèi)網(wǎng)絡(luò)狀況導(dǎo)致的網(wǎng)絡(luò)延遲,平均每次驗(yàn)證需消耗200 ms左右。因此,有效地減少物體轉(zhuǎn)向次數(shù),可以提高因網(wǎng)絡(luò)延遲所導(dǎo)致的運(yùn)行效率。同樣對(duì)比圖4與圖5可知,優(yōu)化前物體在移動(dòng)過(guò)程中的轉(zhuǎn)向次數(shù)為10,優(yōu)化后物體在移動(dòng)過(guò)程中的轉(zhuǎn)向次數(shù)為4,優(yōu)化比為2.5∶1。

優(yōu)化方法已經(jīng)在一款商業(yè)游戲《英魂之刃》中應(yīng)用,《英魂之刃》是全球首款次世代MOBA頁(yè)游,支持跨平臺(tái)游戲,目前已正式登陸騰訊QQ游戲平臺(tái)。在短短的5個(gè)月測(cè)試期間,PCU已經(jīng)突破5.8萬(wàn)人,日活躍超過(guò)25萬(wàn)人,周活躍超過(guò)50萬(wàn)人,并且以每周10%增長(zhǎng)率遞增?！队⒒曛小返拿總€(gè)游戲玩家都會(huì)自動(dòng)帶領(lǐng)10個(gè)具有AI的NPC角色參與游戲,當(dāng)游戲玩家增加到一定的數(shù)量,會(huì)導(dǎo)致NPC角色充斥整個(gè)游戲,成為動(dòng)態(tài)的障礙物?！队⒒曛小返挠螒蚍?wù)器有2類:大廳服務(wù)器(LPS)與 戰(zhàn)斗服務(wù)器(BS),都部署在CPU為至強(qiáng)2640虛擬機(jī)上。LPS部署的物理機(jī)被分割為2臺(tái)虛擬機(jī),BS部署的物理機(jī)被分割為3臺(tái)虛擬機(jī)。

LPS(只有單臺(tái)虛擬機(jī)承載):

1萬(wàn)人,CPU占用8%,內(nèi)存占用約3 GB;

2萬(wàn)人,CPU占用12%,內(nèi)存占用約5 GB;

3萬(wàn)人,CPU占用16%,內(nèi)存占用約7 GB;

5萬(wàn)人,CPU占用20%,內(nèi)存占用約9 GB。

BS(共計(jì)36臺(tái)虛擬機(jī)承載):

1 000人,CPU占用30%,內(nèi)存占用2.5 GB,每秒平均轉(zhuǎn)向0.57次;

1 300人,CPU占用50%,內(nèi)存占用3.5 GB,每秒平均轉(zhuǎn)向0.61次;

1 600人,CPU占用75%,內(nèi)存占用4.5 GB,每秒平均轉(zhuǎn)向0.68次。

以上數(shù)據(jù)表明,在游戲玩家穩(wěn)步遞增的過(guò)程中,服務(wù)器內(nèi)存沒(méi)有呈現(xiàn)指數(shù)級(jí)的暴漲,智能物體的移動(dòng)轉(zhuǎn)向次數(shù)相當(dāng)穩(wěn)定。商業(yè)級(jí)的《英魂之刃》應(yīng)用驗(yàn)證了優(yōu)化方法的效果,相比較提供理想環(huán)境中的測(cè)試數(shù)據(jù),更具商業(yè)與理論雙重價(jià)值。

文獻(xiàn)[12]從4種基本形式:本能,文化,控制,隱私,研究了不舒適的交互體驗(yàn)。其中控制強(qiáng)調(diào):人機(jī)交互準(zhǔn)則早就主張,軌跡的控制應(yīng)回歸于用戶;也就是說(shuō),好的設(shè)計(jì)是:人控制界面,而不是界面控制人。如果理解游戲的本質(zhì)是一種以玩家為中心的體驗(yàn)服務(wù),那么游戲中具有AI的NPC角色,應(yīng)該按照玩家意想的狀態(tài)進(jìn)行運(yùn)動(dòng),而不是漫無(wú)目的地自由運(yùn)動(dòng),尤其是在運(yùn)動(dòng)到某個(gè)既定的目的地時(shí),不走直線而是不停地變換方向,就會(huì)導(dǎo)致玩家感覺(jué)失去對(duì)NPC的控制能力,整個(gè)游戲的用戶體驗(yàn)就會(huì)受到極大的削弱。這是一種典型的用戶放棄了控制機(jī)器而產(chǎn)生的不適感。因此,減少移動(dòng)過(guò)程中的轉(zhuǎn)向次數(shù)不但能提高智能物體的移動(dòng)速度,而且能改善用戶體驗(yàn)。

5 結(jié)束語(yǔ)

本文提出的優(yōu)化方法本質(zhì)上也是A*搜索算法的一種改進(jìn),與文獻(xiàn)[6]中應(yīng)用Bresenham算法具有相似的思路,但減少了結(jié)果集中的節(jié)點(diǎn)數(shù)量;與文獻(xiàn)[8]的分層尋路方法相比,其時(shí)間復(fù)雜度基本在一個(gè)量級(jí)上。分層尋路思想的實(shí)際是一種3D渲染技術(shù)中LOD算法在尋路中的應(yīng)用,但對(duì)數(shù)據(jù)制作提出了更高的要求,會(huì)成倍加大數(shù)據(jù)制作的成本,而優(yōu)化方法則不會(huì);文獻(xiàn)[9]中基于定位點(diǎn)和路徑復(fù)用的尋路算法,是一種針對(duì)靜態(tài)障礙物環(huán)境下的優(yōu)化算法,但約束條件太強(qiáng),其適用情景極為有限,而優(yōu)化方法適用于靜態(tài)與動(dòng)態(tài)障礙物環(huán)境,具有廣譜的效果。

本文方法適合虛擬場(chǎng)景中低速運(yùn)動(dòng)且?guī)в蠥I的NPC角色的移動(dòng)路徑計(jì)算,這類NPC角色與玩家的互動(dòng)強(qiáng)調(diào)良好的用戶體驗(yàn)。然而優(yōu)化方法不適合類似汽車、飛機(jī)等具有高速運(yùn)動(dòng)特征的虛擬物體的移動(dòng)路徑計(jì)算,需要作進(jìn)一步的研究。

[1] 維基百科.廣度優(yōu)先搜索[EB/OL].(2013-03-01). http://zh.wikipedia.org/wiki/%E5%B9%BF%E5% BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7% B4%A2.

[2] 維基百科.深度優(yōu)先搜索[EB/OL].(2013-03-01).http:// zh.wikipedia.org/wiki/%E6%B7%B1%E5%BA%A6%E4% BC%98%E5%85%88%E6%90%9C%E7%B4%A2.

[3] 維基百科.迪科斯徹算法[Z].2013-03-01.

[4] 維基百科.A*搜尋算法[Z].2013-03-01.

[5] 陳和平,張前哨.A*算法在游戲地圖尋徑中的應(yīng)用與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與軟件,2005,22(12):118-120.

[6] 王同喜,孫淑霞.基于A*和Bresenham相結(jié)合的網(wǎng)絡(luò)游戲?qū)ぢ匪惴ㄔO(shè)計(jì)與實(shí)現(xiàn)[J].成都理工大學(xué)學(xué)報(bào):自然科學(xué)版,2007,34(4):456-459.

[7] 詹海波.人工智能尋路算法在電子游戲中的研究和應(yīng)用[D].武漢:華中科技大學(xué),2006.

[8] 蔡方方,楊士穎,張小鳳,等.雙層A*算法在游戲?qū)ぢ贩矫娴难芯縖J].微型電腦應(yīng)用,2010,26(1):26-28.

[9] 梁 毅,周 剛.基于定位點(diǎn)和路徑復(fù)用的大型多人在線游戲?qū)ぢ穼ぢ匪惴╗J].計(jì)算機(jī)應(yīng)用,2010, 30(12):3215-3217.

[10] Law E L C,Roto V,Hassenzahl M,et al.Understanding, Scoping and Defining User Experience:A Survey Approach [C]//Proc.of the 27th International Conference on Human Factors in Computing Systems.New York,USA:ACM Press,2009:719-728.

[11] 陳 東.大型多人在線角色扮演類游戲用戶體驗(yàn)研究[D].大連:大連海事大學(xué),2007.

[12] Benford S,Greenhalgh C.Uncomfortable User Experience [J].Communications of the ACM,2013,56(9):66-73.

[13] 百度百科.兩點(diǎn)之間線段最短[EB/OL].(2013-05-17).http://baike.baidu.com/view/5187378.htm#1_1.

編輯 顧逸斐

Optimization Method of Moving Path for Object with a Width in Virtual Scene

WU Yong-min1,2,ZHANG Bin2
(1.Department of Computer Science,Minjiang University,Fuzhou 350108,China;
2.Program R&D Department,NetDragon Websoft Inc.,Fuzhou 350003,China)

The optimization path finding algorithm computes a moving path of the object with a width in game scene, which searches a continuous node composed of a node-set from map mask.Starting from the initial node,along the path from start node to find the farthest node and no visible obstacles,as a starting point,move in circles until the termination node set.Then sequentially connect these visible nodes,which can get optimal path.The redundant node with node set, makes the path smooth,reduces the times of changing direction in the process of moving objects,eliminates the object with a width not pass through a narrow channel,needs to re-compute the path problem,which achieves a better user experience.

virtual scene;path finding algorithm;optimization method;object with a width;farthest and visible node;node merging

1000-3428(2014)10-0308-06

A

TP301.6

10.3969/j.issn.1000-3428.2014.10.057

吳擁民(1968-),男,副教授、碩士、CCF會(huì)員,主研方向:軟件體系結(jié)構(gòu),分布式系統(tǒng),游戲引擎;張 斌,助理工程師。

2013-10-06

2013-12-23E-mail:yongminwu@sohu.com

中文引用格式:吳擁民,張 斌.虛擬場(chǎng)景中有寬度物體移動(dòng)路徑的優(yōu)化方法[J].計(jì)算機(jī)工程,2014,40(10):308-313.

英文引用格式:Wu Yongmin,Zhang Bin.Optimization Method of Moving Path for Object with a Width in Virtual Scene [J].Computer Engineering,2014,40(10):308-313.