吳婷婷,吳 琳,沈弼龍

(國防大學(xué),北京 100091)

兵棋作為研究戰(zhàn)爭的重要工具之一,其基本的組成要素為棋盤、棋子和規(guī)則[1]。戰(zhàn)場環(huán)境的模擬體現(xiàn)在棋盤建模中,棋盤在兵棋中的作用主要體現(xiàn)在兩個方面:一是展現(xiàn)戰(zhàn)場環(huán)境的態(tài)勢,為指揮人員的正確決策提供戰(zhàn)場環(huán)境信息;二是提供模型計算所需要的環(huán)境數(shù)據(jù)信息[2]。在計算機兵棋中,棋盤的建模不僅需要有較好的可視化效果,還需要對環(huán)境中的信息進行量化、特征提取,形成計算機能識別的數(shù)據(jù)信息。隨著科學(xué)技術(shù)的發(fā)展,戰(zhàn)爭形態(tài)和戰(zhàn)爭樣式發(fā)生了巨大的變化,戰(zhàn)爭不僅受制于有形的自然地理環(huán)境,還受到無形的網(wǎng)絡(luò)、電磁等環(huán)境的制約,武器射程的增加以及戰(zhàn)略支援能力的提升使得戰(zhàn)場空間范圍越來越大。傳統(tǒng)的兵棋棋盤多數(shù)針對特定區(qū)域的環(huán)境進行建模,空間范圍有限,分辨率大小固定。不斷擴大的戰(zhàn)場空間范圍和愈加復(fù)雜的戰(zhàn)場環(huán)境,對兵棋系統(tǒng)的環(huán)境建模提出了全球性、多尺度等新要求。針對以上問題,本文介紹了一種全球離散網(wǎng)格系統(tǒng)——六邊形分層空間索引(Hexagonal Hierarchical Spatial Index,H3空間索引)[3],將其作為戰(zhàn)場環(huán)境建模的基本架構(gòu),設(shè)計數(shù)據(jù)結(jié)構(gòu)存儲環(huán)境屬性,并通過仿真實驗分析了棋子尋路行為在H3空間索引的性能,驗證了其用于兵棋系統(tǒng)環(huán)境建模的可行性。

1 兵棋棋盤的量化建模方法

兵棋棋盤提供戰(zhàn)場環(huán)境信息,棋子空間位置信息和系統(tǒng)中模型計算所需的數(shù)據(jù)信息。如圖1所示,指揮人員通過棋盤展現(xiàn)的態(tài)勢下達作戰(zhàn)命令,計算機根據(jù)棋盤中獲取的信息進行模型計算,計算完成后將信息推送至棋盤上形成可視化的戰(zhàn)場態(tài)勢信息。地理信息數(shù)據(jù)的使用需進行轉(zhuǎn)換后方可為棋盤計算所使用。通常采用柵格化的方法對地圖進行量化建模,用于柵格化的圖形主要有正三角形、正方形和正六邊形,只有這三種圖形滿足平面上無重疊和無遺漏的拼接[4]。正三角形在量化建模中使用較少,對于正方形和正六邊形,在很多游戲地圖量化建模中均有采用,這兩種圖形在對地圖進行柵格化時有著不同的優(yōu)缺點,表1為兩種圖形進行量化時的優(yōu)缺點比較。

圖1 兵棋推演人機交互過程

構(gòu)建全球離散網(wǎng)格系統(tǒng),同樣需要根據(jù)不同圖形柵格化的優(yōu)缺點,針對需求,選擇合適的圖形進行剖分。基于地理坐標系剖分的全球離散網(wǎng)格可看作使用正方形進行剖分,基于多面體剖分的離散網(wǎng)格系統(tǒng)需要將多面體面片進一步剖分,剖分時根據(jù)面片選擇圖形。正二十面體、正十二面體和正八面體投影變形小,其面片均為三角形,因此無法采用正方形進一步劃分,又因為在三角形和六邊形劃分中,六邊形的優(yōu)點更多而使用較為廣泛。已有較多研究人員對全球網(wǎng)格索引系統(tǒng)進行研究。如童曉沖等人[8]在正多面體剖分的基礎(chǔ)上提出了新的全球網(wǎng)格六邊形索引結(jié)構(gòu),韓陽等人[9]在地理坐標系基礎(chǔ)上提出將全球劃分成不同面片的混合式網(wǎng)格劃分方法等。不同的離散網(wǎng)格系統(tǒng)采用四邊形或六邊形進行劃分,可在使用時根據(jù)用途進行選擇,見表1。

表1 不同圖形柵格化的優(yōu)缺點

真實戰(zhàn)場環(huán)境復(fù)雜多變,既不可能也沒有必要將所有的環(huán)境信息建模到棋盤中。在建模過程中要把握對作戰(zhàn)行動起著關(guān)鍵作用的環(huán)境信息[10],如高程、地貌類型、坡度等。環(huán)境特征的提取相當于二次建模[11],是將地圖上的特征屬性映射到格元的邊、點、面上,采用合適的數(shù)據(jù)結(jié)構(gòu)對屬性進行存儲,方便計算機讀取。如地形地貌可以存儲為格元的面屬性;河流、隧道等條狀類的屬性可作為格元的邊屬性進行存儲[12-13]。

不同的格元因其邊、頂點的數(shù)量不同,編碼方式有所不同。如圖2所示,六邊形在網(wǎng)格中,因為鄰近格元的共享關(guān)系,六邊形中一個點由三個面共享,一個六邊形內(nèi)有六個點,一條邊由兩個面共享,一個六邊形有六條邊,平攤后,單個六邊形有兩個頂點、三條邊、一個面,可通過坐標編碼唯一標識[14]。在網(wǎng)格(2,2)中,分別對網(wǎng)格的左右頂點編碼為(2,2,L)和(2,2,R),網(wǎng)格(2,2)的三條邊編碼為(2,2,W)、(2,2,N)和(2,2,E)。

圖2 六邊形編碼

在提取環(huán)境屬性過程中,特征屬性的分類應(yīng)該適當,地形類型的劃分不應(yīng)過多,通常選取5～25種類型,分類過繁則計算復(fù)雜,容易偏離研究重點;分類過于粗糙則難以有效反映作戰(zhàn)行動[15]。最終的地形類型數(shù)量要以模擬的戰(zhàn)爭層次和需要進行確定。針對六邊形環(huán)境屬性的提取方法較多,張錦明[16]在其文中提到可根據(jù)地理數(shù)據(jù)在六邊形的壓蓋面積,利用“面積占優(yōu)法”、“長度占優(yōu)法”、“中心歸屬法”等方法對格網(wǎng)的屬性進行確定,并提出一種可以簡化壓蓋面積比的計算方法,采用柵格矩陣算法來提高地圖處理的效率;繆坤等人[17]則將產(chǎn)生式規(guī)則引入到六邊形的地形量化過程中,其制定了地形的量化規(guī)則,使六邊形在建模過程中自動生成格元屬性;張瀚等人[18]則針對地理信息中的弧段提出串序匹配擬合方法,使各弧段的關(guān)系能夠在進行擬合后保持原有關(guān)系,并通過實驗驗證了效率。由此可見,在兵棋棋盤的建模中需要采用合適的圖形對地圖進行柵格化,對格元編碼建立起高效的索引結(jié)構(gòu),并通過索引存儲環(huán)境信息,使得棋盤信息既可為人所讀,又可為計算機所讀。上述的全球離散網(wǎng)格系統(tǒng)研究方法和環(huán)境建模方法為兵棋棋盤建模提供了借鑒。2018年,Uber公司開源公布了其應(yīng)用于出行業(yè)務(wù)的H3空間索引。H3空間索引封裝了眾多接口,調(diào)用方便,為兵棋棋盤建模研究又提供了一個全新的平臺。

2 H3空間索引的介紹

全球戰(zhàn)場環(huán)境的量化建模需要對地球球面進行柵格化,Uber公司開發(fā)的H3空間索引[3]對全球空間進行剖分,可滿足兵棋棋盤戰(zhàn)場環(huán)境量化建模的需求,為下一步進行全球戰(zhàn)場環(huán)境建模提供了基礎(chǔ)和解決方案。其用于兵棋棋盤建模存在以下幾個優(yōu)點。

2.1 全球范圍的網(wǎng)格剖分

戰(zhàn)爭涉及的區(qū)域越來越廣,陸海空天電網(wǎng)多維戰(zhàn)場空間的拓展、武器裝備的升級改造、遠距離投送和支援能力的提高使得現(xiàn)代化戰(zhàn)爭并不局限于某一區(qū)域,戰(zhàn)爭模擬也需要緊貼實際情況,建立起廣闊的戰(zhàn)場環(huán)境模型,為認識和研究現(xiàn)代化戰(zhàn)爭,推演信息化條件下的聯(lián)合戰(zhàn)爭創(chuàng)設(shè)技術(shù)條件。一個全球化的戰(zhàn)場環(huán)境則可以很好地滿足推演需求。H3空間索引對全球進行網(wǎng)格剖分和編碼,可根據(jù)經(jīng)緯度快速定位至網(wǎng)格。利用H3空間索引構(gòu)建全球戰(zhàn)場可為不同類型的推演提供基礎(chǔ)條件。針對不同推演目的,在模擬的戰(zhàn)場環(huán)境范圍改變時無須對環(huán)境重新建模,使兵棋能夠更好地滿足各種不同類型的推演。兵棋除了提供訓(xùn)練功能,還可在教學(xué)中發(fā)揮重要作用,通過對經(jīng)典戰(zhàn)例的回顧與重現(xiàn),分析和總結(jié)戰(zhàn)爭經(jīng)驗,這同樣需要有一個廣闊通用的模擬戰(zhàn)場環(huán)境作為戰(zhàn)例推演分析的基礎(chǔ)。

2.2 多分辨率六邊形剖分

兵棋中棋子的機動、部署、作戰(zhàn)等一系列活動都是基于棋盤網(wǎng)格進行計算的,因此對空間劃分時采用的網(wǎng)格類型對系統(tǒng)仿真有著重要影響?，F(xiàn)實中的地面機動方向應(yīng)是360°的[19-20],在建模過程中模擬方向越多,模擬機動的效果越逼真。H3空間索引在網(wǎng)格劃分時采用的圖形為六邊形,與大多數(shù)兵棋系統(tǒng)進行網(wǎng)格劃分采用的圖形一致。在此基礎(chǔ)上,已有一些基于六邊形網(wǎng)格的建模方法研究,能夠為戰(zhàn)場環(huán)境建模提供借鑒。分辨率的高低決定著空間柵格化后格元數(shù)量的多少。分辨率越高環(huán)境信息表示越精細,分辨率越低環(huán)境信息表示越概略。對連續(xù)空間柵格化可使計算機處理數(shù)據(jù)信息更為簡便,但格元的數(shù)量影響著系統(tǒng)的整體響應(yīng)速度。分辨率過高,空間格點數(shù)量較多導(dǎo)致空間存儲量劇增,給計算機的計算能力帶來很大的挑戰(zhàn);分辨率過低,戰(zhàn)場環(huán)境模擬不真實,推演過于粗略,難以反映作戰(zhàn)中存在的問題。如表2所示,H3空間索引設(shè)置了0～15共16個層級,每個層級用以剖分的六邊形數(shù)量不同,級別越高,六邊形表示的實際范圍越小,可進行更精細的建模。兵棋中的棋盤需根據(jù)模擬的戰(zhàn)爭行動來確定比例尺大小,戰(zhàn)略戰(zhàn)役級兵棋推演中棋盤表示較為概略,而戰(zhàn)術(shù)層級兵棋推演中的棋盤則更為詳盡[19]。采用H3空間索引可根據(jù)推演的規(guī)模選擇合適的層級使用,甚至在推演過程中可以進行層級的切換以滿足不同級別的部隊作戰(zhàn)推演需求。相比于針對不同推演方案構(gòu)建不同精度戰(zhàn)場環(huán)境模型的方法,H3空間索引提供了極大的便利。如圖3所示,六邊形分別采用孔徑為3、4、7[3,21]的方式進行細分,H3空間索引采用圖中孔徑為7的劃分方式對層級進行細分。

圖3 六邊形多分辨率劃分

表2 H3網(wǎng)格各層級六邊形平均邊長[22]

2.3 投影變形小

傳統(tǒng)的經(jīng)緯度網(wǎng)格劃分符合人們的認知習(xí)慣,但是基于經(jīng)緯度劃分的網(wǎng)格隨著緯度的升高變形逐漸增大,在兩極地區(qū)甚至退化成三角形?；诙嗝骟w的投影方式將多面體投射到地球表面,可以用來構(gòu)建全球網(wǎng)格的有正六面體、正十二面體和正二十面體等,多面體面數(shù)越多,越接近球體,投影的誤差也就越小[23]。如圖4所示,H3空間索引采用去頂?shù)恼骟w進行投影,正二十面體接近球體,投影克服了基于經(jīng)緯網(wǎng)劃分時兩極的非均勻性,各個區(qū)域的網(wǎng)格大小一致[6]。盡管其存在12個五邊形,造成了網(wǎng)格劃分的不一致性,但是其在定位時將五邊形放置在海面上,五邊形的面積隨著層級的升高變小,可在精度允許的范圍內(nèi)忽略其影響。

圖4 H3空間索引投影

2.4 編碼方式簡單

在H3空間索引中,其邊、點、面(網(wǎng)格索引)均采用64位的編碼模式進行編碼,可以從編碼中方便地獲取編碼模式、所處層級等信息,其中網(wǎng)格編碼如表3所示,橫向表示位數(shù),網(wǎng)格編碼使用的位數(shù)計算如公式(1)所示:

網(wǎng)格編碼位數(shù)=縱軸數(shù)×16+橫軸數(shù)

(1)

第1位保留為0;第2～5位共四位表示索引模式,模式1表示網(wǎng)格編碼,模式2表示單向邊的編碼,模式3將作為雙向邊的編碼,模式4為網(wǎng)格頂點編碼,在網(wǎng)格編碼中,其表示為0001。在建模過程中進行索引操作時主要用到網(wǎng)格索引,網(wǎng)格索引第6～8位設(shè)置為0;第9～12位表示當前H3空間索引層級,有0～15個層級,如第五層級編碼,表示為0101;第13～19位表示當前網(wǎng)格所在的基網(wǎng)格編碼,如圖5,正二十面體有二十個面,每個面有5.5個六邊形,再加上12個五邊形,共122個基網(wǎng)格;基網(wǎng)格所在層級為第0層,第1～15層每層用3位表示網(wǎng)格在該層級的編碼,六邊形采用孔徑為7的剖分方式進行多層級劃分,H3空間索引在每個六邊形面上建立一個IJK坐標,坐標編碼如圖6所示,分別用0～6表示7個子六邊形;高于當前網(wǎng)格編碼層級的網(wǎng)格編碼,在其余高層級未使用的剩余位數(shù)均賦為1。

表3 H3網(wǎng)格編碼[24]

圖5 H3空間索引基網(wǎng)格劃分[3]

圖6 IJK坐標編碼[25]

3 基于H3空間索引建模示例

3.1 基于H3空間索引的建?？蚣?/h3>

H3空間索引提供了一個全球范圍的六邊形索引,如圖7所示,本章設(shè)置數(shù)據(jù)結(jié)構(gòu)與H3空間索引相結(jié)合,環(huán)境矢量數(shù)據(jù)處理后,將六邊形的邊屬性和面屬性進行映射存儲,在環(huán)境建模基礎(chǔ)之上,以A*算法[26]為例對棋子機動進行尋路建模,展現(xiàn)尋路結(jié)果。

圖7 基于H3空間索引的建?？蚣?/p>

3.2 兵棋棋盤建模示例

棋盤承載的環(huán)境信息對作戰(zhàn)模擬起著重要作用。本節(jié)選擇H3空間索引的第五層級進行棋盤建模,其六邊形網(wǎng)格的邊長約為8.54 km,平均面積約為252.9 km。對自然環(huán)境屬性進行建模,設(shè)計數(shù)據(jù)結(jié)構(gòu)存儲網(wǎng)格數(shù)據(jù),為兵棋推演過程中的模型計算提供環(huán)境數(shù)據(jù)信息。

兵棋棋盤建模關(guān)鍵是將地理環(huán)境、氣象環(huán)境、電磁環(huán)境等影響作戰(zhàn)的屬性存儲在對應(yīng)的網(wǎng)格中,地理環(huán)境主要有地形地貌、障礙物等,氣象環(huán)境如雨雪天氣會對行軍造成影響,潮汐變化會對登陸作戰(zhàn)造成影響,在電磁環(huán)境中飛機等武器裝備產(chǎn)生的雷達信號等會形成電磁干擾,影響通信、目標探測等活動。系統(tǒng)運行過程中通過網(wǎng)格索引高效地獲取數(shù)據(jù)信息,從而進行模型計算。建模過程中目前只考慮地理環(huán)境,首先對環(huán)境類型進行分類,如提取面屬性需要對地形進行分類,分為山地、開闊地、湖泊等,建立起地形對照表,如表4所示,建模的數(shù)據(jù)值應(yīng)與表4對應(yīng)。

表4 面屬性對照表

建立起屬性對照表后對矢量數(shù)據(jù)進行讀取和處理,通過一定規(guī)則進行判定,如:六邊形內(nèi)面積占比第一的地貌類型定為面屬性。屬性特征提取后便可存入相應(yīng)數(shù)據(jù)結(jié)構(gòu)中為計算機讀取。建?？梢暬Ч鐖D8所示,對不同的屬性采用不同的顏色進行標記,如面屬性中湖泊用藍色進行標記,開闊地用灰色標記,草地、森林用綠色標記;邊屬性用紅色標記障礙物,表示此邊不可通行。不同的顏色信息以及經(jīng)緯度查詢功能,如圖9所示,可幫助指揮人員快速獲取棋盤信息,提高推演效率[2]。

圖8 棋盤環(huán)境建模

圖9 經(jīng)緯度信息查詢

3.3 棋子機動尋路示例

兵棋中棋子的機動行為涉及海、陸、空三域,其中陸上機動規(guī)則最為復(fù)雜。在本節(jié)建模中,考慮影響機動的地形因素和障礙因素。如圖10的棋子所示:六邊形的六個等距方向為其機動方向,在棋子選擇機動路徑時,首先需考慮是否有障礙因素阻礙棋子機動,紅線代表障礙因素,棋子不可通過此方向到下一個網(wǎng)格中去;其次,棋子機動還將考慮其是否能在下一網(wǎng)格的地形上通行。在完成對環(huán)境屬性特征的提取后,網(wǎng)格中已經(jīng)含有機動計算的屬性,尋路計算在已建模好的棋盤中進行。

實驗采用A*算法對棋子在棋盤中的尋路過程進行模擬,棋子在機動過程中讀取棋盤網(wǎng)格中存儲的環(huán)境信息,首先判斷是否為障礙邊,再判斷通過此邊到達的鄰接網(wǎng)格中的地形類型是否可通行。六邊形中存儲的環(huán)境屬性對棋子的機動有著重要影響,它決定著棋子在機動過程的機動方向、能否到達目的地等。

圖10 棋子機動方向選擇

棋子機動時在算法中加入了對地形的判斷和障礙邊的判斷,因此,棋子在尋路過程中的路線為避開障礙和不可通過地形的最短路。輸入不同的起始坐標和終點坐標,可以得到尋路結(jié)果。如圖11所示,起始點S和終點D間最短距離應(yīng)是二者間虛線距離,但在尋路過程中,六邊形中的環(huán)境屬性影響路徑選擇,障礙邊和湖泊地形不可通過,最終路徑如圖11黑色線段所示。

圖11 尋路結(jié)果

4 實驗分析

4.1 實驗環(huán)境與數(shù)據(jù)

硬件環(huán)境:Intel i5處理器, 16 G內(nèi)存。

軟件環(huán)境:Windows 10 64位操作系統(tǒng)。

開發(fā)環(huán)境:Python版本為3.7.9[27]。

地圖數(shù)據(jù):地圖數(shù)據(jù)源采用高德地圖,選取區(qū)域進行實驗的范圍為70°E～120°E,20°N～50°N。

H3空間索引層級:使用層級為第四、五、六層級。

4.2 實驗結(jié)果

兵棋在運行過程中從棋盤讀取數(shù)據(jù)需要考慮其獲取棋盤信息的效率。棋盤的量化建模過程涉及六邊形的編碼方式,傳統(tǒng)兵棋棋盤的六邊形建模通常采用圖2所示的編碼方式,而H3空間索引則采用表3所示的64位的編碼方式。本節(jié)用棋子機動對六邊形的兩種不同的編碼方式進行實驗,測試兩種編碼方式在相同實驗條件下的吞吐量。

棋子機動時路徑搜索的效率與其通過索引獲取數(shù)據(jù)信息的速度和搜索的空間狀態(tài)的數(shù)量有關(guān)。實驗在兩種不同的編碼方式上分別隨機產(chǎn)生200和800個障礙,通過六邊形的邊屬性進行存儲。傳統(tǒng)棋盤編碼的六邊形數(shù)量根據(jù)H3空間索引選取的特定區(qū)域在第四、五、六層級上填充的六邊形數(shù)量確定,以保證搜索空間的大小相同。實驗中路徑長度表示路徑搜索經(jīng)過的格元數(shù)量,記為lpath,路徑搜索的時間記為ti,假設(shè)路徑長度在區(qū)間[a,b]內(nèi)的路徑數(shù)量有m條,則區(qū)間[a,b]內(nèi)棋子機動行為系統(tǒng)的吞吐量為

(2)

在每種條件下進行200次尋路,通過公式(2)計算尋路的吞吐量。實驗結(jié)果如下圖所示,圖12、圖13、圖14分別表示在傳統(tǒng)編碼方式與H3空間索引編碼方式下,棋子機動行為在不同障礙邊數(shù)量和不同數(shù)量的狀態(tài)空間中進行尋路的吞吐量。

圖12 不同編碼方式和障礙數(shù)量下的棋子機動吞吐量實驗結(jié)果a)

圖13 不同編碼方式和障礙數(shù)量下的棋子機動吞吐量實驗結(jié)果b)

圖14 不同編碼方式和障礙數(shù)量下的棋子機動吞吐量實驗結(jié)果c)

由上圖實驗結(jié)果可知,棋子機動的尋路過程中,隨機產(chǎn)生的障礙邊對棋子的尋路效率并沒有太大的影響,原因是隨機產(chǎn)生的障礙邊大片連接形成“死胡同”的概率較小,A*算法尋路較少進行迂回擴展,因此在隨機生成障礙邊的數(shù)量不足以形成大片“死胡同”的情況下,障礙對棋子機動效率的影響不大。

4.3 實驗小結(jié)

從單個實驗結(jié)果圖和多個實驗結(jié)果圖進行對比可發(fā)現(xiàn),采用A*算法進行尋路時,路徑長度的增加使得搜索的狀態(tài)空間數(shù)量增加,棋子機動的吞吐量減小。除此之外,在路徑長度較短時,傳統(tǒng)的網(wǎng)格編碼方式比H3空間索引編碼方式的吞吐量更大,隨著路徑長度的增加,兩種網(wǎng)格編碼方式的吞吐量差距逐漸縮小,到最后幾乎持平,從這點看,使用H3空間索引建立全球戰(zhàn)場環(huán)境對系統(tǒng)整體的響應(yīng)速度與傳統(tǒng)編碼方式相比差別不大。盡管傳統(tǒng)的網(wǎng)格編碼方式在路徑長度較短時占據(jù)優(yōu)勢,但路徑長度較短時系統(tǒng)的響應(yīng)速度快,兩種編碼方式效率的高低在運行過程中對系統(tǒng)和用戶而言并不會帶來太大的影響;在搜索空間逐漸增大時,因搜索空間數(shù)量的增加帶來的效率問題成為影響系統(tǒng)效率的關(guān)鍵。因此,要使用H3空間索引進行棋盤建模,還需進一步優(yōu)化模型算法,使兵棋系統(tǒng)在其架構(gòu)下能高效進行推演。

5 結(jié)束語

兵棋是創(chuàng)新作戰(zhàn)理論,制定作戰(zhàn)方案和研究戰(zhàn)爭的重要工具。隨著戰(zhàn)場空間的拓展,需提供全球戰(zhàn)場空間的支撐,H3空間索引為全球戰(zhàn)場空間的構(gòu)建提供了基礎(chǔ)框架。本文在H3空間索引的基礎(chǔ)上進行自然環(huán)境的建模,利用其索引建立數(shù)據(jù)結(jié)構(gòu)存儲環(huán)境屬性,并對棋子在棋盤的尋路過程進行模擬,研究尋路效率,探究利用H3空間索引對全球戰(zhàn)場環(huán)境建模的可行性。兵棋推演過程中,棋盤環(huán)境與棋子間的交互頻繁,要使用H3空間索引構(gòu)建戰(zhàn)場環(huán)境,還需要探索更高效的建模方法,進一步提高兵棋推演的效率和準確性。