吳擁民,張 斌

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

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

吳擁民1,2,張 斌2

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

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

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

1 概述

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

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

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

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

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

2 移動路徑方法的問題

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

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

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

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

如果這一組節(jié)點數(shù)量太多,路徑不夠平滑,會導(dǎo)致物體在移動過程中頻繁變換移動方向,降低移動速度還占用額外存儲空間,從而給玩家?guī)聿缓玫挠脩趔w驗。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖7 可見最遠節(jié)點的判定流程

具體過程如下:

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

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

圖8 物體重心節(jié)點的計算規(guī)則

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

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

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

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

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

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

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

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

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

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

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

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

根據(jù)重心節(jié)點在物體中的位置固定,計算得出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)中間的區(qū)域與步驟2.3中獲得的矩形區(qū)域的重疊部分即為掃描節(jié)點集所在區(qū)域,只要橫坐標x從minX開始遍歷至maxX,依次計算直線fb(x)和ft(x)在該橫坐標下的縱坐標為掃描起始縱坐標和掃描終止縱坐標,即可獲得所有掃描節(jié)點集中的節(jié)點,如圖12所示。

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

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

4 優(yōu)化方法的評測

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

[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)用與實現(xiàn)[J].計算機應(yīng)用與軟件,2005,22(12):118-120.

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

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

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

[9] 梁 毅,周 剛.基于定位點和路徑復(fù)用的大型多人在線游戲?qū)ぢ穼ぢ匪惴╗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] 陳 東.大型多人在線角色扮演類游戲用戶體驗研究[D].大連:大連海事大學(xué),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會員,主研方向:軟件體系結(jié)構(gòu),分布式系統(tǒng),游戲引擎;張 斌,助理工程師。

2013-10-06

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

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