0

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

如果相邻的方格已经在打开列表中，请检查通往该方格的这条路径是否更好。换句话说，如果我们使用当前方块到达那里，检查那个方块的 G 分数是否更低。如果没有，不要做任何事情。

例子：

父级（已遍历）：O
分支：A、B、C

父（工作）：A
分支：B，D

打开的列表包含 A、B、C，现在是 D。

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

请澄清。

4

2 回答 2

3

基本 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*。从理论上讲，您永远不会高估任何链接的成本。这意味着您将始终找到最有效的路线，但会花费更长的时间来找到它，因为您将扩展更多节点。

从实际的角度使用它可以允许稍微不可接受的启发式（可以稍微高估的启发式）。您找到的路线很可能会稍微不理想，但对于游戏使用来说应该不会太糟糕。但是，计算变得更快，因为您不再扩展所有内容。我使用常规触发距离启发式方法在 1k*1k 地图上进行的一个（缓慢）实现花费了 6 分钟，但在增加时间 3 的情况下只需几秒钟。路线并没有太大的不同。将启发式时间设为 5 使路线基本上是直线并且速度更快，但无法使用。

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

因此，在您的示例中，它将 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 与 O 与 B 进行了比较。

于 2011-07-21T11:18:32.410 回答
1

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

给出的定义告诉我们比较 B 的 G 值（之前在工作节点为 O 时首次添加到打开列表时计算）和从开始到达 A 的成本 (O) 和到达成本的总和B 来自 A。

于 2011-07-21T11:24:17.140 回答