李 恬，張樹美，趙俊莉

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

0 引言

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

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

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

1 問題描述

1.1 RTS游戲中的尋路問題

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

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

1.2 常見尋路算法局限性

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

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

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

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

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

2 流場(chǎng)尋路算法

2.1 基本數(shù)據(jù)結(jié)構(gòu)

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

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

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

圖2 代價(jià)字段示意圖Fig.2 Schematic diagram of cost field

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

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

圖4 流場(chǎng)字段示意圖Fig.4 Schematic diagram of flow field

2.2 算法基本思想

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

算法的基本步驟如下：

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

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

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

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

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

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

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

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

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

3 流場(chǎng)尋路算法的改進(jìn)

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

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

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

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

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

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

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

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

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

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

圖6 紅黑樹結(jié)構(gòu)Fig.6 Red-black tree structure

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

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

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

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

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

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

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

3.3 流場(chǎng)計(jì)算

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

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

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

1） while（OPEN表不為空）

2） ｛

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

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

5） 更新當(dāng)前點(diǎn)周圍的節(jié)點(diǎn)到OPEN表；//周圍8鄰域的節(jié)點(diǎn)進(jìn)行遍歷更新

6） 確定周圍節(jié)點(diǎn)的前置鄰接點(diǎn)是否為當(dāng)前節(jié)點(diǎn)；

7） 確定周圍節(jié)點(diǎn)的流場(chǎng)方向；

8） ｝

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

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

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

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

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

圖9 流場(chǎng)結(jié)果圖Fig.9 Result diagram of flow field

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

表2 不同算法的平均移動(dòng)時(shí)間 單位：sTab.2 Average moving times of different algorithms unit：s

5 結(jié)語

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

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