问题标签 [a-star]

我们能否让人们以每种语言发布 A* 寻路算法的简单优化实现代码？

这主要是为了好玩和玩 stackoverflow 本身的能力......虽然我实际上有兴趣获得一个 ActionScript 3 版本。

但想法是，即使创建了不同的编程语言，这个“问题”也将在未来不断更新！

我不知道在网上还有其他地方可以看到伪代码“翻译”成许多（更不用说每种）不同的语言。似乎它是一个有价值的资源，虽然不一定是这个网站的设计目的，但尝试一下并看看它是否是一个可以使用 stackoverflow 的有价值的东西并没有什么坏处！

我在我的一本 AI 书籍中读到，在模拟或游戏中用于寻路的流行算法（A-Star、Dijkstra）也用于解决著名的“15 谜题”。

谁能给我一些关于如何将 15 谜题简化为节点和边图的指示，以便我可以应用其中一种算法？

如果我将图中的每个节点都视为游戏状态，那么那棵树不会变得很大吗？或者这只是这样做的方法吗？

我正在查看 A* 寻路算法的定义，它在不同地方的定义似乎有所不同。

不同之处在于遍历节点的后继节点时执行的操作，并发现后继节点在封闭列表中。

• 一种方法（由Wikipedia和本文建议）说：如果继任者在封闭列表中，则忽略它
• 另一种方法（例如，在此处和此处建议）说：如果继任者在封闭列表中，请检查其成本。如果它高于当前计算的分数，则从封闭列表中删除该项目以供将来检查。

我很困惑 - 哪种方法是正确的？直觉上，第一个对我来说更有意义，但我想知道定义上的差异。其中一个定义是错误的，还是它们在某种程度上是同构的？

我在（非常少的）空闲时间制作了一个 roguelike。每个级别基本上都是几个由路径连接在一起的矩形房间。然而，我希望房间之间的路径看起来自然且多风。例如，我不会考虑以下自然外观：

我真的想要更像这样的东西：

这些路径必须满足一些属性：

1. 我必须能够指定它们的边界区域，
2. 我必须能够参数化它们的风和长度，
3. 线条不应看起来像是从一条路径开始并在另一条路径结束。例如，上面的第一个例子看起来好像从 A 开始，在 B 结束，因为它基本上反复改变方向，直到它与 B 对齐，然后就直奔那里。

我希望使用 A*，但老实说，我不知道我的启发式方法是什么。我也考虑过使用遗传算法，但我不知道这种方法最终会有多实用。

我的问题是，什么是获得我想要的结果的好方法？请不要只指定“A*”或“Dijkstra 算法”之类的方法，因为我还需要一个好的启发式帮助。

我需要 A* 搜索算法的 Erlang 实现。任何指针？

我正在开发一款使用 A-star (A*) 进行路径查找的游戏，但我已经到了这样一个地步，即我有一些大于单个网格正方形的对象。

我在 16*16px 的网格上运行。墙段为 16*16，因此使单个正方形无法通过。我的一些坏人是 32*32，所以他们需要检查一个间隙是否至少有 2 个方格宽，以便能够通过它。

我不能简单地将网格设置为 32*32，因为设计需要薄壁（16 像素），并且有几个较小的坏蛋只占用一个 16*16 的正方形。

如何实现这种多分辨率环境？A-star 仍然是正确的工具吗？

A-star 用于在图中找到起始节点和结束节点之间的最短路径。如果目标状态不是具体已知的，而我们只有目标状态的标准，则使用什么算法来解决问题？

例如，一个数独游戏可以用类似 Astar 的算法来解决吗？我们不知道最终状态会是什么样子（哪个数字在哪里），但我们知道数独的规则，即获胜状态的标准。因此，我有一个 startnode 和一个 endnode 的标准，使用哪种算法？

我已经在 AS3 中实现了 A* 算法，它工作得很好，除了一件事。生成的路径通常不会采用最“自然”或最顺畅的路线到达目标。在我的环境中，对象可以像水平或垂直移动一样便宜地沿对角线移动。这是一个非常简单的例子；起点用 S 标记，终点（或终点）用 F 标记。

如您所见，在第一轮查找过程中，节点 [0,2]、[1,2]、[2,2] 都将被添加到可能节点列表中，因为它们的得分均为 N。当我试图决定继续使用哪个节点时，我遇到的问题出现在下一点。在上面的示例中，我使用 possibleNodes[0] 来选择下一个节点。如果我将其更改为 possibleNodes[possibleNodes.length-1] 我得到以下路径。

然后使用 possibleNextNodes[Math.round(possibleNextNodes.length / 2)-1]

所有这些路径都具有相同的成本，因为它们都包含相同数量的步骤，但在这种情况下，最明智的路径如下......

是否有一种正式接受的方法可以使路径看起来更合理，而不仅仅是在数学上正确？

make_heap/push_/pop_什么时候使用 std::set 比使用 std::vector 以及A* 操作中的优先级队列更有效（时间） ？我的猜测是，如果打开列表中的顶点很小，则使用向量是更好的选择。但是有人有这方面的经验吗？

我对高估/低估这些术语感到困惑。我完全了解 A* 算法的工作原理，但我不确定高估或低估启发式算法的影响。

当您采取直接鸟瞰线的平方时是否高估了？为什么它会使算法不正确？相同的启发式用于所有节点。

当您取直接鸟瞰线的平方根时是否低估了？为什么算法仍然正确？

我找不到一篇解释得很好很清楚的文章，所以我希望这里有人有一个很好的描述。