胡正紅，張俊花

(太原師范學(xué)院計算機系，山西 太原 030012)

隨著科技的發(fā)展，人工智能技術(shù)應(yīng)用在許多游戲開發(fā)過程中以提高游戲的可玩性。路徑探索是游戲開發(fā)過程中經(jīng)常遇到的問題，通常可以采用廣度優(yōu)先搜索算法或深度優(yōu)先搜索算法來實現(xiàn)路徑搜索，但這些常用搜索算法在“連連看”游戲?qū)ぢ分写嬖跀?shù)據(jù)冗余、運行時間長的缺點。針對該游戲路徑搜索的特點，首先我們對常見的廣度優(yōu)先搜索算法進行詳細分析與研究，結(jié)合游戲中的應(yīng)用情況，研究A* 搜索算法和啟發(fā)式搜索技術(shù)，設(shè)計估價函數(shù)，改進A*算法用于游戲?qū)ぢ贰?/p>

1 廣度優(yōu)先搜索算法在游戲中的應(yīng)用

“連連看”游戲規(guī)則是:在有限的時間內(nèi)，將圖案相同的兩張牌用三根以內(nèi)的直線連在一起就可以消除，只要把所有的圖案全部消完即可獲得勝利［1］。

采用廣度優(yōu)先搜索，將目標函數(shù)修改為從一個點到另一個點的轉(zhuǎn)彎次數(shù)，首先把圖形Start (x1，y1)壓入隊列。然后擴展圖形Start(x1，y1)可以直線到達的節(jié)點，用集合S0=Find(x1，y1)表示這些節(jié)點都可通過轉(zhuǎn)彎數(shù)為0的路徑到達，如果圖形Target(x2，y2)包含在集合S0 中，結(jié)束搜索。

否則，繼續(xù)擴展集合S0 中空格可以直線到達的節(jié)點，用集合S1={Find(p)|p∈S0}表示，令S1’=S1－S0(S1 包含了S0)，表示S1’中的節(jié)點和圖形Start(x1，y1)之間可以通過轉(zhuǎn)彎數(shù)目為1的路徑連起來。如果圖形B(x2，y2)在S1’中，則圖形S，T 之間可以用轉(zhuǎn)彎數(shù)目為1的路徑連接，結(jié)束搜索。

否則，繼續(xù)展開S1’集合中的空格可以直線到達的節(jié)點，用集合S2=Find{Find(p)|p∈S1’}表示，令S2’=S2－S0－S1=S2－S0－S1’(S2 包含了S0和S1)，集合S2’是圖形A(x1，y1)可以通過轉(zhuǎn)彎數(shù)目為2的路徑到達的格子。如果圖形T(x2，y2)在集合S2’中，則圖形A，B 之間可以用轉(zhuǎn)彎數(shù)目為2的路徑連接，否則圖形A，B 之間不能通過轉(zhuǎn)彎小于3的路徑連接。

2 A*算法的估價函數(shù)設(shè)計

A*算法具備很多優(yōu)點。首先，如果起點和終點之間存在有效路徑，A* 就一定能夠找到;其次，只要H(n)是可納的，它就一定能找到一條最短路徑;第三，A*算法是啟發(fā)式搜索算法中搜索狀態(tài)最少的一種算法，它使啟發(fā)式函數(shù)得到了最有效的應(yīng)用［2］。

啟發(fā)式搜索的核心是估價函數(shù)F(n)，“連連看”中連線不能從尚未消去的圖案上經(jīng)過，節(jié)點只能在四個方向移動，兩個相同圖案之間的連線不能超過兩個彎。

因此估價函數(shù)中，需要考慮當(dāng)前格Current 到目標格Target的移動耗費，當(dāng)前格Current 與開始格Start的轉(zhuǎn)彎數(shù)，用估價函數(shù)表示為［3］:

在“連連看”游戲中，格子S的移動方向分水平上、水平下、豎直上、豎直下四個方向，每個格子對應(yīng)著有圖案、無圖案兩種狀態(tài)。

設(shè)計二維數(shù)組map［Rows］［Cols］表示對應(yīng)的方格是否有圖狀態(tài)，當(dāng)數(shù)組元素值取1 表示該位置有圖，取0 表示無圖。

估價函數(shù)F(n)的取值設(shè)定:

G(n):移動的距離。結(jié)合游戲的要求，這里設(shè)定沿著四個方向移動，移動位置上有圖則距離值為無窮大，這樣的格子不考慮擴展，如果無圖距離值為1，如圖1所示。

圖1 G值的設(shè)定

H(n):指定格子到目標格橫向走的步數(shù)與縱向走的步數(shù)和;例如T(Tx，Ty)是終點，C(Cx，Cy)是當(dāng)前點，則:h(n)=|Tx－Cx|+ |Ty－Cy|。

C(n):起點Start 到指定格子的轉(zhuǎn)彎數(shù)，直線連接C 取值為0，轉(zhuǎn)一次彎，C值為1;轉(zhuǎn)兩次彎，C值為2;轉(zhuǎn)彎數(shù)為3，估價函數(shù)無窮大。

例如:開始點S 與終點T 在一條橫線上，周圍的格子狀態(tài)如圖1所示;計算S 點的四方向節(jié)點的F(n)，上方和左方的節(jié)點估價函數(shù)無窮大，右方節(jié)點的f(n)=1+3+0，下方節(jié)點的f(n)=1+5+0;計算過程如圖2－圖4所示。

圖2 初始狀態(tài)

圖3 G值的計算

圖4 H值的計算

展開右方F值=4的點，計算其右節(jié)點估價函數(shù)f=4+(1+2+0)=7，如圖5所示。

展開F值=7的節(jié)點，計算出其右節(jié)點估價函數(shù)f=7+(1+1+0)=9，如圖6所示。

展開F=9的節(jié)點，終點就在它的展開節(jié)點中了，完成了最短路徑工作。

圖5 估價表示

圖6 展開f=4的節(jié)點

圖7 展開f=7的節(jié)點

3 A*算法的應(yīng)用設(shè)計

A*算法是一種典型的啟發(fā)式搜索算法，它除了利用上述的啟發(fā)函數(shù)來對搜索過程中的每一個節(jié)點進行評估，另外它還必須有兩個表:Open 表和Close 表［4］。

Open 表由未考察的結(jié)點組成，保存了打開節(jié)點的F值;每次從Open 表中取F值最小的節(jié)點展開后續(xù)節(jié)點。

Close 表由已考察的結(jié)點組成，將已展開的節(jié)點加入其中(不包括終點)。

結(jié)合“連連看”的要求，A*算法實現(xiàn)的過程可以用偽代碼描述，假設(shè)起始節(jié)點為Start，目標節(jié)點為Target，其中Current是每次被考察的節(jié)點，臨時節(jié)點Temp 代表Current的四方向上的有效子結(jié)點，所謂有效子結(jié)點就是指在“連連看”中沒有圖案的格子。當(dāng)Current 等于Target 時搜索成功。

A*算法作為“連連看”中的尋路算法，用偽代碼表示如下:

4 A*算法在“連連看”中的應(yīng)用

4.1 數(shù)字化運動方向

A*算法的數(shù)據(jù)結(jié)構(gòu)設(shè)置，程序設(shè)計有其一定的模式，這里針對“連連看”，給出A*算法的實現(xiàn)代碼。

“連連看”中節(jié)點的運動方向是4個，可以設(shè)置一個常量數(shù)組，把每個方向的移動坐標變動量存入數(shù)組，定義類的方法，傳入?yún)?shù):起始點坐標和目標點坐標:

圖8 數(shù)字化方向

4.2 計算轉(zhuǎn)彎

“連連看”中計算節(jié)點的轉(zhuǎn)彎數(shù)很關(guān)鍵，因此定義類方法GetCrossing，傳遞節(jié)點的ID 號，返回起點到節(jié)點的轉(zhuǎn)彎數(shù)。

4.3 尋路設(shè)計

展開節(jié)點后，定義類方法FindPath 傳遞相關(guān)參數(shù)計算節(jié)點坐標，記錄節(jié)點ID 號，增加節(jié)點到OpenList，計算G、H、E、F值，然后把展開的節(jié)點加入到whichNode 中。

5 算法分析

假設(shè)游戲地圖n 行m 列，設(shè)N=m* n，由于每個節(jié)點做為擴展節(jié)點進入Open 表最多一次，因此Open 表中最多處理N個展開節(jié)點。擴展每個節(jié)點需要O(1)的時間，因此算法最多耗時O(N)。構(gòu)造相應(yīng)的最短路徑需要O(L)的時間，L是最短路徑的長度。當(dāng)節(jié)點數(shù)為N 時，廣度優(yōu)先搜索算法的復(fù)雜度為O(N* N)，A*算法的復(fù)雜度為O(N+L)，計算量不會隨著節(jié)點的展開迅速增加，只要起點和終點之間存在有效路徑，A*算法就能夠快速找到。

6 總結(jié)

本文將A*算法應(yīng)用在“連連看”游戲?qū)ぢ匪阉魃?，給出了改進的估價函數(shù)、算法運行流程，能夠用O(N+L)的時間完成最短路徑搜索，很好地適應(yīng)游戲的要求。A*算法結(jié)合了啟發(fā)式方法和形式化方法，為許多即時戰(zhàn)略游戲所用到，可以修改方向參數(shù)，對于游戲中八方向移動搜索路徑也具有一定的實際應(yīng)用價值。

［1］胡正紅.一種尋路算法在游戲中的應(yīng)用［J］.山西電子技術(shù)，2009(6):53－54.

［2］陳和平，張前哨.A算法在游戲地圖尋徑中的應(yīng)用與實現(xiàn)［J］.計算機應(yīng)用與軟件，2005(12):118－120.

［3］Hu zhenhong，Jinli.Application and Implementation of A* Algorithm in Picture Matching Path－finding［G］.In:2010 International Conference on Computer Application and System Modeling(ICCASM 2010)，Taiyuan，China，2010:224－227.

［4］陳煉，鄧少波，萬芳.A算法在梵塔問題中的應(yīng)用［J］.計算機工程，2005(4):168－170.