使用A*JPS进行3D搜索

Question

如何将Jump Point Search概括为3D搜索量？

到目前为止,我已经为3D立方体定义了修剪规则,涉及三个运动中的每一个 - 直线(0,0,1),一阶对角线(0,1,1)和二阶(1,1,1) .

我最关心的是本文定义的最佳转折点.我一直无法确定它们是如何得出的,因此如何从三个维度推导出自己的.

有关如何做到这一点的任何建议？

Answer 1

它不是试图导出转折点，而是有助于使用对二维算法的直观理解。

由于两个位置之间的最短距离是直线，因此我们知道对角线移动速度最快，因为它相当于一维中的两步。在 3D 中，这意味着对角线相当于三步。（实际上，这些值是sqrt(2)和sqrt(3)）。有了这个，我们选择通过尽可能多的轴移动来进行优化...转动沿 2D 轴移动比转动沿 3D 轴移动更糟糕。同样，沿 1D（直线）移动甚至比 2D 移动更糟糕。这是跳转点所做的核心假设。

在剔除算法中，假设如果您在最不理想的轴 (1D) 上跳跃，则不存在更高轴阶的最佳转弯（转向 2D 轴），直到在最不理想的轴 (1D) 上出现平行墙。相同的轴顺序。例如，请看图 2(d)，其中代码看到一维平行墙，并将 2D 运动添加回列表中。

作为启发式

向前求值，直到有一个空位（并且距离墙有 2 个空位），然后将此点添加到跳转列表中。对于跳转列表上的任意点，向新方向跳转。目标 > 2D 向前移动 > 1D 向前移动 > 1D 向后移动 > 2D 向后移动。我们可以将这个启发式推广到任何 n 维......

评估下一个方向，其中 + 指向目标，n 为增加的维度量，给出等式... + n D > + n-1 D > ... +1D > 0D > -1D > .. .> - n-1 D > - n D

3D 中最佳->最差转折点的顺序

1. 3D+ = [1, 1, 1]
2. 2D+ = [1, 1, 0], [1, 0, 1], [0, 1, 1]
3. 1D+ = [1, 0, 0], [0, 1, 0], [0, 0, 1], [-1, 1, 1], [1, -1, 1], [1, 1, - 1]

（下面的次优；[0, 0, 0] 没用，所以我没有包括它）

4. 0D = [1, -1, 0], [1, 0, -1], [-1, 1, 0], [-1, 0, 1], [0, -1, 1], [0, 1, -1]
5. 1D- = [-1, 0, 0], [0, -1, 0], [0, 0, -1], [-1, -1, 1], [1, -1, -1], [-1, 1, -1]
6. 2D- = [-1, -1, 0], [-1, 0, -1], [0, -1, -1]
7. 3D- = [-1, -1, -1]

唷，打字很痛苦，但它应该可以解决你的问题。

请记住，当您“跳跃”时，请记住您跳跃的轴顺序；你需要找到同一轴线上的平行墙。因此，沿 [1, 0, 1] 方向移动，您需要找到位于 [1, 1, 0] 和 [0, 1, 1] 处的墙壁，以便“解锁” [ 方向上的跳跃点1, 1, 1]。

按照相同的逻辑，如果在一维 [1, 0, 0] 中移动，则检查 [0, 1, 0] 中是否有墙，以添加 [0, 1, 1] 和 [1, 1, 0]。您还可以检查 [0, 0, 1] 以添加 [1, 0, 1] 和 [0, 1, 1] 作为跳转点。

希望你明白我的意思，因为它确实很难想象和计算，但一旦你掌握了数学知识，就很容易掌握。

结论

使用 A* 启发式...

• Dijkstra = 距起点的距离
• 贪心第一 = 距目标的距离

然后添加我们的新启发式！

• + n D > + n-1 D > ... +1D > -1D > ... > - n-1 D > - n D
• 如果任意n D 点有平行障碍物，则可以为每个开放的n+1 D 方向添加一个跳跃点。

编辑：代码的“并行”定义

• 与您移动方向顺序相同的任何点
• 不是该方向的下一个点
• 与下一个点具有相同数量的正向和负向维度移动（例如，[1, 1, -1] 平行于 [1, -1, 1] 和 [-1, 1, 1]，但不平行于[ 1, 0, 0]