java - 二维数组中两点之间的计算

Question

我正在做 2D 数组映射，例如:

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

这是一个游戏。 “T”是巨魔，“P”是玩家。巨魔在这场比赛中追逐玩家。假设玩家现在不会移动。 Troll的位置(行，列)为(3,2)，Player为(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))) ;

到达那里需要 4 个步骤。

我对距离公式很困惑。难道我不能在这种情况下使用它吗？但在某些情况下，它会采取正确的步骤。

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

Answer 1

我认为您指的是能够沿对角线移动。如果你沿对角线移动，你实际上移动了 sqrt(2) “单位”，所以你将能够“移动得更快”，因为当你使用对角线时你每一步需要超过一个单位.

它在某些情况下对你有用，当你让巨魔和玩家对齐相同的 x 或 y 值时，你只需要一个单位移动就可以找到他。

---

如果你想避开对角线，那么你就不能采取“更快”的移动，一个好的距离度量是 manhattan distance , 这基本上是

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:

• 经典欧氏距离不起作用，因为对角线位于 length 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)}