基于H3空间索引的兵棋战场环境建模与应用探析

吴婷婷,吴 琳,沈弼龙

(国防大学,北京 100091)

兵棋作为研究战争的重要工具之一,其基本的组成要素为棋盘、棋子和规则[1]。战场环境的模拟体现在棋盘建模中,棋盘在兵棋中的作用主要体现在两个方面:一是展现战场环境的态势,为指挥人员的正确决策提供战场环境信息;二是提供模型计算所需要的环境数据信息[2]。在计算机兵棋中,棋盘的建模不仅需要有较好的可视化效果,还需要对环境中的信息进行量化、特征提取,形成计算机能识别的数据信息。随着科学技术的发展,战争形态和战争样式发生了巨大的变化,战争不仅受制于有形的自然地理环境,还受到无形的网络、电磁等环境的制约,武器射程的增加以及战略支援能力的提升使得战场空间范围越来越大。传统的兵棋棋盘多数针对特定区域的环境进行建模,空间范围有限,分辨率大小固定。不断扩大的战场空间范围和愈加复杂的战场环境,对兵棋系统的环境建模提出了全球性、多尺度等新要求。针对以上问题,本文介绍了一种全球离散网格系统——六边形分层空间索引(Hexagonal Hierarchical Spatial Index,H3空间索引)[3],将其作为战场环境建模的基本架构,设计数据结构存储环境属性,并通过仿真实验分析了棋子寻路行为在H3空间索引的性能,验证了其用于兵棋系统环境建模的可行性。

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

兵棋棋盘提供战场环境信息,棋子空间位置信息和系统中模型计算所需的数据信息。如图1所示,指挥人员通过棋盘展现的态势下达作战命令,计算机根据棋盘中获取的信息进行模型计算,计算完成后将信息推送至棋盘上形成可视化的战场态势信息。地理信息数据的使用需进行转换后方可为棋盘计算所使用。通常采用栅格化的方法对地图进行量化建模,用于栅格化的图形主要有正三角形、正方形和正六边形,只有这三种图形满足平面上无重叠和无遗漏的拼接[4]。正三角形在量化建模中使用较少,对于正方形和正六边形,在很多游戏地图量化建模中均有采用,这两种图形在对地图进行栅格化时有着不同的优缺点,表1为两种图形进行量化时的优缺点比较。

图1 兵棋推演人机交互过程

构建全球离散网格系统,同样需要根据不同图形栅格化的优缺点,针对需求,选择合适的图形进行剖分。基于地理坐标系剖分的全球离散网格可看作使用正方形进行剖分,基于多面体剖分的离散网格系统需要将多面体面片进一步剖分,剖分时根据面片选择图形。正二十面体、正十二面体和正八面体投影变形小,其面片均为三角形,因此无法采用正方形进一步划分,又因为在三角形和六边形划分中,六边形的优点更多而使用较为广泛。已有较多研究人员对全球网格索引系统进行研究。如童晓冲等人[8]在正多面体剖分的基础上提出了新的全球网格六边形索引结构,韩阳等人[9]在地理坐标系基础上提出将全球划分成不同面片的混合式网格划分方法等。不同的离散网格系统采用四边形或六边形进行划分,可在使用时根据用途进行选择,见表1。

表1 不同图形栅格化的优缺点

真实战场环境复杂多变,既不可能也没有必要将所有的环境信息建模到棋盘中。在建模过程中要把握对作战行动起着关键作用的环境信息[10],如高程、地貌类型、坡度等。环境特征的提取相当于二次建模[11],是将地图上的特征属性映射到格元的边、点、面上,采用合适的数据结构对属性进行存储,方便计算机读取。如地形地貌可以存储为格元的面属性;河流、隧道等条状类的属性可作为格元的边属性进行存储[12-13]。

不同的格元因其边、顶点的数量不同,编码方式有所不同。如图2所示,六边形在网格中,因为邻近格元的共享关系,六边形中一个点由三个面共享,一个六边形内有六个点,一条边由两个面共享,一个六边形有六条边,平摊后,单个六边形有两个顶点、三条边、一个面,可通过坐标编码唯一标识[14]。在网格(2,2)中,分别对网格的左右顶点编码为(2,2,L)和(2,2,R),网格(2,2)的三条边编码为(2,2,W)、(2,2,N)和(2,2,E)。

图2 六边形编码

在提取环境属性过程中,特征属性的分类应该适当,地形类型的划分不应过多,通常选取5～25种类型,分类过繁则计算复杂,容易偏离研究重点;分类过于粗糙则难以有效反映作战行动[15]。最终的地形类型数量要以模拟的战争层次和需要进行确定。针对六边形环境属性的提取方法较多,张锦明[16]在其文中提到可根据地理数据在六边形的压盖面积,利用“面积占优法”、“长度占优法”、“中心归属法”等方法对格网的属性进行确定,并提出一种可以简化压盖面积比的计算方法,采用栅格矩阵算法来提高地图处理的效率;缪坤等人[17]则将产生式规则引入到六边形的地形量化过程中,其制定了地形的量化规则,使六边形在建模过程中自动生成格元属性;张瀚等人[18]则针对地理信息中的弧段提出串序匹配拟合方法,使各弧段的关系能够在进行拟合后保持原有关系,并通过实验验证了效率。由此可见,在兵棋棋盘的建模中需要采用合适的图形对地图进行栅格化,对格元编码建立起高效的索引结构,并通过索引存储环境信息,使得棋盘信息既可为人所读,又可为计算机所读。上述的全球离散网格系统研究方法和环境建模方法为兵棋棋盘建模提供了借鉴。2018年,Uber公司开源公布了其应用于出行业务的H3空间索引。H3空间索引封装了众多接口,调用方便,为兵棋棋盘建模研究又提供了一个全新的平台。

2 H3空间索引的介绍

全球战场环境的量化建模需要对地球球面进行栅格化,Uber公司开发的H3空间索引[3]对全球空间进行剖分,可满足兵棋棋盘战场环境量化建模的需求,为下一步进行全球战场环境建模提供了基础和解决方案。其用于兵棋棋盘建模存在以下几个优点。

2.1 全球范围的网格剖分

战争涉及的区域越来越广,陆海空天电网多维战场空间的拓展、武器装备的升级改造、远距离投送和支援能力的提高使得现代化战争并不局限于某一区域,战争模拟也需要紧贴实际情况,建立起广阔的战场环境模型,为认识和研究现代化战争,推演信息化条件下的联合战争创设技术条件。一个全球化的战场环境则可以很好地满足推演需求。H3空间索引对全球进行网格剖分和编码,可根据经纬度快速定位至网格。利用H3空间索引构建全球战场可为不同类型的推演提供基础条件。针对不同推演目的,在模拟的战场环境范围改变时无须对环境重新建模,使兵棋能够更好地满足各种不同类型的推演。兵棋除了提供训练功能,还可在教学中发挥重要作用,通过对经典战例的回顾与重现,分析和总结战争经验,这同样需要有一个广阔通用的模拟战场环境作为战例推演分析的基础。

2.2 多分辨率六边形剖分

兵棋中棋子的机动、部署、作战等一系列活动都是基于棋盘网格进行计算的,因此对空间划分时采用的网格类型对系统仿真有着重要影响。现实中的地面机动方向应是360°的[19-20],在建模过程中模拟方向越多,模拟机动的效果越逼真。H3空间索引在网格划分时采用的图形为六边形,与大多数兵棋系统进行网格划分采用的图形一致。在此基础上,已有一些基于六边形网格的建模方法研究,能够为战场环境建模提供借鉴。分辨率的高低决定着空间栅格化后格元数量的多少。分辨率越高环境信息表示越精细,分辨率越低环境信息表示越概略。对连续空间栅格化可使计算机处理数据信息更为简便,但格元的数量影响着系统的整体响应速度。分辨率过高,空间格点数量较多导致空间存储量剧增,给计算机的计算能力带来很大的挑战;分辨率过低,战场环境模拟不真实,推演过于粗略,难以反映作战中存在的问题。如表2所示,H3空间索引设置了0～15共16个层级,每个层级用以剖分的六边形数量不同,级别越高,六边形表示的实际范围越小,可进行更精细的建模。兵棋中的棋盘需根据模拟的战争行动来确定比例尺大小,战略战役级兵棋推演中棋盘表示较为概略,而战术层级兵棋推演中的棋盘则更为详尽[19]。采用H3空间索引可根据推演的规模选择合适的层级使用,甚至在推演过程中可以进行层级的切换以满足不同级别的部队作战推演需求。相比于针对不同推演方案构建不同精度战场环境模型的方法,H3空间索引提供了极大的便利。如图3所示,六边形分别采用孔径为3、4、7[3,21]的方式进行细分,H3空间索引采用图中孔径为7的划分方式对层级进行细分。

图3 六边形多分辨率划分

表2 H3网格各层级六边形平均边长[22]

2.3 投影变形小

传统的经纬度网格划分符合人们的认知习惯,但是基于经纬度划分的网格随着纬度的升高变形逐渐增大,在两极地区甚至退化成三角形。基于多面体的投影方式将多面体投射到地球表面,可以用来构建全球网格的有正六面体、正十二面体和正二十面体等,多面体面数越多,越接近球体,投影的误差也就越小[23]。如图4所示,H3空间索引采用去顶的正二十面体进行投影,正二十面体接近球体,投影克服了基于经纬网划分时两极的非均匀性,各个区域的网格大小一致[6]。尽管其存在12个五边形,造成了网格划分的不一致性,但是其在定位时将五边形放置在海面上,五边形的面积随着层级的升高变小,可在精度允许的范围内忽略其影响。

图4 H3空间索引投影

2.4 编码方式简单

在H3空间索引中,其边、点、面(网格索引)均采用64位的编码模式进行编码,可以从编码中方便地获取编码模式、所处层级等信息,其中网格编码如表3所示,横向表示位数,网格编码使用的位数计算如公式(1)所示:

网格编码位数=纵轴数×16+横轴数

(1)

第1位保留为0;第2～5位共四位表示索引模式,模式1表示网格编码,模式2表示单向边的编码,模式3将作为双向边的编码,模式4为网格顶点编码,在网格编码中,其表示为0001。在建模过程中进行索引操作时主要用到网格索引,网格索引第6～8位设置为0;第9～12位表示当前H3空间索引层级,有0～15个层级,如第五层级编码,表示为0101;第13～19位表示当前网格所在的基网格编码,如图5,正二十面体有二十个面,每个面有5.5个六边形,再加上12个五边形,共122个基网格;基网格所在层级为第0层,第1～15层每层用3位表示网格在该层级的编码,六边形采用孔径为7的剖分方式进行多层级划分,H3空间索引在每个六边形面上建立一个IJK坐标,坐标编码如图6所示,分别用0～6表示7个子六边形;高于当前网格编码层级的网格编码,在其余高层级未使用的剩余位数均赋为1。

表3 H3网格编码[24]

图5 H3空间索引基网格划分[3]

图6 IJK坐标编码[25]

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

3.1 基于H3空间索引的建模框架

H3空间索引提供了一个全球范围的六边形索引,如图7所示,本章设置数据结构与H3空间索引相结合,环境矢量数据处理后,将六边形的边属性和面属性进行映射存储,在环境建模基础之上,以A*算法[26]为例对棋子机动进行寻路建模,展现寻路结果。

图7 基于H3空间索引的建模框架

3.2 兵棋棋盘建模示例

棋盘承载的环境信息对作战模拟起着重要作用。本节选择H3空间索引的第五层级进行棋盘建模,其六边形网格的边长约为8.54 km,平均面积约为252.9 km。对自然环境属性进行建模,设计数据结构存储网格数据,为兵棋推演过程中的模型计算提供环境数据信息。

兵棋棋盘建模关键是将地理环境、气象环境、电磁环境等影响作战的属性存储在对应的网格中,地理环境主要有地形地貌、障碍物等,气象环境如雨雪天气会对行军造成影响,潮汐变化会对登陆作战造成影响,在电磁环境中飞机等武器装备产生的雷达信号等会形成电磁干扰,影响通信、目标探测等活动。系统运行过程中通过网格索引高效地获取数据信息,从而进行模型计算。建模过程中目前只考虑地理环境,首先对环境类型进行分类,如提取面属性需要对地形进行分类,分为山地、开阔地、湖泊等,建立起地形对照表,如表4所示,建模的数据值应与表4对应。

表4 面属性对照表

建立起属性对照表后对矢量数据进行读取和处理,通过一定规则进行判定,如:六边形内面积占比第一的地貌类型定为面属性。属性特征提取后便可存入相应数据结构中为计算机读取。建模可视化效果如图8所示,对不同的属性采用不同的颜色进行标记,如面属性中湖泊用蓝色进行标记,开阔地用灰色标记,草地、森林用绿色标记;边属性用红色标记障碍物,表示此边不可通行。不同的颜色信息以及经纬度查询功能,如图9所示,可帮助指挥人员快速获取棋盘信息,提高推演效率[2]。

图8 棋盘环境建模

图9 经纬度信息查询

3.3 棋子机动寻路示例

兵棋中棋子的机动行为涉及海、陆、空三域,其中陆上机动规则最为复杂。在本节建模中,考虑影响机动的地形因素和障碍因素。如图10的棋子所示:六边形的六个等距方向为其机动方向,在棋子选择机动路径时,首先需考虑是否有障碍因素阻碍棋子机动,红线代表障碍因素,棋子不可通过此方向到下一个网格中去;其次,棋子机动还将考虑其是否能在下一网格的地形上通行。在完成对环境属性特征的提取后,网格中已经含有机动计算的属性,寻路计算在已建模好的棋盘中进行。

实验采用A*算法对棋子在棋盘中的寻路过程进行模拟,棋子在机动过程中读取棋盘网格中存储的环境信息,首先判断是否为障碍边,再判断通过此边到达的邻接网格中的地形类型是否可通行。六边形中存储的环境属性对棋子的机动有着重要影响,它决定着棋子在机动过程的机动方向、能否到达目的地等。

图10 棋子机动方向选择

棋子机动时在算法中加入了对地形的判断和障碍边的判断,因此,棋子在寻路过程中的路线为避开障碍和不可通过地形的最短路。输入不同的起始坐标和终点坐标,可以得到寻路结果。如图11所示,起始点S和终点D间最短距离应是二者间虚线距离,但在寻路过程中,六边形中的环境属性影响路径选择,障碍边和湖泊地形不可通过,最终路径如图11黑色线段所示。

图11 寻路结果

4 实验分析

4.1 实验环境与数据

硬件环境:Intel i5处理器, 16 G内存。

软件环境:Windows 10 64位操作系统。

开发环境:Python版本为3.7.9[27]。

地图数据:地图数据源采用高德地图,选取区域进行实验的范围为70°E～120°E,20°N～50°N。

H3空间索引层级:使用层级为第四、五、六层级。

4.2 实验结果

兵棋在运行过程中从棋盘读取数据需要考虑其获取棋盘信息的效率。棋盘的量化建模过程涉及六边形的编码方式,传统兵棋棋盘的六边形建模通常采用图2所示的编码方式,而H3空间索引则采用表3所示的64位的编码方式。本节用棋子机动对六边形的两种不同的编码方式进行实验,测试两种编码方式在相同实验条件下的吞吐量。

棋子机动时路径搜索的效率与其通过索引获取数据信息的速度和搜索的空间状态的数量有关。实验在两种不同的编码方式上分别随机产生200和800个障碍,通过六边形的边属性进行存储。传统棋盘编码的六边形数量根据H3空间索引选取的特定区域在第四、五、六层级上填充的六边形数量确定,以保证搜索空间的大小相同。实验中路径长度表示路径搜索经过的格元数量,记为lpath,路径搜索的时间记为ti,假设路径长度在区间[a,b]内的路径数量有m条,则区间[a,b]内棋子机动行为系统的吞吐量为

(2)

在每种条件下进行200次寻路,通过公式(2)计算寻路的吞吐量。实验结果如下图所示,图12、图13、图14分别表示在传统编码方式与H3空间索引编码方式下,棋子机动行为在不同障碍边数量和不同数量的状态空间中进行寻路的吞吐量。

图12 不同编码方式和障碍数量下的棋子机动吞吐量实验结果a)

图13 不同编码方式和障碍数量下的棋子机动吞吐量实验结果b)

图14 不同编码方式和障碍数量下的棋子机动吞吐量实验结果c)

由上图实验结果可知,棋子机动的寻路过程中,随机产生的障碍边对棋子的寻路效率并没有太大的影响,原因是随机产生的障碍边大片连接形成“死胡同”的概率较小,A*算法寻路较少进行迂回扩展,因此在随机生成障碍边的数量不足以形成大片“死胡同”的情况下,障碍对棋子机动效率的影响不大。

4.3 实验小结

从单个实验结果图和多个实验结果图进行对比可发现,采用A*算法进行寻路时,路径长度的增加使得搜索的状态空间数量增加,棋子机动的吞吐量减小。除此之外,在路径长度较短时,传统的网格编码方式比H3空间索引编码方式的吞吐量更大,随着路径长度的增加,两种网格编码方式的吞吐量差距逐渐缩小,到最后几乎持平,从这点看,使用H3空间索引建立全球战场环境对系统整体的响应速度与传统编码方式相比差别不大。尽管传统的网格编码方式在路径长度较短时占据优势,但路径长度较短时系统的响应速度快,两种编码方式效率的高低在运行过程中对系统和用户而言并不会带来太大的影响;在搜索空间逐渐增大时,因搜索空间数量的增加带来的效率问题成为影响系统效率的关键。因此,要使用H3空间索引进行棋盘建模,还需进一步优化模型算法,使兵棋系统在其架构下能高效进行推演。

5 结束语

兵棋是创新作战理论,制定作战方案和研究战争的重要工具。随着战场空间的拓展,需提供全球战场空间的支撑,H3空间索引为全球战场空间的构建提供了基础框架。本文在H3空间索引的基础上进行自然环境的建模,利用其索引建立数据结构存储环境属性,并对棋子在棋盘的寻路过程进行模拟,研究寻路效率,探究利用H3空间索引对全球战场环境建模的可行性。兵棋推演过程中,棋盘环境与棋子间的交互频繁,要使用H3空间索引构建战场环境,还需要探索更高效的建模方法,进一步提高兵棋推演的效率和准确性。