java - 关于 A* 寻路的问题

Question

好吧，我正在尝试将 A* Pathfinding 实现到一个简单的 tilemap 数组中，我有几个问题。

对于打开/关闭列表，我应该只使用 arrayList 来存储它找到的所有点，还是有更好的方法来存储它们？

其次，我该如何检查邻居？我是否拿走开始牌，检查上、下、左、右，哪个成本最低？

Answer 1

只要您没有为游戏实现此功能，即高 fps 视频游戏，我怀疑您的性能会因用作 ArrayList 而受到重大影响，那应该没问题。

至于问题的第二部分，假设每个节点只有 4 个连接方向，那么是的，对每个邻居进行简单的顺序检查就可以了。

Answer 2

我在过去使用PriorityQueue开放列表实现了这一点。比较器对 A* 启发式值起作用。这是非常干净的，每次插入和轮询最坏的情况下，您将获得 O(log n) 性能。优于标准实现可以将轮询改进为 O(1) 摊销。对于visited列表，使用磁贴中的标志或单独的HashSet. 后者的优点是没有初始化成本，并且插入和成员资格的渐近成本相同。但是哈希的常数因子大于检查布尔映射值的常数因子。

Answer 3

我不知道“tilemap 数组”是什么，但我假设“找到的点”是指搜索树中的节点。存储尚未探索的节点的数据结构需要满足两个重要属性，继承自 Dijkstra 算法：

1. 获取成本最低的节点应该很快，至少 O( n )
2. 一旦找到更短的路径，您将希望降低节点的成本

前者可以使用堆来实现。二进制堆相当容易实现。斐波那契堆提供更好的渐近性能，但在大多数应用程序中不应该是必需的。到目前为止，我看到的大多数库中的堆都不支持后一个要求，通常称为减少键。为了实现这一点，您的节点应该保存有关它们在堆中的当前位置的信息。这样，当一个节点改变它的成本时，你可以获得它在 O(1) 中的当前位置并在 O(log n ) 中调整位置。您可以使用相同的变量来确定项目是否在堆中。

现在回答你的第二个问题。通常，您通过从堆中删除最小元素来检查成本。换句话说，对于每个邻居，您要么将其插入堆中，要么如果它已经在堆中，则如果新成本更好，则调整其成本（以及它的堆位置）。