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

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

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

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

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

enter image description here

Ответы

Ответ 1

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

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

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

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

    Позвольте называть это s (для прямых шагов)

  • Расстояние тогда √2 & times; d + s.

В коде:

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