计算2D阵列中的2个点

Question

我正在做二维数组映射,如:

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

这是一场比赛.'T'是巨魔,'P'是玩家.Troll在这场比赛中追逐球员.假设玩家现在不会移动.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;博士:

• 经典的欧几里德距离不起作用,因为对角线的长度为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)}