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\$
2
  • \$\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\$
    – House
    Apr 26 '17 at 16:29
8
\$\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:

$$d_{\text{Euclidean}} = \sqrt{ \left(\vec b - \vec a\right)^2} = \sqrt {(b_x - a_x)^2 + (b_y - a_y)^2}$$

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

$$d_{\text{Chebyshev}} =\max\left(\left| b_x - a_x \right|, \left| b_y - a_y \right|\right)$$

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:

$$d_{\text{Manhattan}} =\left| b_x - a_x \right| + \left| b_y - a_y \right|$$

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.


If you do need to navigate around obstacles, then as mentioned in the comments, you need to use some type of pathfinding function like A*. But you can use the metrics above as your heuristic function, to help A* prioritize searching the most promising options.

If you want to know the path distance to many cells from a given seed cell, rather than just a single path from start to end, then you can use breadth-first search, which will enumerate the cells in order of increasing "hop count" from your initial cell.

\$\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.