齊 燕,常晉義

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

0 引言

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

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

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

1 預(yù)備知識(shí)

1.1 差分進(jìn)化算法

差分進(jìn)化算法是一種有效的全局優(yōu)化方法,主要是基于群體式搜索,然后通過(guò)交叉、變異、選擇等操作來(lái)求得最終的最優(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ù)來(lái)計(jì)算終點(diǎn)距離起點(diǎn)的最小代價(jià)[12]．A*算法不僅僅在游戲地圖尋徑當(dāng)中應(yīng)用,目前還在智能機(jī)器人的最短路徑規(guī)劃以及封閉式場(chǎng)景貨車最佳路線的規(guī)劃中使用[13-15]．代價(jià)函數(shù)是A*算法中最重要的一步．

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

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

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

(1)

其中,σ(vn)為起點(diǎn)距離當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià),而ρ(vn)為當(dāng)前節(jié)點(diǎn)距終點(diǎn)的預(yù)估代價(jià)．

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

ρ(vn)必須滿足代價(jià)真實(shí)性原則與代價(jià)一致性原則．代價(jià)真實(shí)性即ρ(vn)的取值不能超過(guò)當(dāng)前節(jié)點(diǎn)距目標(biāo)節(jié)點(diǎn)的真實(shí)代價(jià)．而代價(jià)一致性原則要求ρ(vn)滿足式(2)所示條件:

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

(2)

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

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

證明首先假設(shè)vi+1為vi的下一個(gè)目標(biāo)節(jié)點(diǎn),則

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

(3)

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

2 主要結(jié)果

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

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

ρ(vn)=w1*Γ(P)

(4)

其中,w為角色P實(shí)際代價(jià)的權(quán)重系數(shù),而Γ為相鄰路徑距離之和,Γ可由以下計(jì)算得到

(5)

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

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

(6)

其中,(xn,yn)為當(dāng)前節(jié)點(diǎn)vn的橫縱坐標(biāo),而(xm,ym)為目標(biāo)節(jié)點(diǎn)vm的橫縱坐標(biāo)．

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

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

(7)

其中,w2為實(shí)際代價(jià)函數(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ā)情況下可以更好地進(jìn)行重規(guī)劃,但是稀疏A*算法在游戲地圖尋徑當(dāng)中可能陷入局部最優(yōu)的情況,從而較難發(fā)現(xiàn)游戲地圖中的全局最優(yōu)路徑.因此,引入差分進(jìn)化算法來(lái)對(duì)稀疏A*算法進(jìn)行優(yōu)化,通過(guò)差分進(jìn)化和稀疏A*算法相結(jié)合,克服了差分進(jìn)化方法尋徑中不能重規(guī)劃的缺點(diǎn),同時(shí)也加強(qiáng)了稀疏A*算法在尋找全局最優(yōu)路徑上的能力．本文提出的基于差分進(jìn)化和稀疏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 仿真實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

圖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*算法的改進(jìn)算法,因此與稀疏A*算法在性能上進(jìn)行比較是有必要的．接下來(lái)對(duì)所提出的算法與稀疏A*算法在運(yùn)行時(shí)間、路徑長(zhǎng)度和總體代價(jià)上進(jìn)行了對(duì)比,表1為本文方法與稀疏A*算法的性能比較,可以看出本文方法所規(guī)劃出來(lái)的路徑距離更短,總代價(jià)更?。?/p>

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

4 結(jié)語(yǔ)

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