一種混合算法在游戲尋徑中的應用

王善坤，張治海

（大連理工大學 城市學院，遼寧 大連116600）

一種混合算法在游戲尋徑中的應用

王善坤，張治海

（大連理工大學 城市學院，遼寧 大連116600）

路徑規劃是游戲人工智能領域的核心問題，如何建立一種高效的路徑規劃方法仍是研究的熱點之一。針對游戲中NPC的路徑規劃問題，將A*算法與改進的人工勢場法相結合，提出了一種混合算法。A*算法用于全局路徑規劃，生成節點路徑。改進的人工勢場法用于局部路徑規劃，使NPC能夠有效避讓環境中的動態障礙物。實驗仿真結果驗證了該算法的有效性和可行性。

A*算法；人工勢場法；路徑規劃；人工智能

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

1　基于A*算法的全局路徑規劃

1.1A*算法

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

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

A*算法在執行時需要維護兩張表：OPEN表和CLOSED表，OPEN表保存所有已生成而未訪問的節點，CLOSED表中記錄已訪問過的節點［5］。算法執行流程如下：

Step1：設起始點為S，目標點為G，初始化OPEN表和CLOSED表，將起始點S放入OPEN表；

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

Step3：若n為目標點G，搜索結束。從目標點G回溯到起始點S，獲得兩點間的最佳路徑；

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

Step5：從OPEN表中刪除節點n，并將節點n放入CLOSED表；

Step6：重復Step2～Step5，直到搜索到目標點G，或是搜索失敗，路徑不存在。

1.2路徑優化

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

圖1　未優化的路徑

圖2　優化后的路徑

2　基于改進人工勢場法的局部路徑規劃

人工勢場法是一種常用的局部路徑規劃方法［6］，它的基本思想是將NPC抽象成一個質點，將其在游戲虛擬環境中的運動，抽象成在人造的虛擬力場中的運動，目標點對其產生吸引力，障礙物對其產生排斥力，最后通過求合力來控制NPC的運動。應用人工勢場法規劃出來的路徑一般是比較平滑并且安全，但是這種方法存在局部極小值等問題。

2.1斥力勢函數

在虛擬力場中，障礙物對NPC產生斥力。算法中所用的斥力勢函數如式（2）所示：

在式（2）中，η為斥力系數；ρ（x，x0）為NPC與障礙物之間的最短距離；ρ（x，xg）為NPC與目標點之間的相對距離；ρ0為常數，在ρ0的范圍內NPC受到障礙物的斥力，在此范圍外則不受斥力作用。斥力為斥力勢函數的負梯度，可以分解為兩個分力之和，即：

在式（3）中，Frep為障礙物對NPC的排斥力，Frep1和Frep2是它的兩個分力。Frep1的方向是從障礙物指向NPC，Frep2的方向是從NPC指向目標點。

2.2引力勢函數

在虛擬力場中，目標點對NPC產生吸引力。算法中所用的引力勢函數如式（6）所示：

在式（6）中，k為引力系數；ρ（x，xg）為NPC與目標點之間的相對距離。引力為引力勢函數的負梯度，其方向從NPC指向目標點，即：

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

2.3斥力系數

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

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

3　混合算法

傳統的路徑規劃方法并不適用于復雜、多變環境中的NPC路徑規劃問題，文中將全局路徑規劃和局部路徑規劃相結合，提出了一種適用于NPC路徑規劃的混合算法。首先根據已知全局環境信息，將A*算法用于全局路徑規劃，生成從起始點到目標點的全局路徑，并對路徑進行優化處理，剔除路徑中的冗余節點，使路徑變得更平滑。然后根據從NPC運動過程中所獲取的局部環境信息，將人工勢場法用于局部路徑規劃，對路徑進行優化、調整，使NPC安全、無碰撞的到達目標點。混合算法不僅利用全局環境信息建立了全局最優路徑，還具有良好的避障能力，有效解決了復雜、多變環境中的NPC路徑規劃問題。算法執行流程如下：

Step1：根據已知環境信息，將A*算法用于全局路徑規劃，生成從起始點到目標點的路徑節點序列；

Step2：優化A*路徑；

Step3：將路徑中起始點的相鄰節點作為子目標點；

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

Step5：當NPC的運動出現停滯或震蕩時，利用A*算法重新規劃從NPC當前位置到子目標點之間的路徑；優化新路徑，并用其替代原路徑；

Step6：重復Step4～Step5，直到NPC到達子目標點；

Step7：取路徑中當前子目標點的下一個相鄰節點作為子目標點；

Step8：轉到Step4，直到NPC到達目標點；若N步后仍未到達目標點，則轉到Step1重新規劃。

4　實驗仿真分析

實驗仿真的硬件環境：CPU Intel?CoreTMi5-2400@3.1 GHz，內存為2GB；軟件環境：操作系統為MicrosoftWindows XPProfessional；仿真系統開發平臺為：MicrosoftVisualC++6.0。

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

圖3　優化后的路徑

圖4　A*規劃的全局路徑

圖5　仿真過程

圖6　仿真結果

5　結束語

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

［1］柳長安，鄢小虎，劉春陽，等.基于改進蟻群算法的移動機器人動態路徑規劃方法［J］.電子學報，2011，39（5）:1220-1224.

［2］葉煒垚，王春香，楊明，等.基于虛擬障礙物的移動機器人路徑規劃方法.機器人［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］詹海波.人工智能尋路算法在電子游戲中的研究和應用［D］.武漢:華中科技大學，2006.

［5］張程，肖大薇，張盈謙.基于區域搜索的A*算法在游戲尋徑中的應用研究.電子設計工程［J］，2014，22（13）:15-17.

［6］張殿富，劉福.基于人工勢場法的路徑規劃方法研究及展望［J］.計算機工程與科學，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稿件編號：201510107

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