A*跳转点搜索 - 修剪如何真正起作用？

Question

我遇到过Jump Point Search,对我来说似乎很甜蜜.但是,我不确定他们的修剪规则是如何实际工作的.更具体地说,在图1中,它表明了这一点

我们可以立即修剪所有灰色邻居,因为这些邻居可以从x的父节点最佳地到达,而无需通过节点x

然而,这似乎有些不一致.在第二个图像中,可以通过首先通过节点7并x完全跳过对称路径(即,6 -> x -> 5似乎是对称的)来到达节点5 6 -> 7 -> 5.这与如何在不经过x第一图像的情况下到达节点3的情况相同.因此,我不明白这两个图像是如何完全等效的,而不仅仅是彼此的旋转版本.

其次,我想了解这个算法如何推广到三维搜索量.

Answer 1

我理解这是关于优先事项的。为了枚举每个非对称路径，您必须枚举所有节点 - 但您选择哪条路径并不重要，因为它们是对称的。因此，作者决定采用对角线优先——也就是说，任何对角线移动总是出现在路径中的任何直线移动之前。这就是为什么直线有更多的节点被修剪——因为它一定是在考虑了所有对角线之后发生的。