How to calculate diagonal distance on a 3 dimensional grid-CodePudding

I'm trying to adapt Sebastian Lague's A-Star path finding code (youtube) to 3 dimensions. I have it somewhat working but occasionally the path produced between my nodes is sub-optimal, and I think it's because I'm calculating distance wrong.

To move along a single dimension from one node to the next is a distance of 1. To move in 2 dimensions (diagonally) the distance is √2 (which is simplified to 1.4 in the code). These values are multiplied by 10 to keep them as integers, so 10 and 14 respectively.

To calculate the distance on a 2d plane you take the smaller of the X and Y distances and multiply it by 14, then minus the smaller distance from the larger one and multiply what remains by 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);

Moving in 3 dimensions is still a diagonal move, so the distance should still be 14. So moving forward and to the left by one node is no farther than moving up, forward, and to the left by one. So rather than take the smallest value and multiply it by 14, I've been taking the middle value and multiplying it by 14. Then I subtract the middle value from the largest value and multiply the remainder by 10.

If X was largest, Y was in the middle, and Z was smallest then whenever I needed to move diagonally to approach the y value I may as well move toward the Z value at the same time, so I don't think I even need to factor the distance on the Z axis in.

    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);

For some reason my path still has kinks in it, like it will move down one node before moving back up. The white line shows the optimal path between the 2 white cubes while the black follows the nodes the path is actually taking.

Maybe it's a rounding issue but I'm not super confident I haven't missed anything while calculating the distance.

I've only been coding for 4-5 months, so I apologise if this is really obvious. Any help would be appreciated.

CodePudding user response：

In your code, changing location in two dimensions should be based on 14 (10 * square root of 2), but changing in all three dimensions at once should be based on 17 (10 * square root of 3), if my quick math is correct. I suspect that may solve your issue.

(Sure enough...here's a short explanation of why it should be based on sqrt(3).)

CodePudding user response：

As Beska said, it should be root(3) in some casesof a 3D space, but why? pythagore theorem also works in 3D, where distance = root(a² b² c²)

In your 3D space if you move in only 1 direction you'll have a distance of root(1² 0² 0²) which is 1

if you move in 2 directions, you'll get a root(1² 1² 0²) which is root(2)

but if you move in both 3 directons you'll end up with root(1² 1² 1²) which is root(3)

hope I got clear :)