在二维数组中计算两点之间的距离

Question

我正在进行2D数组映射，例如：

* 0 1 2 3 4 5 6
0 # # # # # P #
1 # # # # # # #
2 # # # # # # #
3 # # T # # # #
4 # # # # # # #

这是一个游戏。 'T'代表巨魔，'P'代表玩家。在这个游戏中，巨魔会追逐玩家。假设玩家现在不移动。 巨魔的位置（行，列）是（3,2），而玩家的位置是（0,5）。

巨魔可以向右上方向走来追逐玩家。也就是说，它只需要走3步即可到达P位置：

(3,2)->(2,3)->(1,4)->(0,5)

但是，当我使用欧几里得距离公式时：

    (int) Math.floor(Math.sqrt(Math.pow((0-3) , 2) + Math.pow((5-2) , 2))) ;

需要走四步才能到达那里。

我对距离公式感到非常困惑。在这种情况下我不能使用它吗？但在某些情况下，它可以迈出正确的步伐。

希望有人能解释一下这个问题，谢谢。

- annie

---

@LarsBlumberg 巨魔的移动（行，列）：（2,3）->（1,4）->（0,5） - annie

Answer 1

我认为你是指能够斜着走。如果你斜着走，实际上会移动sqrt(2)个单位，因此你将能够“更快地移动”，因为你每步可以走多个单位。

当巨魔和玩家的x或y值对齐时，这在某些情况下对你有用，因此你只需要移动一个单位就能到达他。

---

如果你想避免斜线移动，以便不能进行“更快”的移动，一个好的距离度量标准是曼哈顿距离，它基本上是：

manhattan_distance(a,b) = abs(a.x - b.x) + abs(a.y - b.y)

---

补充：如果您想保持对角线启用状态，可以按以下方式计算距离：

diffX = abs(a.x - b.x)
diffY = abs(a.y - b.y)
numSteps = max(diffX, dixxY) //max is returning the higher value of both.

这种方法奏效的原因是你会尽可能地进行对角线移动，而此次数为 min(diffX,diffY)，此后你只需在一个轴上移动剩下的步骤，通过 min(diffX,diffY) 步骤在此轴上变得“更接近”，因此你需要进行 max(diffX-diffY) - min(diffX,diffY) 步非对角线移动。现在将两种不同类型的移动（对角线/非对角线）相加，即可得到：

numMoves = max(diffX-diffY) - min(diffX,diffY) + min(diffX,diffY) = max(diffX-diffY)

例如，在您的矩阵中：

diffX = abs(3-0) = 3
diffY = abs(2-5) = 3
max(diffX,diffY) = 3 

---

tl;dr:

• 传统的欧几里得距离并不适用，因为对角线长度为sqrt(2)，所以使用它时你会移动得更快。
• 可以通过避免对角线和使用曼哈顿距离dist(a,b) = abs(a.x - b.x) + abs(a.y - b.y)来解决这个问题。
• 或者允许对角线，并使用距离度量：dist(a,b) = max{abs(a.x-b.x),(a.y-b.y)}

- amit

---

谢谢 :) 这是我第一次听到曼哈顿距离。 - annie