基于差分進化和稀疏A*算法的游戲地圖智能尋徑方法

齊 燕,常晉義

(1.蘇州托普信息職業(yè)技術(shù)學(xué)院 信息技術(shù)學(xué)院,江蘇 昆山 215311; 2.常熟理工學(xué)院 計算機科學(xué)與工程學(xué)院,江蘇 常熟 215500)

0 引言

隨著人工智能(AI)技術(shù)的發(fā)展,越來越多的產(chǎn)業(yè)與人工智能相結(jié)合產(chǎn)生了較好的應(yīng)用效果,例如：路徑規(guī)劃、計算機視覺、服務(wù)式機器人等[1-3]．其中,智能尋徑方法[4]因人工智能算法的成熟而受到了越來越多的關(guān)注,并成為目前的研究熱點．

近年來,游戲行業(yè)的發(fā)展也將尋徑方法帶入到了游戲產(chǎn)業(yè),Non-Player Character(NPC)的出現(xiàn)也造成了游戲地圖中的智能尋徑方法的廣泛應(yīng)用．若想使得NPC角色更加靈活與智能化,游戲設(shè)計研究者必須開發(fā)一個較好的尋徑方法來搜尋最佳路徑．較為經(jīng)典的Dijkstra算法[5]可以較好地完成尋找路徑這一任務(wù),但是存在最終路徑并非最優(yōu)路徑且算法穩(wěn)定性較差等問題．Greedy算法[6]也是尋徑算法中的一種,該算法通過導(dǎo)出局部最大值或者最小值來尋找最優(yōu)路徑,但Greedy算法只取局部最優(yōu),并不需要考慮當前的決定對之后決策的影響,所以盡管Greedy算法給出了接近于最優(yōu)的結(jié)果，但是還不能給出最優(yōu)路徑．目前在游戲地圖尋徑問題上應(yīng)用最廣泛的是A*算法[7],是采用一種直接搜索的方法來求得靜態(tài)網(wǎng)絡(luò)中的最優(yōu)路徑．A*算法通過比較當前路徑柵格的8個鄰居的啟發(fā)式函數(shù)值F來逐步確定下一個路徑柵格,但是無法計算出來存在多個最小值的情況,即不能出現(xiàn)最優(yōu)解．同時,A*算法當面臨地圖較大且復(fù)雜的時候運行速度較慢,并不能應(yīng)用到實時場景當中．

為了解決A*算法在游戲地圖尋徑當中面臨的問題,本文提出了一種基于差分進化和稀疏A*算法的游戲地圖智能尋徑算法,該算法通過對A*算法進行剪枝處理[8-9]去除冗余操作,從而實現(xiàn)實時要求并且通過差分進化算法來提高總體的全局尋優(yōu)能力．

1 預(yù)備知識

1.1 差分進化算法

差分進化算法是一種有效的全局優(yōu)化方法,主要是基于群體式搜索,然后通過交叉、變異、選擇等操作來求得最終的最優(yōu)解的一種方法．具體如算法1[10]所示.

算法1 Differential Evolution Algorithm，DE

Input:種群:M;交叉因子:D;迭代次數(shù)T

t←1

fori-1 toMdo

forj=1 toDdo

end

end

while (|f(Δ)|≥ε)or (t≤T)do

fori=1 toMdo

?(Mutation and Crossover)

forj=1 toDdo

end

?(Selection)

iff(ui,t)

xi,t←ui,t;

iff(xi,t)

Δ←xi,t;

end

else

xi,t←xi,t;

end

end

t=t+1

end

return the best Δ

1.2 A*算法

A*算法[11]是一種應(yīng)用在游戲地圖中尋找最短路徑的較有效的方法,其使用直接搜索方式,并且采用啟發(fā)式函數(shù)來計算終點距離起點的最小代價[12]．A*算法不僅僅在游戲地圖尋徑當中應(yīng)用,目前還在智能機器人的最短路徑規(guī)劃以及封閉式場景貨車最佳路線的規(guī)劃中使用[13-15]．代價函數(shù)是A*算法中最重要的一步．

定義1V={vi|i∈1,2,…}表示在游戲地圖中起點距終點所經(jīng)過的路徑節(jié)點集合,vi表示在游戲地圖中起點距終點中的某一節(jié)點．

定義2 對于節(jié)點vn,其代價函數(shù)f(vn)可定義如下:

f(vn)=σ(vn)+ρ(vn)

(1)

其中,σ(vn)為起點距離當前節(jié)點的實際代價,而ρ(vn)為當前節(jié)點距終點的預(yù)估代價．

根據(jù)定義2可知,代價函數(shù)f(vn)也稱為距離函數(shù),是啟發(fā)式函數(shù)的一種,在游戲地圖尋徑中,代價即距離．預(yù)估代價ρ(vn)越接近于真實值,其代價函數(shù)功能就越強．當ρ(vn)=σ(vn)時,A*算法即變?yōu)镈ijkstra算法,即通過增加橫向節(jié)點數(shù)目來提高算法的尋徑能力,同時,隨著橫向節(jié)點的增多,其運行速度也同樣會變慢,使得算法的整體效率變慢．所以如何確定實際代價σ(vn)與預(yù)估代價ρ(vn)在總體代價函數(shù)f(vn)中的權(quán)重是非常重要的．

ρ(vn)必須滿足代價真實性原則與代價一致性原則．代價真實性即ρ(vn)的取值不能超過當前節(jié)點距目標節(jié)點的真實代價．而代價一致性原則要求ρ(vn)滿足式(2)所示條件:

ρ(vi+1)+κ(vi,vi+1)≥ρ(vi)

(2)

其中,κ(vi,vi+1)為節(jié)點vi距下一節(jié)點vi+1的真實代價,而ρ(vi+1)為下一節(jié)點vi+1距最終節(jié)點的預(yù)估代價．

定理1 如果ρ(vi)≤ρ(vi+1)+κ(vi,vi+1),那么距最終節(jié)點所有路徑f(vn)全部為單調(diào)費遞增函數(shù)．

證明首先假設(shè)vi+1為vi的下一個目標節(jié)點,則

f(vi+1)=σ(vi+1)+ρ(vi+1)=σ(vi)+σ(vi,vi+1)+ρ(vi+1)≥σ(vn)+ρ(vn)

(3)

A*算法是一個較為經(jīng)典的尋徑問題的解決方案,但是當其應(yīng)用在游戲地圖尋徑問題上時,因為游戲地圖尋徑需要較低的時延,所以其效率與準確率產(chǎn)生了一定的沖突,并不能通過有效的手段來控制在較低的時延下產(chǎn)生較好的路徑規(guī)劃.本文提出了一種基于差分進化和稀疏A*算法的游戲地圖AI智能尋徑算法來應(yīng)對此問題．

2 主要結(jié)果

在A*算法研究的基礎(chǔ)上,使用差分進化方法結(jié)合稀疏A*算法來生成最佳游戲地圖路徑,主要是因為在實際應(yīng)用場景中,游戲地圖中的NPC是實時變化的,角色在線不能完全按照初始路徑規(guī)劃方法來確定唯一路徑,需要試試檢測當時所在路徑點距離終點的動態(tài)最佳路徑. 所以,建立了一種重規(guī)劃算法來確定游戲最佳路徑,同時考慮了路徑的最優(yōu)性與路徑重規(guī)劃的實時性．由于A*算法耗時較長并不能作為實時的路徑重規(guī)劃算法,為了避免算法搜索空間中的無用中間步驟與節(jié)點,對A*算法進行剪枝處理,稱為稀疏A*算法．首先,設(shè)計了以下稀疏A*算法的代價函數(shù),稀疏A*算法與A*算法相類似,需要同時對實際代價與預(yù)估代價設(shè)計．具體如下所示.

ρ(vn)為角色P在游戲地圖中節(jié)點vn處的預(yù)估代價

ρ(vn)=w1*Γ(P)

(4)

其中,w為角色P實際代價的權(quán)重系數(shù),而Γ為相鄰路徑距離之和,?？捎梢韵掠嬎愕玫?/p>

(5)

其中,Si.i+1為兩個相鄰節(jié)點的距離．

σ(vn)為角色P在游戲地圖中節(jié)點vn處的實際代價,將其設(shè)置為當前節(jié)點vn與目標節(jié)點vm的歐氏距離,則為

(6)

其中,(xn,yn)為當前節(jié)點vn的橫縱坐標,而(xm,ym)為目標節(jié)點vm的橫縱坐標．

所以,稀疏A*算法的總體代價函數(shù)f(vn)為

f(vn)=w1*Γ(P)+w2*σ(vn)

(7)

其中,w2為實際代價函數(shù)的權(quán)重系數(shù)．

稀疏A*算法的算法流程如圖1所示.

圖1 稀疏A*算法的算法流程

根據(jù)稀疏A*算法的流程,其具體稀疏A*算法如算法2所示.

算法2 A*Algorithm

Input:Game map data

Set the start and end pointsviandvjof this Path;

Put the inaccessible points in the Close table,and the start points in Open table;

While Current node is not a target point

Calculate cost of all feasible successors

f(vn)=w1*Γ(P)+w2*σ(vn)

Fori=1to total number of reachable grids

If Nodes are in the Open table and cost less

Update Open table

End

Ifnodevinot within Open table

Putvijoin Open table

End

End

Sorting the nodes in the Open table by cost;

If Open table ≠?

Put node with smallest cost into Close table

Else

No accessible trail

End

End

Output:the best path

稀疏A*算法可以較好地尋找到最優(yōu)路徑,并可以在面臨任何突發(fā)情況下可以更好地進行重規(guī)劃,但是稀疏A*算法在游戲地圖尋徑當中可能陷入局部最優(yōu)的情況,從而較難發(fā)現(xiàn)游戲地圖中的全局最優(yōu)路徑.因此,引入差分進化算法來對稀疏A*算法進行優(yōu)化,通過差分進化和稀疏A*算法相結(jié)合,克服了差分進化方法尋徑中不能重規(guī)劃的缺點,同時也加強了稀疏A*算法在尋找全局最優(yōu)路徑上的能力．本文提出的基于差分進化和稀疏A*算法的游戲地圖智能尋徑算法如算法3所示.

算法3 Game Map Path-Finding Method Based on Differential Evolution and Sparse A*Algorithm

Input:Game map data

Use Differential Evolution to plan an optimal path〈vi,…,vj〉 for an NPC from the start pointvito the goal pointvj;

The NPC advances along 〈vi,…,vj〉,constantly detecting whether NPC has reached the target point as it does so;

If NPC not reach the end

Reprogramming using the sparse A*algorithm;

Else

Statistical optimal path;

Output:the best path

3 仿真實驗結(jié)果及分析

為了驗證本文提出的游戲地圖尋徑方法的有效性和可應(yīng)用性,選取山脈地形與城市建筑群地形對本文算法與原稀疏A*算法進行仿真試驗,實驗所采用的硬件平臺與軟件環(huán)境具體為:CPU:IntelCorei7-9700K;顯卡:GTX 2060;內(nèi)存:16 G;操作系統(tǒng):Windows 10;仿真軟件:Matlab.

在山脈地形上對所提出的算法進行仿真試驗.首先在實驗中設(shè)置NPC的起點與終點,其中,在游戲地圖中的起點為(0,0,0),然后將游戲地圖尋徑的終點設(shè)置為(100,100,100)．在實驗中,假設(shè)該NPC為勻速前進,其速度為3 m/s,圖2和圖3是稀疏A*算法在游戲地圖尋徑上的表現(xiàn),分別為2維平面上的展示和3維實際平面上的展示．

圖2 稀疏A*算法在山脈地形上的表現(xiàn)(2維) 圖3 稀疏A*算法在山脈地形上的表現(xiàn)(3維)

接下來,將稀疏A*算法在山脈地形上進行仿真試驗,同樣的,地圖中的起點為(0,0,0),終點同樣設(shè)置為(100,100,100)．圖4和圖5是本文算法尋徑的表現(xiàn),分別為2維平面上的展示和3維實際平面上的展示．

圖4 本文方法在山脈地形上的表現(xiàn)(2維) 圖5 本文方法在山脈地形上的表現(xiàn)(3維)

由圖2-5可以看出,本文方法相較于稀疏A*算法有著較好的路徑規(guī)劃能力且在遇到山脈等情況時會進行重規(guī)劃而進一步選取更優(yōu)的路徑．

最后將稀疏A*算法在城市建筑群地形上進行仿真試驗.圖6-9為稀疏A*算法與本文算法尋徑的表現(xiàn),分別為2維平面上的展示和3維實際平面上的展示．

圖6 稀疏A*算法在城市建筑群地形上的表現(xiàn)(2維) 圖7 稀疏A*算法在城市建筑群地形上的表現(xiàn)(3維)

圖8 本文方法在城市建筑群地形上的表現(xiàn)(2維) 圖9 本文方法在城市建筑群地形上的表現(xiàn)(3維)

由圖6-9可以看出,本文方法相較于稀疏A*算法在面臨城市建筑較多的情況下可以更早地規(guī)避城市建筑,具有更優(yōu)的路徑規(guī)劃．

本文方法是稀疏A*算法的改進算法,因此與稀疏A*算法在性能上進行比較是有必要的．接下來對所提出的算法與稀疏A*算法在運行時間、路徑長度和總體代價上進行了對比,表1為本文方法與稀疏A*算法的性能比較,可以看出本文方法所規(guī)劃出來的路徑距離更短,總代價更小．

表1 本文方法與稀疏A*算法的性能對比

4 結(jié)語

人工智能技術(shù)迅速發(fā)展,已經(jīng)在各方面取得了重要的成就,本文針對A*算法在游戲地圖尋徑中容易陷入局部最優(yōu)導(dǎo)致不能找到最優(yōu)路徑,且由于差分進化算法不能進行重規(guī)劃的問題,提出了一種新的游戲地圖AI技術(shù)尋徑方法.該方法基于差分進化和稀疏A*方法相結(jié)合,在游戲地圖尋徑上取得了較好的結(jié)果．仿真實驗證明了本文算法相較于稀疏A*算法具有更低的總體代價、更短的路徑長度，能夠較好地適用于游戲地圖的尋徑研究．