如何计算 3 维网格上的对角线距离

Question

我正在尝试使 Sebastian Lague's A-Star path finding code (youtube) 适应 3 个维度。我有一些工作，但偶尔我的节点之间产生的路径是次优的，我认为这是因为我计算的距离错误。

沿单个维度从一个节点移动到下一个节点的距离为 1。要在二维（对角线）中移动，距离为 √2（在代码中简化为 1.4）。这些值乘以 10 以保持整数，因此分别为 10 和 14。

要计算 2d 平面上的距离，您需要取较小的 X 和 Y 距离并将其乘以 14，然后用较大的距离减去较小的距离，然后将剩余的距离乘以 10。

    int dstX = Mathf.Abs(nodeA.gridX - nodeB.gridX);
    int dstY = Mathf.Abs(nodeA.gridY - nodeB.gridY);

    if (dstX > dstY)
    {
        return 14 * dstY + 10 * (dstX - dstY);
    }
    else
        return 14 * dstX + 10 * (dstY - dstX);

3维移动仍然是对角线移动，所以距离应该还是14。所以向前和向左移动一个节点并不比移动向上更远，向前，向左。因此，我不是取最小值并将其乘以 14，而是取中间值并将其乘以 14。然后我从最大值中减去中间值并将余数乘以 10。

如果X最大，Y在中间，Z最小，那么每当我需要沿对角线移动接近y值时，我也可以同时移动到Z值，所以我不会'我想我什至不需要考虑 Z 轴上的距离。

    int xDistance = Mathf.Abs(nodeA.gridX - nodeB.gridX);
    int yDistance = Mathf.Abs(nodeA.gridY - nodeB.gridY);
    int zDistance = Mathf.Abs(nodeA.gridZ - nodeB.gridZ);

    int largest = Mathf.Max(xDistance, yDistance, zDistance);
    int middle = GetMiddleValue(xDistance, yDistance, zDistance);
    int smallest = Mathf.Min(xDistance, yDistance, zDistance);

    return 14 * middle + 10 * (largest - middle);

出于某种原因，我的路径仍然有问题，就像它会在向上移动之前向下移动一个节点。 The white line shows the optimal path between the 2 white cubes while the black follows the nodes the path is actually taking.

也许这是一个四舍五入的问题，但我不是很有信心我在计算距离时没有遗漏任何东西。

我只写了 4-5 个月的代码，所以如果这真的很明显，我深表歉意。任何帮助将不胜感激。

Answer 1

在您的代码中，在两个维度上更改位置应基于 14（10 * 2 的平方根），但同时更改所有三个维度应基于 17（10 * 3 的平方根），如果我的快速数学是正确的。我想这可能会解决您的问题。

（果然...here's 简短解释为什么要基于 sqrt(3)。）

Answer 2

正如 Beska 所说，在某些情况下 3D space 应该是 root(3)，但为什么呢？勾股定理也适用于 3D，其中 distance = root(a² + b² + c²)

在您的 3D space 中，如果您仅朝一个方向移动，您的距离为 root(1² + 0² + 0²)，即 1

如果你朝两个方向移动，你会得到一个根(1² + 1² + 0²)，即根(2)

但是如果你同时移动 3 个方向，你最终会得到 root(1² + 1² + 1²) 也就是 root(3)

希望我说清楚了:)

如何计算 3 维网格上的对角线距离

How to calculate diagonal distance on a 3 dimensional grid

c#

path-finding