Рассчитать расстояние на сетке между двумя точками

Question

Мне нужно рассчитать расстояние по сетке между 2 точками. Разрешенное движение является горизонтальным и вертикальным, а также диагональным для следующего соседа (так что вращение на 45 градусов).

Таким образом, расстояние Манхэттена не является вариантом. Кроме того, евклидово расстояние не является вариантом, поэтому оно не перемещается правильно вдоль сетки, что может привести к низкому значению (как в красной строке).

Я ищу, чтобы получить расстояние, как в зеленой линии, где он перемещается из ячейки в ячейку.

Предпочтительно, чтобы формула была быстрой.

Answer 1

Это довольно просто:

• Вы двигаться по диагонали к цели до тех пор, пока вы либо на той же строке или же седловины. Это будет мин (dx, dy) шаги.

  Давайте назовем это d (для диагональных шагов)

• Затем двигаться по прямой линии к цели. Это будет максимальным (dx, dy) - d шаги.

  Давайте назовем это с (для прямых шагов)

• Расстояние затем √2 × д + с.

В коде:

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