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

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

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

0 引言

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

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

本文通過分析上述算法的優(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ù)最后可能會得到不同的尋路結(jié)果[3]。A*算法的估價(jià)函數(shù)如式(1)所示：

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

(1)

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

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

(1)曼哈頓距離

若節(jié)點(diǎn)A的坐標(biāo)為(xa,xa)，節(jié)點(diǎn)B的坐標(biāo)為(xb,xb)，在場景中沿水平方向或者垂直方向移動一個單位的代價(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)，在場景中沿水平方向或者垂直方向移動一個單位的代價(jià)為D。則節(jié)點(diǎn)A與節(jié)點(diǎn)B的距離dis為：

(3)

(3)對角線距離

dx=|xa-xb|

dy=|ya-yb|

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

dis=dis_l+dis_k

(4)

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

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

2 A*加速算法

2.1 物體碰撞檢測

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

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

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

2.2 搜索策略

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

(5)

在實(shí)際應(yīng)用中，對于路徑節(jié)點(diǎn)E，它的每個鄰接節(jié)點(diǎn)Ei都是待搜索節(jié)點(diǎn)，Ei的方向信息是其父節(jié)點(diǎn)E至本身節(jié)點(diǎn)的方向向量，則對于節(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)是不可通過節(jié)點(diǎn)且節(jié)點(diǎn)(xn+1,yn+1)可通過節(jié)點(diǎn)。

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

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

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

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

2.3 算法描述

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

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

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

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

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

②如果Pi不在OpenSet中，則通過啟發(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í)行。

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

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

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

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

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

圖2 本文算法尋路效果圖

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

4 結(jié)論

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