关于寻路算法的一些思考（7）：地图表示

作者: C_GO流媒体后台开发 | 来源:发表于2018-10-07 13:00 被阅读35次

本文由伯乐在线 - hf_cherish 翻译，黄利民校稿。未经许可，禁止转载！
英文出处：theory.stanford.edu。欢迎加入翻译组。

本系列：

在本系列文档大部分内容中，我都假设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个拐角点（顶点），则至多有N²条边。下图展示了这个问题：

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

可视图的另一个缺陷是，每次调用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*在网格上生成非网格移动的方法。