CODEWITHSUNDEEP
javaalgorithmcoordinatesshortest-path
annie
annie

Reputation: 75

Calculation between 2 points in 2D-array

I am doing 2D array map like:

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

This is a game. 'T' is the Troll and 'P' is the Player. Troll chase the Player in this game. Let assume Player will not move now. The position(row, column) of Troll is (3,2) and Player(0,5)

Troll can chase the Player by walking toward upper-right direction. That mean, it only takes 3 steps to arrive P position:

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

But, when I use the Euclidean Distance formula: 

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

it takes 4 steps to go there.

I am so confused about the Distance formula. Is it I can't use it in this situation? But in some case, it takes correct steps.

Hope someone can explain this problem, thank you.

Upvotes: 5

Views: 4258

Answers (1)

amit
amit

Reputation: 178521

I think you are referring to being able to move in a diagonal. If you move in a diagonal, you actually move sqrt(2) "units", so you will be able to "move faster", because you take more than one unit per step when you do use diagonals.

It works in some situations for you when you have the troll and the player aligned with the same x or y value, so you take only one unit moves to get to him.

If you want to avoid diagonals, so you cannot take "faster" moves, a good distance metric is the manhattan distance, which is basically 

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

Addition: If you want to keep digonals enabled, you can calculate the distance as:

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

This works because you are going to make as much diagonal moves as you can, and this number is min(diffX,diffY), and then you have to move in only one axis for the reminder of moves, you got "closer" in this axis by min(diffX,diffY) steps, so you are left to make max(diffX-diffY) - min(diffX,diffY) moves, now sum the two "kinds" of moves (diagonal/non-diagonal) moves, and you get:

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

Example, on your matrix:

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

tl;dr:

  • Classic euclidean distance does not work because diagonal is at length sqrt(2) - so you move faster when using it.
  • It can be solved by avoiding diagonals and using the manhattan distance dist(a,b) = abs(a.x - b.x) + abs(a.y - b.y)
  • Or by allowing diagonals and using the distance metric: dist(a,b) = max{abs(a.x-b.x),(a.y-b.y)}

Upvotes: 7

Related Questions