1
\$\begingroup\$

Say I have a 9x7 grid (could be any size) I want to be able to calculate the distance any square is from another. In the image I have selected 5,4 is my target square. Now square (1,2) is 4 moves away (if you can move left, right, up, down and diagonal), as denoted by the orange dot. It is clear from the diagram that the distance from the target square is simply showed by a growing square surrounding the target square. Is there a function which will calculate me the distance of a particular square to my target square using the x and y values of both squares.

e.g. I want to know how many moves it will take from (8,5) to the target square, looking at the diagram I know this is three but is there a function I can use?enter image description here

\$\endgroup\$
  • \$\begingroup\$ A* (called "A star") is an algo that does this, but it may be overkill since it includes ways to have some squares cost more than others to go through. Imagine a character navigating terrain, and wanting to take the route that takes the least time. \$\endgroup\$ – Almo Apr 26 '17 at 16:16
  • \$\begingroup\$ You want to do this for the whole grid (like your colors show) or just a single grid space? A breadth first search style expansion from your target would give you distances for all your grid locations pretty fast. What to do it for every cell to every other cell? en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm \$\endgroup\$ – MichaelHouse Apr 26 '17 at 16:29
6
\$\begingroup\$

If you don't need to navigate around obstacles along the way, you can do this with a simple formula.

Just like in continuous space we can use the Euclidean distance metric:

distance = sqrt((end.x - start.x)^2 + (end.y - start.y)^2)

In a discrete square grid we can use the Chebyshev distance metric (if we can move on diagonals):

distance = max(abs(end.x - start.x), abs(end.y - start.y))

Or, if we can't take diagonal moves, we'd use the Manhattan distance metric:

distance = abs(end.x - start.x) + abs(end.y - start.y)

All of these extend naturally to 3 (or more) dimensions by adding more terms following the same pattern.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.