java - 为什么 A* 寻路有时走直线有时走对角线？ ( java )

Question

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

我使用在上一个问题中找到的答案作为实现 A* 路径查找的基础。 (Pathfinding 2D Java game?)。

为了真正向您展示我的要求，我需要向您展示我制作的视频屏幕截图。我只是想看看这个人如何移动到某个位置然后再返回，这就是结果......

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

根据方向选择不同的路径，意想不到的结果。有什么想法吗？

Answer 1

如果您正在寻找一个简单的解决方案，我是否可以建议您进行一些随机化？

我的意思是:在 cokeandcode 代码示例中，有生成“后继状态”(使用 AI 术语)的嵌套 for 循环。我指的是它在“当前”状态周围的 3x3 正方形上循环，在堆上添加要考虑的新位置。

一个相对简单的修复方法(应该 :))是稍微隔离该代码，并使其在其余处理步骤之前生成一个节点链表。然后Containers.Shuffle(或者是Generics.Shuffle？)那个链表，继续那里的处理。基本上，有一个例程说，“createNaiveNeighbors(节点)”返回一个 LinkedList = {(node.x-1,node.y), (node.x, node.y-1)... } (请原谅 pidgin Java，我正在尝试(但总是失败)简明扼要。

但是，一旦构建了链表，您就应该能够执行“for (Node n : myNewLinkedList)”而不是

for (int x=-1;x<2;x++) {

    for (int y=-1;y<2;y++) {

并且仍然使用完全相同的正文代码!

理想情况下，这会做的是“改变”所考虑节点的顺序，并创建更接近对角线的路径，但不必更改启发式。这些路径仍然是最有效的，但通常更靠近对角线。

当然，缺点是，如果多次从 A 到 B，可能会选择不同的路径。如果这是 Not Acceptable ，您可能需要考虑进行更彻底的修改。

希望对您有所帮助!-Agor