基于Flash 3D技術(shù)的浙江財(cái)經(jīng)學(xué)院漫游系統(tǒng)的研究

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

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

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

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

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

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

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

1.1 環(huán)境柵格化

人物的行走只是發(fā)生在地面的二維平面上，所以在研究碰撞檢驗(yàn)時(shí)，地面的占據(jù)情況足夠來表示行走的可行性。基于規(guī)矩形的柵格單元，首先提取三維虛擬場景特征向量，對(duì)其進(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軸）正方向。每一個(gè)單元格用一個(gè)二維數(shù)組map[i][j]表示，map[i][j]的值為在X軸正上方j(luò)個(gè)單元，在Y軸正右方i個(gè)單元所存儲(chǔ)的環(huán)境信息。map即為我們所建立的數(shù)字地圖。對(duì)于靜態(tài)環(huán)境，這種離散只需要執(zhí)行一次。

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

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

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

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

2 算法描述

2.1 算法定義

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

2.2 估價(jià)函數(shù)

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

，

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

h（n）是n到目標(biāo)的實(shí)際最短距離[3]。這時(shí)，也稱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ā)信息。所以在估價(jià)函數(shù)的選擇過程中應(yīng)盡量使。

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

如圖2-1。這樣估價(jià)函數(shù)f在g值一定的情況下，會(huì)或多或少的受估價(jià)值h的制約，節(jié)點(diǎn)距目標(biāo)點(diǎn)近，h值小，f值相對(duì)就小，能保證最短路的搜索向終點(diǎn)的方向進(jìn)行。但是在模擬現(xiàn)實(shí)的環(huán)境中必然存在障礙物，而對(duì)障礙物的規(guī)避會(huì)不可避免的導(dǎo)致代價(jià)的增大。所以單純的歐拉距離會(huì)直接導(dǎo)致估計(jì)代價(jià)小于實(shí)際代價(jià)而致使算法不可采納。為此，本文采取基于歐拉路徑的優(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)化歐拉的計(jì)算繁瑣復(fù)雜，點(diǎn)與點(diǎn)之間的估計(jì)代價(jià)不能一下子確定。但是對(duì)于一個(gè)靜態(tài)環(huán)境而言，點(diǎn)與點(diǎn)之間的估計(jì)代價(jià)是可以確定的，即啟發(fā)函數(shù)值的計(jì)算只要進(jìn)行一次即可。所以只好做好前序工作，就可以使路徑的尋找更加準(zhǔn)確高效。優(yōu)化后的路徑和橡皮條算法[4]所得到的路徑有類似之處，但相比之下該路徑會(huì)更短。

2.3 算法的實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

由此可見，對(duì)于每次查找我們需要對(duì)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，同時(shí)節(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。以一個(gè)8*8的網(wǎng)格作為虛擬環(huán)境測試。其中，障礙物占據(jù)8個(gè)連續(xù)的單元塊。測試的結(jié)果只輸出算法所選擇的最短路徑，如A->C->D->B。另外，在滿足多元規(guī)劃的同時(shí)必然滿足單元規(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)制信息存儲(chǔ)的方式對(duì)其進(jìn)行離散化，結(jié)合啟發(fā)函數(shù)的優(yōu)化實(shí)現(xiàn)基于A*算法的多元路徑選擇。但目前算法只是停留在針對(duì)靜態(tài)環(huán)境的搜索，對(duì)于動(dòng)態(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*算法估價(jià)函數(shù)的特性分析[J].武漢工程職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2006，6：31-33.

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

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

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

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

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

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

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

由此可見，對(duì)于每次查找我們需要對(duì)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，同時(shí)節(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。以一個(gè)8*8的網(wǎng)格作為虛擬環(huán)境測試。其中，障礙物占據(jù)8個(gè)連續(xù)的單元塊。測試的結(jié)果只輸出算法所選擇的最短路徑，如A->C->D->B。另外，在滿足多元規(guī)劃的同時(shí)必然滿足單元規(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)制信息存儲(chǔ)的方式對(duì)其進(jìn)行離散化，結(jié)合啟發(fā)函數(shù)的優(yōu)化實(shí)現(xiàn)基于A*算法的多元路徑選擇。但目前算法只是停留在針對(duì)靜態(tài)環(huán)境的搜索，對(duì)于動(dòng)態(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*算法估價(jià)函數(shù)的特性分析[J].武漢工程職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2006，6：31-33.

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

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

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

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

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

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

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

由此可見，對(duì)于每次查找我們需要對(duì)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，同時(shí)節(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。以一個(gè)8*8的網(wǎng)格作為虛擬環(huán)境測試。其中，障礙物占據(jù)8個(gè)連續(xù)的單元塊。測試的結(jié)果只輸出算法所選擇的最短路徑，如A->C->D->B。另外，在滿足多元規(guī)劃的同時(shí)必然滿足單元規(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)制信息存儲(chǔ)的方式對(duì)其進(jìn)行離散化，結(jié)合啟發(fā)函數(shù)的優(yōu)化實(shí)現(xiàn)基于A*算法的多元路徑選擇。但目前算法只是停留在針對(duì)靜態(tài)環(huán)境的搜索，對(duì)于動(dòng)態(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*算法估價(jià)函數(shù)的特性分析[J].武漢工程職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2006，6：31-33.

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