计算2点之间的网格距离

我需要计算2点之间的网格距离。 允许的运动是水平和垂直的，以及与下一个邻居的对角线（所以45度旋转）。

所以曼哈顿距离不是一个选择。 欧几里德距离也不是一个选项，因为它不会沿着网格正确移动，这可能导致一个低值（如红线所示）。

我正在寻找距离在绿色线条中从一个细胞移动到另一个细胞的距离。

公式最好是快速的。

Answer 1

这很简单：

• 你沿着对角线向目标移动，直到你要么在同一行或同一列。 这将是min（ dx ， dy ）步骤。

  我们称之为d （对角线步骤）

• 然后你朝着球门的直线前进。 这将是max（ dx ， dy ） – d步。

  让我们称之为（直接步骤）

• 距离是√2× 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; }