3D搜索使用A * JPS

Question

我如何将Jump Point Search推广到3D搜索空间？

到目前为止，我已经为一个3D立方体定义了每个三维移动（直线（0,0,1），一阶对角线（0,1,1）和二阶（1,1,1））的修剪规则。

我最关心的是论文中定义的最优转折点。我无法确定它们是如何推导出来的，因此也不知道如何在三维空间中推导出自己的转折点。

有什么建议吗？

- Puppy

---

我对这篇论文的理解是跳跃点是最优转折点，算法3仅仅是一个概念设备，用来证明使用这些跳跃点对搜索的最优性没有影响。 - user7116

你认为它们只是从算法中产生，而不是你必须明确编程的东西吗？ - Puppy

他们将纸分成三部分，第一部分描述了他们的修剪策略以及如何添加节点（即在给定方向“d”上跳跃）。第二部分提出转折点，他们声称这仅是一个“理论结果，表明使用跳跃点进行搜索可以保持最优性”。最后一部分只是一个基准测试，并不使用算法3（使用转折点进行路径缩减）。 - user7116

2D JPS算法中有一个假设。这个引理是说，你永远不会被困在“循环”扩展中，因为扩展首先是对角线的，所有次要的水平/垂直方向都依赖于所选择的方向。因此，你不可能停留在同一个地方。我无法证明或否定这一点，但在3D中，仅仅将2D情况扩展到3D似乎不那么明显是否成立。 - StarShine

转折点只用于证明算法找到了最优路径吗？也许应该只关注跳点和正确修剪强制邻居。 - soncis

Answer 1

不是试图推导转折点，而是使用对算法在2D中的直观理解会更有帮助。因为两个位置之间的最短距离是一条直线，我们知道对角移动是最快的，因为它相当于在1D中走了两步。在3D中，这意味着对角线相当于三步（实际上，这些值分别是sqrt(2)和sqrt(3)）。基于此，我们选择通过尽可能多地跨越轴来进行优化...沿着2D轴移动比沿着3D轴移动转弯更差。同样，沿着1D（直线）移动甚至比2D移动更差。这就是JPS的核心假设。

在选材算法中，有一个假设，即如果您正在跳到最不理想的轴（1D），则在同一轴序上直到出现平行墙壁之前，没有更高轴序的最佳转弯（转向2D轴）。例如，请参见图2(d)，代码在1D中看到平行墙壁并将2D移动添加回列表中。

作为一种启发式方法，评估前进，直到只剩下一个空格（并且离墙还有2个空格），然后将此点添加到跳跃列表中。对于跳跃列表上的任何点，请朝新方向跳跃。目标> 2D运动向前> 1D运动向前> 1D运动向后> 2D运动向后。我们可以将此启发式方法推广到任何n维度...

评估下一步的方向，以+表示朝着目标方向，n表示增加的维数的数量，给我们这个方程式... +nD > +n-1 D > ... +1D > 0D > -1D > ... > -n-1 D > -nD

在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]的跳跃点。

用相同的逻辑，如果您沿着1D [1,0,0]移动，则检查[0,1,0]是否有墙壁可添加[0,1,1]和[1,1,0]。您还要检查[0,0,1]以添加[1,0,1]和[0,1,1]作为跳跃点。

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

结论

使用A*启发式算法...

• 迪杰斯特拉=距离起点的距离
• 贪婪优先=距离目标的距离

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

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

编辑： 您代码中“平行”的定义

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

- Aaron3468

---

我正在尝试这个，强制邻居的情况相当奇怪。我很难理解它。你也不能在3D中实现2D强制邻居x3，否则会出错。如果有人有一个关于哪些节点可以被修剪和哪些必须在3D情况下检查强制邻居的示例，请告诉我:p - soncis

好的，我已经成功解决了3D JPS中所有强制邻居的情况，如果有人需要帮助，请联系我^^ - soncis

请注意，[1, 1, 1] 直接指向目标，您需要旋转整个点集以将它们转换为全局坐标系。如果我不使用相对坐标，列表将会有8倍的长度。 - Aaron3468

@soncis，您是否愿意通过电子邮件与我联系？我的邮箱是[e-mail]。我有许多问题想问！ - Enqueuing

我想在一个类似于Minecraft的体素游戏中实现A和JPS算法。我有一个基本的A算法，在平面地图上运行良好。但是，实现第三个维度让我感到头疼。我需要实现实体可以跳过节点的可能性，但为了找到正确的路径，我还必须检查头部上方的空间。另一个问题是实体可以具有不同的大小，这使得问题更加复杂。有人有什么想法如何实现这一点吗？ - burli