当前位置：文江博客话题详情

了解AStar算法

发布于 2024-11-25 21:01:25 字数 621 浏览 2 评论 0原文

通过此链接：链接< /a>

如果相邻的方格已在打开列表中，请检查是否通往那个广场的这条路是一条更好的路。换句话说，检查一下如果我们使用当前方块，该方块的 G 分数较低到达那里。如果没有，请不要执行任何操作。

示例：

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

父级（正在处理）：A
分支：B、D

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

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

请澄清。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

枫林﹌晚霞¤ 2024-12-02 21:01:25

基本 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 上工作，到 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。

Basic A* is:

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

In the official A* terminology, G-score is the cost to get there. H-score is the estimate to get from there to where you want to go.

Extremes are if your H-score always overestimates; the new score (estimate + new cost) will then always be lower than the previous square's estimate + cost, so you'll beeline to the target. If your H-score always underestimates (or is 0, or whatever) you'll always prefer squares closer to your point of departure, as they'll have a lower cost so far, so you'll basically floodfill from that position.

You can use A* from a theoretical point of view or from a practical point of view. Theoretically, you may never overestimate the cost of any link. That means that you will always find the most efficient route, but will take longer finding it as you'll expand a lot more nodes.

Using it from the practical point of view allows slightly-inadmissible heuristics (ones that can overestimate slightly). The route you find will most likely be slightly unoptimal but shouldn't be too bad for game use. The calculations get way faster though, since you don't expand everything anymore. One (slow) implementation I had made took 6 minutes across a 1k*1k map with a regular trig distance heuristic but only a few seconds with that augmented times 3. The routes weren't too different. Making the heuristic times 5 made the routes basically a beeline & much faster still, but unusably so.

WRT your direct question:
It's the second square you evaluate. You have the roads from O to A,B,C planned (with a given cost G for each of those routes). Now, suppose there's a highway from O through A to B, instead of a dirt road from O to B. That means that going through A is faster. When expanding A it looks at all surrounding squares and adds the cost + heuristic to the open list if it wasn't in there already. If it was in there, it sees if the new route is faster (lower G to get to that square) and only if so, does it replace it.

So in your example, it adds O->A->D to the list and then checks if O->A->B is faster than O->B.

-- addendum

Open list: 2 / A (through O), 5 / B (through O), 7 / C (through O)

Closed list: 0 / O (origin / through nothing)

Take A as it's the lowest cost so far. Then, for each neighbor of A calculate the cost to get there.

If there's an entry for it already and the cost is lower than we know so far, replace the entry.
If there's no current entry, add it.

Working on A, with roads of cost 2 to B and 3 to D. Going to B through A has a cost of 4, where the current entry is 5. So we replace it. D isn't in there, so we add it.

Open list: 4 / B (through A), 5 / D (through A), 7 / C (through O)

Closed list: 0 / O (origin / through nothing), 2 / A (through O)

So we compared A to B versus O to B.

回复收藏 0 原文