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

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

到那里需要4步。

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

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

Answer 1

我认为你指的是能够沿对角线移动。如果你沿对角线移动，你实际上移动 sqrt(2) "units"，所以你将能够 "move faster"，因为当你使用对角线时，你每一步需要超过一个单位。

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

如果你想避开对角线，所以你不能采取 "faster" 步，一个好的距离度量是 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)，然后你必须只在一个轴上移动以提醒移动，你得到 "closer" 在此轴上移动 min(diffX,diffY) 步，因此您需要进行 max(diffX-diffY) - min(diffX,diffY) 次移动，现在将两个 "kinds" 次移动 (diagonal/non-diagonal) 移动相加，然后您得到：

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;博士:

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

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

Calculation between 2 points in 2D-array

java

algorithm

shortest-path

coordinates