謝楊潔++張釗維++葉鵬飛++楊瑤瑤

摘要：本文首先提取三維虛擬漫游場景的特征向量，在此基礎(chǔ)上進(jìn)行路徑選擇，并提出基于A*算法的優(yōu)化方案。該方案將提取的特征向量離散化為二進(jìn)制信息單元，以歐拉距離為基礎(chǔ)結(jié)合橡皮條算法進(jìn)行啟發(fā)函數(shù)的優(yōu)化選取。

關(guān)鍵詞：A*算法 規(guī)避障礙 最短路徑 柵格化

中圖分類號：TP311.52 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2014）08-0099-02

3D漫游動畫技術(shù)是繼多媒體技術(shù)之后的21世紀(jì)代表性技術(shù)?；贔lash3D技術(shù)的校園3D漫游系統(tǒng)將使觀察者逼真的感受到校園場景分布，地圖導(dǎo)游，充分感受校園的美好風(fēng)光。而許多漫游系統(tǒng)都缺乏高效性，用戶在使用過程中會碰到大量的延遲。本文主要討論優(yōu)化漫游過程中的路徑選擇算法，以提高漫游系統(tǒng)的效率和速度。

1 漫游環(huán)境的表示

漫游環(huán)境的表示是將現(xiàn)實3D環(huán)境轉(zhuǎn)換成虛擬環(huán)境的過程。對虛擬環(huán)境的表示基本上有4 種方法[1]：①障礙物的多邊形表示；②無障區(qū)域的表示；③均勻網(wǎng)格方法；④路徑圖。而無障區(qū)域的表示與路徑圖被公認(rèn)為不適于表示復(fù)雜的3D環(huán)境，另外Schwartz和Sharir[2]曾經(jīng)在報告中指出在3D情況中，多邊形表示方法的運(yùn)行時間復(fù)雜度會達(dá)到指數(shù)級。因此，大多數(shù)的3D虛擬環(huán)境的表示都選擇了網(wǎng)格表示法。本文中我們將采用的正是二進(jìn)制網(wǎng)格表示的方法。其實質(zhì)為通過對虛擬環(huán)境的柵格化實現(xiàn)從模擬信息到數(shù)字信息的轉(zhuǎn)化。

1.1 環(huán)境柵格化

人物的行走只是發(fā)生在地面的二維平面上，所以在研究碰撞檢驗時，地面的占據(jù)情況足夠來表示行走的可行性?；谝?guī)矩形的柵格單元，首先提取三維虛擬場景特征向量，對其進(jìn)行均勻網(wǎng)格化，并用二進(jìn)制來表示特征向量的信息。根據(jù)一般的制圖習(xí)慣，將圖形的左下角的頂點(diǎn)作為坐標(biāo)原點(diǎn)，而以坐標(biāo)原點(diǎn)出發(fā)水平向右為水平方向（X軸）正方向，以坐標(biāo)源點(diǎn)出發(fā)豎直向上為垂直方向（Y軸）正方向。每一個單元格用一個二維數(shù)組map[i][j]表示，map[i][j]的值為在X軸正上方j(luò)個單元，在Y軸正右方i個單元所存儲的環(huán)境信息。map即為我們所建立的數(shù)字地圖。對于靜態(tài)環(huán)境，這種離散只需要執(zhí)行一次。

1.2 障礙物的二進(jìn)制表示

對于任何一個單元點(diǎn)均包含自己的特定值。其中，當(dāng)值為0的時候表示在虛擬三維環(huán)境中，該點(diǎn)是可以通行的。相反，當(dāng)值取1的時候則表示該點(diǎn)已被占據(jù)。即對于任意一個單元格中的值，我們可以用下列表達(dá)式進(jìn)行描述

由此可見，針對已知的虛擬環(huán)境如圖1-1，對其進(jìn)行柵格化，我們可以得到如圖1-2的結(jié)果。

轉(zhuǎn)化后的圖形依舊保持三維影像的平面感，在進(jìn)行數(shù)據(jù)處理時需要將平面按順時針進(jìn)行45°的旋轉(zhuǎn)。如圖1-3。

2 算法描述

2.1 算法定義

A*算法是一種靜態(tài)網(wǎng)格路徑求解最短路徑最有效的方法。算法實際上可以理解為一種貪心的過程，每個階段都要使用貪心的思想來尋找代價最小的路徑。使用合適的啟發(fā)函數(shù)可以高效地找出兩點(diǎn)之間的最佳路徑。事實上，A*算法的關(guān)鍵部分正是啟發(fā)函數(shù)，這個啟發(fā)函數(shù)不是由 A*算法本身決定的，而是根據(jù)實際情況進(jìn)行自主選擇。也正是這種特性使得A*算法具備更強(qiáng)的可移植性和適用性。

2.2 估價函數(shù)

A*算法的估價函數(shù)的形式為一個簡單的加法表達(dá)式

，

其含義為x點(diǎn)到出發(fā)點(diǎn)的代價。其中h（x）表示x點(diǎn)到出發(fā)點(diǎn)的估計代價，而g（x）則表示x點(diǎn)到起點(diǎn)的實際代價，是一個確定常數(shù)值。凡是一定能找到最佳求解路徑的搜索算法稱為可采納的（admissible），數(shù)學(xué)上已嚴(yán)格證明A*算法是可采納的。其充要條件是：對任意結(jié)點(diǎn)n，都有，

h（n）是n到目標(biāo)的實際最短距離[3]。這時，也稱h（n）是可采納的且必然存在。

A*算法的選擇原則為啟發(fā)函數(shù)必須可納，否則算法將無法保證最后的解是最優(yōu)的。在啟發(fā)函數(shù)可采納的前提條件下應(yīng)盡量使h（x）的值接近h（x）導(dǎo)數(shù)的值。在h（x）=0情況下，A*算法將完全退化成一般深度搜索的dijkstra算法，雖然能找到最優(yōu)解，但是失去啟發(fā)式搜索的啟發(fā)信息。所以在估價函數(shù)的選擇過程中應(yīng)盡量使。

因此，對于幾何路網(wǎng)來說，可以取兩節(jié)點(diǎn)間歐幾理德距離（直線距離）做為估價值，即

如圖2-1。這樣估價函數(shù)f在g值一定的情況下，會或多或少的受估價值h的制約，節(jié)點(diǎn)距目標(biāo)點(diǎn)近，h值小，f值相對就小，能保證最短路的搜索向終點(diǎn)的方向進(jìn)行。但是在模擬現(xiàn)實的環(huán)境中必然存在障礙物，而對障礙物的規(guī)避會不可避免的導(dǎo)致代價的增大。所以單純的歐拉距離會直接導(dǎo)致估計代價小于實際代價而致使算法不可采納。為此，本文采取基于歐拉路徑的優(yōu)化路徑，如圖2-2。步驟如下：

Step1：選取原點(diǎn)與目標(biāo)點(diǎn)的歐拉距離。

Step2：若遇到障礙物，沿著障礙物的邊沿到達(dá)障礙物邊界。

Step3：以新到達(dá)的邊界點(diǎn)為原點(diǎn)，重復(fù)步驟1和步驟2直到到達(dá)目標(biāo)點(diǎn)。

表面上來看，優(yōu)化歐拉的計算繁瑣復(fù)雜，點(diǎn)與點(diǎn)之間的估計代價不能一下子確定。但是對于一個靜態(tài)環(huán)境而言，點(diǎn)與點(diǎn)之間的估計代價是可以確定的，即啟發(fā)函數(shù)值的計算只要進(jìn)行一次即可。所以只好做好前序工作，就可以使路徑的尋找更加準(zhǔn)確高效。優(yōu)化后的路徑和橡皮條算法[4]所得到的路徑有類似之處，但相比之下該路徑會更短。

2.3 算法的實現(xiàn)

算法實現(xiàn)的過程可用以下步驟簡要描述：

Step1：設(shè)置兩個頂點(diǎn)集合T和S。其中，S中存放已找到最短路徑的頂點(diǎn)。初始狀態(tài)時，集合S中只有一個頂點(diǎn)，即原點(diǎn)V0；T中存放當(dāng)前還未找到最短路徑的頂點(diǎn)；

Step2：求得從S中的頂點(diǎn)到T中的頂點(diǎn)的所有路徑中代價最小的路徑，假設(shè)該節(jié)點(diǎn)為Vk。將Vk加入到頂點(diǎn)集合S中。endprint

Step3：繼續(xù)重復(fù)步驟2，直到所有頂點(diǎn)都加入到集合S中，或從集合S中的任意頂點(diǎn)出發(fā)到集合T中的任意頂點(diǎn)都不存在可行路徑。

為了實現(xiàn)以上步驟來完成最短路徑的搜索，除了以上的S與T集合以為，另外需要設(shè)置2個關(guān)鍵數(shù)組。

（1）fval[i]：表示當(dāng)前找到的從原點(diǎn)V0到終點(diǎn)Vi的最小代價、初始狀態(tài)下，fval[i]為gval[V0][i]，為鄰接矩陣的第V0行，表示V0點(diǎn)到終點(diǎn)Vi的實際代價。

（2）path[i]：表示在最短路徑頂點(diǎn)Vi的前一個頂點(diǎn)號。對于后期實現(xiàn)路徑的可視化至關(guān)重要。

其中，最關(guān)鍵的核心數(shù)組是fval[ ]。通過對fval的遞推修改，時刻更新保存最小代價。其遞推公式如下：

初始：fval[k]=gval[V0][Vk]，V0為原點(diǎn)

由此可見，對于每次查找我們需要對fval[i]做反復(fù)操作：

Step1：在fval里查找屬于S集合并且fval[i]值最小的節(jié)點(diǎn)u。

Step2：將u加入集合S。

Step3：修改其他頂點(diǎn)的fval及path。當(dāng)節(jié)點(diǎn)k屬于S，同時節(jié)點(diǎn)k可以直接到達(dá)節(jié)點(diǎn)u，即在k與u之間至少存在一條可行路徑并且fval[u]+g[u][k]

3 結(jié)果測試

3.1 測試環(huán)境

本次算法研究的測試環(huán)境為CodeBlocks 8.02。以一個8*8的網(wǎng)格作為虛擬環(huán)境測試。其中，障礙物占據(jù)8個連續(xù)的單元塊。測試的結(jié)果只輸出算法所選擇的最短路徑，如A->C->D->B。另外，在滿足多元規(guī)劃的同時必然滿足單元規(guī)劃，所以這里單元測試不再進(jìn)行。根據(jù)輸出的路徑，我們進(jìn)行人工制圖檢測算法的可行性。

3.2 測試

測試條件：測試數(shù)據(jù)規(guī)定A處出發(fā)，需要達(dá)到的點(diǎn)為B，C，D。

算法求得路徑為：A->B->C->D。（如圖4-3所示）

4 結(jié)語

本文提出了在虛擬障礙環(huán)境中進(jìn)行全局漫游的路徑規(guī)劃算法。該方法以提取的特征向量為基礎(chǔ)，通過二進(jìn)制信息存儲的方式對其進(jìn)行離散化，結(jié)合啟發(fā)函數(shù)的優(yōu)化實現(xiàn)基于A*算法的多元路徑選擇。但目前算法只是停留在針對靜態(tài)環(huán)境的搜索，對于動態(tài)的環(huán)境還要進(jìn)行下一步的研究。

參考文獻(xiàn)

[1]Jones L A， Lang J H. A state observer for the Permanent-Magnet Synchronous Motor [J]. IEEE Trans. on Industrial Electronics

（S0278-0046），1989，36（3）：374-382.

[2]Chen S， Nahrstedt K. Distributed QoS Routing with Imprecise State Information. In Proceedings of 7th IEEE International Conference on Computer， Communications and Networks （ICCCN'98）， Lafayette， LA， 1998，10：614-621.

[3]鐘敏.A*算法估價函數(shù)的特性分析[J].武漢工程職業(yè)技術(shù)學(xué)院學(xué)報，2006，6：31-33.

[4]陳勇，王棟，陳戈.一種三維虛擬場景自動漫游的快速路徑規(guī)劃算法[J].系統(tǒng)仿真學(xué)報，2007，7：2507-2554.

Step3：繼續(xù)重復(fù)步驟2，直到所有頂點(diǎn)都加入到集合S中，或從集合S中的任意頂點(diǎn)出發(fā)到集合T中的任意頂點(diǎn)都不存在可行路徑。

為了實現(xiàn)以上步驟來完成最短路徑的搜索，除了以上的S與T集合以為，另外需要設(shè)置2個關(guān)鍵數(shù)組。

（1）fval[i]：表示當(dāng)前找到的從原點(diǎn)V0到終點(diǎn)Vi的最小代價、初始狀態(tài)下，fval[i]為gval[V0][i]，為鄰接矩陣的第V0行，表示V0點(diǎn)到終點(diǎn)Vi的實際代價。

（2）path[i]：表示在最短路徑頂點(diǎn)Vi的前一個頂點(diǎn)號。對于后期實現(xiàn)路徑的可視化至關(guān)重要。

其中，最關(guān)鍵的核心數(shù)組是fval[ ]。通過對fval的遞推修改，時刻更新保存最小代價。其遞推公式如下：

初始：fval[k]=gval[V0][Vk]，V0為原點(diǎn)

由此可見，對于每次查找我們需要對fval[i]做反復(fù)操作：

Step1：在fval里查找屬于S集合并且fval[i]值最小的節(jié)點(diǎn)u。

Step2：將u加入集合S。

Step3：修改其他頂點(diǎn)的fval及path。當(dāng)節(jié)點(diǎn)k屬于S，同時節(jié)點(diǎn)k可以直接到達(dá)節(jié)點(diǎn)u，即在k與u之間至少存在一條可行路徑并且fval[u]+g[u][k]

3 結(jié)果測試

3.1 測試環(huán)境

本次算法研究的測試環(huán)境為CodeBlocks 8.02。以一個8*8的網(wǎng)格作為虛擬環(huán)境測試。其中，障礙物占據(jù)8個連續(xù)的單元塊。測試的結(jié)果只輸出算法所選擇的最短路徑，如A->C->D->B。另外，在滿足多元規(guī)劃的同時必然滿足單元規(guī)劃，所以這里單元測試不再進(jìn)行。根據(jù)輸出的路徑，我們進(jìn)行人工制圖檢測算法的可行性。

3.2 測試

測試條件：測試數(shù)據(jù)規(guī)定A處出發(fā)，需要達(dá)到的點(diǎn)為B，C，D。

算法求得路徑為：A->B->C->D。（如圖4-3所示）

4 結(jié)語

本文提出了在虛擬障礙環(huán)境中進(jìn)行全局漫游的路徑規(guī)劃算法。該方法以提取的特征向量為基礎(chǔ)，通過二進(jìn)制信息存儲的方式對其進(jìn)行離散化，結(jié)合啟發(fā)函數(shù)的優(yōu)化實現(xiàn)基于A*算法的多元路徑選擇。但目前算法只是停留在針對靜態(tài)環(huán)境的搜索，對于動態(tài)的環(huán)境還要進(jìn)行下一步的研究。

參考文獻(xiàn)

[1]Jones L A， Lang J H. A state observer for the Permanent-Magnet Synchronous Motor [J]. IEEE Trans. on Industrial Electronics

（S0278-0046），1989，36（3）：374-382.

[2]Chen S， Nahrstedt K. Distributed QoS Routing with Imprecise State Information. In Proceedings of 7th IEEE International Conference on Computer， Communications and Networks （ICCCN'98）， Lafayette， LA， 1998，10：614-621.

[3]鐘敏.A*算法估價函數(shù)的特性分析[J].武漢工程職業(yè)技術(shù)學(xué)院學(xué)報，2006，6：31-33.

[4]陳勇，王棟，陳戈.一種三維虛擬場景自動漫游的快速路徑規(guī)劃算法[J].系統(tǒng)仿真學(xué)報，2007，7：2507-2554.

Step3：繼續(xù)重復(fù)步驟2，直到所有頂點(diǎn)都加入到集合S中，或從集合S中的任意頂點(diǎn)出發(fā)到集合T中的任意頂點(diǎn)都不存在可行路徑。

為了實現(xiàn)以上步驟來完成最短路徑的搜索，除了以上的S與T集合以為，另外需要設(shè)置2個關(guān)鍵數(shù)組。

（1）fval[i]：表示當(dāng)前找到的從原點(diǎn)V0到終點(diǎn)Vi的最小代價、初始狀態(tài)下，fval[i]為gval[V0][i]，為鄰接矩陣的第V0行，表示V0點(diǎn)到終點(diǎn)Vi的實際代價。

（2）path[i]：表示在最短路徑頂點(diǎn)Vi的前一個頂點(diǎn)號。對于后期實現(xiàn)路徑的可視化至關(guān)重要。

其中，最關(guān)鍵的核心數(shù)組是fval[ ]。通過對fval的遞推修改，時刻更新保存最小代價。其遞推公式如下：

初始：fval[k]=gval[V0][Vk]，V0為原點(diǎn)

由此可見，對于每次查找我們需要對fval[i]做反復(fù)操作：

Step1：在fval里查找屬于S集合并且fval[i]值最小的節(jié)點(diǎn)u。

Step2：將u加入集合S。

Step3：修改其他頂點(diǎn)的fval及path。當(dāng)節(jié)點(diǎn)k屬于S，同時節(jié)點(diǎn)k可以直接到達(dá)節(jié)點(diǎn)u，即在k與u之間至少存在一條可行路徑并且fval[u]+g[u][k]

3 結(jié)果測試

3.1 測試環(huán)境

本次算法研究的測試環(huán)境為CodeBlocks 8.02。以一個8*8的網(wǎng)格作為虛擬環(huán)境測試。其中，障礙物占據(jù)8個連續(xù)的單元塊。測試的結(jié)果只輸出算法所選擇的最短路徑，如A->C->D->B。另外，在滿足多元規(guī)劃的同時必然滿足單元規(guī)劃，所以這里單元測試不再進(jìn)行。根據(jù)輸出的路徑，我們進(jìn)行人工制圖檢測算法的可行性。

3.2 測試

測試條件：測試數(shù)據(jù)規(guī)定A處出發(fā)，需要達(dá)到的點(diǎn)為B，C，D。

算法求得路徑為：A->B->C->D。（如圖4-3所示）

4 結(jié)語

本文提出了在虛擬障礙環(huán)境中進(jìn)行全局漫游的路徑規(guī)劃算法。該方法以提取的特征向量為基礎(chǔ)，通過二進(jìn)制信息存儲的方式對其進(jìn)行離散化，結(jié)合啟發(fā)函數(shù)的優(yōu)化實現(xiàn)基于A*算法的多元路徑選擇。但目前算法只是停留在針對靜態(tài)環(huán)境的搜索，對于動態(tài)的環(huán)境還要進(jìn)行下一步的研究。

參考文獻(xiàn)

[1]Jones L A， Lang J H. A state observer for the Permanent-Magnet Synchronous Motor [J]. IEEE Trans. on Industrial Electronics

（S0278-0046），1989，36（3）：374-382.

[2]Chen S， Nahrstedt K. Distributed QoS Routing with Imprecise State Information. In Proceedings of 7th IEEE International Conference on Computer， Communications and Networks （ICCCN'98）， Lafayette， LA， 1998，10：614-621.

[3]鐘敏.A*算法估價函數(shù)的特性分析[J].武漢工程職業(yè)技術(shù)學(xué)院學(xué)報，2006，6：31-33.

[4]陳勇，王棟，陳戈.一種三維虛擬場景自動漫游的快速路徑規(guī)劃算法[J].系統(tǒng)仿真學(xué)報，2007，7：2507-2554.