<font style="vertical-align: inherit;"><font style="vertical-align: inherit;">地图表示(寻路思想)</font></font>
在本文档的大部分内容中，我假设 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 部分和源代码）。
环绕图#
如果您的世界是球形或环形的，则对象可以从地图的一端“环绕”到另一端。最短路径可以位于任何方向，因此必须探索所有方向。如果使用网格，您可以调整启发式考虑环绕。而不是abs(x1 - x2)您可以使用min(abs(x1 - x2), (x1+mapsize) - x2, (x2+mapsize) - x1). 这将采用min三个选项：要么留在地图上不回绕，x1在左侧时回绕，或x2在左侧时回绕。你会对每个环绕的轴做同样的事情。本质上，您假设地图与其自身的副本相邻来计算启发式。
连接组件#
在某些游戏地图中，源和目的地之间没有路径。如果您要求 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 在这里，或这篇论文.
跳过链接#
从网格构建的寻路图通常为每个位置分配一个顶点，并为从一个位置到相邻位置的每个可能的移动分配一条边。边不限于在相邻顶点之间。“跳过链接”或“快捷链接”是非相邻顶点之间的边。它用于缩短寻路过程。
跳过链接的移动成本应该是多少？有两种方法：
- 使成本与最佳路径的移动成本相匹配。这保留了 A* 的良好属性，例如寻找最佳路径。为了让 A* 朝着正确的方向推进，通过将跳过链接的成本降低 1% 左右来打破跳过链接和常规链接之间的联系。
- 使成本与启发式成本相匹配。这会对性能产生更大的影响，但您会放弃最佳路径。
添加跳过链接是分层地图的近似。它需要较少的努力，但通常可以为您带来许多相同的性能优势。
对于地牢房间和走廊网格地图，矩形对称减少和跳跃点搜索提供了两种不同的方法来构建跳过链接。矩形对称减少静态地构建额外的边（他们称之为宏边），然后使用标准图形搜索；作为图搜索算法的一部分，跳转点搜索动态地构建更长的边。对于路线图和其他类型的图表，Contraction Hierarchies值得一看；看到这篇论文或这个图书馆。当我在 1997 年写这个页面时，我不知道收缩层次结构，或者我会使用这个术语而不是组成术语“跳过链接”。
航点#
一个航点是沿着一条路径的一个点。航点可以特定于每条路径或成为游戏地图的一部分。航点可以手动输入或自动计算。在许多即时战略游戏中，玩家可以通过按住 Shift 键的方式手动添加特定路径的航点。当沿路径自动计算时，航路点可用于压缩路径表示。地图设计者可以手动向地图添加航点（或“信标”）以标记沿良好路径的位置，或者可以使用算法在地图上自动标记航点。
由于跳过链接的目标是在使用这些链接时加快寻路速度，因此跳过链接应放置在设计者放置的航路点之间。这将使他们的利益最大化。
如果航路点不是太多，可以预先计算每对航路点之间的最短路径（使用所有对最短路径算法，而不是 A*）。常见的情况是一个单元沿着自己的路径直到到达一个航路点，然后它将沿着预先计算的航路点之间的最短路径，最后它会离开航路点高速公路并沿着自己的路径到达目标。
使用带有虚假成本的航路点或跳过链接可能会导致次优路径。有时可以在后处理步骤或移动算法中消除不良路径。
图形格式建议#
首先在您已经使用的游戏世界表示上进行寻路。如果这不令人满意，请考虑将游戏世界转换为不同的寻路表示。
在许多网格游戏中，有大面积的地图具有统一的移动成本。A* 不“知道”这一点，并且浪费精力探索它们。创建更简单的图形（导航网格、可见性图形或网格图的分层表示）可以帮助 A*。
该可视性图表示产生最佳路径时，运动成本是恒定的，并允许A *，以相当快地运行，但可以使用大量内存的边缘。网格允许移动成本（地形、坡度、危险区域的惩罚等）的细微变化，边缘使用很少的内存，但节点使用大量内存，并且寻路可能很慢。导航网格介于两者之间。当移动成本在较大区域中保持不变时，它们运行良好，允许移动成本存在一些变化，并产生合理的路径。路径并不总是像可见性图表示那样短，但它们通常是合理的。分层映射 使用多层次的表示来处理长距离的粗路径和短距离的详细路径。
您可以在这篇插图详尽的文章 中阅读有关导航网格的更多信息。请注意，这篇文章正在比较 (a) 保持可步行的多边形与仅保留导航点，以及 (b) 沿顶点移动与沿多边形中心移动。这些大多是正交的。保持可行走的多边形有助于稍后动态调整路径，但并非在所有游戏中都需要。使用顶点更适合避障，如果您使用路径平滑，它不会对路径质量产生负面影响。如果没有路径平滑，边的性能可能会更好，因此请考虑边或边 + 顶点。
构建网格地图的单独非网格表示的另一种方法是使用 A* 的变体，它可以更好地理解具有统一成本的网格地图。请参阅跳转点搜索以加快方形网格上的 A* 和Theta*以在网格上生成非网格移动。