游戲場景中基于直接交互機制的蟻群路徑規(guī)劃算法

孟志剛，鄭佳欣，李海泉

1.長沙學院計算機科學與工程學院，湖南 長沙 410022；2.長沙理工大學汽車與機械工程學院，湖南 長沙 410004

近年來，游戲產(chǎn)業(yè)飛速發(fā)展，游戲中的環(huán)境變得更加復雜和真實，為了提高玩家的游戲體驗，不少人員開始進行即時戰(zhàn)略游戲的研究，其中很重要的一部分就是運動控制。不同于傳統(tǒng)的路徑規(guī)劃算法僅追求點到點之間的最短路徑以及減少路徑中的轉(zhuǎn)彎次數(shù)，即時戰(zhàn)略游戲中的路徑規(guī)劃算法更希望能降低游戲角色在路途中被敵方單位攻擊的概率，選擇一條避開攻擊到達基地從而獲得更多敵方基地信息的路徑。

路徑規(guī)劃是一個應用廣泛的算法，常用的如經(jīng)典的蟻群算法［1］、人工勢場法［2］、A-Star 算法［3］等。針對傳統(tǒng)算法存在的一些問題［4］，當前有一些改進方法。肖金壯等通過動態(tài)更新信息素、引入三次均勻B 樣條曲線進行優(yōu)化，提高路徑搜索質(zhì)量和路徑的平滑性，將其應用在室內(nèi)自動引導車路徑規(guī)劃上［5］。陳勇等提出構建勢場路徑長度因子、路徑平緩性因子以及平滑性因子等多因子啟發(fā)式函數(shù)，解決了傳統(tǒng)蟻群算法中單以距離為指標的局限性，將其應用在移動機器人路徑規(guī)劃上［6］。張子然等設計了一種基于雙向搜索的改進蟻群路徑規(guī)劃算法，量化地圖的局部復雜程度并將信息融合到狀態(tài)轉(zhuǎn)移概率函數(shù)中，減少了路徑拐點，在復雜的地圖中路徑搜索效率更高，其主要被應用在移動機器人路徑規(guī)劃上［7］。傳統(tǒng)路徑規(guī)劃算法除了被應用于研究車輛運輸調(diào)度、移動機器人全局規(guī)劃等領域外，在其他領域也有相關應用。武善平等結(jié)合電子海圖提出一種改進A*算法的艦艇航路規(guī)劃方法，加入自適應的啟發(fā)信息，提高尋路效率；加入安全距離，保證航路的安全性；最后，對原始路徑進行二次優(yōu)化，進一步縮短航路的長度并提高航路的平滑性［8］。王奔等提出了一種改進的蟻群算法，并應用到定制公交問題中，以公交運營成本和乘客上座率作為優(yōu)化目標，車輛核載人數(shù)、乘客預定時間為約束條件，構建綜合評估模型，得到了更加合理的算法規(guī)劃路徑，求解時間更短［9］。邱雷針對游戲中的全局路徑規(guī)劃和局部避障展開研究，將A*算法與Bresenham 算法相結(jié)合，有效減少了無效節(jié)點的搜索數(shù)量；提出改進斥力勢場函數(shù)和模擬流水法設計分段函數(shù)，使游戲角色忽略無效障礙物，以最短路徑到達目標點［10］。

針對傳統(tǒng)路徑規(guī)劃算法在復雜游戲環(huán)境下尋路因素較為單一、信息傳遞較少、被敵方單位擊殺概率較高等問題，我們提出了一種僅僅基于直接交互機制的蟻群尋路算法（以下簡稱為直接交互算法）。我們不僅在普通的網(wǎng)格地圖中和其他經(jīng)典路徑規(guī)劃算法進行了對比實驗，從而驗證其具有較優(yōu)異的表現(xiàn)，而且實現(xiàn)了復雜對抗性即時戰(zhàn)略游戲場景中的相比其他經(jīng)典算法更好的結(jié)果。這種算法不僅僅是Meng et al.提到的通過在螞蟻之間直接交互信息來傳遞代表尋路目標點位置的信息，同時螞蟻還與敵方單位之間進行直接交互，獲取在路徑上對己方單位帶來傷害的敵方單位的位置信息，從而規(guī)劃出一條避開敵方攻擊單位到達敵方基地的更合理路徑［11］。20×20 的柵格網(wǎng)絡仿真實驗驗證了此算法的可行性和有效性。我們還使用了BWAPI軟件庫，以游戲《星際爭霸：母巢之戰(zhàn)》為平臺在設計的地圖上驗證其在實際游戲環(huán)境下的實用性，同時與游戲自帶A*算法和常用的人工勢場尋路算法做了對比實驗，來驗證該算法在實際尋路過程中的優(yōu)越性。

1 傳統(tǒng)蟻群算法原理

復雜的全局性的群體行為可以由簡單、局部的指導個體行為的規(guī)則產(chǎn)生，例如蟻群、鳥群和魚群中所展示的相關行為。對社會性的昆蟲而言，每只昆蟲的簡單個體行為產(chǎn)生了整體性的復雜行為。蟻群算法是一種面向群體的啟發(fā)式搜索方法，其出現(xiàn)就是從對自然界螞蟻覓食的研究中特別是從“聚集成群行為”中受到的啟發(fā)。Dorigo et al.于1991 年首次提出蟻群算法，其基本規(guī)則如下［12］。

1.1 路徑選擇規(guī)則

在路徑選擇階段，螞蟻會根據(jù)路徑上的信息素來選擇移動方向，t時刻螞蟻k從節(jié)點i轉(zhuǎn)移到節(jié)點j的概率可通過相關公式來計算求出。

簡單來說，當一只螞蟻在搜索問題的解時，它會根據(jù)當前位置和周圍信息素濃度選擇下一步的移動方向。具體來說，螞蟻會根據(jù)一定的概率值選擇下一步的移動方向。這個概率值會受到兩個因素的影響，一個是當前位置到下一步位置的距離，另一個是當前位置到下一步位置的信息素濃度。距離越短、信息素濃度越高的路徑被選擇的概率就越大。這個規(guī)則的本質(zhì)是螞蟻之間的相互作用，通過不斷地試錯和交流，整個群體最終會找到全局最優(yōu)解。

1.2 信息素更新規(guī)則

當一只螞蟻走完一條路徑后，它會根據(jù)路徑的距離和路徑的質(zhì)量更新路徑上的信息素濃度。信息素濃度的更新公式如下：

其中，Tij表示路徑上的信息素濃度，ρ是信息素揮發(fā)系數(shù)，表示信息素濃度會隨時間的推移而逐漸減少，ΔTij是信息素的增量。增量的大小與路徑的質(zhì)量成正比，也就是說，路徑質(zhì)量越好（即距離越短），增量就越大，信息素濃度就會被有效地提升。在這個過程中，信息素不斷地被積累和更新，螞蟻在后續(xù)的搜索中會根據(jù)信息素濃度選擇路徑，從而引導整個群體朝著更優(yōu)的方向移動。

傳統(tǒng)的蟻群算法采用了信息素這一種間接交互方式。信息素是一種化學物質(zhì)，在環(huán)境中延續(xù)一段時間后會擴散和衰減，獲得的信息較為有限，且花費時間較多，效率較低，因此它不適宜用在對實時性要求很高的游戲場景中。

2 基于直接交互機制的蟻群路徑規(guī)劃算法

2.1 直接交互的蟻群覓食仿真模型

當螞蟻從蟻巢出發(fā)時，它們處于空載狀態(tài)，當發(fā)現(xiàn)食物后，它們開始搬運食物，處于負載狀態(tài)。覓食過程可以劃分為尋找食物和搬運回巢兩個階段。在這兩個不同階段，直接交互機制都有著相似的規(guī)則。

在尋找食物過程中，螞蟻處于空載狀態(tài)。它們首先檢測自己是否位于食物處。如果是的話，螞蟻將搬運食物并轉(zhuǎn)入負載狀態(tài)。尋找食物的規(guī)則和搬運回巢的規(guī)則非常類似，這兩個過程可以看作對稱的。

在搬運食物回巢階段，螞蟻處于負載狀態(tài)。它們會先查看當前自己是否位于巢穴中，如果是的話就卸載食物并轉(zhuǎn)入空載狀態(tài)。當搬運食物的螞蟻和空載的螞蟻相遇時，它們直接交換覓食路徑的信息。

覓食的螞蟻在感知范圍內(nèi)選擇某只當前回巢最迅速的螞蟻交互信息。

2.2 用于蟻群尋路的直接交互機制

為了避免路線重復或形成循環(huán)，在游戲環(huán)境中獲得更多的信息，如敵方單位的位置、攻擊的頻率等，并實時高效地完成游戲場景中符合要求的路徑的搜尋，我們僅僅采用直接交互機制［7］進行游戲場景下的尋路。

為了增大螞蟻直接交互信息的概率，需要將尋路時螞蟻尋找其他不同狀態(tài)的螞蟻的感知范圍擴大，因此我們將柵格空間中蟻群尋路的直接交互感知范圍從8 個單元擴大到24 個單元，感知范圍內(nèi)一只螞蟻將與其他不同狀態(tài)的螞蟻交換信息，具體為增大移動到被選中螞蟻的位置或離它最近的鄰居位置的概率。

該直接交互機制實現(xiàn)的具體過程中包括兩個輔助的變量：tmpTime記錄螞蟻從蟻巢或食物處離開后經(jīng)過的時間；minTime記錄螞蟻相鄰不同狀態(tài)的其他螞蟻中最小的tmpTime。第i只螞蟻實現(xiàn)直接交互機制的具體過程如下所示。

步驟一：初始化tmpTime，minTime。

步驟二：在螞蟻i的感知范圍內(nèi)查找是否有其他具有不同狀態(tài)的螞蟻。

步驟三：如果步驟二為真，在滿足其條件的螞蟻中找到具有最小tmpTime的螞蟻j。

步驟四：將螞蟻j的tmpTime與螞蟻i的minTime比較，是否比minTime更小。

步驟五：如果步驟四為真，則把這個最小tmpTime賦給螞蟻i的minTime，然后增大螞蟻i向相鄰方格中距螞蟻j位置最近的方格移動的概率。

2.3 對已有蟻群尋路中直接交互機制的信息擴充

為了更好地將直接交互機制的蟻群算法運用到較為復雜且道路兩旁存在敵方攻擊單位的游戲環(huán)境中，我們對上述算法做了一定的信息擴充。

除了Meng et al.提及的螞蟻與螞蟻之間直接交互信息之外，螞蟻還會與游戲中的敵方單位進行直接交互，獲得其所在位置和攻擊范圍等信息，并將這些信息傳遞給其他螞蟻［11］。在與敵方單位交互時，螞蟻僅僅考慮在其前方的物體，因此螞蟻的可視范圍是一個半圓，半徑為ri，大概為螞蟻大小的三倍。具體交互過程如下所示。

步驟一：計算螞蟻與敵方單位之間的距離dij。

步驟二：如果dij＜ri，則計算螞蟻到敵方單位j的方向。

通過增加螞蟻與敵方單位之間的直接交互，使其在對目標點進行最短路徑規(guī)劃的同時考慮到了敵方單位的影響并在路徑中完成相應的避讓，提高了我方偵察單位的存活率，以便從目標點獲得更多信息回到基地。

同時，為了增加交互的螞蟻數(shù)量，還擴大了螞蟻的感知范圍，從相鄰一格的8 個單元擴大到相鄰兩格的24 個單元，大大提高了螞蟻之間進行直接交互的概率，從而提升了路徑規(guī)劃的效率，縮短了完成路徑規(guī)劃所需的時間。

2.4 基于直接交互的蟻群算法的路徑規(guī)劃

通過對直接交互的蟻群覓食仿真模型的研究，對螞蟻間通過直接交互來傳遞信息的方法有了深入的了解，接下來把這種方式應用到路徑規(guī)劃中。

整個過程包括最開始所有螞蟻從起點出發(fā)進行隨機路徑搜索，并標記自身狀態(tài)為尋找目標。當其中一些螞蟻搜尋到目標點以后，立即返回起點并切換自身狀態(tài)為返回起點。兩種不同狀態(tài)的螞蟻在地圖上相遇以后即按照2.2 節(jié)介紹的直接交互機制來完成交互過程。另外，在復雜游戲場景中，螞蟻還會使用2.3 節(jié)引入的信息擴充來完成與敵方單位的交互。算法具體過程如下。

步驟一：設定蟻群中螞蟻數(shù)量為m，路徑規(guī)劃迭代輪數(shù)為n。

步驟二：螞蟻i出發(fā)隨機搜尋路徑，如遇到返回起點狀態(tài)的螞蟻則與其進行直接交互，獲取當前從食物處離開后的經(jīng)過的時間值最小的螞蟻位置。

步驟三：螞蟻i根據(jù)交互獲得的信息選擇最佳前進路徑，如遇到敵方單位則與其進行直接交互，獲取敵方單位所在位置、攻擊范圍等信息。

步驟四：螞蟻i繼續(xù)前進直至尋找到目標點，并輸出當前尋找到的路徑長度以及搜索時間，輸出之后立刻切換自身狀態(tài)為返回起點。

步驟五：每一輪全體m只螞蟻尋路完成后，輸出m只螞蟻中找到的最短路徑為本輪最優(yōu)路徑。

步驟六：完成n輪迭代以后輸出比較后其中最短的路徑為本次算法運行的最短路徑。

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

為了驗證提出的算法在路徑規(guī)劃上的可行性和優(yōu)越性，選擇在PyCharm 軟件和《星際爭霸：母巢之戰(zhàn)》的BWAPI 平臺進行仿真實驗。仿真參數(shù)設置如表1 所示。

表1 仿真實驗參數(shù)數(shù)值

3.1 實驗1：20×20 的柵格地圖

為了驗證算法的有效性，首先在20×20 的柵格地圖中進行仿真實驗分析，同時與人工勢場算法、A*算法和多因素改進蟻群算法進行對比。仿真環(huán)境為（20×20），起始點為（0，20），目標點為（20，0）。最終A*算法、多因素改進蟻群算法和直接交互蟻群算法路徑規(guī)劃在20×20 柵格地圖實驗的對比結(jié)果如表2 所示。

表2 20×20 柵格地圖場景-實驗的對比結(jié)果

由表2 可知，直接交互蟻群算法最短路徑為35 格，優(yōu)于多因素改進蟻群算法，次于A* 算法；總耗時為11.4 s，次于A*算法和多因素改進蟻群算法。而人工勢場算法在這種地圖中沒有找到最短路徑。接下來在障礙物較為簡單的地圖中進行仿真實驗分析，仿真環(huán)境與上文一致，對比結(jié)果如表3所示。

表3 20×20 柵格地圖場景二實驗的對比結(jié)果

由表3 可知，直接交互蟻群算法在場景二簡單地圖中找到的最短路徑優(yōu)于人工勢場算法、A*算法和多因素改進蟻群算法；耗時與人工勢場算法和多因素改進蟻群算法相當。

從兩個場景的尋路表現(xiàn)來看，A*算法和直接交互蟻群算法的效果都比較好，多因素改進蟻群算法表現(xiàn)一般，而人工勢場算法這種在游戲場景中用得較多的尋路算法在場景一地圖中表現(xiàn)不佳。接下來將在游戲場景下對直接交互蟻群算法、A*算法和人工勢場算法做進一步的比較實驗。

3.2 實驗2：游戲場景下的實際地圖

經(jīng)過柵格地圖中的仿真實驗，可以看到我們的直接交互蟻群算法在最短路徑的尋找上并不占優(yōu)勢，但我們的最終目的是應用到游戲中，因此接下來在實際的游戲場景中進行仿真實驗。仿真環(huán)境為游戲《星際爭霸：母巢之戰(zhàn)》的地圖編輯器編寫的地圖，大小為50×37 柵格，并用《星際爭霸：母巢之戰(zhàn)》中“星靈族”的兩個基本單位“龍騎士”（Dragoon）和“探機”（Probe）作為敵方單位和我方尋路單位。探機是工人單位，除了采集資源外，還會被用于偵察。龍騎士是最基礎的遠程單位，它會在一定范圍內(nèi)巡邏，并攻擊我方的探機。

仿真實驗模擬了一個很常見的游戲場景，地圖情況如圖1 所示，在這個實驗中，我方探機將繞開敵方巡邏的龍騎士，到達敵方的基地，并盡可能地停留較長時間，以這樣的方式獲取敵方的信息。

圖1 游戲場景仿真測試地圖

實驗采用星際游戲內(nèi)置的A*尋路算法、在游戲場景中使用較常見的人工勢場尋路算法以及我們提出的基于直接交互機制的蟻群尋路算法來做對比實驗。

其中A*算法的尋路過程比較簡單，遵循找到最短路徑的原則，不會對游戲中敵方單位的攻擊作出回避來減少己方探機傷害。人工勢場的尋路過程中，敵方巡邏的龍騎士作為需要避開的威脅，其周圍會產(chǎn)生斥力場，斥力場范圍根據(jù)龍騎士的視野范圍設定，目的是讓我方探機盡量遠離其視野范圍，降低被擊殺的概率。敵方基地作為目的地，會產(chǎn)生引力場，這個引力場范圍必須非常大而且強度適中才能抵消龍騎士的斥力場，使探機在躲避龍騎士的同時朝著基地前進。

我們設置了4 架探機進行仿真實驗，基于直接交互機制的蟻群尋路算法與A*尋路算法、人工勢場尋路算法的對比實驗結(jié)果如表4 所示。

表4 游戲場景地圖實驗的對比結(jié)果

在上面的游戲場景仿真測試地圖中，人工勢場算法表現(xiàn)很好，是因為它可以通過斥力場的影響自動躲避動態(tài)障礙物，不像A*算法只是一味地去尋找最短路徑。直接交互蟻群算法表現(xiàn)比人工勢場算法更佳的原因是，一方面它可以與敵方單位直接交互，從而保證可以躲避敵方單位的攻擊；另一方面在多個探機之間存在信息交互，因此實現(xiàn)了一種協(xié)作機制。而這正是單一借助場景地圖中目標、障礙物和敵方單位分別產(chǎn)生引力場和斥力場的人工勢場算法所缺乏的地方。

3.3 實驗結(jié)果分析

我們提出的基于直接交互機制的蟻群算法對比星際爭霸游戲自帶的A*算法在復雜的游戲環(huán)境中有更好的表現(xiàn)，探機的停留時間達33.1s，遠長于自帶A*算法的0.9s。對比的人工勢場算法雖表現(xiàn)很好，但仍不及提出的算法，這是因為信息擴充后的直接交互機制的蟻群算法實現(xiàn)的協(xié)作機制類似于增加了一種新的人工勢場——協(xié)作勢場，而對比的人工勢場算法只提供了一種人工勢場——避開火力勢場。

直接交互機制提供的協(xié)作機制類似于增加了一種協(xié)作勢場，它相當于在敵方單位上疊加了多個斥力場，使得我方探機遠離敵方單位。該疊加斥力場范圍大于單一斥力場范圍，這樣我方單位可以及時避開敵方單位。

而對比的人工勢場算法只采用了避開火力勢場，單一的避開火力勢場無法讓遠處的探機及早避開敵方單位，因此普通的人工勢場尋路算法在游戲場景中的表現(xiàn)不及提出的算法。

4 結(jié)論

我們主要針對在復雜的游戲環(huán)境中傳統(tǒng)的路徑規(guī)劃算法尋路因素較為單一、信息傳遞較少、被敵方單位擊殺概率較大等問題提出改進策略。在傳統(tǒng)的蟻群算法模型中引入直接交互機制，既傳遞了代表尋路目標點位置的信息，又可以獲得路徑上對己方單位帶來傷害的敵方單位的位置信息。這樣使螞蟻間信息傳遞的效率提高，避免了路線重復或形成循環(huán)，降低對螞蟻走過的位置再次選擇的概率，在游戲環(huán)境中獲得更多的信息。它還實現(xiàn)了螞蟻與敵方單位的交互，極大提高了我方偵察單位的存活率。同時還擴大了螞蟻的感知范圍，提高了螞蟻之間進行交互的概率，縮短了完成路徑規(guī)劃所需的時間。總之，小型簡單柵格地圖已經(jīng)證明了我們所提出算法的優(yōu)越性，在大型復雜游戲場景中的表現(xiàn)更驗證了本算法的可行性、有效性和優(yōu)越性。今后打算將提出的直接交互蟻群算法應用在AGV 的路徑規(guī)劃中，并嘗試將其與強化學習算法結(jié)合在一起來使用。