了解Astar算法实现

Question

从这个链接：http://www.policyalmanac.org/games/aStarTutorial.htm

如果相邻的广场已经开放列表中，选中这条道路是否 到广场是一个更好的。换句话说，如果我们使用当前的方块 到达那里，如果该方块的G分数较低，请查看 。否则，不要做任何事情。

实施例：

父（已经遍历）：o
分支：A，B，C

父（工作）：甲
分行：B，d

打开清单包含A，B，C和现在D.

现在，上面引用中的大胆陈述是比较哪条路径，路径A到B？ 即 A的比较到B & & Ò到B OR 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分总是高估;新的分数（估计值+新的成本）将总是低于先前的平方的估计值+成本，因此您将直接到达目标。如果你的H分总是低估（或者是0或者其他），你总是会选择离你的出发点更近的方格，因为他们到目前为止成本更低，所以你基本上会从那个位置进行填充。

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

从实际的角度来看，使用它可以允许稍微不允许的启发式（可以稍微高估）。你发现的路线很可能会稍微不理想，但对于游戏使用来说不应该太糟糕。虽然计算速度更快，因为你不再扩展一切。我所做的一个（缓慢的）实现花了6分钟在1k * 1k的地图上进行，并且使用了常规的触发距离启发式算法，但是只有几秒钟的时间增加了3次。这些路线并没有太大的差别。使启发式时间5使得路线基本上仍然更快，但无法如此。

WRT你的直接问题： 这是你评估的第二个平方。你有从O到A，B，C规划的道路（每条路线的给定成本G）。现在，假设从O到A到B的高速公路，而不是从O到B的土路。这意味着通过A的速度更快。扩展时，它会查看所有周围的正方形，并将开销列表的成本+启发式添加到已打开的列表中。如果它在那里，它会看到新的路线是否更快（降低到达那个方格），只有这样，它才能取代它。

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

- 补遗

打开清单：2/A（通过O），5/B（通过O），7/C（通过O）

封闭列表：0/O（原点/通过无）

拿A，因为它是目前为止成本最低的。然后，A的每个邻居计算到达那里的成本。

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

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

打开清单：4/B（通过A），5/d（通过A），7/C（通过O）

封闭列表：0/O（原点/通过任何操作），2/A （通过O）

所以我们比较了A到B对O2至B.

Answer 2

那么，如果我们是在节点A的工作，我们正在考虑它的邻居。假设我们现在正在考虑B节点（它在openList中）。

给出的定义告诉我们比较B的G值（当工作节点为O时，它首次添加到打开列表时的先前计算值）和从开始（O）到达A的成本总和从A到达B的费用。