基于A*算法的游戲地圖尋路實現(xiàn)及性能比較

邱 磊

(武漢船舶職業(yè)技術(shù)學(xué)院電子系， 湖北 武漢 430050)

0 引 言

游戲，國外稱之為“第九藝術(shù)”，是一種世界范圍內(nèi)的通用語言.隨著互聯(lián)網(wǎng)技術(shù)的應(yīng)用以及軟件技術(shù)的突破，人工智能的應(yīng)用獲得了進一步推廣，而路徑搜索是人工智能搜索技術(shù)的一個重要應(yīng)用領(lǐng)域.目前中國網(wǎng)絡(luò)游戲、手機3G增值等業(yè)務(wù)迅速發(fā)展，尋路技術(shù)已經(jīng)成為眾多游戲的一個核心組成部分.物體按照某種指定目的地的方式移動，其就要求程序必須能夠找到一條從起點到目標(biāo)點的最佳路徑，這條路徑應(yīng)該是繞過障礙物并且到達目的地最短的路徑，完成這個任務(wù)的最好的算法就是A*.A*算法作為一種靈活的、高性價比的尋路算法，一直被游戲行業(yè)所廣泛采用[1]，很多游戲中的尋路算法都基于A*算法，如紅色警戒、帝國時代等.本質(zhì)上講，A*算法反復(fù)檢查它已經(jīng)看到但是還沒有搜索到的最有希望的位置，當(dāng)一個位置被搜索到其恰好就是目標(biāo)時，A*算法結(jié)束；否則，為進一步的搜索它將記錄這個位置的所有相鄰位置.本文對比分析了各種尋路算法的性能，并針對A*算法，采用了3種不同的啟發(fā)式函數(shù)以分析其對A*算法執(zhí)行結(jié)果的影響.

1 A*算法的描述

A*算法是把常規(guī)方法(如Dijkstra算法)和啟發(fā)式方法(如最佳優(yōu)先搜索算法)結(jié)合在一起的更為折中的算法，相對于最佳優(yōu)先搜索算法來說要更加貼近于Dijkstra算法，盡管基于“無法保證最佳解”的啟發(fā)式方法，A*卻能保證找到一條最短路徑，即找到最優(yōu)解.

A*是一種典型的啟發(fā)式搜索算法，如果一個估價函數(shù)可找出最短的路徑，則稱之為具有可采納性.A*算法是可采納的，它的估價函數(shù)表示為：f(n)=g(n)+h(n)[2]，這里，f(n)是節(jié)點的估價函數(shù)，表示從初始節(jié)點經(jīng)過節(jié)點n到目標(biāo)節(jié)點的最佳路徑的代價；g(n)表示從初始節(jié)點到任意節(jié)點n的代價；啟發(fā)式函數(shù)h(n)是從節(jié)點n到目標(biāo)節(jié)點的最小代價評估值.選擇一個好的啟發(fā)式函數(shù)是重要的，不同的啟發(fā)式函數(shù)會影響A*的搜索性能，一個具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法的充分條件是[3]：(1)搜索樹上存在著從初始節(jié)點到目標(biāo)節(jié)點的最優(yōu)路徑；(2)問題域是有限的；(3)所有節(jié)點的子節(jié)點的搜索代價值>0；(4)h(n)<=h*(n)(h*(n)為節(jié)點n移動到目標(biāo)的實際代價值).

對于一個搜索問題，顯然條件(1)、(2)、(3)都是很容易滿足的，而條件(4)：h(n)<=h*(n)是需要精心設(shè)計的.由于h*(n)無法知道，所以一個滿足條件(4)的啟發(fā)策略h(n)就難能可貴了，一個好的h(n)的評價是：h(n)在h*(n)的下界之下，并且盡量接近h*(n).啟發(fā)式函數(shù)可以控制A*的行為：

(1) 若h(n)=0，則A*演變成Dijkstra算法；若h(n)比g(n)大很多，則A*演變成BFS算法.

(2) 若h(n)<=h*(n)，則A*保證能找到一條最短路徑，h(n)越小，A*擴展的節(jié)點越多，運行的就越慢；若h(n)>h*(n) ，則A*不能保證找到一條最短路徑，但運行的較快；若h(n)=h*(n)，則A*不擴展別的節(jié)點，只尋找最佳路徑，運行的非?？?

2 A*算法在復(fù)雜情況下的應(yīng)用

2.1 A*算法的優(yōu)化——分層尋路

分層尋路是一種比較有效的優(yōu)化A*算法的方法.其基本思想是把二維地圖(或三維空間)按不同的復(fù)雜層次來劃分[4]，如圖1所示.圖中有4個屋子，標(biāo)號為1、2、3、4，屋子之間有門，如虛線所示.假設(shè)要從1號屋子里的起始點走到3號屋子里的目的地，首先可以把地圖分為兩層：第一層只包括屋子和屋子之間的關(guān)系(門)，不考慮屋子里的細節(jié)，這層最簡單.第二層是屋子內(nèi)部的細節(jié)，比如桌椅等，這層比較復(fù)雜，所采取的步驟為：

(1) 對各個屋子之間整體使用A*算法，找到屋子1到屋子3的路徑為1-2-4-3；

(2) 在2號與4號屋子之間設(shè)定中間目的地“子目的地1”，對1號和2號屋子的內(nèi)部細節(jié)使用A*算法找到從起始點到“子目的地1”之間的路徑；

(3) 讓游戲角色走到2號屋子的門外；

(4) 再確定中間目的地“子目的地2”，依次類推，對2號和4號屋子的內(nèi)部細節(jié)使用A*算法.

圖1 分層尋路

2.2 游戲地圖的劃分

應(yīng)用A*算法之前，應(yīng)先對游戲地圖進行劃分，劃分后的每個地圖小塊視為一個節(jié)點，圖2(A)是基本地圖，3個黑色區(qū)域為障礙物，底下的圓圈為起始點，最上面的圓圈為目的地.

柵格法是一種最簡單的劃分方式，也是本文所采用的方式，如圖2(B)，首先把地圖等距離地劃分為大小相同的格子，然后根據(jù)黑色在一個格子中所占面積的百分比來決定這個格子的屬性，比如說40%以上就認為這個格子是不可穿越的，如圖2(B)中陰影的部分,這樣就把具體的地圖劃分成可以使用A*算法搜索的地圖了.

圖2 劃分地圖的幾種方法

四叉樹法對柵格法作了改進，如圖2(C)：不再把地圖分成大小相同的格子，而是根據(jù)實際需要把地圖分割成大小不同的格子.遞歸地將一個大的正方形格子劃分為4個更小的正方形格子，直到每個正方形格子都有一致(或至少大部分一致)的地形.

適合于三維游戲的地圖劃分方法為導(dǎo)航網(wǎng)格法，如圖2(D)，由于三維物體是由多邊形構(gòu)成的，游戲在處理時一般又把多邊形再細分成三角形，三角形是游戲中三維空間的最基本的構(gòu)成單元.導(dǎo)航網(wǎng)格的基本思想就是給每個三角形一個反映是否可以通過的屬性，這樣就可以對三維空間使用二維A*算法了.

可視點法采取了不同于上面幾種方法的策略：它不再硬性劃分地圖的空間結(jié)構(gòu)，而是在障礙物外的鄰近地方取點，用幾個點把障礙物包起來，如圖2(E).用尋路算法時只需把這些點連接起來[4,5].

廣義圓柱體法的基本思想是將相鄰障礙物之間的空間看作一個2D圓柱體， 它的外形會在行進中進行改變.在每兩個相鄰的障礙物之間計算一個中心軸線，如圖2(F)，這些線的交點為搜索提供了位置[6-8].

3 仿真實驗對比分析

為了驗證A*算法是一種比較高效的尋路算法，在26×20=520個節(jié)點的游戲地圖上，首先利用柵格法按8方向連接對地圖進行劃分，然后分別采用A*算法(以曼哈頓距離為啟發(fā)函數(shù))、A*算法(以歐式距離為啟發(fā)式函數(shù))、A*算法(以切比雪夫距離為啟發(fā)函數(shù))、Dijkstra算法、雙向廣度優(yōu)先搜索算法和動態(tài)A*算法5種算法進行尋路仿真實驗，以對比分析各種搜索算法擴展節(jié)點的數(shù)量，圖3～圖7顯示了5種算法的尋路演示結(jié)果.圖8 給出了動態(tài)A*算法尋路的基本思想，由于只在非常小的區(qū)域中進行重新規(guī)劃，充分利用了已經(jīng)計算好的路徑，因而使得整個尋路過程可動態(tài)適應(yīng)游戲環(huán)境的變化.

圖3 Dijkstra算法尋路演示 圖4 雙向廣度優(yōu)先搜索算法尋路演示 圖5 A*算法(曼哈頓距離)尋路演示

接下來，在相同的26×20=520個節(jié)點的游戲地圖上，采用與圖3～圖7相同的障礙物環(huán)境以及相同的初始節(jié)點和目標(biāo)節(jié)點，對以上各種尋路算法的耗時進行分析.在路徑求解過程中分別以0.007 813 s和0.003 906 s為每步執(zhí)行計算的時間間隔，則各個算法的路徑計算耗時如表1所示(誤差范圍小于0.01 s)：

由上述5種算法擴展節(jié)點的數(shù)量和計算耗時可知，雖然尋路的結(jié)果都可以保證找到最短路徑，但各算法的性能明顯不同.Dijkstra算法由于基于廣度優(yōu)先搜索策略，且沒有啟發(fā)式信息，因此遍歷計算時擴展的節(jié)點數(shù)較多，從而效率低.雙向廣度優(yōu)先搜索算法相對于廣度優(yōu)先算法來說，由于分別從初始節(jié)點和目標(biāo)節(jié)點兩個方向以廣度優(yōu)先的順序同時擴展，搜索深度雖然得到了明顯的降低，但擴展的節(jié)點數(shù)仍然較多，因此效率也不高.A*算法由于根據(jù)啟發(fā)式函數(shù)的導(dǎo)向信息進行定向搜索，僅僅遍歷了最短路徑附近的相關(guān)節(jié)點，省去了大量無關(guān)節(jié)點的訪問，計算量明顯減少，因此極大地提高了路徑搜索的效率，并且當(dāng)繞過障礙物以后A*算法搜索的區(qū)域非常少.

圖6 A*算法(歐氏距離)尋路演示 圖7 A*算法(切比雪夫距離)尋路演示 圖8 動態(tài)A*算法尋路演示

表1 各個算法的路徑計算耗時

啟發(fā)式函數(shù)h(n)對A*算法的影響很大，以曼哈頓距離、歐式距離和以切比雪夫距離為啟發(fā)函數(shù)，A*算法尋路時擴展節(jié)點的數(shù)量和計算耗時并不相同，可見所選的啟發(fā)函數(shù)對A*算法很重要，一個好的啟發(fā)函數(shù)有利于盡快找到最優(yōu)解.另外，Dijkstra算法和雙向廣度優(yōu)先搜索算法與A*算法求解的路徑雖然都是最優(yōu)路徑，但并不完全一樣，這是因為A*算法在搜索中加入了與問題有關(guān)的啟發(fā)性的信息，以指導(dǎo)搜索朝著最有希望的方向前進.

因此，在游戲地圖尋路效率上，A*算法的效率高于Dijkstra算法和雙向廣度優(yōu)先搜索算法，A*算法的確是一種比較高效的尋路算法.

4 結(jié)束語

本文利用柵格法對游戲地圖進行劃分，對比了6種尋路算法的性能及啟發(fā)式函數(shù)對A*算法性能的影響，但并未給出A*算法針對不同的游戲地圖劃分方式及執(zhí)行效率差異的對比分析，下一步的研究將拓展到這個方面.另外，很多文獻探討了A*算法的改進優(yōu)化問題，因此進一步提高算法效率的空間已非常狹窄[9]，公認的提高A*算法尋路性能以及尋路程序產(chǎn)生路徑質(zhì)量的一個方法是優(yōu)化底層搜索空間，這將是一個有吸引力的課題.

參考文獻

[1] 蔡方方，楊士穎. 雙層A*算法在游戲?qū)ぢ贩矫娴难芯縖J]. 微型電腦應(yīng)用, 2010, 26(1): 26.

[2] 馬少平.人工智能[M]. 北京: 清華大學(xué)出版社, 2004: 32-34.

[3] EmilMatthew. Introduction to Heuristics Search—A*Algorithm Principle and Practice[DB/OL]. http://emilmatthew.51.net/EmilPapers/0632AStarSearch, 2006.

[4] Mark Deloura. A*速度優(yōu)化. 游戲編程精粹1[M]. 北京:人民郵電出版社, 2004: 240.

[5] 葉 展, 葉 丁編. 游戲的設(shè)計與開發(fā)：夢開始的地方[M]. 北京: 人民交通出版社, 2003: 253-261.

[6] Kumar Pawan. Efficient Path Finding for 2D Games (Proceedings of CGAIDE’2004)[C]. Game Simulation and Artificial Intelligence Centre (GSAI), 2004: 265-266.

[7] 葉東曙. 基于碰撞的三維場景尋徑算法研究[D]. 武漢:華中科技大學(xué)碩士學(xué)位論文, 2009.

[8] Yngvi Bjornsson. Fringe Search: Beating A*at Pathfinding on Game Maps[R]. School of Computer Science Reykjavik University Reykjavik, Iceland IS-103.

[9] 靳旭棟. 游戲領(lǐng)域中啟發(fā)式尋徑算法的運用和優(yōu)化[D]. 上海:華東師范大學(xué)碩士學(xué)位論文, 2006.