二维阵列中两点间的计算

Question

我正在绘制二维数组地图，如：

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

这是个游戏。“不是”是Troll，“P”是玩家。在这场比赛中，巨魔追逐玩家。让我们假设玩家现在不会移动。Troll的位置(行、列)是(3,2)和牌手(0，5)。

巨魔可以通过向右上角的方向前进来追逐玩家.这意味着，到达P位置只需3步：

(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(a,b) = abs(a.x - b.x) + abs(a.y - b.y)

加法：如果您希望启用digonals，您可以按以下方式计算出距离：

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