logo标签列表

为什么A*寻路有时会直线行进，有时会斜着走？（Java）

javaartificial-intelligencea-starpath-finding
9
我正在开发一个简单的基于二维网格的模拟游戏，并具备完全功能的路径查找。
我使用了之前问题中的答案作为实现A*路径查找的基础。（Pathfinding 2D Java game?）。
为了更好地说明我的问题，我需要展示这个视频屏幕截图。我只是测试人物如何移动到一个位置并返回，以下是结果...

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

根据方向选择不同的路径，结果出乎意料。有任何想法吗？
1
同意，视频是一个很好的想法。 - Mike Burton
耶，Screenjelly非常适合这种事情！ - Relequestual
你几乎肯定已经阅读了我的答案，并且不会再次阅读，所以我将在这里粘贴我最近的编辑，因为我认为这可能是帮助你理解你所看到的行为的最简单方法：如果你真的对了解发生了什么感兴趣，我建议你渲染A*搜索的步骤。根据你的问题，这可能对你来说非常有启发性。 - Mike Burton
可能是如何使用A-star（A *）找到最“自然”直接路线的最佳方法的重复问题。 - BlueRaja - Danny Pflughoeft
该链接可能是垃圾邮件或已损坏。 - flup
显示剩余3条评论
9个回答
3
如果你正在寻找一个相对简单的解决方案，我可以建议一下随机化。我的意思是，在cokeandcode代码示例中，有嵌套的for循环来生成“后继状态”（使用AI术语）。我指的是循环遍历“当前”状态周围的3x3正方形，将新位置添加到要考虑的堆栈上的地方。
相对简单的修复方法应该是将该代码隔离一下，并在处理步骤的其余部分之前生成一个节点的LinkedList。然后使用Containers.Shuffle（或Generics.Shuffle？）对该LinkedList进行随机化，并在那里继续处理。基本上，有一个例程说，“createNaiveNeighbors(node)”返回一个LinkedList = {(node.x-1,node.y)，(node.x，node.y-1)... }（请原谅我的pidgin Java，我试图（并且总是失败）简洁明了）。
一旦你构建了LinkedList，你就应该能够做到“for (Node n : myNewLinkedList)”而不是...
for (int x=-1;x<2;x++) {

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

并且仍然使用完全相同的主体代码！
理想情况下，这将会“打乱”节点顺序，并创建更接近对角线但不必更改启发式的路径。路径仍将是最有效的，但通常会更接近对角线。
缺点是，如果您多次从A到B，可能会采用不同的路径。如果这是不可接受的，则需要考虑更彻底的修改。
希望这有所帮助！ -Agor
哇，谢谢Agor。虽然这可能不会被选为我准确问题的“答案”，但它是我在看到这个之前发表的WalkLikeHumanHeuristic评论的答案。我不能说我理解你所说的一切，但我大致了解它的思路。我一定会研究这个的。如果您想加入我的团队并实现此目标，我很乐意尝试！ - Relequestual
没问题，很高兴能帮忙。我很受邀请的荣幸，但是我还是一名学生（并且在暑假期间工作），所以我必须谢绝。祝你好运！ - agorenst
我也是个学生 :) 不过不像你一样在攻读硕士学位。好的，没问题。我还在找工作！ - Relequestual
另一个需要考虑的因素是权重。它可以简单地计算成本最佳路线：在草地上行走的成本为2，而在路径上行走的成本为1，这鼓励人们走特定类型的地形；或者它可以用另一种方式来表示，即改变方向的成本为1，移动的成本也为1，以鼓励直线移动。与其计算总移动次数，你要计算总“成本”（在引入不同的“成本”之前，这是相同的事情）。 - NibblyPig
2

两条路径长度相同，因此算法的工作正常 - 它正在寻找最短路径。然而，A*算法没有指定它将采取哪条最短路径。实现通常采用“第一条”最短路径。如果您想每次获得相同的结果，您需要添加某种优先规则（以便您的期望路径在搜索中首先出现），但是如果没有看到您的实现，就不可能确切知道原因。

如果您查看第一个链接，并按照该问题的答案，该页面实际上包含了我使用的所有路径查找代码的链接。 在调查过程中，我有4种启发式选择。A启发式（仅基于成本），最近的，最近的平方和曼哈顿。我将尝试其他3个，因为A是默认值。 - Relequestual
你所说的A启发式是什么？A算法使用当前代价加上剩余估计值（"启发式"）来进行计算。Closest、ClosestSquared和Manhattan是常用的启发式方法，但我不知道有任何名为"A*启发式"的方法。 - Michael Deardeuff
我的错误。这只是一个接口类！还有很多要学习的！ :) 它在ClosestHeuristic上。尝试了另外两个。ClosestSquaredHeuristic有时会出现一些问题，而ManhattanHeuristic避免了锯齿状，看起来更好。 我想知道是否有WalkLikeHumanHeuristic... - Relequestual
人类通常不需要从一个网格方块走到另一个网格方块！ - Kylotan
是的，我知道，但我的意思是在二维网格环境中。猜测随机化是我能做到的最接近的方式了。 - Relequestual
2

原因是你想让算法走的路径。
我不知道你的A*使用的启发式方法，但在第一种情况下，它必须先到达隧道的尽头，然后规划从隧道尽头到目标的路线。

在第二种情况下，最简单的移动方式是向下移动直到撞到墙壁，然后规划从墙壁到目标的路线。

我知道的大多数A*都使用视线启发式方法或者在块世界中使用曼哈顿距离。这些启发式方法可以给出最短的路径，但如果有障碍物强制要求走一条与视线不同的路线，则路径取决于起点。
该算法将尽可能沿着视线前进。

2
原因其实很简单：路径总是尽可能使用最低的启发式，因为它以贪婪的方式搜索。靠近目标点的路径是最优路径。
如果允许对角线移动，这种情况就不会发生。
你知道的，这是有道理的。我不打算允许对角线移动，因为这会引起房间角落的问题。这只是我用Java制作的第二个游戏，第一个是经典直升机游戏的糟糕版本...所以，我在学习中前进，尽量保持简单。我预计一旦我建立了好的东西，就会开放给其他开发人员参与。 - Relequestual
1
最有可能的答案是直接向南走，可以最先接近目标；相反地，这不是一个选择，因此它通过逐段优化子路径，结果是交替上/横移动作被视为最佳选择。
如果你想让它在返回时沿着对角线走，你需要在路径上识别一些感兴趣的点（例如隧道的入口），并在启发式中考虑这些点。或者，你可以通过重新计算通过感兴趣点的任何子路径来在算法中考虑它们。
早些时候，他们会对地图进行预编译静态分析，并在瓶颈处放置路径查找标记。根据你的最终目标，这也可能是一个好主意。
如果你真的想了解正在发生什么，我建议渲染A*搜索的步骤。鉴于你的问题，这可能会让你大开眼界。
谢谢Mike，我真的很喜欢Stack，并珍惜那些发帖回答的人，所以当我看到编辑过的注释时，我会重新阅读。非常感谢 :) 我不确定我完全理解你的意思，但我认为我知道你在说什么。由于这是一个模拟游戏，最终任何东西都可能改变，因此我不认为我可以使用标记。我刚刚才明白它是如何工作的，并记得有一个网站展示了A*算法的进展情况，我会去看一下的。我可以将其实现到我的游戏中，尽管我觉得在我的水平上可能有点困难。 我将启发式函数更改为曼哈顿距离，两次都直接通行了。 - Relequestual
1
在每种情况下，它都更倾向于尽早接近目标节点的路径，这也是A*算法的设计初衷。
0
根据你的A*算法实现方式，即使使用相同的启发式方法，你也会看到不同的结果，正如许多人所提到的。这是由于当两条或更多路径相同时，你如何排序你的开放集合将决定最终路径的样子。如果你有一个可接受的启发式方法，你总会得到最优路径，但是访问的节点数会随着你拥有的平局数量增加而增加（相对于产生较少平局的启发式方法）。
如果你认为访问更多的节点不是问题，我建议使用随机化（这是你当前接受的答案）建议。如果你认为搜索更多的节点是个问题，并且想要进行优化，我建议使用某种形式的平局解决方法。看起来你正在使用曼哈顿距离，如果你在两个节点平局时使用欧几里得距离作为平局解决方法，你将得到更直接的路径到达目标，并且你将访问更少的节点。当然，这是在没有陷阱或者视线阻塞到目标的情况下。
为了避免访问具有阻挡元素的节点，我建议找到一种考虑这些阻挡元素的启发式方法。当然，新的启发式方法不应该比普通的A*搜索做更多的工作。
我建议看一下我的问题，因为它可能会产生一些关于这个问题的想法和解决方案。
0

如果我看得没错的话，球体首先沿着直线向右移动，因为它不能直接朝着目标前进（路径被阻挡了）。 然后，它沿着直线朝着目标前进。它只是看起来斜着走而已。

我认为你没有理解重点。如果我没有表达清楚，对不起。我是在谈论去程和回程之间的比较。 - Relequestual
啊好的。我没有看完整个视频。我现在用的是小带宽网络连接... - Burkhard
不用担心。无论如何，感谢您抽出时间回答我的问题 :) 感激不尽！ - Relequestual
0

你的搜索首先是向“下”方向查找吗？这可能会解释算法。尝试将其更改为首先查找“向上”，我敢打赌你会看到相反的行为。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接