为什么路径查找有时是直线,有时是对角线?(爪哇)

如果你在寻找一个简单的ish解决方案,我可以建议你做一点随机化吗?

我的意思是:在cokeandcode示例中,有嵌套的for循环生成“后继状态”(使用AI术语)。我指的是它围绕“当前”状态在3x3方块上循环的点,在桩上添加新的位置来考虑。

一个相对简单的修复方法是(应该:))稍微隔离代码,并让它在处理步骤的其余部分之前生成节点的linkedlist。然后将Containers.Shuffle(或者是泛型.Shuffle?)链接到该链表,并在那里继续处理。基本上,有一个常规的说法, 它返回一个LinkedList={(node.x-1,node.y),(node.x,node.y-1)…}(请原谅pidgin Java,我试图(但总是失败)简洁。

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

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

而且仍然使用完全相同的身体代码!

通常 靠近对角线。

当然,不利的一面是,如果你多次从A到B,可能会采取不同的路径。如果这是不可接受的,你可能需要考虑更剧烈的修改。

-阿戈尔

原因其实很简单:路径总是尽可能使用最低的启发式,因为它以贪婪的方式搜索。接近目标是一条最佳路径。

如果你允许对角线运动,这就不会发生。

原因是您希望算法走的路径。
我不知道A*使用的启发式方法,但在第一种情况下,它必须先到达隧道末端,然后规划从隧道末端到目标的路线。

在第二种情况下,最简单的移动目标是向下,直到它击中墙壁,然后它规划从墙壁到目标的路线。

Manhattan Distance 在区块世界的情况下。这种启发式方法为您提供了最短的路径,但如果遇到障碍物,迫使您选择与视线不同的路径,则路径取决于您的起点。
该算法将尽可能长时间地在视线范围内运行。

如果你想让它沿着对角线往回走,你必须确定路径上的一些感兴趣的点(例如隧道口),并在启发式中考虑这些点。或者,您可以在算法中通过重新计算通过感兴趣点的任何子路径来考虑它们。

在那一天,他们曾经对地图进行预编译静态分析,并在阻塞点放置寻路标记。根据你的最终目标,这可能也是一个好主意。

在每种情况下,它都倾向于选择更快地将其带到目标节点的路径,这就是A*的设计目的。

如果我看到右边,球体在直线上首先向右移动,因为它无法直接朝向目标(路径被阻塞)。

您的搜索是否首先朝着“向下”的方向?这也许可以解释这个算法。尝试先将其更改为“向上”,我打赌您会看到相反的行为。

如果您不认为访问更多节点是一个问题,我建议使用随机化(这是您当前接受的答案)建议。如果您认为搜索更多节点是一个问题,并且希望进行优化,我建议使用某种类型的分界线。看起来你使用的是曼哈顿距离,如果你使用欧几里得距离,当两个节点平分时,你将得到更多的直达目标的路径,你将访问更少的节点。这当然是没有陷阱或障碍的视线的目标。

我建议你看看 my question 因为它可能会产生一些想法和解决这个问题的办法。