改進A*算法在游戲地圖路徑搜索中的應用研究

鐘 瑛 陳凌峰 朱順痣

（廈門理工學院計算機與信息工程學院 福建 361024）

0 前言

全球電子游戲產業始于20世紀70年代，在這四十多年的快速發展中，從電視游戲、電腦游戲再到網絡游戲，電子游戲產業在全球市場中占據了不可忽視的份量。2000年中國網絡游戲市場規模僅為0.3億元人民幣，到2006年市場規模已經達到65.4億元人民幣，2011年中國網絡游戲市場規模達413.8億元，環比增長17.5%。同時網絡游戲也帶動了如通信業、IT產業、媒體以及出版業等發展[1]。

對游戲方面的學術研究和科技發展一直是游戲產業快速發展原因之一。路徑搜索問題作為其中一項重要的研究課題也一直被學者們研究討論。路徑搜索問題本質上是指在給定的網絡圖中尋找出一條從起始點到目標點之間最短路徑[2]。對于路徑搜索問題，已經有很多搜索決策了，大體上可以分為盲目搜索算法和啟發式搜索算法。A*算法作為啟發式搜索算法之一，被廣大游戲開發人員應用于游戲地圖中的路徑搜索。

1 A*算法

A*算法是啟發式搜索算法的一種，也被稱為最好的優先搜索算法，在許多游戲路徑搜索中都會使用A*算法，是由著名的人工智能學者Nilsson等專家提出的。A*算法采用的表達式是：F(n)=H(n)+G(n)，F(n)表示節點n的估價函數，G(n)表示從起始節點S0到節點n的行走代價，H(n)是從節點n到目標節點Sg的最優路徑的估價值[3]，這個依賴于啟發式信息。A*算法對啟發函數進行了一些條件約束，例如：對于所有的節點，均有h（n）≤h*（n）,h*（n）是節點n到目標節點Sg的實際距離，這樣能夠保證尋找到的路徑是最優路徑。

A*算法的具體步驟如下：

將起始節點S0放入OPEN表中。

如果OPEN表為空，則搜索失敗，退出算法。

選擇OPEN表中F值最小的節點為當前節點n，然后移到CLOSE表。

判斷當前節點n是不是目標節點Sg，如果是，則搜索成功，退出算法；否則繼續第（5）步。

擴展當前節點n的所有子節點，若沒有可擴展的子節點，則算法繼續；否則，設子節點m，對每一個子節點計算其F值、G值、H值，并作如下判斷：

子節點m既不在OPEN表中也不在CLOSE表中，則將它放入OPEN表中，并將一個指向父節點的指針指向節點n。這樣當找到目標節點的時候可以根據這個指針，回溯到起始節點，得到搜索到的路徑。

子節點m已經在OPEN中，判斷新F值是否小于已有的F值。若是，則更新子節點m的數據，并將指針指向節點n，否則不處理。

子節點m已經在CLOSE表中，則不作處理，繼續算法。

跳轉到第(3)步，直至找到目標節點或者搜索失敗。

2 A*算法的不足和改進

2.1 A*算法的不足

雖然A*算法相對于其他算法都具有較高的效率，但其本身也存在著不足，可以歸納為兩點：

對OPEN表的遍歷。在A*算法選擇進行擴展的節點時，都要在OPEN表中選取F值最小的節點來進行擴展。此時，需要對OPEN表進行遍歷，這一步驟是A*算法中最耗時的部分。在尋找F值最小的節點的時候，需要對OPEN表進行排序或者比較，然而，游戲環境中的節點有時都會成千上萬，導致OPEN表中存儲的節點勢必也會很多，遍歷OPEN表則將產生很大的計算量。而在游戲中，路徑搜索要反復進行，OPEN表也會反復被遍歷，如此累計起來的大量耗時計算，會讓玩家有種極其不好的游戲體驗感。

如果搜索的路徑相對較長，靠近目標節點由于G值的不斷累計將導致F值會相對較大，而該節點的F值會和遠離目標節點的部分節點的F值相同，A*算法計算過程中會把這些節點也計算進去，最后將導致產生大量的無用節點。因此，通過減少無用節點量也會提高A*算法的效率。

2.2 A*算法的改進

針對上述所說的不足，本文提出了相應的改進方法，針對OPEN表的遍歷，使用最小二叉堆進行優化OPEN表結構；針對計算過程產生的過多無用節點，采用以向量夾角余弦作為新啟發式信息加入計算的方法來改善。

（1）最小二叉堆優化OPEN表遍歷

最小二叉堆是二叉堆的一種數據結構，其定義是：二叉堆是一顆有序的完全二叉樹。所謂有序性，就是父子節點值之間有大小的約定。如果每個節點的值都小于它的子節點的值，則稱為最小化堆[4] ，也就是最小二叉堆。使用最小二叉堆存儲OPEN表中的節點，以節點的F值作為父子節點值的約定，每個節點的F值都比它的子節點的F值都要小，依次類推，其根節點便是OPEN表中F值最小的節點。所以當搜索過程中需要尋找最小F值時，直接讀取根節點就可以。

（2）以向量夾角余弦作為新啟發式信息

在3.1的(2)所提到的不足點，在A*算法中是一種常見現象。因為隨著路徑搜索的不斷深入，節點的G值不斷累積，雖然H值會隨著靠近目標節點而減小，但F值總體是遞增的。而對于那些遠離目標的節點，是H值較大，G值較小，但組成的F值可能和那些靠近目標節點的F值相同，從而導致算法對兩種節點都會計算，增加了計算量。為此，本文對該現象提出了以向量夾角余弦作為新啟發式信息來解決這個問題。

如圖1，A為起始節點，B為目標節點，C和D分別是A*算法搜索過程中考察過的節點，則向量和向量之間的夾角為α，向量和向量之間的夾角為β。假設采用歐幾里得距離作為啟發函數的A*算法，C和D的各自F值剛好相同，而C點在最優路徑上。那么在計算過程中，C點和D點都會被考察，但由于C點更接近于目標節點B且在最優路徑上，C點應更優先計算，而D點雖然會被考察但會變為無用節點。

根據向量夾角余弦公式和A、B、C各自的坐標，可以求出：

圖1 不同位置的向量夾角余弦

為此，根據余弦函數，本文對每一個需要計算啟發函數的節點n作如下處理：

節點n的啟發函數：

其中，ho（n）是節點n根據歐幾里得距離計算出的估價值，hcos（n）是節點n根據節點n和起始節點組成向量和向量

之間的夾角ω的余弦值的估價值。W是一定權值。

所以，對于C、D兩點有：

通過上述處理后，必定存在Fcos（C）＜Fcos（D），因此，在計算過程中，C點比D點優先考查。當C點的后續節點m存在Fcos（m）≤Fcos（D），D點將在計算結束前都不會被考查，則程序將減少對無用節點的考查，加速了程序的運行。如果將這樣的處理擴大到整個程序的計算過程中，必然會減少考查無用節點數，程序的計算效率便能得到進一步的提高。

為了保證A*算法的單調性約束h（xi）-h（xj）≤c（xi，xj），選擇適當的W來保證限制，具體測試數據及結果見后續。由此可知，節點n離目標節點和起始節點的連線越遠，則hcos（n）越大，估價函數值也會比原本沒有加入hcos（n）時的估價值還大。并且hcos（n）是非直線式變化的。通過加入向量夾角的余弦值作為啟發式信息之一，可以限制A*算法的搜索范圍，減少搜索過程中無效節點的數量。

3 仿真實驗模擬

本文使用MFC程序實現了標準的A*算法和改進的A*算法。將標準的A*算法、Dijkstra算法、加入向量夾角余弦的改進A*算法進行了比較，同時還對不同W權值的改進A*算法進行了比較。在此，所有的計算都是使用了最小二叉堆的OPEN表進行計算。圖1 是在仿真實驗中標準A*算法的路線圖。

圖1 仿真實驗程序中標準A*算法

3.1 改進A*算法的對比試驗

上述中，我們提出將向量夾角余弦加入估價函數中進行搜索。在對向量夾角余弦附上權值W并進行一定的處理后，作為啟發式信息來縮小A*算法的搜索范圍，提高其效率。當考察的節點離起始節點和目標節點之間的直線越遠，其估價值就會因為新啟發式信息而變大，其增加量是曲線增長的。經過多次試驗測試后，確定權值W在一定范圍內，可大大減少A*算法的搜索節點數和總訪問節點次數。

表1 不同權值W的采用向量夾角余弦作為啟發式信息的改進A*算法

由上面的數據可以看出，標準A*算法的搜索節點數和總訪問節點次數都較大。而無論權值W多少，改進A*算法的搜索節點數和搜索總訪問節點次數都少于標準A*算法，說明這個啟發式信息是符合A*算法的搜索。并且權值W為15比W為5的A*算法更具有效率。本文采用的啟發函數是歐幾里得距離，而這樣的估價值是遠遠小于實際最優路徑值，那么加入新啟發式信息，也能夠保證A*算法的單調性約束。通過數據分析，采用新啟發式信息的改進A*算法比標準A*算法提高了1-15%不等，且取決于權值W。

3.2 Dijkstra算法、改進A*算法對比試驗

傳統的路徑搜索問題的算法有很多種，而常用于游戲地圖的搜索算法是A*算法和Dijkstra算法。因此，仿真實驗中也把Dijkstra算法作為其中一種路徑搜索算法進行比較，從中可以對比三種算法在游戲地圖中的路徑搜索效率。以下是50組數據中的6組數據。

表2 多種路徑搜索算法的實驗數據

1 94 120 384 413 88 187 2 58 126 124 129 51 112 3 104 257 393 435 96 228 4 43 79 161 178 32 56 5 66 143 285 308 57 120 6 101 244 376 410 93 213

從上述數據中可以看出，雖然在問題有解的情況下，Dijkstra算法能夠找到解且是最優的，但它搜索節點數和總訪問節點次數都是非常多，如果應用于實際游戲地圖中其效率將是很低的。而A*算法明顯比Dijkstra算法更具有效率，兩種數據都少于Dijkstra算法的數據。改進A*算法依舊能夠比標準A*算法更加有效率。通過數據分析，改進A*算法比標準A*算法提高了5-15%不等。

4 總結

A*算法中作為啟發式搜索算法的一種，深受程序開發人員的推崇，在許多游戲地圖路徑搜索中都有所應用。但A*算法本身并不完美，也存在這不足。首先，A*算法最耗時的部分就是在OPEN表中尋找F值最小的節點。本文采用最小二叉堆的方法來構造OPEN表，利用最小二叉堆的根節點最小值的特點，不但省去了對OPEN表的遍歷所消耗的時間，也極大的優化了A*算法對OPEN表的增、刪操作，路徑搜索的效率提高了5%。其次，通過引入了以向量夾角余弦作為新的啟發式信息，來收縮A*算法的搜索范圍和減少搜索無用的節點。最 后得出的A*算法比標準A*算法的游戲路徑搜索效率提高了近15%。

[1]張玥.基于產業鏈結構的中國網絡游戲產業發展研究[J].中原工學院學報, 2012年10月第23卷(第5期):64-67.

[2]周先曙.最短路徑問題及其解法研究[J].電腦知識與技術,2010年2月, 第6卷(第6期):1403-1405,1412.

[3]邱磊.基于A*算法的游戲地圖尋路實現及性能比較[J].陜西科技大學學報, Dec.2011(No.6):89-93.

[4]翁惠玉, 俞勇.數據結構：題解與拓展[M].1.高等教育出版社, 2011-07,151-155.

[5]Patrick Lester.A* Pathfinding for Beginners [EB/OL].July 18, 2005[2012-2-20].http://www.policyalmanac.org/games/aStarTutorial.htm.

[6]陳和平，張前哨．A算法在游戲地圖尋徑中的應用與實現[J]．計算機應用與軟件，2005(12)：118—120.

[7]劉敏.Dijkstra算法求解最短路徑的設計與實現[J].電腦知識與技術, April 2012(No.12):2759-2761.

[8]邱磊, 張輝.2D游戲地圖的尋路實現[J].湖南工業大學學報,2012年1月(第26卷第1期):66-69.