即時戰(zhàn)略游戲的智能流場尋路算法設計與實現(xiàn)

李 恬，張樹美，趙俊莉

（青島大學數(shù)據(jù)科學與軟件工程學院，山東青島266071）

0 引言

游戲是在有限環(huán)境和固定規(guī)則中集中探索人工智能（Artificial Intelligence，AI）的理想領域，可以對解決問題的技術進行開發(fā)和評估以便解決更復雜的現(xiàn)實問題。人工智能多被應用在國際象棋、拼字游戲、西洋雙陸棋、跳棋等棋盤游戲中［1］，尤其是在最復雜的棋類游戲圍棋中，AlphaGo 以絕對優(yōu)勢戰(zhàn)勝了世界頂級職業(yè)圍棋高手，證明了游戲中人工智能發(fā)展取得巨大突破。相應地，人工智能也被引入到了組成游戲的各種元素中，用以增加玩家的挑戰(zhàn)性、游戲的可玩性和模擬世界的真實性，1986 年Minsky 提出了Agent 技術使得智能代理成為可能，2001 年Lent 將電子游戲用作人工智能研究的試驗臺，其后2003 年Buro 提倡進行即時戰(zhàn)略（Real-Time Strategy，RTS）游戲的研究，并提供了一個用于探索游戲人工智能和許多其他核心復雜問題的沙盒。即時戰(zhàn)略游戲作為人工智能應用最多最早的游戲之一，不僅有策略AI、戰(zhàn)術AI、戰(zhàn)術布置、危險估計和地形分析等多方面的AI 應用，更有包含簡單AI 尋路和群體AI 尋路的路徑搜索算法的重要應用。智能路徑搜索算法是游戲中最基本最核心的問題，也是RTS 游戲中的重要部分。

路徑搜索算法是在起點和終點之間尋找到一條可行路徑的算法，應用在眾多方面，包括網(wǎng)絡流量、機器人路徑規(guī)劃、軍事仿真和計算機游戲，有十分豐富的理論基礎和眾多應用場景。1956 年Dijkstra［2］提出的Dijkstra 算法是一種典型的最短路徑算法，它計算圖中某源點到其他某點的最短路徑；其后1968 年Hart 等［3］提出了一種基于啟發(fā)式搜索的A*算法，使得查找路徑時間縮短；趙建民等［4］將A*算法應用到RTS游戲中，用以改進單個對象尋徑；余帥等［5］將勢場法運用到RTS 游戲的交互尋路中；葉青等［6］用雙層朝向處理方法解決群體運動朝向；Malinowski 等［7］應用基于非易失性內(nèi)存（Non-Volatile Random Access Memory，NVRAM）的分布式緩存實現(xiàn)了大規(guī)模的并行仿真；Sartoretti等［8］結合強化和模仿學習提出了一種多智能體尋路（Multi-Agent Path Finding，MAPF）的新框架，Ho等［9］采用批處理的方法實現(xiàn)無人機交通管理中的多智能體尋路。但是，這些尋路算法并不能滿足多智能體快速尋路的需求，目前大多是通過優(yōu)化單條路徑規(guī)劃速度來提高整體運動速率，并沒有在全局宏觀改進群體路徑規(guī)劃，所以需要新的算法用來解決短時間內(nèi)大量移動智能體的并發(fā)尋路問題。在2013 年由Pentheny 提出的流場尋路算法［10］將物理學中的流場動力學引入到游戲尋路中并成功應用于游戲《最高指揮官2》和《堅守陣地2》中，實現(xiàn)了多物體的同時快速尋路，突破了智能體數(shù)量的限制，使游戲中的智能體可以模擬人的真實行動，移動時能夠聚集和分散。

本文主要設計了即時戰(zhàn)略游戲中一種新型的路徑搜索算法——流場尋路算法，并對算法從數(shù)據(jù)結構存儲、路徑代價計算和流場生成算法三方面做出了改進，進一步提高了流場尋路算法的運行效率，解決即時戰(zhàn)略游戲中的碰撞阻塞問題。

1 問題描述

1.1 RTS游戲中的尋路問題

即時戰(zhàn)略游戲［5］是一種即時進行的，有資源采集、基地建造、科技發(fā)展和戰(zhàn)斗元素的戰(zhàn)略游戲。即時戰(zhàn)略游戲歷史悠久，在英國最早可追溯到1983 年Gibson 開發(fā)的《Stonkers》和1987 年發(fā)行的《Nether Earth》，在北美普遍認為1984 年由Evryware’s Dave 和Barry Murry 開 發(fā) 的《The Ancient Art of War》是現(xiàn)代即時戰(zhàn)略的始祖［11］。大型的即時戰(zhàn)略類游戲可以讓人體驗到一種指揮千軍萬馬縱橫沙場的英雄意境，如：《帝國時代》、《星際爭霸》和《紅色警戒》［12］。以上游戲都充分利用AI加強對資源建筑控制和戰(zhàn)斗沖突，使得在游戲中更加注重移動規(guī)模、即時性和交互性［13-15］，但以上的這幾款典型RTS 游戲都或多或少存在多次碰撞和行動阻塞的缺點［16］，為解決此類問題，《星際爭霸》采取取消碰撞［17］，《紅色警戒》按順序物體逐一進行尋路，《帝國時代》采用限制尋路數(shù)量等的簡化方法。為了讓游戲中的智能體尋路更加真實和精細，游戲開發(fā)者必須使用智能化的搜索路徑方法，這樣游戲才可能最大限度地模擬真實世界的場景，游戲中的移動智能體就像真正的人一樣，能夠針對不同的情景做出合理適當?shù)姆答仯龀龈兄h(huán)境后的最有利的行為。

隨著計算機技術的發(fā)展、網(wǎng)絡傳輸效率的提高和游戲品質的提升，RTS 游戲的地圖、場景、聲音和角色造型也都有不同水平的進步，所以地圖和游戲智能體規(guī)模增大使得游戲中智能尋路越來越重要［18］，采取一種智能尋路算法可以避免游戲中的阻塞現(xiàn)象和多次碰撞問題，不同的算法所呈現(xiàn)出的效果不盡相同，適用場景也不同。

1.2 常見尋路算法局限性

游戲中的地圖一般采用柵格化的方法來構造以便于路徑計算，然后采用不同的尋路算法進行計算。圖1 為200×160大小的矩形地圖，將其劃分為多個長度為4 的小正方形，則網(wǎng)格的個數(shù)為50×40，將每個網(wǎng)格看作節(jié)點，邊則為節(jié)點間的通路，將（0，0）設置為目標節(jié)點，深灰色區(qū)域表示障礙物，是不可通過區(qū)域。初始化地圖完成后，隨機生成n 個智能體，使用不同的尋路算法計算每個智能體的生成路徑。

最早所采用的尋路算法為Dijkstra 算法，它被廣泛應用于各種場合，如：地理信息系統(tǒng)（Geographic Information System，GIS）路徑規(guī)劃［19］、城市道路優(yōu)化［20］、物流配送［21］、救災路線［22］，可以看出以上場景都是兩點間尋找一條最優(yōu)路徑的問題，只需考慮找到兩點之間的最短路徑，忽略了實際問題中全局群體移動和出口瓶頸的阻塞碰撞問題，并不適用于游戲中即時不確定的多個智能體移動。其后，A*算法的出現(xiàn)解決了游戲中單個非玩家角色（Non-Player Character，NPC）的智能化尋路問題，如減少了搜索區(qū)域，降低搜索的成本時間，確保在較短的時間內(nèi)找到相對合適的最優(yōu)路徑，成為目前游戲中使用最廣泛的尋路算法，同時也在城市交通［23］、車輛調度［24］、鑲嵌線提取［25］、停車場尋路［26］、士兵作戰(zhàn)［27］中有重要應用。

圖1 初始化地圖Fig.1 Initialization of map

人工勢場法作為一種常見的局部路徑規(guī)劃方法也被引入到RTS游戲中，其算法主要是模擬虛擬力場，目標點對物體產(chǎn)生引力，障礙物對物體產(chǎn)生斥力，引力和斥力產(chǎn)生的合力形成物體的運動路徑。如遺傳算法、蟻群算法等智能仿生算法也常常被應用在路徑規(guī)劃中，主要是模擬遺傳變異、螞蟻覓食等自然界中的各種行為和現(xiàn)象，但是此類智能算法需要多次迭代才能得到更為準確的路徑。

以上方法都可實現(xiàn)路徑規(guī)劃，但傳統(tǒng)路徑規(guī)劃計算速度慢，人工勢場法適用于局部規(guī)劃，智能路徑規(guī)劃需多次迭代，這都十分影響游戲的流暢度和用戶體驗。而流場尋路算法很好地解決了RTS 游戲對于尋路時間和數(shù)量的要求，適合于大規(guī)模模擬人群的移動，其主要思想是根據(jù)地圖和目的地生成有關于路徑的“場”，這個“場”標記了地圖中任意位置到達目標節(jié)點的運動方向，本文將詳細介紹流場尋路算法。

2 流場尋路算法

2.1 基本數(shù)據(jù)結構

流場尋路有三種數(shù)據(jù)類型，用來存儲經(jīng)過某節(jié)點代價時的代價字段類型，存儲該節(jié)點到達目標節(jié)點最小代價值的完整代價字段類型和經(jīng)過該節(jié)點時到目標節(jié)點方向的流場字段類型。

代價字段類型是初始化地圖時對每個節(jié)點的代價提前設定數(shù)值的代價類型，一般用最大值代表不可通過的區(qū)域，如：墻體、高山等，用正整數(shù)代表通過的代價值，并用不同的值代表不同的地形地貌，如：沼澤、海洋、沙漠和斜坡代價值大于經(jīng)過平原的代價值，代價值最小為1。如果有某些地方?jīng)]有明確的代價值，則將一個靜態(tài)全局變量賦給代價字段以便于流場的計算和表示，本文實驗的初始代價值為20，用變量INFI表示最大值268 435 455（0xFFFFFFF），以大小為10×10 的部分地圖為例，結果如圖2所示。

完整代價字段存儲的是完整代價值和標志位的字段類型，完整代價值是當前節(jié)點到目標節(jié)點的代價值，標志位記錄整合代價的活動波前和視線，以便優(yōu)化流場字段的方向值。圖3 中深灰色代表的是障礙物，黑色直線是從點G 所發(fā)出的視線，即點G與障礙物最近邊緣的連線并延長所形成的射線，而視線的方向和兩視線間的所夾部分是由障礙物和點G的位置來決定的。最淺灰色部分代表的是視線所穿過的區(qū)域，作用是將中等深灰色部分的智能體移動到此區(qū)域以便在視線范圍內(nèi)，可直接到達目標點G。

圖2 代價字段示意圖Fig.2 Schematic diagram of cost field

圖3 完整代價字段示意圖Fig.3 Schematic diagram of integration cost field

流場字段存儲一個枚舉方向查找表的索引字段類型，智能體到達目標節(jié)點過程中經(jīng)過某一節(jié)點時的運動方向，一般會是枚舉類型，有東、西、南、北、東南、西南、東北、西北這八個枚舉值。如果檢測到到達方向的下一節(jié)點為障礙點，則跳過該節(jié)點，如圖4 所示，遇到障礙時不可跨越，所以只能向箭頭所指的六個方向移動。

圖4 流場字段示意圖Fig.4 Schematic diagram of flow field

2.2 算法基本思想

即時戰(zhàn)略游戲中一般將地圖劃分為多個正方形組成的規(guī)則網(wǎng)格，網(wǎng)格點看作節(jié)點，尋路在網(wǎng)格的基礎上進行搜索。流場尋路只需要計算一次地圖中所有節(jié)點的流場方向就可以不受智能體數(shù)量的限制進行移動。

算法的基本步驟如下：

1）初始化智能體和地圖，定義集合S，地圖中繪制網(wǎng)格、障礙和目標節(jié)點，集合S 用來存放已經(jīng)計算過但未確定流場方向的節(jié)點；

2）將目標節(jié)點v加入集合S，并賦值v的完整代價值為0；

3）從集合S中選取完整代價值最小的節(jié)點u；

4）記錄節(jié)點u，并將其從集合S中刪除；

5）計算更新節(jié)點u 的8 鄰域節(jié)點的完整代價值，并將未加入集合S的節(jié)點加入集合S；

6）根據(jù)完整代價值確定8鄰域節(jié)點流場字段值；

7）重復上述3）～6）過程，直至集合S為空。

通過循環(huán)得到集合S 中節(jié)點的鄰域節(jié)點的代價值，將代價值進行比較決定經(jīng)過節(jié)點后的下一節(jié)點是8 鄰域節(jié)點中的哪個節(jié)點，并進行標記，生成流場字段值，表明每個運動智能體經(jīng)過此節(jié)點時的流場方向。

以上就是流場尋路的數(shù)據(jù)結構和整個算法思想，雖然流場尋路算法解決了多智能體同時快速尋路的問題，讓RTS 游戲中的所有運動智能體看起來十分流暢和智能，但是，流場尋路算法仍有不足，如：算法運算過程中產(chǎn)生不必要的重復計算，數(shù)據(jù)沒有一個很好的排列方式和計算順序，計算地圖中代價值的方法和得到流場的方法比較復雜甚至需要計算非線性偏微分方程，本文就這些問題對流場尋路算法做了一定改進。

3 流場尋路算法的改進

3.1 數(shù)據(jù)存儲方式

2.2 節(jié)算法基本步驟中的3）、4）中，節(jié)點u 并非隨意選擇的節(jié)點，應選取在集合S 中完整代價值最小的節(jié)點，最簡單方法為遍歷整個集合并進行比較。但隨著地圖的增大，比較次數(shù)也會增多，并且比較次數(shù)與地圖增大次數(shù)呈正線性相關，其比例關系如圖5所示。

圖5 地圖節(jié)點數(shù)與比較次數(shù)的關系Fig.5 Relationship between number of map nodes and number of comparisons

如圖6 所示，采用紅黑樹方式進行節(jié)點的存儲，保證前序遍歷的第一個節(jié)點是完整代價值最小的節(jié)點，每次取最小元素進行循環(huán)即可。雖然這會造成排序插入的消耗，但是紅黑樹的查找、插入和刪除的時間復雜度均為O(log n)，因此在大地圖、多次進行比較的情況下對于算法優(yōu)化的效果十分明顯。

將OPEN表和CLOSE表引入算法中，OPEN表中存放將要計算的節(jié)點，初始只有目標節(jié)點，CLOSE表中存放已經(jīng)計算過并得到流場的節(jié)點，OPEN 表采用紅黑樹的方式進行存儲，按照完整代價值排列，前序遍歷為代價值最小的元素。

遍歷的基本過程為：取OPEN 表的代價值最小的元素節(jié)點，將其加入到CLOSE 表中，并檢查該節(jié)點的相鄰節(jié)點，其中相鄰節(jié)點分為三種：

1）如果該節(jié)點均不在OPEN 表和CLOSE 表中，將其加入到OPEN 表中，并對該節(jié)點的整合代價值和流場方向進行賦值；

2）如果該節(jié)點在CLOSE表中，新生成的整合代價值小于原來的值，則節(jié)點重新賦值；

3）如果該節(jié)點在CLOSE表中，新生成的整合代價值大于等于原來的值，不做任何操作。

如圖7 所示，深色圓點部分是已經(jīng)遍歷過CLOSE 表中的節(jié)點，淺灰色是OPEN 表中的節(jié)點，未標記部分則是還未遍歷過的節(jié)點。

圖6 紅黑樹結構Fig.6 Red-black tree structure

圖7 節(jié)點的遍歷過程Fig.7 Traversal process of nodes

3.2 利用懲罰函數(shù)優(yōu)化路徑代價計算

在Pentheny 提出的代價值的計算方式中，采用程函方程［28］進行計算，程函方程是一種非線性偏微分方程，以哈密頓-雅可比偏微分方程（Hamiltonian-Jacobi partial differential equation，HJ-PDE）［29］的形式進行定義，如式（1）所示：

其中：Ω 是Rn中的域，φ（x）是到源點的距離或者時間，f（x）是在Ω 中定義的正向速度函數(shù)。通常用n 元數(shù)組來定義節(jié)點，以二維節(jié)點x=(i，j)為例，本文算法定義直接連接兩個節(jié)點的線段作為邊，邊的長度沿對應的軸p(p ∈{x，y})來定義網(wǎng)格的長度hp，將相鄰鄰域節(jié)點定義為單邊相連的節(jié)點，如有節(jié)點y=(i+hx，j)，則是節(jié)點x=(i，j)在x 軸方向的相鄰鄰域節(jié)點。采用Godunov逆風離散化［30］對程函方程進行離散，在x方向的離散結果為g（x），如式（2）所示：

U(x)是節(jié)點x=(i，j)指向φ 方向的離散化近似值，是沿著p 方向U（x）相鄰兩個鄰域的最小U 值，(n)+=max(0，n)。由以上分析可知，基于密哈頓-雅可比的程函方程的約束條件為：，并得到坐標軸的每個方向都將影響整合代價值的計算結果。當n 取得更小值時，g(x)取值隨之減小，因此，在整合代價值計算過程中盡量避免方向的變化，對在x、y兩個方向發(fā)生變化的g(x)進行懲罰。

在計算完整代價值的時候需要重復計算，由于非線性偏微分方程的計算比較復雜，又有和(n)+=max(0，n)

根據(jù)實驗結果，選擇懲罰因子為10 對方向進行懲罰，保證對角線方向的代價值大于水平或豎直方向。

3.3 流場計算

流場尋路的基本算法中采用視線法預處理數(shù)據(jù)并進行整合代價值的計算，但是在“波”向前進行推動的時候，需要比較所有計算過的到達此節(jié)點的完整代價值，并保證值的最小唯一性，這就造成計算過程中節(jié)點信息存儲的增加。受文獻［31］啟發(fā)引入Dijkstra算法，采用廣度遍歷的方式反向進行計算，根據(jù)前置鄰接點和后置鄰接點解決多路徑的問題，使得計算過程中同時計算多條路徑，進而得到最優(yōu)解。

將目標節(jié)點看作是初始節(jié)點，在“波”向前推進的過程中，運用Dijkstra算法計算每個節(jié)點的前置鄰接點，這在流場中的方向將有前置鄰接點指向這個節(jié)點，具體實現(xiàn)過程為：兩個約束條件，將求解有約束的非線性規(guī)劃問題轉換為計算無約束極小值問題，根據(jù)問題實際情況采用懲罰函數(shù)進行計算，再進行整合代價值的計算。

將約束問題min g(x)，滿足限制ci(x)≥0，?x ∈I，轉化為無約束問題序列，如式（3）所示：

1） while（OPEN表不為空）

2） ｛

3） 取OPEN表代價值最小的節(jié)點；

4） 將節(jié)點刪除并插入到CLOSE表中；

5） 更新當前點周圍的節(jié)點到OPEN表；//周圍8鄰域的節(jié)點進行遍歷更新

6） 確定周圍節(jié)點的前置鄰接點是否為當前節(jié)點；

7） 確定周圍節(jié)點的流場方向；

8） ｝

將目標節(jié)點首先加入紅黑樹中，采用廣度優(yōu)先的搜索方式，將目標節(jié)點的相鄰節(jié)點全部加入到樹中，借助改進后的存儲方式，每次取完整代價值最小的點進行計算，計算后刪除當前節(jié)點，選取下一整合代價值最小的點，循環(huán)操作直到樹為空。

圖8 為截取部分所得完整代價數(shù)值表，左下角為目標節(jié)點（0，0）。生成流場結果如圖9所示。

完成流場計算后，智能體運動將不受數(shù)量限制，處于地圖中任意位置的智能體均可按照流場方向移動，且在大地圖中多智能體移動時更符合群體移動規(guī)律，智能體傾向于向地勢平緩更易到達目標點的空曠區(qū)域聚集移動。

本實驗從數(shù)據(jù)存儲方式、路徑代價計算方法和流場計算方式三個方面改進了流場尋路算法。改進后的流場尋路算法在數(shù)據(jù)讀取方面更具有優(yōu)勢，并且簡化了算法的計算步驟，不再需要計算視線后再得到整合代價值才能計算出流場方向，可通過直接計算整合代價值得到前置鄰接點的方式得到流場方向。本文采用的方式簡化了算法的實現(xiàn)過程，提高了路徑的計算速度，從整體上優(yōu)化算法。

圖8 節(jié)點的完整代價值Fig.8 Integration cost value of node

圖9 流場結果圖Fig.9 Result diagram of flow field

4 實驗結果與分析

仿真實驗在Visual Studio 2017 平臺下使用OpenGL 實現(xiàn)算法可視化，對不同數(shù)量的智能體，對不同算法生成路徑和完成移動的時間進行比較。實驗結果表明，流場尋路在即時戰(zhàn)略游戲中的作用十分顯著，使大量移動智能體在更短的時間內(nèi)到達同一目的地。

實驗中分別比較了Dijkstra 算法、A*算法、人工勢場法、流場尋路和改進后的流場尋路算法中移動智能體數(shù)量為1、10、20、50、100和200情況下的尋路時間和完成移動時間。實驗數(shù)據(jù)證明，當移動數(shù)量越多時，采用流場尋路算法更具有優(yōu)勢，能在相同時間內(nèi)無數(shù)量限制進行尋路。

表1 為不同算法不同數(shù)量智能體計算路徑所需要的時間，而表2 為不同算法下不同數(shù)量智能體完成移動所需時間。結合表1、2 中的數(shù)據(jù)可以說明，流場尋路算法在大型地圖的多次尋路中具有優(yōu)勢，并在障礙較多、地形復雜的地圖中也可以快速尋路，具有較好的穩(wěn)定性。

表1 不同算法的平均尋路時間 單位：sTab.1 Average pathfinding times of different algorithms unit：s

通過表1、2 也可以看出，隨著移動智能體數(shù)量增多，傳統(tǒng)算法的所用時間約為數(shù)量的倍數(shù)，而流場尋路算法不會隨著數(shù)量的增多而增加尋路時間和運動時間，是一個在一定數(shù)值范圍內(nèi)的穩(wěn)定值，尋路時間約為0.4 s，移動時間約為20 s。因為地圖中有x×y個節(jié)點，類比于n個節(jié)點中的Dijkstra 算法時間復雜度為O（n2），則本文中的Dijkstra 算法時間復雜度為O((m×n)2)；又因為智能體的數(shù)量為MOVE_OBJECT_NUM（以u來代替），需執(zhí)行u次Dijkstra算法，可以得到整個結果的時間復雜度為O(u×(m×n)2)；如果使用流場尋路的話，則只需計算一次算法，為O((m×n)2)。

表2 不同算法的平均移動時間 單位：sTab.2 Average moving times of different algorithms unit：s

5 結語

大量游戲［32］如早期的沙丘、紅警再到星際、魔獸以及現(xiàn)在的帝國時代、最高指揮官等都需要解決類似多智能體移動的問題，本文提出了流場尋路算法，并對其在數(shù)據(jù)存儲方式、整合代價值計算方式和流場生成方式進行組合式改進，提高了流場尋路的計算速度和智能體的移動效率，也提高了游戲的智能水平，使得數(shù)以萬計的智能體也可在大型地圖上同時并發(fā)尋路，增加了該類游戲的可玩性和真實性，進一步優(yōu)化了游戲體驗。

本文主要集中在改進算法本身并實現(xiàn)，該算法還可實現(xiàn)多目標點的流場計算，也可用圖形處理器（Graphics Processing Unit，GPU）代替中央處理器（Central Processing Unit，CPU）進行計算。對于移動中躲避障礙物、墻壁和其他智能體等問題，后續(xù)將進行深入研究。