启发式 / 开普饭

启发式函数h(n)告诉 A*从任何顶点到目标的最小成本的估计n。选择一个好的启发式函数很重要。

A* 对启发式算法的使用#

启发式可用于控制 A* 的行为。

一个极端，如果h(n)是0，那么只g(n)起一个作用，A*变成Dijkstra's Algorithm，保证找到最短路径。
如果h(n)始终低于（或等于）移动n到目标的成本，则保证 A* 找到最短路径。越低h(n)，节点 A* 扩展得越多，速度越慢。
如果h(n)恰好等于从n目标移动到目标的成本，那么 A* 将只遵循最佳路径，而不会扩展任何其他内容，使其速度非常快。尽管您无法在所有情况下都做到这一点，但您可以在某些特殊情况下做到这一点。很高兴知道在给定完美信息的情况下，A* 将表现完美。
如果h(n)有时大于从n目标移动的成本，则 A* 不能保证找到最短路径，但它可以运行得更快。
在另一个极端，如果h(n)相对于非常高g(n)，则仅h(n)起作用，并且 A* 变成 Greedy Best-First-Search。

所以我们有一个有趣的情况，我们可以决定我们想要从 A* 中得到什么。有了 100% 准确的估计，我们将很快得到最短路径。如果我们太低，那么我们将继续获得最短路径，但它会变慢。如果我们太高，那么我们放弃最短路径，但 A* 会跑得更快。

在游戏中，A* 的这个特性非常有用。例如，您可能会发现在某些情况下，您宁愿拥有“好的”路径而不是“完美的”路径。要在g(n)和之间移动平衡h(n)，您可以修改其中任何一个。

速度还是准确性？#

A* 根据启发式和成本函数改变其行为的能力在游戏中非常有用。可以利用速度和准确性之间的权衡来使您的游戏更快。对于大多数游戏，您并不真正需要两点之间的最佳路径。你需要一些接近的东西。您需要什么可能取决于游戏中发生的事情，或者计算机的速度。使用保证它永远不会高估成本的函数意味着它有时会大大低估成本。

假设您的游戏有两种类型的地形，平坦和山地，并且移动成本分别为 1 平地和 3 山，A* 将沿着平地搜索三倍于沿着山地搜索的距离。这是因为有可能有一条沿着平坦地形绕山而行的小路。您可以使用 1.5 作为两个地图空间之间的启发式距离来加速 A* 的搜索。然后A*会比较3和1.5，看起来不会像比较3比1那么糟糕。它对山地地形没有那么不满意，所以它不会花太多时间去寻找绕过它的方法。或者，您可以通过减少 A* 搜索绕山路径的次数来加速 A* 的搜索——告诉 A* 在山上的移动成本是 2 而不是 3。现在它沿着平坦地形搜索的距离只有两倍如沿山区地形。这两种方法都放弃了更快获得某些东西的理想路径。

速度和准确性之间的选择不一定是静态的。您可以根据 CPU 速度、进入寻路的时间比例、地图上的单位数量、单位的重要性、团队规模、难度级别或任何其他因素动态选择。使权衡动态的一种方法是构建一个启发式函数，假设穿越一个网格空间的最小成本为 1，然后构建一个可扩展的成本函数：

g'(n) = 1 + alpha * (g(n) - 1)

如果alpha为0，则修改后的代价函数将始终为1。在此设置下，地形代价完全被忽略，A*工作在简单的可通行/不可通行网格空间级别。如果alpha为 1，则将使用原始成本函数，您将获得 A* 的全部好处。您可以设置alpha介于两者之间的任何位置。

您还应该考虑从返回绝对最小成本的启发式转换为返回预期最小成本。例如，如果您的地图大部分是移动成本为 2 的草原，但地图上的某些空间是移动成本为 1 的道路，那么您可以考虑让启发式假设没有道路，然后返回2 * distance。

速度和准确性之间的选择不必是全局的。您可以根据地图某些区域的准确性的重要性动态选择一些内容。例如，在当前位置附近选择一条好的路径可能更重要，假设我们最终可能会在某个时刻重新计算路径或改变方向，那么为什么要对路径的远处部分保持准确呢？或者也许在地图的安全区域拥有最短路径并不那么重要，但是当偷偷经过敌方村庄时，安全和快速是必不可少的。

规模#

A* 计算f(n) = g(n) + h(n)。要添加两个值，这两个值需要处于相同的比例。如果g(n)以小时h(n)为单位，以米为单位，那么 A* 会考虑g或h太多或太少，你要么不会得到那么好的路径，要么你的 A* 运行得比它应该的慢。

精确启发式#

如果您的启发式恰好等于沿最佳路径的距离，您将看到 A* 扩展很少的节点，如下一节中所示的图表所示。A* 内部发生的事情是它f(n) = g(n) + h(n)在每个节点上进行计算。当h(n)完全匹配时g(n)，的值f(n)不会沿路径改变。所有不在正确路径上的节点将比正确路径上的节点具有更高的值f。由于 A*f在考虑了低值节点之前不会考虑高值f节点，因此它永远不会偏离最短路径。

预计算精确启发式#

构建精确启发式的一种方法是预先计算每对点之间的最短路径的长度。这对于大多数游戏地图来说是不可行的。但是，有一些方法可以近似这种启发式：

在细网格的顶部放置一个粗网格。预先计算任何一对粗网格位置之间的最短路径。
预先计算任意一对航路点之间的最短路径。这是粗网格方法的推广。

然后添加一个启发式方法h'来估计从任何位置到附近航点的成本。（如果需要，后者也可以预先计算。）最终的启发式将是：

h(n) = h'(n, w1) + 距离(w1, w2) + h'(w2, 目标)

或者，如果你想要一个更好的，但更昂贵的启发，评估上面所有对的w1，w2是接近分别为节点和目标。

线性精确启发式#

在特殊情况下，您可以在不预先计算任何内容的情况下使启发式精确。如果你有一张没有障碍物和慢地形的地图，那么从起点到目标的最短路径应该是一条直线。

如果您使用的是简单的启发式（不知道地图上的障碍物），它应该与精确的启发式相匹配。如果没有，那么您可能在规模或您选择的启发式类型方面有问题。

网格地图的启发式方法#

在网格上，可以使用众所周知的启发式函数。

使用与允许的移动相匹配的距离启发式：

在允许4 个移动方向的方形网格上，使用曼哈顿距离 (L ₁ )。
在允许8 个移动方向的方形网格上，使用对角线距离 (L _∞ )。
在允许任何移动方向的方形网格上，您可能需要也可能不需要欧几里得距离 (L ₂ )。如果 A* 在网格上寻找路径，但您不允许在网格上移动，您可能需要考虑地图的其他表示。
在允许6 个移动方向的六边形网格上，使用适用于六边形网格的曼哈顿距离。

将步长距离乘以步的最小成本。例如，如果您以米为单位进行测量，距离为 3 个方格，每个方格为 15 米，那么启发式将返回 3 ⨉ 15 = 45 米。如果您正在测量时间，距离是 3 个方格，并且每个方格至少需要 4 分钟才能穿过，那么启发式将返回 3 ⨉ 4 = 12 分钟。启发式返回的单位（米、分钟等）应与成本函数使用的单位相匹配。

曼哈顿距离#

方形网格的标准启发式是曼哈顿距离。查看您的成本函数并找到D从一个空间移动到相邻空间的最小成本。在简单的情况下，您可以设置D为 1。您可以在 4 个方向上移动的方形网格上的启发式应该是D曼哈顿距离的倍：

函数启发式（节点）=
    dx = abs(node.x - 目标.x)
    dy = abs(node.y - 目标.y)
    返回 D * (dx + dy)

你怎么选D？使用与您的成本函数相匹配的比例。对于最佳路径和“可接受”启发式，将 D 设置为相邻方块之间的最低成本。在没有障碍物的情况下，在移动成本最小为 D 的地形上，向目标移动一步应该增加gD 和减少hD。当您将两者相加时，f（设置为g + h）将保持不变；这是启发式和成本函数比例匹配的标志。您还可以通过增加 D 或降低最低和最高边缘成本之间的比率来放弃最佳路径以使 A* 运行得更快。

（注意：上图在启发式中添加了一个决胜局。）

对角线距离#

如果您的地图允许对角线移动，则需要不同的启发式方法。（4 东，4 北）的曼哈顿距离将为 8⨉D。但是，您可以简单地移动（4 东北），因此启发式应该是 4⨉D2，其中 D2 是对角移动的成本。

函数启发式（节点）=
    dx = abs(node.x - 目标.x)
    dy = abs(node.y - 目标.y)
    返回 D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)

这里我们计算如果你不能走对角线，你要走的步数，然后用对角线减去你节省的步数。有min(dx, dy)对角步骤，每一个都需要花费，D2但可以节省2⨉D非对角步骤。

当 D = 1 且 D2 = 1 时，这称为切比雪夫距离。当 D = 1 且 D2 = sqrt(2) 时，这称为八分距。

另一种写法是D * max(dx, dy) + (D2-D) * min(dx, dy). 帕特里克·莱斯特（Patrick Lester）以不同的方式编写它，使用if (dx > dy) (D * (dx-dy) + D2 * dy) else (D * (dy-dx) + D2 * dx). 这些都是等价的。

欧几里得距离#

如果你的单位可以以任何角度移动（而不是网格方向），那么你应该使用直线距离：

函数启发式（节点）=
    dx = abs(node.x - 目标.x)
    dy = abs(node.y - 目标.y)
    返回 D * sqrt(dx * dx + dy * dy)

但是，如果是这种情况，那么直接使用 A* 可能会遇到麻烦，因为成本函数g将与启发式函数不匹配h。由于欧几里德距离比曼哈顿或对角线距离短，您仍然会得到最短路径，但 A* 将需要更长的时间来运行：

欧几里得距离，平方#

我看过几个 A* 网页建议您使用距离平方来避免欧几里得距离中昂贵的平方根：

函数启发式（节点）=
    dx = abs(node.x - 目标.x)
    dy = abs(node.y - 目标.y)
    返回 D * (dx * dx + dy * dy)

不要这样做！这肯定会遇到规模问题。的比例g和h需要匹配，因为您将它们加在一起形成f. 当 A* 计算时f(n) = g(n) + h(n)，距离的平方将远高于成本g，您最终会得到高估的启发式。对于更长的距离，这将接近对g(n)无贡献的极端情况f(n)，并且 A* 将退化为贪婪的最佳优先搜索：

要尝试解决此问题，您可以缩小启发式方法。但是，您会遇到相反的问题：对于较短的距离，g(n)与 A*相比，启发式算法将太小，并且 A* 将降级为 Dijkstra 算法。

如果在分析后发现平方根的成本很大，请使用欧氏距离的快速平方根近似值或使用对角线距离作为欧氏距离的近似值。

多个目标#

如果你要搜索任何的几个目标，构建一个启发h'(x)是最小h1(x), h2(x), h3(x), ...哪里h1, h2, h3是启发式每附近景点。

一种思考方式是，我们可以将每个目标的新零成本边添加到新的图节点。通往该新节点的路径必须经过目标节点之一。

如果您想搜索所有多个目标的路径，最好的选择可能是 Dijkstra 算法，当您找到所有目标时提前退出。可能有 A* 的变体可以计算这些路径；我不知道。

如果您想搜索单个目标附近的位置，请使用 A* 搜索来查找通往目标区域中心的路径。在处理 OPEN 集中的节点时，当您拉出足够接近的节点时退出。

打破关系#

在一些网格地图中，有许多相同长度的路径。例如，在地形没有变化的平坦区域，使用网格会导致许多等长路径。A* 可能会探索具有相同f值的所有路径，而不是只有一个。

解决此问题的快速方法是调整g或h值。决胜局需要相对于顶点具有确定性（即，它不应是随机数），并且需要使f值不同。由于 A* 按f值排序，使它们不同意味着只会f探索其中一个“等效”值。

打破关系的一种方法是h稍微调整规模。如果我们f将其向下扩展，那么随着我们朝着目标前进，它会增加。不幸的是，这意味着 A* 更愿意扩展靠近起点的顶点而不是靠近目标的顶点。相反，我们可以h稍微向上扩展（甚至 0.1%）。A* 更愿意扩展靠近目标的顶点。

启发式 *= (1.0 + p)

p应该选择该因子以便p <（采取一步的最小成本）/（预期的最大路径长度）。假设您不希望路径长度超过 1000 步，您可以选择 p = 1/1000。（请注意，这略微破坏了启发式的“可接受性”，但在游戏中几乎无关紧要。）这种打破平局的推动的结果是 A* 探索的地图比以前少得多：

当然，当有障碍物时，它仍然需要探索以找到绕过它们的方法，但请注意，通过障碍物后，A* 探索的很少：

Steven van Dijk 建议更直接的方法是传递h给比较函数。当f值相等时，比较函数将通过查看来打破平局h。

另一种打破联系的方法是在启发式或边缘成本中添加一个确定性随机数。（选择确定性随机数的一种方法是计算坐标的散列。）h与上述调整相比，这打破了更多的联系。感谢 Cris Fuhrman 提出这个建议。

打破平局的另一种方法是更喜欢沿着从起点到目标的直线的路径：

dx1 = 当前.x - 目标.x
dy1 = 当前.y - 目标.y
dx2 = start.x - 目标.x
dy2 = start.y - 目标.y
交叉 = abs(dx1*dy2 - dx2*dy1)
启发式 += 交叉*0.001

此代码计算起始到目标向量和当前点到目标向量之间的向量叉积。当这些向量不对齐时，叉积会更大。结果是此代码将稍微偏向于从起点到目标沿着直线路径的路径。当没有障碍物时，A* 不仅探索较少的地图，而且路径看起来也很漂亮：

然而，因为这个决胜局更喜欢沿着从起点到目标的直线路径，所以在绕过障碍物时会发生奇怪的事情（注意路径仍然是最佳的；它看起来很奇怪）：

要以交互方式探索这个决胜局的改进，请参阅James Macgill 的 A* 小程序[或试试这面镜子或这面镜子]。使用“清除”清除地图，并选择地图对角的两个点。当您使用“经典A*”方法时，您会看到并列的效果。当您使用“Fudge”方法时，您将看到上述叉积添加到启发式中的效果。

另一种打破关系的方法是仔细构建您的 A* 优先级队列，以便具有特定值的新插入f总是比具有相同值的旧插入排名更好（更低）f。

打破网格关系的另一种方法是尽量减少转弯。x,y 从父节点到当前节点的变化告诉您移动的方向。对于从当前到邻居考虑的所有边，如果 x,y 的变化与从父节点到当前节点的变化不同，则给移动成本增加一个小惩罚。

在我自己的项目中，我使用“棋盘”方法。在广度优先搜索中，我改变了插入顺序，以便路径在水平和垂直步骤之间交替。在 Dijkstra 的算法和 A* 中，我改变了移动成本，以便路径在水平和垂直步骤之间交替。我有这两种黑客的代码示例和截图在我的A *实施指南。

上述对启发式或成本的修改是对潜在低效率的“创可贴”修复。当有许多同样好的路径时，就会出现连接，从而导致需要探索大量节点。考虑“更聪明地工作，而不是更努力地工作”的方法：

替代地图表示可以通过减少图中节点的数量来解决问题。将多个节点合并为一个，或者删除除重要节点之外的所有节点。矩形对称减少是在方形网格上执行此操作的一种方法；也看看“框架四叉树”。分层寻路使用具有很少节点的高级图来查找大部分路径，然后使用具有更多节点的低级图来细化路径。
有些方法不考虑节点的数量，但会减少访问的节点数量。跳转点搜索会跳过包含大量关系的大面积节点；它专为方形网格而设计。跳过链接添加跳过地图区域的“快捷方式”边缘。该ALPHA *算法（PDF）增加了一些深度优先搜索到A *的通常的广度优先的行为，所以它可以探索一条路径，而不是同时处理所有这些的。
边缘搜索 (PDF)通过加快节点处理来解决该问题。它不是保持 OPEN 集排序并一次访问一个节点，而是批量处理节点，仅扩展具有低 f 值的节点。这与HOT 队列方法有关。

近似启发式#

具有精确距离的启发式算法是使 A* 快速的理想选择，但通常不切实际。我们通常可以对图进行预处理以构建近似距离，并在 A* 启发式算法中使用该近似值。

ALT A*使用“地标”和三角不等式对寻路图进行预处理，以加快寻路速度。ALT 还做了一些其他的事情，但启发式改进是引起我注意的部分。它的实现非常简单，有时不到 15 行代码，并产生了令人印象深刻的加速。

“地标”这个名字有点误导。这些点需要放置在地图的外边缘。一些作者将其称为“差分启发式”。

具有里程碑意义的方法存储了大量可以压缩的数据。压缩差分启发式显示压缩地标数据的结果。您可以在同一空间中存储更多地标，从而获得改进的启发式值。

地标可能是更通用方法的特例。本文探讨了如何将地图转换为使用常规距离度量的地图。

距离预言机似乎是相关的，但我还没有研究它们。