问题标签 [a-star]

前段时间我问了一个关于java 2d pathfinding的问题... Pathfinding 2D Java game？

我正在开发的游戏是基于主题医院的想法。从我的问题中选择的答案，A* 寻路，链接很棒，非常有帮助。我最终将把它应用到我的游戏中，但是我还有一些关于它的问题/问题。

在我的游戏中，地图会改变。本教程假设地图是静态的（我认为）。我一直在看代码，据我所知，我只需要创建一个方法来调用来更新寻路代码中的游戏地图。

其次，我看到了 GameMap 类。我有自己的班级，叫做 Board，里面有所有的瓷砖。我相信我可以将 GameMap 上的方法集成到我的 Board 类中。正确的？

第三，我一直在研究任何房间都将被视为阻塞的推理。我的意思是，房间覆盖的任何方格都被算作阻塞。我在想人们会从哪里进入房间。然后，他们将不得不在这些房间周围移动才能到达不同的地方。我在想我会为每个正方形反转 Blocked 布尔值，但这有两个原因是行不通的。1，房间可能有相邻的墙壁，并且可能会破坏寻路。2、如果阻塞状态只是简单的倒置，那么房间内的任何实心物品倒置后都会被视为不实心，这可能会在它们与墙壁接触时出现问题。

想一想，如果您可以将正方形的边制作成块状而不是实际的整个正方形会更好。这一定是可能的，但我只是通过使用上一个问题中的教程获得，并且不确定我是否应该尝试更改 A* 来执行此操作，或者解决房间物品问题的解决方法。

对这些问题有什么想法或建议吗？我今天正在实施简单的路径查找，但只是提前思考。

我正在开发一个简单的基于 2d 网格的 sim 游戏，并且具有功能齐全的寻路功能。

我使用在上一个问题中找到的答案作为实现 A* 路径查找的基础。（寻路 2D Java 游戏？）。

为了真正向您展示我的要求，我需要向您展示我制作的视频屏幕截图。我只是在测试这个人将如何移动到一个位置并再次返回，这就是结果......

http://www.screenjelly.com/watch/Bd7d7pObyFo

根据方向选择不同的路径，结果出人意料。有任何想法吗？

我已经编写了 A* 搜索算法的实现。问题是我目前使用的启发式方法只能在方形网格上准确地工作。由于我的地图是等距的，因此启发式没有考虑地图的实际布局，因此也没有考虑单元格之间的距离。

更新：经过大量的日志记录和分析（读作花费大量时间试图找出平庸），我得出的结论是，我目前的启发式方法工作得很好，有一个小例外：最终结果与真正的直线相反对角线运动。

这意味着在等轴测sqrt(2)地图上，直线移动的成本实际上是对角线移动的数倍，它被计算为对角线移动的移动。问题是：如何修改我当前的启发式方法，以便为等距布局产生正确的结果？简单地替换为，反之亦然是行不通的。diagonalstraight

我正在查看马里奥 AI 竞赛中的人一直在做什么，其中一些人利用 A*（A-Star）路径算法构建了一些非常简洁的马里奥机器人。

（马里奥 A* 机器人行动视频）

我的问题是，A-Star 与 Dijkstra 相比如何？看着它们，它们看起来很相似。

为什么有人会使用一个而不是另一个？尤其是在游戏路径的背景下？

8 拼图是一个有 9 个位置的方板，由 8 个编号的瓷砖和一个间隙填充。在任何时候，与间隙相邻的瓷砖都可以移动到间隙中，从而创建新的间隙位置。换句话说，间隙可以与相邻（水平和垂直）的瓷砖交换。游戏的目标是从任意配置的图块开始，然后移动它们以使编号的图块按升序排列，或者围绕棋盘周边排列，或者从左到右排列，左上角为 1 -手的位置。

我想知道什么方法可以有效地解决这个问题？

我喜欢玩益智游戏 Flood-It，可以在线玩：

https://www.lemoda.net/javascript/flood-it/game.html

它也可以作为 iGoogle 小工具使用。目的是用最少数量的连续洪水填充来填充整个电路板。

我正在尝试编写一个可以最佳解决这个难题的程序。解决这个问题的最佳方法是什么？理想情况下，我想使用A*算法，但我不知道估计剩余步数的函数应该是什么。我确实编写了一个程序，该程序进行了深度 4 蛮力搜索以最大化填充区域。它工作得相当好，在解决难题方面击败了我，但我对那个算法并不完全满意。

有什么建议么？提前致谢。

我了解如何在树结构中使用广度优先搜索和 A*，但鉴于下图，它将如何实现？换句话说，搜索将如何遍历图形？S 是开始状态

图表在这里

我有一个非常大的 A* 寻路函数，它经常被调用并且必须放在另一个线程中，否则它会使我的游戏卡顿。我来自 Java 背景，最近阅读了有关 HashMap（基本上相当于 NSDictionary）的速度以及您可以使用的不同实现的讨论。我很好奇 NSDictionary 有多快，以及是否有人发现它是处理大量即时和临时对象分配的可行选择，或者它是否太慢了。

目前，我在 A* 算法中使用 NSMutableArray 作为打开和关闭列表 - 由于 O(1) setObject:forKey 和 removeObject:forKey，我将用 NSMutableDictionary 替换关闭列表，并且还创建一个 NSMutableDictionary “镜像”打开列表。路径数据存储在一个大的 NSMutableArray 中——我会保持原样，因为索引访问速度足够快（当然）。

所以我的问题是......这是否会显着提高速度，或者我应该推出自己的列表和/或地图？我只是不确定 NSDictionary做了什么，我想知道。

有没有做多线程 A* 搜索的好方法？单线程相当简单，如（例如）人工智能：一种现代方法中给出的，但我还没有遇到一个好的多线程版本。

假设像 Java、C# 或 Lisp 这样健全的语言，我们有线程池和工作块，当然还有垃圾收集。

维基百科关于 A* 复杂性的说法如下（链接在这里）：

比它的时间复杂度更成问题的是 A* 的内存使用。在最坏的情况下，它还必须记住指数数量的节点。

我看不出这是正确的，因为：

假设我们探索节点 A 及其后继节点 B、C 和 D。然后我们将 B、C 和 D 添加到开放节点列表中，每个节点都伴随着对 A 的引用，然后我们将 A 从开放节点移动到封闭节点节点。

如果在某个时候我们找到了另一条通往 B 的路径（例如，通过 Q），它比通过 A 的路径更好，那么只需将 B 对 A 的引用更改为指向 Q 并更新其实际成本 g (和逻辑上 f)。

因此，如果我们在一个节点中存储它的名称、它的引用节点名称以及它的 g、h 和 f 分数，那么存储的最大节点数就是图中的实际节点数，不是吗？我真的不明白为什么算法在任何时候都需要在内存中存储一​​定数量的节点，这些节点与最佳（最短）路径的长度成指数关系。

有人可以解释一下吗？

编辑据我所知，现在阅读您的答案，我从错误的角度进行推理。我认为给定的图是理所当然的，而指数复杂度是指仅由“分支因子”定义的概念图。