虛擬場景中有寬度物體移動路徑的優化方法

吳擁民,張 斌

(1.閩江學院計算機科學系,福州350108;2.網龍網絡有限公司程序研發部,福州350003)

虛擬場景中有寬度物體移動路徑的優化方法

吳擁民1,2,張 斌2

(1.閩江學院計算機科學系,福州350108;2.網龍網絡有限公司程序研發部,福州350003)

提出一種虛擬場景中有寬度物體移動路徑的優化方法,在地圖掩碼數據經過尋路算法搜索后,得到一組連續路徑節點組成的節點集,從起始節點出發,沿著路徑節點找出離起始節點最遠且沒有障礙物遮擋的可見節點,作為下一個起點,循環往復直至節點集的終止節點,并順序連接這些可見節點,即可得到優化路徑。通過合并節點集中的多余節點,使路徑更平滑,從而減少物體移動過程中改變方向的次數,解決有寬度物體無法通過狹窄通道后,須重新計算路徑的問題,達到了更好的用戶體驗效果。

虛擬場景;尋路算法;優化方法;有寬度物體;最遠可見節點;節點合并

1 概述

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

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

在游戲場景中,尋路效果的好壞不僅僅是個算法問題,其本質是一種以玩家為中心的體驗服務。游戲中具有AI的NPC角色,應該按照玩家意想的狀態進行運動,而不是漫無目的地自由運動,尤其是在運動到某個既定的目的地時,不走直線而是不停地變換方向,就會導致玩家感覺失去對NPC的控制能力,整個游戲的用戶體驗就會受到極大的削弱。

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

文獻[1-9]提出的方法都只是以降低時間復雜度為目標,但無法解決游戲場景中,跟玩家高度互動且具有AI的NPC角色,在移動過程出現頻繁轉向或因通路狹窄而重新計算路徑,給玩家帶來不好的用戶體驗的問題。同時,移動路徑的重新計算會導致內存占用不規則的漲落,系統空間復雜度變得極為不穩定。為解決這個問題,本文提出一種虛擬場景中有寬度物體移動路徑的優化方法。

2 移動路徑方法的問題

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

圖1 含掩碼數據的地圖

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

圖2 A*尋路算法獲得的一組連續路徑節點

如果這一組節點數量太多,路徑不夠平滑,會導致物體在移動過程中頻繁變換移動方向,降低移動速度還占用額外存儲空間,從而給玩家帶來不好的用戶體驗。

另一方面,游戲中的虛擬物體一般具有寬度屬性。若物體有寬度屬性,說明該物體有抽象外圍輪廓,則該物體在與其他物體相互作用時,在空間中會受該輪廓的影響。若經過一個狹縫區域時,對于無寬度物體,理論上只要有一個無限小的縫隙就可以通過,但對于有寬度物體,狹縫的大小必須滿足物體外圍輪廓的尺寸才可通過。由于有寬度物體的約束,會導致有寬度物體在不能通過狹縫通路時重新尋路,加劇了不良的用戶體驗。

3 移動路徑的優化方法

虛擬場景中有寬度物體移動路徑的優化方法基本思路是:通過合并節點集中的多余節點,讓路徑更平滑,就可以減少物體移動過程中改變方向的次數,以達到路徑優化的效果。具體流程如圖3所示。

圖3 移動路徑優化方法的執行流程

執行流程的步驟如下:

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

圖4 節點集中各節點在邏輯上的相鄰關系

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

步驟3將起始節點S,第一最遠節點T1,第二最遠節點T2,第三最遠節點T3,……,終止節點E的中心點順次連接起來,所得到的連線即為優化路徑,如圖5所示。

圖5 移動路徑優化后的最終路徑

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

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

查找開始前,設置t,pass和block3個臨時變量:Ppass為當前Pi能看到的最遠節點,pass初始值i;Pblock為不能看到的最近節點,block初始值n;Pt為當前要判斷能否可見的節點,t初始值n;

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

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

如此反復判斷,最終找到Pi能看到的最遠節點Pt,如圖6所示。

圖6 查找可見最遠節點的二分查找法流程

在步驟2中,判定可見最遠節點的方法是:計算有寬度物體從判斷起點到目標節點的移動過程的矩形區域外圍,所有位于該矩形區域內的完整節點和部分節點即為掃描節點集,判斷該掃描節點集中是否有障礙物節點,若有則不可見,若無則可見,如圖7所示。

圖7 可見最遠節點的判定流程

具體過程如下:

(1)假設物體占地區域長度為橫向節點數L,寬度為豎向節點數W,判斷起點為節點A,目標節點為節點B。

(2)定位所述有寬度物體的重心節點,計算重心節點的規則,如圖8所示,從4個方向到達物體邊緣的距離left,top,right,bottom,得到以下數據:

圖8 物體重心節點的計算規則

(3)計算有寬度物體移動過程的矩形區域外圍,如圖9所示,得出該矩形區域的2個對角線頂點所在節點的坐標分別為(minX,minY),(maxX,maxY),其中:

圖9 有寬度物體移動過程的矩形區域外圍

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

1)x=b,表示有寬度物體朝水平方向移動,所述矩形區域中的所有節點就是掃描節點集,如圖10左邊矩形。

2)y=b,a=0,有寬度物體朝垂直方向移動,所述矩形區域中的所有節點就是掃描節點集,如圖10右邊矩形。

圖10 物體水平或垂直移動時的掃描節點集

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

根據重心節點在物體中的位置固定,計算得出m與n的值分別為:

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

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

圖11 物體正向傾斜移動時獲取的起止縱坐標

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

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

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

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

圖12 物體反向傾斜移動時獲取的起止縱坐標

(5)對所獲得的掃描節點集中的每個節點進行屬性判斷,只要有一個節點是障礙物節點,則A,B兩節點不可見,否則A,B兩節點可見。

4 優化方法的評測

優化方法具有如下優點:

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

(2)減少了路徑節點的數量,從而節省了移動路徑節點的內存空間。對比圖4與圖5可知,優化前的路徑節點數量為19,優化后的路徑節點數量為5,優化比為4∶1。當虛擬場景中有數萬個智能物體在移動時,節省的移動路徑節點的內存空間將相當可觀。

(3)減少了物體在移動過程中的轉向次數,可以提高移動速度。物體每次轉向,都會向服務器發送驗證信息,根據統計經驗,國內網絡狀況導致的網絡延遲,平均每次驗證需消耗200 ms左右。因此,有效地減少物體轉向次數,可以提高因網絡延遲所導致的運行效率。同樣對比圖4與圖5可知,優化前物體在移動過程中的轉向次數為10,優化后物體在移動過程中的轉向次數為4,優化比為2.5∶1。

優化方法已經在一款商業游戲《英魂之刃》中應用,《英魂之刃》是全球首款次世代MOBA頁游,支持跨平臺游戲,目前已正式登陸騰訊QQ游戲平臺。在短短的5個月測試期間,PCU已經突破5.8萬人,日活躍超過25萬人,周活躍超過50萬人,并且以每周10%增長率遞增。《英魂之刃》的每個游戲玩家都會自動帶領10個具有AI的NPC角色參與游戲,當游戲玩家增加到一定的數量,會導致NPC角色充斥整個游戲,成為動態的障礙物。《英魂之刃》的游戲服務器有2類:大廳服務器(LPS)與 戰斗服務器(BS),都部署在CPU為至強2640虛擬機上。LPS部署的物理機被分割為2臺虛擬機,BS部署的物理機被分割為3臺虛擬機。

LPS(只有單臺虛擬機承載):

1萬人,CPU占用8%,內存占用約3 GB;

2萬人,CPU占用12%,內存占用約5 GB;

3萬人,CPU占用16%,內存占用約7 GB;

5萬人,CPU占用20%,內存占用約9 GB。

BS(共計36臺虛擬機承載):

1 000人,CPU占用30%,內存占用2.5 GB,每秒平均轉向0.57次;

1 300人,CPU占用50%,內存占用3.5 GB,每秒平均轉向0.61次;

1 600人,CPU占用75%,內存占用4.5 GB,每秒平均轉向0.68次。

以上數據表明,在游戲玩家穩步遞增的過程中,服務器內存沒有呈現指數級的暴漲,智能物體的移動轉向次數相當穩定。商業級的《英魂之刃》應用驗證了優化方法的效果,相比較提供理想環境中的測試數據,更具商業與理論雙重價值。

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

5 結束語

本文提出的優化方法本質上也是A*搜索算法的一種改進,與文獻[6]中應用Bresenham算法具有相似的思路,但減少了結果集中的節點數量;與文獻[8]的分層尋路方法相比,其時間復雜度基本在一個量級上。分層尋路思想的實際是一種3D渲染技術中LOD算法在尋路中的應用,但對數據制作提出了更高的要求,會成倍加大數據制作的成本,而優化方法則不會;文獻[9]中基于定位點和路徑復用的尋路算法,是一種針對靜態障礙物環境下的優化算法,但約束條件太強,其適用情景極為有限,而優化方法適用于靜態與動態障礙物環境,具有廣譜的效果。

本文方法適合虛擬場景中低速運動且帶有AI的NPC角色的移動路徑計算,這類NPC角色與玩家的互動強調良好的用戶體驗。然而優化方法不適合類似汽車、飛機等具有高速運動特征的虛擬物體的移動路徑計算,需要作進一步的研究。

[1] 維基百科.廣度優先搜索[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] 維基百科.深度優先搜索[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*算法在游戲地圖尋徑中的應用與實現[J].計算機應用與軟件,2005,22(12):118-120.

[6] 王同喜,孫淑霞.基于A*和Bresenham相結合的網絡游戲尋路算法設計與實現[J].成都理工大學學報:自然科學版,2007,34(4):456-459.

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

[8] 蔡方方,楊士穎,張小鳳,等.雙層A*算法在游戲尋路方面的研究[J].微型電腦應用,2010,26(1):26-28.

[9] 梁 毅,周 剛.基于定位點和路徑復用的大型多人在線游戲尋路尋路算法[J].計算機應用,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] 陳 東.大型多人在線角色扮演類游戲用戶體驗研究[D].大連:大連海事大學,2007.

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

[13] 百度百科.兩點之間線段最短[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會員,主研方向:軟件體系結構,分布式系統,游戲引擎;張 斌,助理工程師。

2013-10-06

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

中文引用格式:吳擁民,張 斌.虛擬場景中有寬度物體移動路徑的優化方法[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.