|
在本文档的大部分内容中，我假设 A* 用于某种网格，其中给 A* 的“节点”是网格位置，而“边”是您可以从网格位置行进的方向。但是，A* 旨在处理任意图形，而不仅仅是网格。有多种地图表示可以与 A* 一起使用。 地图表示可以在性能和路径质量上产生巨大的差异。 寻路算法往往比线性算法更糟糕：如果将旅行所需的距离加倍，则找到路径所需的时间将增加一倍以上。你可以把寻路作为搜索某些区域就像一个圆，当圆的直径双打，它拥有4倍的区域。通常，地图表示中的节点越少，A* 的速度就越快。此外，您的节点与单位将移动到的位置越接近，您的路径质量就会越好。 用于寻路的地图表示不必与用于游戏中其他事物的表示相同。但是，使用相同的表示是一个很好的起点，直到您发现需要更好的路径或更高的性能。 网格#网格地图使用将世界统一细分为小的规则形状，有时称为“瓷砖”。常用的网格有方形、三角形和六边形。网格简单易懂，很多游戏都用它们来表示世界；因此，我在本文档中重点介绍了它们。  我为BlobCity使用了网格，因为每个网格位置的移动成本都不同。如果您的移动成本在大面积空间中是统一的（如我在本文档中使用的示例），那么使用网格可能会非常浪费。当它可以跳过大区域到另一侧时，没有必要让 A* 一次移动一步。网格上的寻路也会产生网格上的路径，可以对其进行后处理以消除锯齿状运动。但是，如果您的单位不受限制在网格上移动，或者您的世界甚至不使用网格，那么在网格上寻路可能不是最佳选择。 瓷砖运动即使在网格中，您也可以选择用于移动的图块、边和顶点。瓷砖是默认选择，特别是对于单位只移动到瓷砖中心的游戏。在此图中，A 处的单位可以移动到任何标记为 B 的位置。您可能还希望允许对角移动，但移动成本相同或更高。 如果您使用网格进行寻路，您的单位不受网格限制，并且移动成本是统一的，则您可能希望通过从一个节点直线移动到远处一个节点，并且在两者之间没有障碍的情况下拉直路径他们俩。 边缘移动如果您的单位可以在网格空间内的任何位置移动，或者如果图块很大，请考虑边缘或顶点是否更适合您的应用程序。 一个单位通常在其中一个边缘（通常在中间）进入瓷砖并在另一个边缘离开瓷砖。在瓷砖上寻路时，单位移动到瓷砖的中心，但在边缘上寻路时，单位将直接从一个边缘移动到另一个边缘。我写了一个边缘之间道路绘制的java小程序演示；这可能有助于说明如何使用边缘。 顶点运动网格系统中的障碍物通常在顶点处具有角。绕过障碍物的最短路径是绕过拐角。通过在顶点上寻路，该单元从一个角移动到另一个角。这会产生最少浪费的运动，但需要调整路径以考虑单元的大小。 多边形地图#最常见的网格替代方法是使用多边形表示。如果跨大区域的移动成本是统一的，并且您的单位可以直线移动而不是跟随网格移动，则您可能需要使用非网格表示。即使您的游戏将网格用于其他事物，您也可以使用非网格图进行寻路。 这是一种多边形地图表示的简单示例。在这个例子中，单位需要绕过两个障碍物：  想象一下你的单位将如何在这张地图中移动。最短路径将在障碍物的角落之间。所以我们选择那些角（红色圆圈）作为关键的“导航点”来告诉 A*；这些可以在每次地图更改时计算一次。如果您的障碍物在网格上对齐，导航点将与网格的顶点对齐。另外，寻路的起点和终点需要在图中；这些在每次调用 A* 时添加一次。 除了导航点，A*还需要知道哪些点是相连的。简单的算法是构建一个可见性图：可以相互看到的点对。简单的算法可能适合您的需求，尤其是在游戏过程中地图没有变化的情况下，但如果简单算法太慢，您可能需要更复杂的算法。此外，由于我们已将起点和终点导航点添加到图形中，因此我们会检查从这些导航点到现有顶点以及彼此之间的视线，并在需要的地方添加边。 A* 需要的第三条信息是点之间的旅行时间。如果您的单位在网格上移动，这将是曼哈顿距离或对角网格距离，或者如果它们可以直接在导航点之间移动，则为直线距离。 A* 然后将考虑从导航点到导航点的路径。粉红色的线就是这样一种路径。这比寻找从网格点到网格点的路径要快得多，当您只有几个导航点而不是许多网格位置时。当途中没有障碍物时，A* 会做得很好——起点和终点由一条边连接，A* 会立即找到那条路径，而无需扩展任何其他导航点。即使有障碍物需要考虑，A* 也会从一个角落跳到另一个角落，直到找到最佳路径，这仍然比寻找从一个网格位置到另一个位置的路径要快得多。 维基百科有更多关于机器人文献中的可见性图。这个幻灯片也是一个很好的介绍。 管理复杂性上面的例子比较简单，图形也很合理。在一些具有大量开放区域或长走廊的地图中，可见性图的问题变得很明显。连接每对障碍角的主要缺点是，如果有 N 个角（顶点），则最多有 N 2 条边。这个例子演示了这个问题：  这些额外的边主要影响内存使用。与网格相比，这些边提供了“捷径”，大大加快了寻路速度。有一些算法可以通过去除冗余边来简化图。但是，即使去除了冗余，仍然会有大量的边。 可见性图的另一个缺点是，每次调用 A* 时，我们必须将开始/结束节点及其新边添加到图中，然后在找到路径后将其删除。节点很容易添加，但添加边需要从新节点到所有现有节点的视线，这在大地图中可能会很慢。一种优化是只查看附近的节点。另一种选择是使用减少的可见性图来删除与两个顶点都不相切的边（这些边永远不会在最短路径中）。 导航网格#我们可以用不重叠的多边形来表示可步行区域，而不是用多边形表示障碍物，也称为导航网格。可步行区域可以附加附加信息（例如“需要游泳”或“移动成本 2”）。障碍不需要存储在这种表示中。 前面的例子变成了这样：  然后我们可以像对待网格一样对待它。与网格一样，我们可以选择使用多边形中心、边或顶点作为导航点。 多边形运动与网格一样，每个多边形的中心为寻路图提供了一组合理的节点。此外，我们必须添加开始和结束节点，以及我们所在多边形中心的一条边。在这个例子中，黄色路径是我们通过多边形中心使用探路者找到的路径，粉红色的路径是理想的路径。  可见性图表示将产生粉红色路径，这是理想的。使用导航网格可以使地图易于管理，但路径质量会受到影响。我们可以通过平滑它使路径看起来更好。 多边形边缘移动通常不需要移动到多边形的中心。相反，我们可以穿过相邻多边形之间的边缘。在这个例子中，我选择了每条边的中心。黄色路径是我们通过边缘中心的探路者找到的路径，它与理想的粉红色路径相当。  您可以沿边缘选取更多点以生成更好的路径，但成本会增加。 多边形顶点移动绕过障碍物的最短路径是绕过拐角。这就是我们使用角来表示可见性图的原因。我们可以将顶点与导航网格一起使用：  在这个例子中，只有一个障碍。当我们需要绕过障碍物时，黄色路径穿过一个顶点，就像粉色（理想）路径一样。然而，虽然可见性图方法会从起点到障碍物的角落有一条直线，但导航网格增加了一些步骤。这些步骤通常不应通过顶点，因此路径看起来不自然，具有“贴墙”行为。 混合运动每个多边形的哪些部分可以作为寻路的导航点没有任何限制。您可以沿边添加多个点，顶点也是好点。多边形中心很少有用。这是一个同时使用边缘中心和顶点的混合方案：  请注意，要绕过障碍物，路径会通过一个顶点，但在其他地方，它可以通过边缘中心。 路径平滑只要移动成本恒定，路径平滑对生成的路径来说相当容易。算法很简单：如果从导航点i到点i+2有视线，则移除点i+1。重复此操作，直到路径中相邻点之间没有视线。 剩下的只是绕过障碍物角落的导航点。这些是导航网格的顶点。如果使用路径平滑，则无需使用边缘或多边形中心作为导航点；只使用顶点。 在上面的例子中，路径平滑会将黄色路径变成粉红色路径。然而，探路者不知道这些较短的路径，所以它的决定不会是最优的。缩短在近似地图表示（导航网格）中找到的路径并不总是产生与在更精确表示（可见性图）中找到的路径一样好的路径。 分层的#平面地图的表示只有一个级别。很少有游戏只有一个级别——通常有一个“瓷砖”级别，然后是一个“子瓷砖”级别，其中对象可以在一个瓷砖内移动。然而，寻路只发生在更大的层次上是很常见的。您还可以添加更高级别，例如“房间”。 地图表示中的节点越少，寻路速度越快。减少问题的一种方法是进行多级搜索。例如，要从您家到另一个城市的某个地点，您会找到从椅子到汽车、从汽车到街道、从街道到高速公路、从高速公路到城市边缘的路径，从那里到另一个城市，然后到一条街道，到一个停车场，最后到目的地大楼的门口。这里有几个级别的搜索：
将问题分成多个级别可以让您忽略大部分选择。当从一个城市移动到另一个城市时，考虑沿途每个城市的每条街道是相当乏味的。相反，你忽略所有这些，只考虑高速公路。问题变得小而易于管理，解决起来也变得很快。 分层地图在其表示中有许多级别。异构层次结构通常具有固定数量的级别，每个级别具有不同的特征。例如，Ultima V 有一张“世界”地图，上面有城市和地牢。您可以进入城市或地牢并进入第二个地图级别。此外，还有世界的“层”相互叠加，形成三层层次结构。级别可以是不同的类型（平铺网格、可见性、导航网格、航点）。同质层次结构具有任意数量的级别，每个级别都具有相同的特征。四叉树和八叉树可以被认为是同构的层次结构。 在分层地图中，寻路可能发生在多个级别。例如，如果一个 1024x1024 的世界被划分为 64x64 个“区域”，那么找到一条从玩家位置到该区域边缘的路径，然后从一个区域到另一个区域直到到达所需区域，然后从该区域的边缘找到一条路径可能是合理的。该区域到所需的位置。在较粗略的层次上，可以更容易地找到长路径，因为探路者不会考虑所有细节。当玩家实际走过每个区域时，可以再次调用探路者以找到穿过该区域的短路径。通过保持较小的问题规模，探路者可以运行得更快。 您可以对 A* 等图形搜索算法使用多个级别，但不需要在每个级别使用相同的算法。对于小级别，您可以预先计算所有节点对之间的最短路径（使用 Floyd-Warshall 或其他算法）。一般来说，分层地图中的寻路不会产生最优路径，但它们通常很接近。 类似的方法是使用不同的分辨率。首先，绘制一条低分辨率的路径。当您接近某个点时，以更高的分辨率细化路径。这种方法可以与路径拼接一起使用，以避免移动障碍物。 一些可阅读的论文：Near-Optimal Hierarchical Pathfinding (HPA*)在网格上构建了一个两级层次结构，Pathfinding for Dragon Age:Origins解释了商业游戏中使用的几种层次方法，Ultrafast shortest-path queries with linear-time preprocessing通过将“交通节点”用于道路图 [PDF]、游戏中网格地图的交通节点、分层 A*：有效搜索抽象层次、道路网络中的路线规划（Dominic Schultes 的博士论文）、分层注释 A*（第 1 部分）和第 2 部分和源代码）。 环绕图#如果您的世界是球形或环形的，则对象可以从地图的一端“环绕”到另一端。最短路径可以位于任何方向，因此必须探索所有方向。如果使用网格，您可以调整启发式考虑环绕。而不是 连接组件#在某些游戏地图中，源和目的地之间没有路径。如果您要求 A* 查找路径，它最终会在确定没有路径之前探索图形的很大子集。如果可以预先分析地图，请用不同的标记标记每个连接的子图。然后，在寻找路径之前，检查源和目标是否都在同一个子图中。如果没有，那么您就知道它们之间没有路径。分层寻路在这里也很有用，尤其是在子图之间存在单向边的情况下。 路线图#如果您的单位只能在道路上移动，您可能需要考虑为 A* 提供道路和交叉路口信息。每个交叉点将是图中的一个节点，每条道路将是一条边。A* 将找到从交叉点到交叉点的路径，这比使用网格表示要快得多。 对于某些应用程序，您的单位可能不会在交叉路口开始和结束。为了处理这种情况，每次运行 A* 时，您都需要修改节点/边图（这与我们在可见性图和导航网格地图表示中使用的技术相同）。添加起点和终点作为新节点，并在这些点与其最近的交点之间添加边。寻路后，从图中删除这些额外的节点和边，以便图准备好用于下一次 A* 调用。 在这个图中，交叉点成为 A* 的寻路图中的节点。边是节点之间的道路，这些边应该被赋予沿着每条道路的行驶距离。在“道路作为边”框架中，您可以将单向道路合并为图中的单向边。 如果你想为转弯分配成本，你可以稍微扩展框架：节点不是位置，而是将节点视为 <location, direction> 对（状态空间中的一个点），其中方向指示您所在的方向当你到达那个位置时面对。将从 X 到 Y 的边替换为从 <X, dir> 到 <Y, dir> 的边来表示直线驱动，将 <X, dir1> 替换为 <X, dir2> 来表示“转弯”。每个边表示无论是直线行驶或转弯，但不能同时使用。然后，您可以将成本分配给表示转弯的边。 如果您还需要考虑转弯限制，例如“仅右转弯”，您可以使用此框架的变体，其中始终组合两种类型的边。每条边代表一个可选的转弯，然后是直线驱动。在此框架中，您可以表示诸如“您只能向右转”之类的限制：包括从 <X, 北 > 到 <Y, 北> 的边以直行，以及从 <X, 北> 到 <Z, 东> 的边> 用于右转，然后是驱动器，但不要包括 <X, north> 向西的任何东西，因为这意味着左转，并且不包括任何向南的东西，因为这意味着 U 形转弯。 在此框架中，您可以模拟一个大城市市中心，其中有单向街道、某些交叉路口的转弯限制（通常禁止掉头，有时禁止左转）和转弯成本（模拟减速和等待在你右转之前的行人）。与网格地图相比，A* 可以相当快地在道路图环境中找到路径，因为每个图节点的选择很少，并且地图中的节点相对较少。 对于大型路线图，请务必阅读Goldberg 和 Harrelson关于 ALT（A*、地标、三角不等式）的论文（PDF 在这里，或这篇论文. 跳过链接#从网格构建的寻路图通常为每个位置分配一个顶点，并为从一个位置到相邻位置的每个可能的移动分配一条边。边不限于在相邻顶点之间。“跳过链接”或“快捷链接”是非相邻顶点之间的边。它用于缩短寻路过程。 跳过链接的移动成本应该是多少？有两种方法：
添加跳过链接是分层地图的近似。它需要较少的努力，但通常可以为您带来许多相同的性能优势。 对于地牢房间和走廊网格地图，矩形对称减少和跳跃点搜索提供了两种不同的方法来构建跳过链接。矩形对称减少静态地构建额外的边（他们称之为宏边），然后使用标准图形搜索；作为图搜索算法的一部分，跳转点搜索动态地构建更长的边。对于路线图和其他类型的图表，Contraction Hierarchies值得一看；看到这篇论文或这个图书馆。当我在 1997 年写这个页面时，我不知道收缩层次结构，或者我会使用这个术语而不是组成术语“跳过链接”。 航点#一个航点是沿着一条路径的一个点。航点可以特定于每条路径或成为游戏地图的一部分。航点可以手动输入或自动计算。在许多即时战略游戏中，玩家可以通过按住 Shift 键的方式手动添加特定路径的航点。当沿路径自动计算时，航路点可用于压缩路径表示。地图设计者可以手动向地图添加航点（或“信标”）以标记沿良好路径的位置，或者可以使用算法在地图上自动标记航点。 由于跳过链接的目标是在使用这些链接时加快寻路速度，因此跳过链接应放置在设计者放置的航路点之间。这将使他们的利益最大化。 如果航路点不是太多，可以预先计算每对航路点之间的最短路径（使用所有对最短路径算法，而不是 A*）。常见的情况是一个单元沿着自己的路径直到到达一个航路点，然后它将沿着预先计算的航路点之间的最短路径，最后它会离开航路点高速公路并沿着自己的路径到达目标。 使用带有虚假成本的航路点或跳过链接可能会导致次优路径。有时可以在后处理步骤或移动算法中消除不良路径。 图形格式建议#首先在您已经使用的游戏世界表示上进行寻路。如果这不令人满意，请考虑将游戏世界转换为不同的寻路表示。 在许多网格游戏中，有大面积的地图具有统一的移动成本。A* 不“知道”这一点，并且浪费精力探索它们。创建更简单的图形（导航网格、可见性图形或网格图的分层表示）可以帮助 A*。 该可视性图表示产生最佳路径时，运动成本是恒定的，并允许A *，以相当快地运行，但可以使用大量内存的边缘。网格允许移动成本（地形、坡度、危险区域的惩罚等）的细微变化，边缘使用很少的内存，但节点使用大量内存，并且寻路可能很慢。导航网格介于两者之间。当移动成本在较大区域中保持不变时，它们运行良好，允许移动成本存在一些变化，并产生合理的路径。路径并不总是像可见性图表示那样短，但它们通常是合理的。分层映射 使用多层次的表示来处理长距离的粗路径和短距离的详细路径。 您可以在这篇插图详尽的文章 中阅读有关导航网格的更多信息。请注意，这篇文章正在比较 (a) 保持可步行的多边形与仅保留导航点，以及 (b) 沿顶点移动与沿多边形中心移动。这些大多是正交的。保持可行走的多边形有助于稍后动态调整路径，但并非在所有游戏中都需要。使用顶点更适合避障，如果您使用路径平滑，它不会对路径质量产生负面影响。如果没有路径平滑，边的性能可能会更好，因此请考虑边或边 + 顶点。 构建网格地图的单独非网格表示的另一种方法是使用 A* 的变体，它可以更好地理解具有统一成本的网格地图。请参阅跳转点搜索以加快方形网格上的 A* 和Theta*以在网格上生成非网格移动。 |
|
|
