algorithm - 了解 AStar 算法

Question

来自此链接:Link

If an adjacent square is already on the open list, check to see if this path to that square is a better one. In other words, check to see if the G score for that square is lower if we use the current square to get there. If not, don’t do anything.

示例:

parent(已经遍历):O
分支机构:A、B、C

父级(正在处理):A
分支机构:B、D

open list 包含 A、B、C 和现在的 D。

现在，上面引用中的粗体语句是在比较哪条路径，路径 A 到 B？ 即 A 与 B && O 与 B 的比较 或者 A 与 B 的比较 && A 与 D

请澄清。

Answer 1

基本 A* 是:

While we're not close enough to the / a destination
    Take the point that we have now, with the lowest expected total cost (so known cost up to this point plus estimated remaining cost).
    Calculate cost for all surrounding locations & add them back to the priority queue with their expected total cost.

return route that we followed to the closest point

在官方的 A* 术语中，G 分数是到达那里的成本。 H 分数是从那里到你想去的地方的估计。

极端情况是您的 H 分数总是高估；新分数(估算值 + 新成本)将始终低于前一个方 block 的估算值 + 成本，因此您将直奔目标。如果你的 H-score 总是低估(或者是 0，或者其他什么)，你总是更喜欢离你的出发点更近的方 block ，因为到目前为止它们的成本更低，所以你基本上会从那个位置进行填充。

您可以从理论角度或实践角度使用 A*。从理论上讲，您永远不会高估任何链接的成本。这意味着您总能找到最有效的路线，但会花费更长的时间，因为您将扩展更多的节点。

从实际的角度使用它允许稍微 Not Acceptable 启发式(可以略微高估的启发式)。您找到的路线很可能会略微不理想，但对于游戏使用来说应该不会太差。不过，计算速度会更快，因为您不再展开所有内容。我所做的一个(缓慢的)实现在 1k*1k map 上用常规的触发距离启发式算法花费了 6 分钟，但在增加时间 3 的情况下只用了几秒钟。路线并没有太大的不同。将启发式时间设置为 5 使路线基本上成为直线并且速度更快，但不可用。

WRT 你的直接问题: 这是您评估的第二个方 block 。您计划了从 O 到 A、B、C 的道路(每条路线都有给定的成本 G)。现在，假设有一条从 O 到 A 到 B 的高速公路，而不是从 O 到 B 的土路。这意味着通过 A 更快。扩展 A 时，它会查看所有周围的方 block ，如果它不在其中，则将成本 + 启发式方法添加到打开列表中。如果它在那里，它会查看新路线是否更快(降低 G 以到达那个方 block )，只有在这样的情况下，它才会替换它。

因此在您的示例中，它将 O->A->D 添加到列表中，然后检查 O->A->B 是否比 O->B 快。

-- 附录

开放列表:2/A(通过 O)、5/B(通过 O)、7/C(通过 O)

封闭列表:0/O(起源/无中生有)

选择 A，因为它是迄今为止成本最低的。然后，为 A 的每个邻居计算到达那里的成本。

• 如果已经有条目并且成本比我们目前所知的要低，请替换条目。
• 如果没有当前条目，请添加它。

在 A 上工作，到 B 的成本为 2，到 D 的成本为 3。通过 A 到 B 的成本为 4，当前条目为 5。因此我们替换它。 D 不在那里，所以我们添加它。

开放列表:4/B(通过 A)、5/D(通过 A)、7/C(通过 O)

封闭列表:0/O(起源/无)，2/A(通过 O)

因此我们将 A 与 B 与 O 与 B 进行了比较。