即時戰略游戲的智能流場尋路算法設計與實現

李 恬，張樹美，趙俊莉

（青島大學數據科學與軟件工程學院，山東青島266071）

0 引言

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

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

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

1 問題描述

1.1 RTS游戲中的尋路問題

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

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

1.2 常見尋路算法局限性

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

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

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

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

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

2 流場尋路算法

2.1 基本數據結構

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

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

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

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

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

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

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

2.2 算法基本思想

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

算法的基本步驟如下：

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

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

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

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

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

6）根據完整代價值確定8鄰域節點流場字段值；

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

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

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

3 流場尋路算法的改進

3.1 數據存儲方式

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

圖5 地圖節點數與比較次數的關系Fig.5 Relationship between number of map nodes and number of comparisons

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

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

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

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

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

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

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

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

圖7 節點的遍歷過程Fig.7 Traversal process of nodes

3.2 利用懲罰函數優化路徑代價計算

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

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

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

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

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

3.3 流場計算

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

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

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

1） while（OPEN表不為空）

2） ｛

3） 取OPEN表代價值最小的節點；

4） 將節點刪除并插入到CLOSE表中；

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

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

7） 確定周圍節點的流場方向；

8） ｝

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

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

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

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

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

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

4 實驗結果與分析

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

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

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

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

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

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

5 結語

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

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