它不是试图导出转折点，而是有助于使用对二维算法的直观理解。
因为两个位置之间的最短距离是直线，所以我们知道对角线移动速度最快，因为它相当于two一维步骤。在 3D 中，这意味着对角线相当于three脚步。 （实际上，这些值是sqrt(2) and sqrt(3)）。有了这个，我们选择通过移动来优化尽可能多的轴... 转动沿 2D 轴移动比转动沿 3D 轴移动更糟糕。同样，沿一维（直线）移动是均匀的worse比 2D 运动。这是跳转点的核心假设.
在剔除算法中，假设如果您在最不理想的轴 (1D) 上跳跃，则不存在更高轴阶的最佳转弯（转向 2D 轴），直到在最不理想的轴 (1D) 上出现平行墙。相同的轴顺序。例如，看看图2(d) http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf，其中代码看到一维平行墙，并将 2D 运动添加回列表中。
作为启发式
向前求值，直到有一个空位（并且距离墙有 2 个空位），并将这一点添加到跳转列表中。对于跳转列表上的任意点，向新方向跳转。目标 > 2D 向前移动 > 1D 向前移动 > 1D 向后移动 > 2D 向后移动。我们可以将这个启发式推广到任何 n 维......
评估下一个方向，其中 + 指向目标，n 是增加的维度数量，给出了方程......
+nD > +n-1D > ... +1D > 0D > -1D > ... > -n-1D>-nD
3D 中最佳->最差转折点的顺序
- 3D+ = [1, 1, 1]
- 2D+ = [1, 1, 0], [1, 0, 1], [0, 1, 1]
- 1D+ = [1, 0, 0], [0, 1, 0], [0, 0, 1], [-1, 1, 1], [1, -1, 1], [1, 1, - 1]
（下面的次优；[0, 0, 0] 没用，所以我没有包括它）
- 0D = [1, -1, 0], [1, 0, -1], [-1, 1, 0], [-1, 0, 1], [0, -1, 1], [0, 1, -1]
- 1D- = [-1, 0, 0], [0, -1, 0], [0, 0, -1], [-1, -1, 1], [1, -1, -1], [-1, 1, -1]
- 2D- = [-1, -1, 0], [-1, 0, -1], [0, -1, -1]
- 3D- = [-1, -1, -1]
phew打字很痛苦，但它应该可以解决你的问题。
请记住，当您“跳跃”时，请记住您跳跃的轴顺序；你需要找到平行的墙同一轴。因此，沿 [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] 作为跳转点。
希望你明白我的意思，因为它是really很难想象和计算，但一旦掌握了数学知识就很容易掌握。
结论
使用 A* 启发式...
- Dijkstra = 距起点的距离
- 贪心第一 = 距目标的距离
然后添加我们的新启发式！
- +nD > +n-1D > ... +1D > -1D > ... > -n-1D>-nD
- 如果有任何一点nD有平行障碍物，可以为每个空位添加一个跳跃点n+1D方向。
编辑：
代码的“并行”定义
- 与您移动方向顺序相同的任何点
- 不是该方向的下一个点
- 与下一个点具有相同数量的正向和负向维度移动（例如，[1, 1, -1] 平行于 [1, -1, 1] 和 [-1, 1, 1]，但是not到 [1, 0, 0]
