面向虛擬現實的A*算法的分析與改進

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

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

0 引言

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

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

本文通過分析上述算法的優缺點，結合深度優先搜索和啟發式搜索，提出了一種結合尋路節點的方向信息的加速算法，該算法既能保證所得路徑是最優路徑還能提高尋路的效率。

1 A*算法

在靜態網格中，A*算法是搜索最優路徑的有效方法，但采用不同的估價函數最后可能會得到不同的尋路結果[3]。A*算法的估價函數如式(1)所示：

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

(1)

其中，g(n)表示從出發點移動到指定節點n的實際代價，而h(n)是從節點n到目的地的最小代價估計，f(n)表示從出發點搜索到目的地的最優路徑的總代價[4]。

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

(1)曼哈頓距離

若節點A的坐標為(xa,xa)，節點B的坐標為(xb,xb)，在場景中沿水平方向或者垂直方向移動一個單位的代價為D。則節點A與節點B的距離dis為：

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

(2)

(2)歐幾里得距離

若節點A的坐標為(xa,xa)，節點B的坐標為(xb,xb)，在場景中沿水平方向或者垂直方向移動一個單位的代價為D。則節點A與節點B的距離dis為：

(3)

(3)對角線距離

dx=|xa-xb|

dy=|ya-yb|

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

dis=dis_l+dis_k

(4)

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

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

2 A*加速算法

2.1 物體碰撞檢測

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

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

通過對整個場景進行全盤掃描，檢測每個網格中是否存在包圍盒區域，若存在，則將此網格標記為不可通過，否則標記為可通過。如圖1所示，深色區域為不可通過。

圖1 網格構建效果圖

2.2 搜索策略

尋路網格確定后，需要考慮的就是路徑搜索策略了。傳統A*算法雖然通過估算節點的路徑代價減少了尋路節點的數量，但沒有充分利用網格節點之間的位置關系。本文通過添加尋路節點的方向信息以及相應的搜索約束規則，對A*算法進行加速。

(5)

在實際應用中，對于路徑節點E，它的每個鄰接節點Ei都是待搜索節點，Ei的方向信息是其父節點E至本身節點的方向向量，則對于節點N=(xn,yn)至其父節點Np=(xpn,ypn)的方向向量為：

dx=xpn-xn

dy=ypn-yn

(6)

(1)當dxN·dxD≥0且dyD≥0時，節點(xn,yn+1)是不可通過節點且節點(xn+1,yn+1)可通過節點。

(2)當dxN·dxD≥0且dyD≤0時，節點(xn,yn-1)不可通過節點且節點(xn+1,yn-1)可通過節點。

(3)當dxN·dxD≤0且dyD≥0時，節點(xn,yn+1)不可通過節點且節點(xn-1,yn+1)可通過節點。

(4)當dxN·dxD≤0且dyD≤0時，節點(xn,yn-1)不可通過節點且節點(xn-1,yn-1)可通過節點。

在A*算法尋路過程中，要確定下一個搜索節點時，必須將當前節點的所有鄰接節點都加入OpenSet進行考察，最后通過計算路徑代價確定最小的節點。

2.3 算法描述

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

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

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

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

①若Pi為不可通行節點或Pi存在于CloseSet中，則不考慮。

②如果Pi不在OpenSet中，則通過啟發函數分別計算Pi的f、g、h值，將節點N設為Pi的父節點，并將Pi加入OpenSet。

③如果Pi在OpenSet中，則重新計算該節點的g值，若比Pi之前的g值小，則更新Pi的g值為重新計算的結果，將節點N設為Pi的父節點。

(4)轉到步驟(2)繼續執行。

此算法通過計算尋路節點的方向信息，采用深度優先搜索策略和約束規則，以節點方向為遞歸方向，對下一個搜索節點進行遞歸查找，從而節約了OpenSet的存儲空間，減少了路徑代價的計算次數，提高了尋路效率。

3 實驗結果

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

A*尋路算法的執行效率主要從路徑的總長度和OpenSet存儲節點個數中體現。表1為傳統A*算法和本文算法實驗數據對比結果，圖2為本文算法尋路效果圖。

表1 算法執行效率比較

圖2 本文算法尋路效果圖

從表1中可以看出，本文算法經過搜索得到的路徑總長度基本與傳統A*算法一致，從而保證了可靠性，但加速A*算法無論是OpenSet存儲節點個數還是路徑節點個數都遠小于傳統A*算法，算法的空間性能得到了較大的提升，同時在時間性能上也優于傳統算法。

4 結論

通過對傳統A*算法的分析以及實現，發現算法本身存在效率不足等問題，于是通過引入路徑節點的方向信息，在尋路過程中進行深度優先搜索對算法進行改進，最后成功運用到虛擬場景中，實現了對場景進行尋路。實驗結果較好地說明了改進的算法能夠保證尋路的可靠性，并且提高了傳統A*算法的尋路效率。