Calculate distance on a grid between 2 points

问题:

I need to calculate the distance on a grid between 2 points. The movement allowed is horizontal and vertical as well diagonal to the next neighbor (so 45 degree rotations).

So Manhattan distance is not an option. Also Euclidean distance is not an option cause then it does not move correct along the grid which can result in a to low value (as in the red line).

I'm looking to get the distance as in the green line where it moves from cell to cell.

It's preferred that the formula is fast.

回答1:

This is pretty simple:

• You move diagonally towards the goal until you're either on the same row or same col. This will be min(dx, dy) steps.

  Let's call this d (for diagonal steps)

• Then you move on a straight line towards the goal. This will be max(dx, dy) - d steps.

  Let's call this s (for straight steps)

• The distance is then √2 × d + s.

In code:

double distance(int x1, int y1, int x2, int y2) {
    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);

    int min = min(dx, dy);
    int max = max(dx, dy);

    int diagonalSteps = min;
    int straightSteps = max - min;

    return sqrt(2) * diagonalSteps + straightSteps;
}