3

我正在尝试使用 A* 算法使敌人节点跟随 C# 中的玩家节点。我已阅读教程并下载了一些 C# 示例。我的 A* 算法现在已经工作到一定程度了。它会在空旷的空间中跟随玩家,但在尝试追踪物体时会遇到障碍。

因此,当我的算法检查并朝 F 值最低的方向移动时,它可能会遇到死胡同,此时它需要向后追溯其步骤,但它不能因为我的代码告诉它先前检查过节点已关闭,无法移动,因此卡住了。

我如何重新计算一个封闭的节点来告诉我的算法可以以这种方式返回。

此外,如果我确实告诉我的算法返回到它自己,那么是什么阻止它再次返回到它刚刚来自的更好的节点?有效地反复在两个节点之间返回。

我看到它应该能够检查封闭列表中的一个节点并确定它在这个特定路径上是否更好,但我不确定它是如何完成的。

我正在使用的启发式方法。

G = Math.Abs(StartNodeX - TargetNodeX) + Math.Abs(StartNodeY - TargetNodeY)

H = Math.Abs(CurrentNodeX - TargetNodeX) + Math.Abs(CurrentNodeY - CurrentNodeY)

F = G + H

伪代码。

  1. 将所有相邻节点添加到打开列表
  2. 检查所有这些节点的最低 F 分数并将该节点添加到最佳路径列表
  3. 将所有选中的节点添加到封闭列表(它们都已被选中,不想再次检查它们)
  4. 重复直到达到目标
  5. 向最佳路径方向移动敌人 1 个节点
  6. 再重复一遍
4

4 回答 4

7

我如何重新计算一个封闭的节点来告诉我的算法可以这样返回?

你不这样做是因为它不好。最佳路径永远不会包括走进死胡同,然后又走回来!根据定义,这是次优路径。A* 算法找到最优路径。

如果我确实告诉我的算法返回到它自己,是什么阻止它再次返回到它刚刚来自的更好的节点;有效地反复在两个节点之间返回。

没有什么能阻止它。这就是为什么做你所描述的事情是一个坏主意。如果你这样做的时候很痛,那就不要这样做

我正在使用的启发式方法......

看起来很乱。

G 是从起点到目标的曼哈顿距离,H 是从当前点到目标的曼哈顿距离,F 是它们的总和。

首先,如果启发式是针对不允许对角线移动的方形网格,曼哈顿距离只是一个有效的度量。你允许对角线移动吗?如果你这样做了,那么这个启发式是错误的。请记住,启发式方法需要低估成本。如果你可以在任何地方沿对角线移动,那么曼哈顿距离就高估了成本。考虑改为使用欧几里得度量。

其次,从起点到目标的距离是一个常数,那么它是如何相关的,你为什么要把它加到任何东西上呢?看起来你说的是每条路径的成本都会增加从起点到目标的距离,这没有任何意义。

根据您的问题,我认为您不了解该算法及其工作原理。我的建议是在尝试实现它之前了解该算法的工作原理。这是英文的算法:

The closed set is an empty set of points.
The queue is an empty queue of paths, ordered by path cost.
Enqueue a path from the start to the start with zero cost.
START: 
If the queue is empty, then there is no solution.
The current path is the cheapest path in the queue.
Remove that path from the queue.
If the last step on the current path is closed then 
    the current path is necessarily bad. (Do you see why?)
    Discard it and go back to the START of the loop.
Otherwise, if the last step on the current path is the destination then
    the current path is the optimal path to the destination, so we're done.
Otherwise, we have the cheapest path *to the last 
    point in that path*. (Do you see why?) 
Therefore, every other path that could possibly go through that point is worse.
Therefore, close off that point. Add it to the closed set so that we can 
    automatically discard any future path that goes through that point.
For each possible direction from the last point of the current path,
    make a new path that extends the current path in that direction.
    The estimated cost of that new path is the known cost to get 
    to its end from the start, plus the estimated cost to get from
    its end to the destination.
    Enqueue the new path with that cost.
Go back to the START of the loop.

那有意义吗?

于 2012-04-28T15:46:13.390 回答
1

因此,如果我正确理解您的问题,这是基本 A* 算法不适合的情况。A* 告诉你,给定这个世界给我从 A 到 B 的最短路径。我假设这个世界正在发生变化。A* 不处理动态世界,因此如果您想使用 A*,唯一的解决方案是每次从头开始重新运行 A*。重置您的队列等。

现在有一些更好的解决方案,我将让您进一步探索。我已经链接了一篇论文和一些幻灯片,这些幻灯片向您展示了我为这些案例制定的一个解决方案。您还将在本文中找到对许多其他算法的参考。

http://www.cs.unh.edu/~ruml/papers/rtds-socs10.pdf

http://www.cs.unh.edu/~ruml/papers/rtds-socs10-talk.pdf

于 2012-04-28T15:34:46.047 回答
0

我到处跑,试图解决这里的旧问题。我希望这么晚了它仍然有帮助。

几个月前,我在 matlab 中解决了一个类似的问题。

G是你的问题。G 告诉您从起始位置沿路径移动的难度是什么,它不是启发式方法。它是可知的,你不需要估计它。

在您仅向 4 个方向之一移动的情况下,并且假设向左、向右、向上或向下移动同样容易,即您没有像“沼泽”这样更难移动的区域其他区域,你只需要计算你从哪里来的路径上的方块数量。

你的 G 在开阔地工作,因为曼哈顿距离(你的 G 度量)是畅通无阻的追逐中的最短路径,你只能在 4 个基本方向上移动。

考虑以下示例,您尝试从 A 到 B。根据您的等式,位置 T 将是 G = 4、H = 2 和 F = 4+2 = 6。

00000
00X00
00X00
00XT0
A0X0B

真正的 A* 路径将由 + 表示,其中 G=10、H=2 和 F=12。

0+++0
0+X+0
0+X+0
0+XT0
A+X0B

以这种方式计算 G 应该可以解决问题。

于 2013-12-01T03:04:17.030 回答
0

从维基百科你可以看到你的启发式函数需要被接受。可接受的启发式算法绝不能给出比真实距离更高的估计值。否则 A* 搜索将不起作用。

你的启发式是不可接受的。您应该找到不同的启发式方法。

于 2012-04-28T15:41:31.030 回答