Calculate the distance/number of moves one square is from another

Question

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?

Answer 1

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.