关于寻路算法的一些思考(7):地图表示

在本系列文档大部分内容中,我都假设A*用于某种网格上,其中的“节点”是一个个网格的位置,“边”是从某个网格位置出发的各个方向。然而,A*可用于任意图形,不仅仅是网格,有很多种地图表示都可以使用A*算法。

地图表示可能对性能和路径的质量产生很大影响。

寻路算法不是线性的,而是越来越差。如果需要行进的距离翻倍了,那么会消耗超过两倍的时间来找路径。你可以想象寻路算法是在搜索一个类似圆的区域,当圆的直径加倍时,区域变成原来的四倍。一般来说,在地图表示中,节点越少,A*算法越快。而且节点越匹配角色单元将要移向的位置,路径质量越好。

游戏中,用于寻路的地图表示不需要和用于其他用途的地图表示一样。但是采用相同的表示是一个不错的起点,直到你发现需要更好的路径或更高的性能。

网格(Grid)

网格图将世界(world)均匀分割为小的规则图形,这些图形有时被称为“图块(tile)”。常用的网格有正方形、三角形和六边形。网格很简单,也很容易了解,很多游戏都采用它来表示世界,因此本文中我重点关注网格。

在《BlobCity》游戏中我采用网格表示,因为在每个网格位置,移动成本都不同。如果在一大片空间内,移动成本都是均匀的(正如前文我举过的例子),那么用网格可能就相当浪费。因为此时,A*无需一次走一步,它可以跳过一大片区域走到另一端。在网格上寻路,得到的也是网格上的路径,可以通过后期处理,消除锯齿状移动。但是如果你的角色单元没有限制必须在网格上移动,或者你的世界甚至不采用网格,那么在网格上寻路可能不是最好的选择。

图块移动(Tile movement)

即使在网格中,也可以选择沿图块、边或顶点移动。图块是默认选项,尤其是角色单元只能移动到图块中心的那些游戏。在上图中,在A处的单元可以移到所有标B的位置。你也许还允许对角线移动,代价相同或者更高。

如果你采用网格寻路,但角色单元不限制仅沿网格移动,并且移动成本是均匀的的,那么你可能想要拉直路径,即如果某两个节点之间没有障碍,可以从一个节点沿直线移动到另一个远处的节点。

边移动(Edge movement)

 

如果角色单元可以移动到一个网格内的任何一点,或者图块很大,就应该考虑,你的应用是否选择边寻路或顶点寻路更好。

一个单元通常从一个边(一般是边的中点)进入图块,并从另一个边离开那个图块。图块寻路中,单元移到图块中心,但边寻路中,单元直接从一个边移到另一个边。我写了一个java applet,演示绘制边之间的道路,可能帮助说明边是如何使用的。
顶点移动(Vertex movement)

网格图中的障碍通常在顶点处有拐角。在障碍物周围,最短的路径就是要绕过这些拐角。顶点寻路中,角色单元从一个拐角移到另一个拐角。这是一种最节省开销的移动,但是要依据角色单元的大小调整路径。

多边形地图(Polygonal maps)

除了网格,最常用的是多边形表示。如果一大片区域的移动成本是均匀的,并且角色单元可以沿直线移动,而不是沿网格移动,你可能想采用一种非网格的表示。在你的游戏中,即使其他东西采用网格,寻路也可以使用非网格的图形表示。这里有个简单的例子,是一种多边形的地图表示。这个例子中,角色单元需要绕过两个障碍。

想象在这个地图中角色单元如何移动。最短路将在这些障碍的拐角点之间,因此我们选择这些拐角点(红色圆点)作为A*算法的关键“导航点”;每次地图改变,就计算一次这些点。如果障碍和网格对齐,那么导航点和网格顶点对齐。此外,寻路的起点和终点应当标示在图中;每次调用A*,都需要将这两个点加到图上。

除了导航点,A*需要知道哪些点是连通的。一个简单的算法是构建可视图:互相可见的点对。这个简单算法可能满足你的需求,尤其是当游戏中地图不常改变时。但是如果这个算法太慢,你可能需要一个更复杂的算法。另外,在图上添加起点和终点后,对任意两个顶点(包括起点和终点),如果两点可见,添加一条这两点连接而成的边。

A*需要的第三条信息是点之间的行进时间。如果在网格上移动,时间就是曼哈顿距离manhattan distance)或对角网格距离diagonal grid distance)。如果可以在导航点之间直接移动,时间就是直线距离

接下来,A*考虑从导航点到导航点的路径,图中粉色线就是其中一条路径。如果导航点很少,而网格位置很多,这种方法要比从网格点到网格点的寻路快得多。如果路上没有障碍,A*性能非常好——起点和终点将由边连接,无需扩展任何导航点,A*可以立即找到路径。即使有障碍,A*也将从一个拐角点跳到另一个拐角点,直到找到最优路径,这将仍然比在网格位置间寻路要快得多。

维基百科中有更多关于机器人文学中的可视图

复杂性管理(Managing complexity)

上边的例子非常简单,图也很合理。然而在一些有很多开放区域或长廊的地图中,可视图的一个弊端就显现出来了。连接每对障碍拐角点的一个主要缺点是,如果有N个拐角点(顶点),则至多有N2条边。下图展示了这个问题:

这些额外的边主要影响内存使用。相比网格,这些边提供一种捷径,大大加快了寻路。虽然有算法可以删除冗余的边,以简化图形,但删除之后仍然有很多边。

可视图的另一个缺陷是,每次调用A*,都要添加起点和终点,以及以它们为顶点的新边,然后在找到路径之后,删除这些添加的东西。节点很好加,但增加边需要考虑从这些新节点到所有已有节点的可见情况,如果地图很大,这可能会很慢。一种优化方案是只看附近的节点,或者也可以用简化可视图,删除和两个顶点都不相切的边(这种边永远不会出现在最短路中)。

导航网(Navigation Meshes)

不用多边形表示障碍,而是将可行区域用不重叠的多边形表示,这也被称为导航网。这些可行区域还可以附有一些信息(如“要求游泳”或“移动成本为2”)。这种表示法不需要存储障碍。

前面的例子就变成了下图这样:

我们可以像处理网格一样处理这个,同样的,可以选择多边形中心点、边或顶点作为导航点。

多边形移动(Polygon movement)

同网格一样,每个多边形的中心提供了一个合理的寻路节点集。此外,还要添加起点和终点,以及这两个点与所在区域中心点所连成的边。下图中,黄色路径是沿多边形中心点寻路所得的路径,粉色路径是理想路径。

可视图表示可以产生那条粉色理想路径。采用导航网使地图易于管理了,但是路径的质量受到影响。我们可以消除路径,使其看起来更好一些。

多边形边移动(Polygon edge movement)

移到多边形的中心通常是不必要的。相反,我们可以穿过相邻多边形的边而移动。下面这个例子中,我选择每条边的中点。黄色路径是沿边中点寻路所得的路径,相比理想的粉红色路径,是一条不错的路径。

 

你也可以增加成本,在边上选更多的点,来产生更好的路径,

多边形顶点移动(Polygon vertex movement)

绕过障碍的最短路径是绕过其拐角,这也是为什么我们在可视图表示中采用拐角点,在这里即是导航网的顶点:

 

上图中,路上只有一个障碍。当要绕过障碍时,黄色路径会穿过一个顶点,粉色路径(理想路径)也一样。然而,可视图方法将直接连线起点和障碍拐角点,导航图则要更多步。这些步骤不应该沿顶点走,因此路径看起来不自然,有“抱墙”行为。

混合式移动(Hybrid movement)

对于多边形的哪个部分可以用作寻路导航点,我们并没有任何约束。你可以在一条边上多加一些点,顶点也不错,多边形的中心点则基本没用。下图是采用了边中点和顶点的一种混合方案:

 

注意要绕过障碍,需要穿过一个顶点,但在其他地方,则可以穿过边中点。

路径消除(Path smoothing)

只要移动成本是固定的,路径消除相当容易。算法很简单:如果点i到点i+2可见,删除点i+1,循环直到邻节点之间都不可见。剩下的只有绕过障碍物拐角点的导航点。这些点都是导航网的顶点。因此如果使用路径消除,就不需要采用边中点或多边形中心点作为导航点,只要顶点就可以了

上面的例子中,路径消除可以将黄色路径变成粉红色路径。然而,寻路算法并不知道这些更短的路径,因此它的决策不会优化。导航网是一种近似地图表示,而可视图是一种精确地图表示。缩短在导航网中找到的路,结果并不总能像通过可视图找到的路一样好。

分层(Hierarchical)

平面地图只有一层。而游戏很少只有一层——往往有一个“图块”层,然后有一个“子图块”层,物体可以在图块中移动。然而我们通常只在高层寻路。你也可以添加更高的层,如“房间”。

在地图表示中,节点越少,寻路越快。还有一种加快寻路速度的方法是多层次搜索。例如,要从你家到另一个城市的某个位置,你会找到一条路,从你的椅子到你的车,从车到街道,从街道到高速公路,从高速公路到城市边缘,再从那儿到另一个城市,然后到一个街道,到一个停车场,最终到达目的地门前。此时,有下述几层搜索:

  • 街道层,你从一个位置走到附近的某个位置,但不会走出这条街。
  • 城市层,你从一条街道走到另一条,直到找到高速公路。你无需担心进入建筑物或停车场,也不用担心在高速公路上行驶。
  • 州层,在高速公路上,你从一个城市到另一个城市。在到达目的城市之前,你无需担心城市内的街道。

将问题分层,可以忽略很多选项。例如当从一个城市到另一个城市时,考虑路上每个城市的每条街道是很乏味的。相反,你可以忽略它们,只考虑高速公路,问题就变得很小且易于管理,解决也变得很快。

分层地图在表示上有很多层。异构层次结构(heterogenous hierarchy)通常有固定层数,各有不同特点。例如,《Ultima 5》有一个“世界”地图,上边有城市和地牢。你可以进入一个城市或地牢,这就进入地图的第二层。另外,世界之上还有世界,从而是一个三层结构。这些层可以是不同的类型(图块网格、可视图、导航网、路标)。而同质层次结构(homogeneous hierarchy)层数任意,每层都有相同的特性。四叉树和八叉树就是同质层次结构的。

分层地图中,寻路可能发生在几个层次。例如,假设一个 1024×1024 的世界被划分为 64×64 个“区域”,则可以这样找到一条路径,从玩家位置到区域边缘,然后从一个区域到另一个区域,直到到达目的区域,然后从那个区域的边缘到达目的位置。粗级别上,更容易找到长路径,因为寻路算法没有考虑所有的细节。当玩家穿过每个区域时,可以再次调用寻路算法,找一个短路径。保证问题规模很小,寻路算法就可以运行得更快。

你可以结合使用分层和图搜索算法,如A*,但是不需要每一层都采用一样的算法。对一些小的层级,你可以预算所有节点间的最短路(用Floyd-Warshall或其他算法)。在分层地图中,通常找不到最优路径,但一般都接近最优。

还有个类似的方法是改变分辨率。首先,绘制低分辨率路径。当接近一个点时,用高分辨率精化路径。这个方法可以结合路径拼接使用,以避免移动障碍。

一些文章:《“龙腾世纪:起源”中的寻路算法》解释某商业游戏中使用的几种分层方法,《采用线性预处理的超快最短路查询》在道路图中使用“运输节点”[PDF],《游戏网格地图的运输节点》、《分层A*:有效搜索抽象层》、《道路网路线规划》(Dominic Schulte的博士论文),逐层注解A*(第一部分第二部分源代码)。

环绕式地图(Wraparound maps)

如果你的世界是球形或环形的,物体可以从地图的一端绕到另一端。最短路可能在任一方向,因此必须探索所有的方向。如果用网格,环绕时可以用启发式方法。此时,我们不用abs(x1 – x2),而采用min(abs(x1 – x2), (x1+mapsize) – x2, (x2+mapsize) – x1),即考虑三种情况的最小值:待在地图上不绕行,x1在左边时绕行,或x2在左边时绕行。绕行每个轴时都这样做。本质上来说,你计算启发值时,假设地图与其副本邻接。

连通组件(Connected Components)

有些游戏地图中,起点和终点之间根本就无路可通。如果用A*找路,它会探索图的很大一个子集,才能确定根本没路。如果可以预先分析地图,用不同的标记标识出所有的连通子图,那么在找路之前,首先检查起点和终点是否都在同一个子图中。如果不在,那么这两者之间无路可通。另外分层寻路在这也可以用,特别是子图之间有单向边时。

道路图(Road maps)

如果你的角色单元只能在道路上走,你可能需要提供A*道路和交叉口的信息。每个交叉口是图上的一个节点,每条路是图上一条边。A*找从交叉口到交叉口的路,这比用网格表示要快得多。

有时,角色单元的起点和终点可能不在交叉口。此时,每次运行A*时,都要修改点/边图(和可视图和导航图采用的技术一样),将起点和终点作为新节点加到图中,然后在这两个点和最近的交叉点之间连线。寻路结束后,再删除这些额外的节点和边,这样图在下次调用A*时还可以使用。

上图中,交叉口是寻路图中的节点,节点之间的道路是边,且每条边都应给定道路行驶距离。在这个框架中,你可以把单向道路作为图上的单向边。

如果你想给转向分配成本,你可以稍稍扩展这个框架:将原来单一的位置节点,变为<位置,方向>节点(静态空间的一个点),其中方向指你到达那个位置后所面向的方向;将原来从X到Y的边,换成从<X,方向>到<Y,方向>的边(代表直行),和从<X,方向1>到<Y,方向2>的边(代表转向)。每条边都或者代表直行,或者代表转向,不可能两者都是。然后你可以给代表转向的边分配成本。

如果你还要考虑转向限制,如“只能右转”,你可以改变上述框架,即结合使用那两种边,每个转向边之后都是直行。例如,在这个框架中,你想表示一个限制“只能右转”:添加一个直行边<X,北>到<Y,北>,一个转向边<X,北>到<Z,东>,转向之后是直行。不要添加<X,北>到任何向西的边,因为这意味着左转,也不要添加任何向南的边,因为这意味着掉头。

利用上述框架,可以对一个大型市中心建模,其中有单向道路,特定路口转向限制(通常禁止掉头,有时禁止左转),以及转向成本(建模在右转之前减速和等待行人)。相比网格图,道路图中A*找路相当快,因为每个节点处的选择很少,而且图上的节点也相对较少。

如果是大型道路图,一定要读读Goldberg和Harrelson发表在ALT(A*, Landmarks, Triangle inequality)上的文章PDF,或者这篇论文)。

跳跃链(Skip links)

基于网格创建的寻路图,一般给每个位置分配一个顶点,给相邻位置之间的每个可能的移动分配一条边。然而边不一定必须是相邻顶点之间的,“跳跃链”或“快捷链”就是非相邻点之间的边,它可以加快寻路进程。

跳跃链的移动成本怎么算呢?有两种方法:

  • 使成本匹配最优路径的移动成本。这保留了A*的优良特性,如寻找最优路径。为了将A*推向正确的方向,要打破跳跃链和常规链之间的关联,即将跳跃链的成本减少1%左右。
  • 使成本匹配启发成本。这对性能有很大影响,但是放弃了最优路径。

添加跳跃链类似于分层地图,花费更少的精力,但往往能给你一样的性能。

对于有地下室和走廊的网格图,矩形对称性缩减和跳跃点搜索提供两种方法建立跳跃链。矩形对称性缩减(Rectangular Symmetry Reduction)静态建立附加边(他们称为宏边),然后调用标准的图搜索算法。跳跃点搜索(Jump Point Search)动态建立长边,是图搜索算法的一部分。对于道路图和其他类型的图,抽象分层值得一看。

路标(Waypoints)

路标是路径上的一个点。路标可以具体到每条路,或者是游戏地图的一部分。路标可以手动输入或自动计算。很多实时策略游戏中,玩家点击就可以手动添加特定路径的路标。当自动计算时,路标可以简化路径表示。地图设计者可以在地图上人工添加路标(或“信标灯”),以标识好路径的位置,或者也可以用算法自动标识。

使用跳跃链是为了加快寻路,因此跳跃链应当放在设计者设置的路标之间,这可以使其利益最大化。

如果路标不是很多,可以预算每对路标之间的最短路(用全对最短路算法,不用A*)。常见的情况就是,一个角色单元先按照自己的路径到达一个路标,然后按照预算的路标间的最短路走,最后离开路标这个高速路,走自己的路到达目标。

如果路标或跳跃链的成本错误,可能导致找到次优路径。有时我们可以通过后期处理或在移动中,消除一个糟糕的路径。

图形格式建议(Graph Format Recommendations)

一开始你在已使用的游戏世界表示中寻路,如果你不满意,考虑将游戏世界转换为方便寻路的另一种表示形式。

很多网格游戏中,地图的很多大块区域移动成本都是均匀的,但是A*不知道这些,并且浪费时间来探索它们。创建一个简单图(导航网,可视图,或者网格图的分层表示)可以帮助A*。

移动成本固定时,可视图产生的是最优路径,且A*运行很快,但是边存储耗费大量内存。网格允许移动成本有细微改变(地形斜坡惩罚用的危险区域等),边存储耗费内存少,但点存储耗费很多内存,而且A*可能很慢。导航网居于两者之间。在大块区域移动成本均匀时,它效果很好,而且允许移动成本的些微改变,还能产生合理的路径。这些路径并不总如可视图产生的一样短,但是通常都是合理的。分层地图采用多层表示来处理长距离内的大致路径,以及短距离内的详细路径。

你可以读读这篇很形象的文章,了解更多关于导航网的知识。注意这篇文章比较了:(a)仅保持可行多边形和仅保持导航点,(b)沿顶点走和沿多边形中心点走。这些大多是正交的。保持可行多边形有利于后期动态调整路径,但是并非所有的游戏都需要。使用顶点更有利于避免障碍,并且如果你采用了路径消除,还不会影响路径质量。如果没有路径消除,边的效果可能更好,所以考虑边或是边+顶点。

除了给网格地图构建一个独立的非网格表示,你也可以改变A*,使其更好得理解成本均匀分布的网格地图。可以参照跳点搜索在方格上加速A*的方法,以及Theta*在网格上生成非网格移动的方法。

1 4 收藏 评论

关于作者:hf_cherish

(新浪微博:@丫丫_Cherish) 个人主页 · 我的文章 · 11

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部