三维网格上对角线距离的计算

Question

我正在尝试使塞巴斯蒂安·拉格的A星路径查找码 (youtube)适应三维。我有些工作，但偶尔我的节点之间产生的路径不是最优的，我认为这是因为我计算错了距离。

沿着一个维度从一个节点移动到另一个节点的距离是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);

三维移动仍然是对角移动，所以距离应该仍然是14。因此，向前移动和向左移动一个节点就等于向前移动、向前移动和左移1。所以，我不是取最小值乘以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);

由于某些原因，我的路径仍然有扭曲，就像它会向下移动一个节点，然后再向上移动。白线显示两个白方之间的最优路径，而黑色则跟随路径实际采取的节点。

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

我只编码了4-5个月，所以如果这很明显的话，我很抱歉。任何帮助都将不胜感激。

Answer 1

在您的代码中，在二维中更改位置应该基于14 (10 *平方根为2)，但如果我的快速数学是正确的，那么同时在所有三个维度中的更改应该基于17 (10 *平方根为3)。我怀疑这能解决你的问题。

(当然.下面是是对为什么应该基于sqrt(3)的简短解释。)

Answer 2

正如Beska所说，在某些情况下，它应该是根(3)，但为什么呢？毕达戈尔定理也适用于3D，其中距离=根(a 2+b 2+c 2)

在你的3D空间中，如果你只朝一个方向移动，你就会有一个根的距离(1平方公里+0 2 2+0 2)，即1。

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

但是，如果你在这两个方向上移动，你最终会得到根(1 2+1 2+1 2)，这是根(3)。

希望我能弄清楚:)