一種混合算法在游戲?qū)街械膽?yīng)用

王善坤，張治海

（大連理工大學(xué) 城市學(xué)院，遼寧 大連116600）

一種混合算法在游戲?qū)街械膽?yīng)用

王善坤，張治海

（大連理工大學(xué) 城市學(xué)院，遼寧 大連116600）

路徑規(guī)劃是游戲人工智能領(lǐng)域的核心問題，如何建立一種高效的路徑規(guī)劃方法仍是研究的熱點(diǎn)之一。針對(duì)游戲中NPC的路徑規(guī)劃問題，將A*算法與改進(jìn)的人工勢(shì)場(chǎng)法相結(jié)合，提出了一種混合算法。A*算法用于全局路徑規(guī)劃，生成節(jié)點(diǎn)路徑。改進(jìn)的人工勢(shì)場(chǎng)法用于局部路徑規(guī)劃，使NPC能夠有效避讓環(huán)境中的動(dòng)態(tài)障礙物。實(shí)驗(yàn)仿真結(jié)果驗(yàn)證了該算法的有效性和可行性。

A*算法；人工勢(shì)場(chǎng)法；路徑規(guī)劃；人工智能

NPC（非玩家角色）通常指的是在游戲中不受玩家控制，而是由計(jì)算機(jī)控制的角色。如何保證NPC在游戲虛擬場(chǎng)景中無障礙的自由運(yùn)動(dòng)一直是游戲?qū)絾栴}的研究熱點(diǎn)。NPC的尋徑問題可以被描述為：為NPC尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)的安全、無碰撞的最優(yōu)路徑［1］。在以往的研究中，通常將路徑規(guī)劃方法分為兩類:全局路徑規(guī)劃和局部路徑規(guī)劃［2］。A*算法是一種最具代表性的全局路徑規(guī)劃方法，但其只適用于靜態(tài)環(huán)境，并不適用于動(dòng)態(tài)環(huán)境。人工勢(shì)場(chǎng)法是一種最常用的局部路徑規(guī)劃方法，該方法結(jié)構(gòu)簡(jiǎn)單、計(jì)算量小，并具備良好的避障能力，但其存在局部極小值等問題。文中提出了一種適用于NPC尋徑問題的混合算法，該算法將全局路徑規(guī)劃和局部路徑規(guī)劃相結(jié)合：將A*算法用于全局路徑規(guī)劃，生成節(jié)點(diǎn)路徑。隨后對(duì)路徑進(jìn)行優(yōu)化處理，減少了路徑中節(jié)點(diǎn)的數(shù)量，使路徑更加平滑、真實(shí)；將改進(jìn)的人工勢(shì)場(chǎng)法用于局部路徑規(guī)劃，使NPC能夠有效避讓環(huán)境中的動(dòng)態(tài)障礙物。實(shí)驗(yàn)仿真結(jié)果驗(yàn)證了該算法的有效性和可行性。

1　基于A*算法的全局路徑規(guī)劃

1.1A*算法

A*算法是一種典型的啟發(fā)式搜索算法，常用于游戲中的NPC的移動(dòng)計(jì)算，或線上游戲的BOT的移動(dòng)計(jì)算上［3］。其啟發(fā)函數(shù)如式（1）所示：

式（1）中，f（n）為起始點(diǎn)經(jīng)n節(jié)點(diǎn)到目標(biāo)點(diǎn)的啟發(fā)函數(shù)；g（n）為起始點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)；h（n）為從節(jié)點(diǎn)n到目標(biāo)點(diǎn)最佳路徑的估計(jì)值［4］。如果估計(jì)值等于節(jié)點(diǎn)n到目標(biāo)點(diǎn)的實(shí)際距離，那么A*法可以非常高速的找到最佳路徑（搜索過程中幾乎不會(huì)走彎路）；如果估計(jì)值比節(jié)點(diǎn)n到目標(biāo)點(diǎn)的實(shí)際距離小，那么A*算法保證能找到一條最佳路徑；如果估計(jì)值比從節(jié)點(diǎn)n到目標(biāo)點(diǎn)的實(shí)際距離大，則A*不能保證找到一條最佳 路徑，但它運(yùn)行得更快。

A*算法在執(zhí)行時(shí)需要維護(hù)兩張表：OPEN表和CLOSED表，OPEN表保存所有已生成而未訪問的節(jié)點(diǎn)，CLOSED表中記錄已訪問過的節(jié)點(diǎn)［5］。算法執(zhí)行流程如下：

Step1：設(shè)起始點(diǎn)為S，目標(biāo)點(diǎn)為G，初始化OPEN表和CLOSED表，將起始點(diǎn)S放入OPEN表；

Step2：若OPEN表為空，搜索結(jié)束，未找到路徑；否則從OPEN表中取出f值最小節(jié)點(diǎn)n；

Step3：若n為目標(biāo)點(diǎn)G，搜索結(jié)束。從目標(biāo)點(diǎn)G回溯到起始點(diǎn)S，獲得兩點(diǎn)間的最佳路徑；

Step4：若n不是目標(biāo)點(diǎn)，則檢查n的全部連通的相鄰子節(jié)點(diǎn)。對(duì)于每一個(gè)子節(jié)點(diǎn)m，計(jì)算g（m）的值。若m在OPEN表中，且其值比表中的小，則將n作為m的父節(jié)點(diǎn)，并重新計(jì)算g（m）和f（m）；若m不在OPEN表中，則將n作為m的父節(jié)點(diǎn)，計(jì)算g（m）、h（m）和f（m），并將其加入到OPEN表中；

Step5：從OPEN表中刪除節(jié)點(diǎn)n，并將節(jié)點(diǎn)n放入CLOSED表；

Step6：重復(fù)Step2～Step5，直到搜索到目標(biāo)點(diǎn)G，或是搜索失敗，路徑不存在。

1.2路徑優(yōu)化

A*算法所規(guī)劃的路徑是由一系列路徑節(jié)點(diǎn)構(gòu)成的，圖1所示為從A到C的節(jié)點(diǎn)路徑。A*算法所規(guī)劃的路徑中存在著大量的多余節(jié)點(diǎn)，例如，圖1中A、B間是可視的，兩點(diǎn)間存在直線路徑，A、B間的其余節(jié)點(diǎn)都是不必要的。優(yōu)化A*路徑就是僅保留路徑中的必要節(jié)點(diǎn)，刪除路徑中的非必要節(jié)點(diǎn)，優(yōu)化前和優(yōu)化后的路徑，分別如圖1和圖2所示。從圖中可以看到，優(yōu)化后的路徑更短、更平滑，并且突破了網(wǎng)格地圖中A*路徑的8方向限制，實(shí)現(xiàn)了360度的全方位路徑。

圖1　未優(yōu)化的路徑

圖2　優(yōu)化后的路徑

2　基于改進(jìn)人工勢(shì)場(chǎng)法的局部路徑規(guī)劃

人工勢(shì)場(chǎng)法是一種常用的局部路徑規(guī)劃方法［6］，它的基本思想是將NPC抽象成一個(gè)質(zhì)點(diǎn)，將其在游戲虛擬環(huán)境中的運(yùn)動(dòng)，抽象成在人造的虛擬力場(chǎng)中的運(yùn)動(dòng)，目標(biāo)點(diǎn)對(duì)其產(chǎn)生吸引力，障礙物對(duì)其產(chǎn)生排斥力，最后通過求合力來控制NPC的運(yùn)動(dòng)。應(yīng)用人工勢(shì)場(chǎng)法規(guī)劃出來的路徑一般是比較平滑并且安全，但是這種方法存在局部極小值等問題。

2.1斥力勢(shì)函數(shù)

在虛擬力場(chǎng)中，障礙物對(duì)NPC產(chǎn)生斥力。算法中所用的斥力勢(shì)函數(shù)如式（2）所示：

在式（2）中，η為斥力系數(shù)；ρ（x，x0）為NPC與障礙物之間的最短距離；ρ（x，xg）為NPC與目標(biāo)點(diǎn)之間的相對(duì)距離；ρ0為常數(shù)，在ρ0的范圍內(nèi)NPC受到障礙物的斥力，在此范圍外則不受斥力作用。斥力為斥力勢(shì)函數(shù)的負(fù)梯度，可以分解為兩個(gè)分力之和，即：

在式（3）中，F(xiàn)rep為障礙物對(duì)NPC的排斥力，F(xiàn)rep1和Frep2是它的兩個(gè)分力。Frep1的方向是從障礙物指向NPC，F(xiàn)rep2的方向是從NPC指向目標(biāo)點(diǎn)。

2.2引力勢(shì)函數(shù)

在虛擬力場(chǎng)中，目標(biāo)點(diǎn)對(duì)NPC產(chǎn)生吸引力。算法中所用的引力勢(shì)函數(shù)如式（6）所示：

在式（6）中，k為引力系數(shù)；ρ（x，xg）為NPC與目標(biāo)點(diǎn)之間的相對(duì)距離。引力為引力勢(shì)函數(shù)的負(fù)梯度，其方向從NPC指向目標(biāo)點(diǎn)，即：

NPC所受的合力如式（8）所示:

2.3斥力系數(shù)

傳統(tǒng)的人工勢(shì)場(chǎng)法認(rèn)為所有障礙物對(duì)NPC的排斥作用都是相同的，因此NPC對(duì)所有障礙物都應(yīng)采用相同的避讓策略。但在游戲場(chǎng)景中，不同位置、不同類型的障礙物對(duì)NPC的排斥作用是不一樣的，越是靠近NPC的行進(jìn)方向、對(duì)NPC的威脅越大的障礙物，其對(duì)NPC的排斥作用就越明顯，因而NPC總是會(huì)選擇優(yōu)先避讓位于其行進(jìn)方向上的最具威脅的障礙物。將以上策略應(yīng)用于傳統(tǒng)的人工勢(shì)場(chǎng)法，引入斥力系數(shù)Cfr，Cfr的計(jì)算公式如式（9）所示：

在式（9）中，θ為NPC行進(jìn)方向與斥力之間的夾角；β為威脅因子，其值大于、等于1。引入斥力系數(shù)后，斥力計(jì)算公式如式（10）所示：

3　混合算法

傳統(tǒng)的路徑規(guī)劃方法并不適用于復(fù)雜、多變環(huán)境中的NPC路徑規(guī)劃問題，文中將全局路徑規(guī)劃和局部路徑規(guī)劃相結(jié)合，提出了一種適用于NPC路徑規(guī)劃的混合算法。首先根據(jù)已知全局環(huán)境信息，將A*算法用于全局路徑規(guī)劃，生成從起始點(diǎn)到目標(biāo)點(diǎn)的全局路徑，并對(duì)路徑進(jìn)行優(yōu)化處理，剔除路徑中的冗余節(jié)點(diǎn)，使路徑變得更平滑。然后根據(jù)從NPC運(yùn)動(dòng)過程中所獲取的局部環(huán)境信息，將人工勢(shì)場(chǎng)法用于局部路徑規(guī)劃，對(duì)路徑進(jìn)行優(yōu)化、調(diào)整，使NPC安全、無碰撞的到達(dá)目標(biāo)點(diǎn)。混合算法不僅利用全局環(huán)境信息建立了全局最優(yōu)路徑，還具有良好的避障能力，有效解決了復(fù)雜、多變環(huán)境中的NPC路徑規(guī)劃問題。算法執(zhí)行流程如下：

Step1：根據(jù)已知環(huán)境信息，將A*算法用于全局路徑規(guī)劃，生成從起始點(diǎn)到目標(biāo)點(diǎn)的路徑節(jié)點(diǎn)序列；

Step2：優(yōu)化A*路徑；

Step3：將路徑中起始點(diǎn)的相鄰節(jié)點(diǎn)作為子目標(biāo)點(diǎn)；

Step4：獲取NPC的位置及其視距內(nèi)的局部環(huán)境信息，計(jì)算引力Fatt，斥力Frep及其合力F；依據(jù)作用于NPC上的合力F和NPC的速度，計(jì)算NPC的新位置；

Step5：當(dāng)NPC的運(yùn)動(dòng)出現(xiàn)停滯或震蕩時(shí)，利用A*算法重新規(guī)劃從NPC當(dāng)前位置到子目標(biāo)點(diǎn)之間的路徑；優(yōu)化新路徑，并用其替代原路徑；

Step6：重復(fù)Step4～Step5，直到NPC到達(dá)子目標(biāo)點(diǎn)；

Step7：取路徑中當(dāng)前子目標(biāo)點(diǎn)的下一個(gè)相鄰節(jié)點(diǎn)作為子目標(biāo)點(diǎn)；

Step8：轉(zhuǎn)到Step4，直到NPC到達(dá)目標(biāo)點(diǎn)；若N步后仍未到達(dá)目標(biāo)點(diǎn)，則轉(zhuǎn)到Step1重新規(guī)劃。

4　實(shí)驗(yàn)仿真分析

實(shí)驗(yàn)仿真的硬件環(huán)境：CPU Intel?CoreTMi5-2400@3.1 GHz，內(nèi)存為2GB；軟件環(huán)境：操作系統(tǒng)為MicrosoftWindows XPProfessional；仿真系統(tǒng)開發(fā)平臺(tái)為：MicrosoftVisualC++6.0。

實(shí)驗(yàn)仿真環(huán)境為仿真軟件生成的30×20的網(wǎng)格地圖，如圖3所示。地圖中點(diǎn)S為路徑搜索的起始點(diǎn)，點(diǎn)G為路徑搜索的目標(biāo)點(diǎn)，黑色方格表示森林、山川、動(dòng)物等人為設(shè)置的障礙物，黑色方格區(qū)域?yàn)镹PC不可通行區(qū)域，白色方格區(qū)域?yàn)镹PC可通行區(qū)域。首先根據(jù)全局環(huán)境信息，將A*算法用于全局路徑規(guī)劃，生成并優(yōu)化一條從起始點(diǎn)S，到目標(biāo)點(diǎn)G的節(jié)點(diǎn)路徑。圖4中的兩個(gè)黑色小圓點(diǎn)，為優(yōu)化后的路徑節(jié)點(diǎn)。隨后，將改進(jìn)的人工勢(shì)場(chǎng)法用于局部路徑規(guī)劃，控制NPC沿著A*算法所規(guī)劃的路徑移動(dòng)，并能夠有效的避開動(dòng)態(tài)障礙物。圖5中，在已規(guī)劃的路徑上出現(xiàn)了5處點(diǎn)狀障礙物，NPC依然可以避開障礙物，繼續(xù)沿著A*所規(guī)劃的路徑向目標(biāo)點(diǎn)移動(dòng)。圖6中，前方路徑上出現(xiàn)了“L”形障礙物，NPC移動(dòng)到“L”形障礙物前出現(xiàn)了停滯，陷入了局部極小點(diǎn)。當(dāng)NPC的運(yùn)動(dòng)出現(xiàn)停滯或震蕩時(shí)，利用A*算法重新規(guī)劃從NPC當(dāng)前位置到子目標(biāo)點(diǎn)之間的路徑，優(yōu)化新路徑，并用其替代原路徑。圖6中，在“L”形障礙物附近出現(xiàn)的兩個(gè)小黑點(diǎn)為新規(guī)劃的路徑節(jié)點(diǎn)，由新路徑替代原有的路徑，NPC沿著新規(guī)劃的路徑移動(dòng)，最終到達(dá)目標(biāo)點(diǎn)。從上面的實(shí)驗(yàn)仿真結(jié)果可以看出，該算法所規(guī)劃的路徑較之傳統(tǒng)的A*算法更加平滑、真實(shí)，算法的避障性能要優(yōu)于傳統(tǒng)的人工勢(shì)場(chǎng)法。

圖3　優(yōu)化后的路徑

圖4　A*規(guī)劃的全局路徑

圖5　仿真過程

圖6　仿真結(jié)果

5　結(jié)束語

文中將A*算法與改進(jìn)的人工勢(shì)場(chǎng)法相結(jié)合，提出了一種適用于NPC路徑規(guī)劃的混合算法。該算法取兩者之長(zhǎng)，去兩者之短，即解決了A*算法所規(guī)劃的路徑不夠平滑的問題，又解決了人工勢(shì)場(chǎng)法存在的局部極小值問題。實(shí)驗(yàn)仿真結(jié)果表明該算法生成的路徑更平滑，并且具備良好的避障能力，使得NPC的尋徑更加自然，有效地提高了NPC智能性。

［1］柳長(zhǎng)安，鄢小虎，劉春陽，等.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法［J］.電子學(xué)報(bào)，2011，39（5）:1220-1224.

［2］葉煒垚，王春香，楊明，等.基于虛擬障礙物的移動(dòng)機(jī)器人路徑規(guī)劃方法.機(jī)器人［J］，2011，33（3）:273-275.

［3］Amit.Pathfinding-Introduction［EB/OL］.（2009-05-01）［2014-09-30］.http://theory.stanford.edu/～amitp/GameProgramming/Astar Comparision.htm l.

［4］詹海波.人工智能尋路算法在電子游戲中的研究和應(yīng)用［D］.武漢:華中科技大學(xué)，2006.

［5］張程，肖大薇，張盈謙.基于區(qū)域搜索的A*算法在游戲?qū)街械膽?yīng)用研究.電子設(shè)計(jì)工程［J］，2014，22（13）:15-17.

［6］張殿富，劉福.基于人工勢(shì)場(chǎng)法的路徑規(guī)劃方法研究及展望［J］.計(jì)算機(jī)工程與科學(xué)，2013，35（6）:89-95.

The study of hybrid algorithm in im p lementing of game

WANG Shan-kun，ZHANG Zhi-hai
（City Institute，Dalian University of Technology，Dalian 116600，China）

Path planning is the core issues in theartificial intelligence field ofgames，and how to establish an effectivemethod of path planning is still focused on.For path planning of NPC in the environmentof games，combiningwith the A*algorithm and the improved artificialpotential fieldmethod，A hybrid algorithm is proposed.A staralgorithm has utilization in the global path planner and created the node path.The improved artificial potential field method is applied to local path planner and it can achieve the aim at avoiding the dynamic obstacles in the environment.The experimental simulation result verifys the feasibility and effectivenessof the algorithm.

A star algorithm；artificial potential field method；path planning；artificial intelligence

TN02

A

1674-6236（2016）19-0022-03

2015-10-17稿件編號(hào)：201510107

王善坤 （1960—），男，遼寧大連人，副教授。研究方向：人工智能、數(shù)據(jù)挖掘。