[發(fā)明專利]虛擬場景中有寬度物體移動路徑的優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201210246083.3
• 申請日: 2012-07-16
• 公開（公告）號: CN102799781A
• 公開（公告）日: 2012-11-28
• 發(fā)明（設(shè)計）人: 劉德建;陳宏展;張斌;吳擁民;徐順帆
• 申請（專利權(quán)）人: 福建天晴數(shù)碼有限公司
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 福州市鼓樓區(qū)京華專利事務(wù)所(普通合伙) 35212
• 代理人: 宋連梅

【技術(shù)領(lǐng)域】

本發(fā)明涉及一種虛擬的2D或3D場景中有寬度物體移動路徑的優(yōu)化方法。

【背景技術(shù)】

隨著電子游戲的不斷發(fā)展，在虛擬的游戲場景中，經(jīng)常需要實(shí)現(xiàn)虛擬物體從一點(diǎn)向另一點(diǎn)移動的功能。在這過程中，要判斷是否有可行路線，以及最優(yōu)路線選擇等，這便是尋路過程。尋路算法類型有很多，例如廣度優(yōu)先搜索、深度優(yōu)先搜索、啟發(fā)式搜索等。這些算法都需要一種與地圖相關(guān)的數(shù)據(jù)，我們稱之為地圖數(shù)據(jù)。“有寬度物體”的解釋：若物體有寬度屬性，說明該物體有抽象外圍輪廓，則該物體在與其他物體相互作用時，在空間中會受該輪廓的影響。若經(jīng)過一個狹縫區(qū)域時，對于無寬度物體理論上只要有一個無限小的縫隙就可以通過，但對于有寬度物體，狹縫的大小必須滿足物體外圍輪廓的尺寸才可通過。

地圖數(shù)據(jù)中有一種是將場景劃分成多個相同大小的平面方格，每個方格代表一個區(qū)域，我們也稱之為一個路徑節(jié)點(diǎn)，每個節(jié)點(diǎn)有自己的屬性，比如是否為障礙物節(jié)點(diǎn)等。每個節(jié)點(diǎn)有個中心點(diǎn)，即該平面方格的中心點(diǎn)。我們稱這種地圖數(shù)據(jù)為掩碼數(shù)據(jù)。每個區(qū)域可以根據(jù)區(qū)域編號得到該區(qū)域的鄰近區(qū)域節(jié)點(diǎn)。在路徑搜索時，尋路算法搜索起始節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，再搜索相鄰節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，直至搜索到終止節(jié)點(diǎn)，從而得到從起始節(jié)點(diǎn)到終止節(jié)點(diǎn)的完整路徑。這種方式簡單實(shí)用，被大量運(yùn)用于2D場景，也適用于較簡單且不包含層次關(guān)系的3D場景。

如圖1所示，為掩碼地圖數(shù)據(jù)的簡單示意圖，陰影部分格子為不可走區(qū)域，即屬于障礙物節(jié)點(diǎn)，其他格子為可走區(qū)域。由上面介紹可以看出，若使用的是掩碼地圖數(shù)據(jù)，經(jīng)過尋路算法搜索之后，將獲得一組連續(xù)的路徑節(jié)點(diǎn)，其中首尾分別為起始節(jié)點(diǎn)S和終止節(jié)點(diǎn)E，以下簡稱為節(jié)點(diǎn)集。如圖2所示，兩個中心有正方形的節(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á)目的地。但是由于這一組節(jié)點(diǎn)數(shù)量太多，路徑不夠平滑，會導(dǎo)致物體在移動過程中頻繁變換移動方向，降低移動速度還占用額外存儲空間，從而給玩家?guī)聿缓玫挠脩趔w驗(yàn)。

【發(fā)明內(nèi)容】

本發(fā)明要解決的技術(shù)問題，在于提供一種虛擬場景中有寬度物體移動路徑的優(yōu)化方法，通過合并節(jié)點(diǎn)集中的多余節(jié)點(diǎn)，讓路徑更平滑，就可以減少物體移動過程中改變方向的次數(shù)，以達(dá)到路徑優(yōu)化的效果。

本發(fā)明是這樣實(shí)現(xiàn)的：一種虛擬場景中有寬度物體移動路徑的優(yōu)化方法，包括如下步驟：

步驟10、使用掩碼地圖數(shù)據(jù)，經(jīng)過尋路算法搜索后，得到一個由一組連續(xù)路徑節(jié)點(diǎn)組成的節(jié)點(diǎn)集，節(jié)點(diǎn)集首尾分別為路徑的起始節(jié)點(diǎn)S和終止節(jié)點(diǎn)E；并檢查節(jié)點(diǎn)集的數(shù)據(jù)是否有效；

步驟20、先將起始節(jié)點(diǎn)S作為判斷起點(diǎn)在所有剩余節(jié)點(diǎn)中查找起始節(jié)點(diǎn)S可見的最遠(yuǎn)節(jié)點(diǎn)，該最遠(yuǎn)節(jié)點(diǎn)為第一最遠(yuǎn)節(jié)點(diǎn)T1，再將第一最遠(yuǎn)節(jié)點(diǎn)T1作為判斷起點(diǎn)查找可見的最遠(yuǎn)節(jié)點(diǎn)，得到第二最遠(yuǎn)的節(jié)點(diǎn)T2，再由第二最遠(yuǎn)節(jié)點(diǎn)T2作為判斷起點(diǎn)查找可見的最遠(yuǎn)節(jié)點(diǎn)，得到第三最遠(yuǎn)節(jié)點(diǎn)T3，然后按此規(guī)律一直查找下去，直到所可見的最遠(yuǎn)節(jié)點(diǎn)為終止節(jié)點(diǎn)E為止；

所述可見是指有寬度物體在從判斷起點(diǎn)到目標(biāo)節(jié)點(diǎn)的途中不會有障礙物；所述可見的最遠(yuǎn)節(jié)點(diǎn)是指離判斷起點(diǎn)最遠(yuǎn)的目標(biāo)節(jié)點(diǎn)；

步驟30、最后，將起始節(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)順次連接起來，所得到的連線即為優(yōu)化路徑。

其中，所述步驟20中，判定所述可見的最遠(yuǎn)節(jié)點(diǎn)的方法是：計算有寬度物體從判斷起點(diǎn)到目標(biāo)節(jié)點(diǎn)的移動過程的矩形區(qū)域外圍，所有位于該矩形區(qū)域內(nèi)的完整節(jié)點(diǎn)和部分節(jié)點(diǎn)即為掃描節(jié)點(diǎn)集，判斷該掃描節(jié)點(diǎn)集中是否有障礙物節(jié)點(diǎn)，若有則不可見，若無則可見。

進(jìn)一步的，所述判定所述可見的最遠(yuǎn)節(jié)點(diǎn)的方法具體過程如下：

步驟21：假設(shè)物體占地區(qū)域長度為橫向節(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；

步驟22：定位所述有寬度物體的重心節(jié)點(diǎn)，計算重心節(jié)點(diǎn)從四個方向到達(dá)物體邊緣的距離left、top、right、bottom，得到以下數(shù)據(jù)：

left=(L-1)/2，

right=L/2，

bottom=(W-1)/2，

top=W/2；

步驟23：計算有寬度物體移動過程的矩形區(qū)域外圍，得出該矩形區(qū)域的兩個對角線頂點(diǎn)所在節(jié)點(diǎn)的坐標(biāo)分別為(minX,minY),(maxX,maxY)，其中：

minX=min(x1,x2)–left，

minY=min(y1,y2)–bottom，

maxX=max(x1,x2)+right，