面向虛擬現(xiàn)實(shí)的A*算法的分析與改進(jìn)

宋 健,何小海,王正勇,卿粼波

(四川大學(xué) 電子信息學(xué)院圖像信息研究所，四川 成都 610064)

0 引言

虛擬現(xiàn)實(shí)技術(shù)是一種可以創(chuàng)建虛擬環(huán)境的多種技術(shù)的集合[1]，它通過(guò)計(jì)算機(jī)和外圍傳感器生成一個(gè)虛擬的3D環(huán)境，使用者可以與虛擬環(huán)境進(jìn)行交互，除了提供視覺(jué)感知外，還包含其他多感知技術(shù)，是一種綜合性極強(qiáng)、多學(xué)科交叉的前沿技術(shù)。目前，虛擬現(xiàn)實(shí)技術(shù)主要應(yīng)用于游戲、教育以及參觀展示方面，在一些大型游戲或場(chǎng)景中，使用者通常不知道自己身在何處，也不知道目的地該如何前往，因此對(duì)虛擬場(chǎng)景進(jìn)行路徑規(guī)劃就顯得格外重要。然而，相較于一般的路徑規(guī)劃，面向虛擬現(xiàn)實(shí)的路徑規(guī)劃則要更為復(fù)雜一些，它面向的是虛擬物體和場(chǎng)景，涉及3D網(wǎng)格的構(gòu)建以及障礙物檢測(cè)，這對(duì)路徑搜索算法的效率提出了更高的要求。

路徑搜索可以分為兩類：盲目搜索和啟發(fā)式搜索。盲目搜索是一種無(wú)信息搜索，它通常不考慮節(jié)點(diǎn)本身的特性，直接按照預(yù)定的策略進(jìn)行搜索，適用于問(wèn)題比較簡(jiǎn)單的情況。常用的盲目搜索算法有：深度優(yōu)先搜索和廣度優(yōu)先搜索。深度優(yōu)先搜索的缺點(diǎn)是可能搜索出來(lái)的路徑不是最優(yōu)路徑，廣度優(yōu)先搜索的不足在于搜索過(guò)程中占用的內(nèi)存較大。其中有一種經(jīng)典的尋路算法是Dijkstra算法，它雖然可以找到最優(yōu)路徑，但是不足之處在于尋路過(guò)程中遍歷的節(jié)點(diǎn)太多從而會(huì)影響算法的效率。因此在自動(dòng)尋路算法中，常用的方法是啟發(fā)式搜索，它會(huì)對(duì)待搜索列表中的元素進(jìn)行代價(jià)評(píng)估，找到其中代價(jià)最優(yōu)的位置，然后從這個(gè)位置繼續(xù)往前探索，最后找到路徑終點(diǎn)停止[2]。目前，A*算法是一種常用的啟發(fā)式搜索算法，經(jīng)常用來(lái)尋找最優(yōu)路徑。相比Dijkstra算法，A*算法雖然降低了尋路過(guò)程中查找的節(jié)點(diǎn)，但對(duì)于相對(duì)復(fù)雜的場(chǎng)景來(lái)說(shuō)，其效率仍然不夠理想。

本文通過(guò)分析上述算法的優(yōu)缺點(diǎn)，結(jié)合深度優(yōu)先搜索和啟發(fā)式搜索，提出了一種結(jié)合尋路節(jié)點(diǎn)的方向信息的加速算法，該算法既能保證所得路徑是最優(yōu)路徑還能提高尋路的效率。

1 A*算法

在靜態(tài)網(wǎng)格中，A*算法是搜索最優(yōu)路徑的有效方法，但采用不同的估價(jià)函數(shù)最后可能會(huì)得到不同的尋路結(jié)果[3]。A*算法的估價(jià)函數(shù)如式(1)所示：

f(n)=g(n)+h(n)

(1)

其中，g(n)表示從出發(fā)點(diǎn)移動(dòng)到指定節(jié)點(diǎn)n的實(shí)際代價(jià)，而h(n)是從節(jié)點(diǎn)n到目的地的最小代價(jià)估計(jì)，f(n)表示從出發(fā)點(diǎn)搜索到目的地的最優(yōu)路徑的總代價(jià)[4]。

在尋路的過(guò)程中，往往尋得的路徑不止一條，但不同路徑所花的代價(jià)可能不同，因此需要找到一條代價(jià)最小的路徑。然而，即使代價(jià)相同的路徑也有可能出現(xiàn)不同的走法。在實(shí)際應(yīng)用中，h(n)與g(n)度量的路徑代價(jià)都是兩個(gè)節(jié)點(diǎn)間的距離值，常見(jiàn)的距離計(jì)算方式有曼哈頓距離、歐幾里得距離和對(duì)角線距離[5]。

(1)曼哈頓距離

若節(jié)點(diǎn)A的坐標(biāo)為(xa,xa)，節(jié)點(diǎn)B的坐標(biāo)為(xb,xb)，在場(chǎng)景中沿水平方向或者垂直方向移動(dòng)一個(gè)單位的代價(jià)為D。則節(jié)點(diǎn)A與節(jié)點(diǎn)B的距離dis為：

dis=D(|xa-xb|+|ya-yb|)

(2)

(2)歐幾里得距離

若節(jié)點(diǎn)A的坐標(biāo)為(xa,xa)，節(jié)點(diǎn)B的坐標(biāo)為(xb,xb)，在場(chǎng)景中沿水平方向或者垂直方向移動(dòng)一個(gè)單位的代價(jià)為D。則節(jié)點(diǎn)A與節(jié)點(diǎn)B的距離dis為：

(3)

(3)對(duì)角線距離

dx=|xa-xb|

dy=|ya-yb|

dis_k=D(dx+dy-2min(dx,dy))

dis=dis_l+dis_k

(4)

相比曼哈頓距離，對(duì)角線距離不僅對(duì)水平和垂直兩個(gè)方向的路徑進(jìn)行代價(jià)估計(jì)，還可以估計(jì)對(duì)角線方向的路徑代價(jià)，而且與歐幾里得距離的計(jì)算方法相比，其運(yùn)算復(fù)雜度也較小，因此，本文采用對(duì)角線距離作為啟發(fā)函數(shù)來(lái)計(jì)算距離。

A*算法的主要思想是：先建立兩個(gè)表(OpenSet和CloseSet)，OpenSet表用于存儲(chǔ)那些準(zhǔn)備搜索、但還沒(méi)加入最佳路徑的節(jié)點(diǎn)，CloseSet表用來(lái)存放已加入最佳路徑的節(jié)點(diǎn)。每次通過(guò)對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行八鄰域擴(kuò)展，然后對(duì)每個(gè)鄰接節(jié)點(diǎn)進(jìn)行考察，若為不可通過(guò)節(jié)點(diǎn)或存在于CloseSet表中則直接跳過(guò)，否則通過(guò)啟發(fā)函數(shù)計(jì)算該節(jié)點(diǎn)的f、g、h值并進(jìn)行更新，最后從OpenSet表中選取f值最小的節(jié)點(diǎn)N，將其作為當(dāng)前節(jié)點(diǎn)加入CloseSet表中并開(kāi)始下一個(gè)路徑節(jié)點(diǎn)的搜索。

2 A*加速算法

2.1 物體碰撞檢測(cè)

網(wǎng)格中除了坐標(biāo)信息還必須有障礙物信息，這就需要對(duì)場(chǎng)景進(jìn)行障礙物檢測(cè)。目前，常用的方法有空間分割法和包圍盒法[6]?？臻g分割法是將虛擬場(chǎng)景進(jìn)行均勻劃分，再檢測(cè)相交的模塊，可以快速剔除不相交的物體。該方法雖然對(duì)較少模型的虛擬環(huán)境效率較高，但在復(fù)雜的場(chǎng)景中，該方法不僅空間占據(jù)率較大且效率較低。包圍盒法主要是采用近似三維場(chǎng)景中模型的立體幾何對(duì)象將模型包圍起來(lái)，之后在做障礙物檢測(cè)時(shí)不需要考慮兩個(gè)模型的每個(gè)面是否相交，而只需要對(duì)兩個(gè)立方體進(jìn)行檢測(cè)，這也就極大地減少了面與面的相交測(cè)試數(shù)量，提升了檢測(cè)的效率，故該算法被廣泛應(yīng)用于各種VR場(chǎng)景的障礙物檢測(cè)。本系統(tǒng)使用的正是包圍盒法，本文主要介紹軸對(duì)齊包圍盒，它是一個(gè)包含該物體的最小長(zhǎng)方體，它的創(chuàng)建比較簡(jiǎn)單，分別找出對(duì)象的所有頂點(diǎn)坐標(biāo)的最大值(xmax,ymax,zmax)和最小值(xmin,ymin,zmin)就能確定[7]。它包含的區(qū)域范圍為：

R={(X,Y,Z)|xmin≤X≤xmax,ymin≤Y≤ymax,zmin≤Z≤zmax}

通過(guò)對(duì)整個(gè)場(chǎng)景進(jìn)行全盤(pán)掃描，檢測(cè)每個(gè)網(wǎng)格中是否存在包圍盒區(qū)域，若存在，則將此網(wǎng)格標(biāo)記為不可通過(guò)，否則標(biāo)記為可通過(guò)。如圖1所示，深色區(qū)域?yàn)椴豢赏ㄟ^(guò)。

圖1 網(wǎng)格構(gòu)建效果圖

2.2 搜索策略

尋路網(wǎng)格確定后，需要考慮的就是路徑搜索策略了。傳統(tǒng)A*算法雖然通過(guò)估算節(jié)點(diǎn)的路徑代價(jià)減少了尋路節(jié)點(diǎn)的數(shù)量，但沒(méi)有充分利用網(wǎng)格節(jié)點(diǎn)之間的位置關(guān)系。本文通過(guò)添加尋路節(jié)點(diǎn)的方向信息以及相應(yīng)的搜索約束規(guī)則，對(duì)A*算法進(jìn)行加速。

(5)

在實(shí)際應(yīng)用中，對(duì)于路徑節(jié)點(diǎn)E，它的每個(gè)鄰接節(jié)點(diǎn)Ei都是待搜索節(jié)點(diǎn)，Ei的方向信息是其父節(jié)點(diǎn)E至本身節(jié)點(diǎn)的方向向量，則對(duì)于節(jié)點(diǎn)N=(xn,yn)至其父節(jié)點(diǎn)Np=(xpn,ypn)的方向向量為：

dx=xpn-xn

dy=ypn-yn

(6)

(1)當(dāng)dxN·dxD≥0且dyD≥0時(shí)，節(jié)點(diǎn)(xn,yn+1)是不可通過(guò)節(jié)點(diǎn)且節(jié)點(diǎn)(xn+1,yn+1)可通過(guò)節(jié)點(diǎn)。

(2)當(dāng)dxN·dxD≥0且dyD≤0時(shí)，節(jié)點(diǎn)(xn,yn-1)不可通過(guò)節(jié)點(diǎn)且節(jié)點(diǎn)(xn+1,yn-1)可通過(guò)節(jié)點(diǎn)。

(3)當(dāng)dxN·dxD≤0且dyD≥0時(shí)，節(jié)點(diǎn)(xn,yn+1)不可通過(guò)節(jié)點(diǎn)且節(jié)點(diǎn)(xn-1,yn+1)可通過(guò)節(jié)點(diǎn)。

(4)當(dāng)dxN·dxD≤0且dyD≤0時(shí)，節(jié)點(diǎn)(xn,yn-1)不可通過(guò)節(jié)點(diǎn)且節(jié)點(diǎn)(xn-1,yn-1)可通過(guò)節(jié)點(diǎn)。

在A*算法尋路過(guò)程中，要確定下一個(gè)搜索節(jié)點(diǎn)時(shí)，必須將當(dāng)前節(jié)點(diǎn)的所有鄰接節(jié)點(diǎn)都加入OpenSet進(jìn)行考察，最后通過(guò)計(jì)算路徑代價(jià)確定最小的節(jié)點(diǎn)。

2.3 算法描述

上述加速后的A*算法，在獲得當(dāng)前OpenSet中路徑代價(jià)最小節(jié)點(diǎn)和帶有方向信息的鄰接節(jié)點(diǎn)后，對(duì)于每個(gè)鄰接節(jié)點(diǎn)，在自身方向上進(jìn)行遞歸查找，直到找到下一個(gè)搜索節(jié)點(diǎn)或不可通過(guò)節(jié)點(diǎn)時(shí)返回。A*加速算法可描述如下：

(1)OpenSet和CloseSet清空，將起點(diǎn)S加入OpenSet。

(2)若OpenSet為空，說(shuō)明尋路失敗，退出尋路過(guò)程。否則從OpenSet中選取f值最小的節(jié)點(diǎn)N，將其作為當(dāng)前節(jié)點(diǎn)加入CloseSet，并從OpenSet中移除。

(3)考察節(jié)點(diǎn)N是否為目的地D，如果是，說(shuō)明已找到最佳路徑，并結(jié)束尋路過(guò)程。如果不是，則獲取該節(jié)點(diǎn)的所有可通過(guò)鄰接節(jié)點(diǎn)Ni，根據(jù)每一個(gè)鄰接節(jié)點(diǎn)的方向信息按照約束規(guī)則進(jìn)行遞歸查找，直至得到下一個(gè)搜索節(jié)點(diǎn)，對(duì)每一個(gè)搜索節(jié)點(diǎn)Pi進(jìn)行下列步驟：

①若Pi為不可通行節(jié)點(diǎn)或Pi存在于CloseSet中，則不考慮。

②如果Pi不在OpenSet中，則通過(guò)啟發(fā)函數(shù)分別計(jì)算Pi的f、g、h值，將節(jié)點(diǎn)N設(shè)為Pi的父節(jié)點(diǎn)，并將Pi加入OpenSet。

③如果Pi在OpenSet中，則重新計(jì)算該節(jié)點(diǎn)的g值，若比Pi之前的g值小，則更新Pi的g值為重新計(jì)算的結(jié)果，將節(jié)點(diǎn)N設(shè)為Pi的父節(jié)點(diǎn)。

(4)轉(zhuǎn)到步驟(2)繼續(xù)執(zhí)行。

此算法通過(guò)計(jì)算尋路節(jié)點(diǎn)的方向信息，采用深度優(yōu)先搜索策略和約束規(guī)則，以節(jié)點(diǎn)方向?yàn)檫f歸方向，對(duì)下一個(gè)搜索節(jié)點(diǎn)進(jìn)行遞歸查找，從而節(jié)約了OpenSet的存儲(chǔ)空間，減少了路徑代價(jià)的計(jì)算次數(shù)，提高了尋路效率。

3 實(shí)驗(yàn)結(jié)果

本文提出的基于A*算法的加速研究應(yīng)用于一個(gè)地質(zhì)資料展示系統(tǒng)，并取得了良好的效果。本文采用C# 編程語(yǔ)言，基于Unity3D游戲引擎框架進(jìn)行開(kāi)發(fā)測(cè)試，虛擬現(xiàn)實(shí)設(shè)備采用三星GearVR，移動(dòng)設(shè)備采用三星Galaxy S7 edge，并在相同設(shè)備條件下，對(duì)傳統(tǒng)A*算法和本文提出的加速算法進(jìn)行了對(duì)比實(shí)驗(yàn)。

A*尋路算法的執(zhí)行效率主要從路徑的總長(zhǎng)度和OpenSet存儲(chǔ)節(jié)點(diǎn)個(gè)數(shù)中體現(xiàn)。表1為傳統(tǒng)A*算法和本文算法實(shí)驗(yàn)數(shù)據(jù)對(duì)比結(jié)果，圖2為本文算法尋路效果圖。

表1 算法執(zhí)行效率比較

圖2 本文算法尋路效果圖

從表1中可以看出，本文算法經(jīng)過(guò)搜索得到的路徑總長(zhǎng)度基本與傳統(tǒng)A*算法一致，從而保證了可靠性，但加速A*算法無(wú)論是OpenSet存儲(chǔ)節(jié)點(diǎn)個(gè)數(shù)還是路徑節(jié)點(diǎn)個(gè)數(shù)都遠(yuǎn)小于傳統(tǒng)A*算法，算法的空間性能得到了較大的提升，同時(shí)在時(shí)間性能上也優(yōu)于傳統(tǒng)算法。

4 結(jié)論

通過(guò)對(duì)傳統(tǒng)A*算法的分析以及實(shí)現(xiàn)，發(fā)現(xiàn)算法本身存在效率不足等問(wèn)題，于是通過(guò)引入路徑節(jié)點(diǎn)的方向信息，在尋路過(guò)程中進(jìn)行深度優(yōu)先搜索對(duì)算法進(jìn)行改進(jìn)，最后成功運(yùn)用到虛擬場(chǎng)景中，實(shí)現(xiàn)了對(duì)場(chǎng)景進(jìn)行尋路。實(shí)驗(yàn)結(jié)果較好地說(shuō)明了改進(jìn)的算法能夠保證尋路的可靠性，并且提高了傳統(tǒng)A*算法的尋路效率。