波束搜索#在主 A* 循环中，OPEN 集存储可能需要搜索以找到路径的所有节点。该束搜索是A的变化*这就使开集的大小有限制。如果该集合变得太大，则具有最坏机会提供良好路径的节点将被丢弃。一个缺点是你必须保持你的集合排序才能做到这一点，这限制了你选择的数据结构的种类。 迭代深化#迭代深化是许多 AI 算法中使用的一种方法，从近似答案开始，然后使其更准确。这个名字来自博弈树搜索，在那里你可以向前看一些移动（例如，在国际象棋中）。您可以尝试通过向前看更多动作来加深树。一旦你的答案没有太大变化或改进，你就认为你有一个很好的答案，当你再次尝试使它更准确时，它也不会改进。在 IDA* 中，“深度”是 我个人认为 IDA* 不需要在游戏地图上寻找路径。ID 算法往往会增加计算时间，同时减少内存需求。然而，在地图寻路中，“节点”非常小——它们只是坐标。我不认为不存储这些节点有什么大的好处。 加权 A*#在游戏中，我们经常将启发式乘以某个常数因子以使 A* 运行得更快。这就是所谓的在文献中。我们可以使用一些权重 f(p) = g(p) + w * h(p) 在大多数情况下，这在实践中似乎运作良好。Wilt 和 Ruml 的 AAAI 2012 论文何时加权 A* 失败？显示了一些没有的情况。 另一种思考方式是 Dijsktra's Algorithm 仅使用 ， 如果仅在路径的某些部分或地图的某些部分启发式太低，我们可以使用动态加权： f(p) = g(p) + w(p) * h(p) 有很多方法可以改变权重，但我在 1997 年写这些页面时并没有探索这个主题。当时我的直觉让我相信在接近开始时使用更高的权重会更好路径和接近终点的较低权重。那是因为我认为权重补偿了启发式太低，并且通常在路径开始时太低并且在路径末尾附近相当准确。然而，研究表明我的直觉是错误的。最好在路径的尽头附近施加重量。 Chen 和 Sturvetant 的 AAAI 2021 论文Necessary and Suffient Conditions for avoiding Reopenings in Best First Suboptimal Search with General Bounding Functions提出了两种方法pxWU，当您接近目标时，它会降低权重： f(p) = g(p) < (2*w - 1) * h(p) ? g(p) / (2*w - 1) + h(p) : (g(p) + h(p)) / w 和pxWD，当您接近目标时会增加重量： f(p) = g(p) < h(p) ? g(p) + h(p) : (g(p) + (2*w - 1) * h(p)) / w} 他们发现增加重量效果更好。他们还有一个交互式演示，您可以在其中尝试不同的加权方案。 带宽搜索#有些人可能会发现有关带宽搜索的两个属性很有用。这种变化假设这 您获得的另一个属性是，如果您可以删除 OPEN 集中的某些节点。只要 奇怪的是，您可以对这两个属性使用不同的启发式方法，结果仍然有效。您可以使用一种启发式方法来保证您的路径不会太糟糕，而另一种方法来确定要在 OPEN 集中删除什么。 注意：当我在 1997 年写这篇文章时，带宽搜索看起来可能很有用，但我从未使用过它，而且我在游戏行业也没有看到太多关于它的文章，所以我可能会删除这一部分。您可以在Google上搜索更多信息，尤其是从教科书中搜索。 双向搜索#您可以并行开始两次搜索，而不是从头到尾搜索——一次从头到尾，一次从头到尾。当他们相遇时，你应该有一个好的路径。 这是一个好主意，在某些情况下会有所帮助。双向搜索背后的想法是搜索结果在地图上呈扇形散开的“树”。一棵大树比两棵小树差很多，所以最好有两棵小搜索树。 该前到前变化的两个搜索链接在一起。该算法不是选择最佳的前向搜索节点 该重新定位方法在退让向前和向后方向上同时搜索。相反，它执行短时间的前向搜索，选择最佳的前向候选者，然后执行后向搜索——不是到起点，而是到那个候选者。一段时间后，它会选择一个最佳的后向候选，并执行从最佳前向候选到最佳后向候选的前向搜索。这个过程一直持续到两个候选人是同一点。 Holte、Felner、Sharon、Sturtevant 的 2016 年论文Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions是最近的结果，其中包含 A* 的近乎最优的双向变体。Pijls 和 Post 的 2009 年论文最短路径的另一种双向算法提出了一种不平衡的双向 A*，它比平衡的双向搜索运行得更快。 动态 A* 和终身规划 A*#有 A* 的变体允许在计算初始路径后改变世界。D* 旨在在您没有完整信息时使用。如果您没有所有信息，A* 可能会出错；D* 的贡献在于它可以在不花费太多时间的情况下纠正这些错误。LPA* 旨在在成本发生变化时使用。使用 A*，路径可能因地图更改而失效；LPA* 可以重用之前的 A* 计算来生成新路径。 然而，D* 和 LPA* 都需要大量空间——本质上你运行 A* 并保留它的内部信息（ 对于具有大量移动单位的游戏，您通常不想保留所有这些信息，因此 D* 和 LPA* 不适用。它们是为只有一个机器人的机器人设计的——你不需要为其他机器人的路径重用内存。如果您的游戏只有一个或少量单位，您可能需要调查 D* 或 LPA*。 跳转点搜索#许多加速 A* 的技术实际上都是关于减少节点数量。在具有统一成本的方形网格中，一次查看所有单个网格空间是一种浪费。一种方法是构建关键点（例如角点）的图形并将其用于寻路。但是，您不想预先计算航点图，请查看 Jump Point Search，这是 A* 的一种变体，可以在方形网格上向前跳过。当考虑当前节点的子节点可能包含在 OPEN 集中时，跳转点搜索会向前跳到从当前节点可见的远处节点。每一步都更昂贵，但它们的数量更少，从而减少了 OPEN 集中的节点数量。有关详细信息，请参阅此博客文章，此博客文章以获得很好的视觉解释，以及这个关于利弊的讨论。 另请参阅Rectangular Symmetry Reduction，它分析地图并将跳转嵌入到图形本身中。这两种技术都是为方形网格开发的。这是为六边形网格扩展的算法。 θ*#有时网格用于寻路是因为地图是在网格上制作的，而不是因为您实际上想要在网格上移动。如果给定关键点（例如角）图而不是网格，A* 会运行得更快并产生更好的路径。但是，如果您不想预先计算角点图，则可以使用 Theta*（在方形网格上运行的 A* 的变体）来查找不严格遵循网格的路径。在构建父指针时，如果有到该节点的视线，Theta* 将直接指向祖先，并跳过其间的节点。与路径平滑不同，它在 A* 找到路径后将路径弄直，Theta* 可以将这些路径分析为 A* 过程的一部分。这可能导致比将网格路径后处理为任意角度路径更短的路径。这篇文章是对算法的合理介绍；另请参阅Lazy Theta*。 Theta* 的想法也可能适用于导航网格。 另请参阅Block A*，它声称通过使用分层方法比 Theta* 快得多。 |
|
|
