基于Flash 3D技術的浙江財經學院漫游系統的研究

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

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

關鍵詞：A*算法 規避障礙 最短路徑 柵格化

中圖分類號：TP311.52 文獻標識碼：A 文章編號：1007-9416（2014）08-0099-02

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

1 漫游環境的表示

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

1.1 環境柵格化

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

1.2 障礙物的二進制表示

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

由此可見，針對已知的虛擬環境如圖1-1，對其進行柵格化，我們可以得到如圖1-2的結果。

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

2 算法描述

2.1 算法定義

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

2.2 估價函數

A*算法的估價函數的形式為一個簡單的加法表達式

，

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

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

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

因此，對于幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即

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

Step1：選取原點與目標點的歐拉距離。

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

Step3：以新到達的邊界點為原點，重復步驟1和步驟2直到到達目標點。

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

2.3 算法的實現

算法實現的過程可用以下步驟簡要描述：

Step1：設置兩個頂點集合T和S。其中，S中存放已找到最短路徑的頂點。初始狀態時，集合S中只有一個頂點，即原點V0；T中存放當前還未找到最短路徑的頂點；

Step2：求得從S中的頂點到T中的頂點的所有路徑中代價最小的路徑，假設該節點為Vk。將Vk加入到頂點集合S中。endprint

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

為了實現以上步驟來完成最短路徑的搜索，除了以上的S與T集合以為，另外需要設置2個關鍵數組。

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

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

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

初始：fval[k]=gval[V0][Vk]，V0為原點

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

Step1：在fval里查找屬于S集合并且fval[i]值最小的節點u。

Step2：將u加入集合S。

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

3 結果測試

3.1 測試環境

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

3.2 測試

測試條件：測試數據規定A處出發，需要達到的點為B，C，D。

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

4 結語

本文提出了在虛擬障礙環境中進行全局漫游的路徑規劃算法。該方法以提取的特征向量為基礎，通過二進制信息存儲的方式對其進行離散化，結合啟發函數的優化實現基于A*算法的多元路徑選擇。但目前算法只是停留在針對靜態環境的搜索，對于動態的環境還要進行下一步的研究。

參考文獻

[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*算法估價函數的特性分析[J].武漢工程職業技術學院學報，2006，6：31-33.

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

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

為了實現以上步驟來完成最短路徑的搜索，除了以上的S與T集合以為，另外需要設置2個關鍵數組。

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

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

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

初始：fval[k]=gval[V0][Vk]，V0為原點

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

Step1：在fval里查找屬于S集合并且fval[i]值最小的節點u。

Step2：將u加入集合S。

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

3 結果測試

3.1 測試環境

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

3.2 測試

測試條件：測試數據規定A處出發，需要達到的點為B，C，D。

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

4 結語

本文提出了在虛擬障礙環境中進行全局漫游的路徑規劃算法。該方法以提取的特征向量為基礎，通過二進制信息存儲的方式對其進行離散化，結合啟發函數的優化實現基于A*算法的多元路徑選擇。但目前算法只是停留在針對靜態環境的搜索，對于動態的環境還要進行下一步的研究。

參考文獻

[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*算法估價函數的特性分析[J].武漢工程職業技術學院學報，2006，6：31-33.

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

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

為了實現以上步驟來完成最短路徑的搜索，除了以上的S與T集合以為，另外需要設置2個關鍵數組。

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

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

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

初始：fval[k]=gval[V0][Vk]，V0為原點

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

Step1：在fval里查找屬于S集合并且fval[i]值最小的節點u。

Step2：將u加入集合S。

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

3 結果測試

3.1 測試環境

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

3.2 測試

測試條件：測試數據規定A處出發，需要達到的點為B，C，D。

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

4 結語

本文提出了在虛擬障礙環境中進行全局漫游的路徑規劃算法。該方法以提取的特征向量為基礎，通過二進制信息存儲的方式對其進行離散化，結合啟發函數的優化實現基于A*算法的多元路徑選擇。但目前算法只是停留在針對靜態環境的搜索，對于動態的環境還要進行下一步的研究。

參考文獻

[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*算法估價函數的特性分析[J].武漢工程職業技術學院學報，2006，6：31-33.

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