采用改进HPA*算法的大型游戏地图路径规划

李艺贵,郭 锐,邱国鹏,2

(1.三明学院 艺术与设计学院,福建 三明 365004;2.克拉斯诺达尔文化学院,俄罗斯 克拉斯诺达尔 350072)

在计算机游戏设计中,游戏角色自动寻路到指定地点并生成最短可达路径是最基础和常用的技术,如图1。对于小地图的游戏来说,使用一些基本的寻路算法就可以很好地解决寻路问题。然而,当游戏场景地图庞大,寻路的两点距离很长且中间有很多障碍物时,传统的寻路算法就会遇到性能瓶颈,出现角色等待时间过长、走错路、游戏画面卡顿等问题。因此,在游戏角色长距离寻路时,需要改进算法,以求解兼顾计算效率和响应速度的最短路径,减小节点计算量,提高运算速度。针对这些问题,本文提出基于HPA*的改进算法,以提高游戏角色自动寻路的速度,从而更好地满足游戏设计的需求。

1 相关研究

针对最短路径求解问题,Dijkstra、Floyd、A*[1]等算法相继被提出并被广泛应用。然而,Dijkstra和Floyd算法的时间和空间复杂度很高,其中Dijkstra算法的时间和空间复杂度均为O(N2),Floyd算法的时间复杂度为O(N3),空间复杂度为O(N2)。在游戏中,这种复杂度的算法很少被使用。相比之下,A*算法是一种启发式最短路径规划方法,时间平均复杂度为O(NlgN)。A*算法常被用于小地图寻路规划,但在大规模地图的长距离寻路时,它会消耗大量计算量,导致CPU被寻路阻塞的情况出现。因此,在设计大场景游戏地图时,有必要提供兼顾搜索速度和效率的改进算法,以提高游戏角色自动寻路的效率和性能。

Hotle等[2-3]提出了一种基于层次化的A*算法,称为HPA(hierarchical path-finding)算法,用于解决大规模地图上的路径规划问题。相对于传统的A*算法,HPA*算法将地图划分为多个区块,并通过关键节点将这些区块连接起来,形成抽象地图。在区块中,A*算法能够有效地寻找最短路径。如果起点和终点在同一区块中,直接使用A*算法寻找最短路径即可。而当起点和终点位于不同的区块时,需要在连接这些区块的关键节点中寻找最短路径。这一过程可以在抽象地图上使用A*算法进行,从而减少了搜索空间,提高了搜索速度。

当前,HPA*算法的研究主要集中在工业机器人路径规划方面,以减少运动响应延迟、降低规划时间和内存负载(Lee等[4]、仲朝亮等[5]、Zuo等[6]和李梓远等[7])。然而,在游戏地图中,对于HPA*算法的研究较少,尤其在场景复杂的大型游戏地图中。Marc等[8-9]通过将游戏地图分为多个抽象层次,逐层搜索后得到完整路径,实验验证了游戏地图的层次抽象表达可以有效减少路径规划计算负荷量。但是,随着地图场景变大和复杂度增加,基本的HPA*分层搜索算法,会导致搜索节点剧增,影响搜索效率。因此,李艳等[10-11]提出了基于HPA*的分层动态路径搜索HPLPA*算法。该算法将游戏地图分层抽象,并在动态环境中及时更新,采用 LPA*算法代替A*算法,实时寻找抽象路径再细化,从而得到最终的路径规划结果,虽然该算法在一定程度上提高了在大型地图上的搜索性能,但由于没有考虑到大型地图的复杂性,只适用于含有少量障碍物的空旷地图。当地图中存在大量障碍物时,HPA*算法的搜索节点数量会剧增,导致预处理时间和存储空间的开销增加,进而影响搜索效率。目前的HPA*改进算法的研究主要集中在场景简单的空旷地图上,忽略了地图复杂性,此外,改进算法没有考虑缓存区块间的寻路路径,都是实时的计算抽象路径并细化,如果寻路距离很长,中间有很多障碍物时,实时路径计算就会遇到性能瓶颈。因此,我们需要进一步研究改进HPA*算法,结合缓存技术,减少实时计算量,以适应复杂的大型游戏地图,提高算法的搜索效率和性能。

本文针对HPA*算法在搜索大规模地图时可能存在的问题,提出了一种HPA*改进算法。该算法基于层级地图,将原始地图进行抽象映射,从而形成抽象地图层,并通过在不同层级之间进行路径搜索来缓存关键节点间的最短路径和构建层级映射矩阵。通过这种方式,可以减少搜索节点的数量,提高算法的搜索效率和速度。此外,还设置了节点权重值,以引导寻路方向和规避closeList循环遍历,从而进一步提高寻路效率和速度。为了验证该算法的性能,我们在不同尺寸的游戏网格地图上进行了实验。实验结果表明,相比于传统的A*和HPA*算法,本文提出的算法能够在搜索效率和速度上都取得很大的提高。

2 HPA*算法

2004年,Botea等学者提出了一种基于A*的多层路径搜索算法,称为HPA*算法。该算法通过对地图进行分层,将大地图转换成多个小地图,形成抽象地图,从而减少搜索空间。HPA*算法的搜索过程包含两个主要部分,离线预处理和实时寻路。在离线预处理阶段,算法通过将地图分层,将大地图转换为多个小地图,形成抽象地图,并在抽象地图上寻找关键节点。在实时寻路阶段,算法根据起点和终点所在的区块,以及这些区块之间的关键节点,对抽象地图进行A*搜索,从而找到最短路径。通过在不同层级之间进行路径搜索,HPA*算法能够有效地减少搜索空间,提高搜索效率。

2.1 离线预处理

2.1.1 预处理地图

选取一副游戏地图进行均匀分区,如图2。地图被分为30×30的网格单元,每个网格单元可以称为节点。图3为图2的分区结果,按照每个区块10×10大小,把地图均匀分成9个子区块。白色节点代表可行走区域,蓝色节点为不可行走区域。

图2 实际游戏地图

图3 游戏网格地图

2.1.2 寻找关键节点

在相邻区块的公共边上选择左右两侧单元格作为关键节点。关键节点的选择规则为:对于任意相邻的两个区块如Zi和Zj,选取公共边上连续无障碍物区域作为相邻区块的互通区域,选择互通区域中间左右两侧单元格作为关键节点。如图4所示,区块Z0与Z1的公共边上黄色网格为互通区域,绿色网格为关键节点。

图4 关键节点示意图

2.1.3 形成抽象地图

在区块内使用A*算法将图4的关键节点依次进行连接形成intra边,连接属于同一个互通区域的关键节点形成inter边,最终形成抽象地图,如图5。

图5 抽象地图

2.2 实时寻路

2.2.1 抽象寻路

根据游戏角色的起点和目标位置信息,找到其所在的区块,在抽象图上使用局部A*方法进行抽象寻路,得到起点与终点之间的一条抽象路径,所得抽象路径如图6所示。

图6 抽象路径

2.2.2 细化路径

对抽象路径上相应的关键节点使用A*算法寻找节点间的实际路径,将抽象路径细化为低层级的实际路径。HPA*算法采用抽象分层思想加速寻路,解决了大规模地图的寻路问题。它的执行步骤简单易懂,易于实现。通过多层抽象,可以根据地图规模进一步缩小搜索空间,从高层到低层逐一细化得到实际路径[12]。相比A*算法,HPA*算法的寻路速度显著加快。 然而,当地图中存在大量障碍物或者地图比较复杂时,在抽象图上使用局部A*方法进行抽象寻路时,会出现过多的搜索节点,从而影响搜索效率。为了解决这个问题,本文通过调整关键节点选取规则、构建层级映射矩阵和缓存路径等方式改进HPA*算法。

3 HPA*改进算法

在空间记忆系统研究中,广泛提出了区域化多层嵌套的组织方式。该方式认为,空间对象可以被划分为多个区块,并且这些区块可以组合成更高级别的空间对象。这种组合形成了区块间的包含关系,这种关系可以被表示为树形结构。同时,不同区块对象之间也可以存在连通关系[13]。改进算法的核心思想是在离线状态下,将游戏地图分为多个区块,并将每个区块抽象为一个节点形成高层级抽象地图。高层级地图是低层级地图的抽象版本,其中低层级地图中的区块可以映射为高层级地图中的节点,形成类似图7所示的结构。由该图可见,该模型主要分为两层:原始地图表示层和抽象地图表示层,抽象地图层是由原始地图的关键节点映射而成。

图7 区块化多层表示

该算法首先在抽象地图中进行抽象寻路,形成抽象寻路序列,再在底层地图进行寻路细化。传统HPA*算法需要实时计算关键节点间的最短路径,这往往会浪费过多的计算性能。为了解决这个问题,改进算法通过构建层级映射矩阵,体现层级地图间的映射关系,加快寻路细化过程。在此过程中,首先需要绘制抽象地图,进而计算区块间最短寻路路径。通过最短路径的关键节点对,构建层级映射矩阵M。最后,创建哈希表缓存最短路径,用于将抽象路径转换为低层级地图细化路径。在映射矩阵中,每个元素M(i,j)表示从区块i到区块j的最短路径中所经过的第一个区块。

在实时寻路过程中,改进算法首先判断起点和目标点是否在同一个区块,再在映射矩阵M中进行抽象寻路,得到从起点区块到终点区块的抽象路径,最后进行路径细化。抽象地图的节点数量比低层级地图中的节点数量要少得多,在抽象地图中进行路径搜索的复杂度更低,可以显著缩短搜索时间。最后通过设置节点权重值和判断节点是否被取,规避Closelist循环遍历,引导寻路方向,提高寻路效率和速度。改进算法的流程图如图8,实现步骤分为离线预处理和实时路径搜索两个部分。

图8 HPA*改进算法的流程图

3.1 离线预处理

3.1.1 预处理地图

每个区块都被分配了一个唯一的编号,用于区分不同的区块。如图3所示,地图被分为30×30的网格单元,每个区块大小为10×10,将地图均匀分成9个子区块。从第一行左上角的第一个区块开始,按照从左向右,从右向左,从左向右的顺序,依次给9个区块分配编号:0、1、2、一直到8。这样的编号方式可以方便地对区块进行标识和索引,便于后续算法的实现和优化。

区块数据结构为:Zone { int zoneId; GridNode[] topAbsNode; GridNode[] downAbsNode; GridNode[] leftAbsNode; GridNode[] rightAbsNode }。zoneId为区块编号,topAbsNode、downAbsNode、leftAbsNode、rightAbsNode分别为区块顶部、下部、左边、右边公共边上关键节点集合。

网格单元节点数据结构为:GridNode { Vector2 position; int zoneId; int nodeFindIndex; int weight; enum nodeType{walk; notWalk }; GridNode nodeFather; floatf; floatg; floath}。Position为网格节点坐标,zoneId、nodeFindIndex、weight分别为节点所在区块编号、游戏寻路次数、网格权重值,nodeType为节点类型,nodeFather为父节点,f、g、h分别为期望值、实际代价值、估计代价值。

3.1.2 选择关键节点

首先在相邻区块的公共边上定义互通区域,互通区域的选择规则为:任意相邻区块Zi和Zj,选择公共边上连续无障碍物区域作为互通区域,互通区域两侧节点分别组成Ti和Tj,则互通点集E是互通区域节点的集合,symm(t)为对称关系,t为互通点,满足下列条件:

E⊂Ti∪Tj;

(1)

∀t∈Ti∪Tj:t∈ E ⟺ symm(t) ∈E;

(2)

t.nodeType!=notWalk。

(3)

在互通区域Zi侧,选择中间网格单元作为关键节点,并按照顺时针方向在每个区块内为关键节点设置唯一的编号,其中,关键节点a必须符合以下条件:

i>j? a∈Ti:a∈Tj,

(4)

a=E[E.length/4]。

(5)

如图9所示,区块Z0与Z1 的公共边上黄色网格为互通区域,Z0上绿色网格为关键节点,Z0与Z5公共边上黄色网格为互通区域,Z0上绿色网格为关键节点。在Z0区块中按照顺时针方向依次给关键节点设置编号:0、1。

图9 关键节点示意图

3.1.3 绘制抽象地图

抽象地图是指在每个区块内,使用A*算法将公共边上的关键节点相互连接,进行连通测试,从而形成intra边,记录下每条边的权重值,权重值表示两个关键节点之间的最短距离,并将每条intra边的最短路径保存在数据文件中。如图10,连通图9的关键节点,形成抽象地图,每条intra边的权值是节点间最短路径。

图10 抽象地图

3.1.4 构建区块间映射矩阵

为了构建区块间的映射矩阵,首先需要计算区块间的最短路径。为此,在抽象地图上使用A*算法进行抽象寻路,以搜索出区块间最短寻路路径,即起始点区块关键节点到其他区块关键节点的最短路径。如公式6,在A*算法的启发式函数中,n表示当前搜索的关键节点,f(n)表示n的期望值,g(n)表示从起始关键节点到n的实际代价,h(n)表示从n到目标关键节点的估计代价。在改进的算法中,g(n)和h(n)的值可以直接获取intra边权重,从而减少节点搜索计算。

f(n)=g(n)+h(n)

(6)

区块间的最短路径可以表示为一条关键节点的序列,其中每个关键节点可以代表一个区块。为了实现不同区块之间的连接和查找,需要构建一个大小为N×N的层级映射矩阵M,存储了每个区块到其他区块的最短抽象路径。矩阵中的每个元素M(i,j)表示从区块i到区块j的最短路径中所经过的第一个区块,如果起始点区块和目标点区块在同一个区块,那么M(i,j)=-1。N是区块的个数,行代表初始起始区块,列代表终点区块。通过直接访问起始区块id和终点区块id,可以在矩阵中查找最优路径。这个映射矩阵是通过将从一个区块到另一个区块的路径“记录”为指向路径上下一个节点的一系列指针的方式来实现的。例如,在图10中,假设起始点在区块0,目标点在区块8。通过抽象寻路,我们可以确定起点需要经过关键节点 0、3、7 、6才能形成最短路径到达区块 8,其中节点3、7、6分别代表区块1 、区块4和区块3。因此,区块0到区块8的中间转移区块为区块1、4、3。我们将区块1的编号填入M(0,8) 中,然后区块1经过区块4可以到达区块8,将区块4的编号填入M(1,8) 中,区块4经过区块3可以达到区块8,将区块3填入M(3,8)中,依此类推,即可填满层级映射矩阵M。

(7)

3.1.5 缓存区块间最短路径

缓存搜索结果是减少寻路算法中搜索节点数量的一种常见技术。通过避免再次搜索已经探索过的节点,算法可以显著减少寻路所需的搜索次数。这种技术可以被广泛应用于各种寻路算法中,以提高算法的效率和性能[14]。改进算法按照前后顺序依次连接区块间寻路序列中的每个关键节点,得出一条抽线路径。例如,对于区块0到区块8,其寻路序列为(0,3,7,6),形成<0,3>,<3,7>,<7,6> ,三个关键节点对。然后,根据所保存的intra边最短寻路数据文件,对关键节点对的抽象路径进行细化,形成节点对的底层细化路径。为了提高算法的性能,我们使用哈希表缓存节点对路径上的所有节点。哈希表的键值可以根据节点对所在的区块ID计算所得,这样可以快速地查找起始关键节点对的细化路径。这种方法可以避免重复计算已经搜索过的路径,从而提高算法的效率。

哈希表定义如下:

Dictionary> cacheTable = new Dictionary>()

哈希键值定义如下:

Cache[Start.zoneId.GetHashCode() ^ end.zoneId.GetHashCode() &0x7FFFFFFF]

3.2 实时路径搜索

在游戏启动时,将层级映射矩阵M和哈希表cacheTable加载到内存中。当游戏角色需要寻路时,需要先判断其起点和目标点是否在同一个区块。如果在同一个区块,A*算法会直接在此区块内进行路径搜索。如果不在同一个区块,需要查询层级映射矩阵M,以获取从起始区块到目标区块的抽象寻路序列。接着,按照序列中节点的顺序,连接关键节点对,并根据这些节点对查询哈希表cacheTable,找到细化的关键节点对寻路路径。最后,将这些细化路径拼接在一起,形成区块间寻路路径。

根据抽象寻路序列,找出第一个序列元素,此元素是起点所在区块通向目标区块的起点关键节点,利用A*算法找出从起点到此关键节点的最短路径,这是起点区块内的起点局部寻路。然后,根据寻路序列找到最后一个序列元素,该元素是通向目标区块的终点关键节点,利用A*算法找出从终点到该关键节点的最短路径,这是目标区块内的终点局部寻路。最终,将起点局部寻路路径、区块间寻路路径、终点局部寻路路径拼接在一起,形成完整的长距离导航路径。在实时A*搜索中,可以通过权重引导寻路方向和规避closeList列表的循环遍历来提高寻路效率和速度。

(1)权重引导寻路方向

为了加快局部区块寻路速度,可以给关键节点周围的节点设置权重值,通过权重引导寻路方向。具体地,在A*算法中,期望值f(n)不仅可以帮助算法更快地找到目标节点,还能起到引导算法的作用。根据公式6,每次提取相邻可行节点时,都要实时计算期望值,并根据该值优先级从高到低的顺序在openList队列中进行扩展搜索,选择期望值最小的节点作为下一个要扩展的节点。

期望值对于寻路的方向判断很重要,通向目的地的方向越准确,寻路的效率就会越高,寻找路径的速度也就越快。从这个角度上来看,期望值问题就变成了如何帮助期望值更加准确的判断通向目的地的方向[15]。在节点中加入权重值来改变期望值从而引导算法快速找到关键节点是一种很好的方式。

如图9,黄色网格是为关键节点标记的引导路径。如果普通节点权重值为100的话,黄色节点权重值为10。在实时A*算法中,计算节点期望值时,需要加上节点的权重值,期望值公式如下。

f(n)=g(n)+h(n) +E(n)。

(8)

式(8)中,n为当前搜索节点,g(n)为起点到n的实际代价,h(n)为当n到目标点的启发式估计代价,E(n)为n的权重。根据公式8,计算期望值时,黄色引导节点比其它节点获得更小的值,这也意味着引导节点在OpenList队列中更靠前,更容易搜索到目标节点。如图11,当A*算法从起点S到目标点D时,搜索到黄色节点时,就会很容易沿着黄色节点一直延伸到关键节点n0和n4,从而减少了openList中节点搜索,加快了搜索速度。

图11 网格权重图

(2)规避openList队列循环遍历

在每次寻路中,当一个节点被加入到openList列表时,需要检查该节点是否已经在closeList列表中。如果在closeList中,就不需要添加到openList列表中。然而,随着closeList列表中搜索节点的增加,会导致CPU计算量的增加,从而影响性能。为了避免这种情况,可以定义一个全局静态整型变量pathFindTimes,用于记录寻路次数。此外,每个节点还需要定义一个nodeFindIndex。每次寻路时,将pathFindTimes的值加1。例如,在游戏开启时,pathFindTimes和nodeFindIndex的初始值相同。当玩家第一次寻路时,pathFindTimes的值会加1。在将一个节点加入到closeList之后,该节点的nodeFindIndex也会加1。当玩家第二次寻路时,在将节点添加到开启列表之前,需要检查该节点的nodeFindIndex 是否等于pathFindTimes的值。如果相等,表示该节点已经在开启列表中,不需要再次添加。通过这种优化方法,可以规避closeList的遍历循环,提高寻路的效率。该优化可归纳如下。

path Find Times+=1;

closeList.Add(node);

node.nodeFindIndex+=1;

While path Find Times!=node.node FindIndex

{open List.Add(node);}

4 实验结果及分析

本文采用C#在Unity游戏引擎上实现A*、HPA*和HPA*改进算法,在不同尺寸游戏网格地图中进行了三组数值仿真实验。地图大小分为3种,分别为64×64、512×512和1024×1024。蓝色节点障碍物按照每幅地图10%的比例随机生成,如图12所示。在64×64的地图上随机选取50对起始点和目标点,并且路径长度都大于30;在512×512的地图上随机选取50对起始点和目标点,并且路径长度都大于250;在1024×1024的地图上随机选取50对起始点和目标点,并且路径长度都大于500。

(a)A*

表1～2给出了3种算法在不同尺寸游戏地图上的寻路时间,在64×64的地图上,3种算法的平均寻路时间相差不大,都在12 ms左右。这是因为64×64的地图规模较小,搜索空间有限,3种算法的效率差异不是很明显。但是在512×512的中等规模地图上,三种算法的平均时间差异非常明显。其中,A*算法的平均时间达到了53 ms以上,而传统HPA*算法和HPA*改进算法的平均时间分别为17.13和9.43 ms。在1024×1024的大型规模地图上,A*算法的平均时间达到了170.12 ms,HPA*算法和HPA*改进算法的平均时间分别为31.76和11.62 ms。这是因为在大规模地图上,搜索空间非常庞大,传统的启发式搜索算法对搜索空间的控制比较弱,而HPA*算法可以将地图划分成更小的区块,从而大大减小搜索空间,提高搜索效率。改进算法在此基础上采用了一系列的优化,如缓存关键节点对最短路径、构建层级间映射矩阵、优化A*实时查询等进一步提高了搜索效率和速度。

如表2,在平均路径长度方面,HPA*和改进算法的表现差异不大,但是A*算法的平均路径长度更短,这是因为A*算法是一种完整的路径搜索算法,它会在搜索过程中保证找到的路径是最优的。而HPA*算法和HPA*改进算法是一种分层搜索算法,它们通过对地图进行分层处理,将搜索空间缩小到一定程度,来提高搜索效率。但由于HPA*只在相邻区域边界选取少量关键点形成抽象图,所以它得到的路径是接近最优的,而不是最优路径,如图13所示。

表2 路径搜索节点实验结果 单位:ms

(a)HPA*路径

在搜索节点数量上,改进算法远低于A*和HPA*算法。A*算法是一种全局搜索算法,需要搜索整个地图才能找到最优解。在搜索过程中,A*算法会考虑周围所有的节点,并计算与目标节点的距离,导致节点数量非常庞大,搜索效率较低。而HPA*算法通过分层的方式,将搜索空间限制在局部范围内,大大减少了搜索节点数量,提高了搜索效率。相比HPA*算法,改进算法通过合并关键节点、缓存搜索结果避免重复搜索等优化策略,从而减少搜索节点,可以更快地找到目标位置。

5 结论

本文针对HPA*算法在运行时容易出现搜索节点过多的问题,提出了一种改进的HPA*算法。该算法的核心思想是将游戏地图分解为两个层级地图,并通过不同层级之间的路径搜索来缓存关键节点对路径和构建层级映射矩阵。此外,还引入了节点权重值以引导寻路方向和规避closeList循环遍历等方式来优化HPA*算法。实验结果表明,改进算法在寻路时间和效率上相较于其他两种算法具有一定优势,且其综合性能相对稳定。未来的研究可以进一步提高改进算法的寻路精度,以使其更好地应用于大规模游戏场景地图设计中。