c++ - 使用 A* JPS 进行 3D 搜索

Question

如何将Jump Point Search推广到 3D 搜索量？

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

我最关心的是论文中定义的最佳转折点。我一直无法确定它们是如何得出的，因此无法确定我自己的三个维度。

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

Answer 1

与其尝试推导转折点，它有助于在 2D 中使用对算法的直观理解。

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

在剔除算法中，假设如果您在最不理想的轴 (1D) 上跳跃，那么直到出现平行墙之前，没有更高轴阶的最佳转弯（转到 2D 轴）相同的轴顺序。例如，请看图 2(d)，其中代码在 1D 中看到平行墙，并将 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]