How do I get the distance between 2 points on an isometric grid?

Question

How do I get the distance between 2 points on an isometric grid? I'm creating a facebook isometric game (in as3), and when I move around a particular type of building, I need to know if it comes within range of another type of structure, for example a tree. I tried taking the grid x,y points for both items, and calculating the x,y from that but it doesn't seem to work.

Answer 1

There are a lot of ways to compute distances, every dot product can be used: a looot of ways.

In your case you surely want to compute the distance between the center of the tiles. I take for granted that you know how to compute the center of a tile.

Once you know the position, you can use the Euclidean distance in the canvas' coordinate space (i.e. √[(x'-x")²+(y'-y")²]) or the same in tile's coordinate system.

Another option is the Manhattan or taxicab distance: d = |x'-x"|+|y'+y"|; even in this case you can use tile's coordinate or canvas' coordinate.

The last option (after L2 and L1 norm) the L"infinite" norm where d is the max between |x'-x"| and |y'-y"|.

Lets see the differences:

The best way to evaluate this norms is to see the shape of a disc.

Given a center, a disc is every point that falls within a fixed distance (however computed).

Euclidean Norm:

The disc is a standard circle in the canvas space and an ellipse in tile space

Euclidean Canvas

Euclidean Tile

While the first one is easier to compute in general (you don't have to go back and forth tile and canvas coords), the second gives a better fill.

The "Euclidean Tile" is the norm that is generally considered the most correct one.

---

Taxicab Norm:

The disc becomes a diamond in canvas coordinate and a sort of rectangle in the tile coordinate (showing how applying the same coordinate changes two times rawly gives the initial result)

Taxicab Canvas

Taxicab Tile

We can see even this time how the canvas coordinate gives the worst results: this is the price for an easier way to compute distances.

The "Taxicab Tile" gives a reasonable results, quite similar to the "Euclidean Tile", but simply summing the tile coordinate. This is a very popular norm for this kind of problems

---

L0 Norm:

Using the max if axial distances, the disc becomes a rectangle and the equivalent diamond in canvas and tile space respectively

L0 Canvas

L0 Tile

Ok, let's face it: the L0 canvas is horrible.

On the other hand the "L0 Tile" make it sense: it is quite clean and very easy to compute. Can be taken into account when playing with slow device and we need to use every clock cycle.

---

Conclusions

The norms computed on canvas coordinates give the worst of the results: the two coordinate systems does not match very well so the price to have a easier norm is simply too high.

The Euclidean norm is the better choice but the slower one; The Taxycab norm offer a very good trade off.

The "L0" is the fastest and easier but the price is to have a distance that is a little unrealistic.

Answer 2

I assume you have points (x1, y1) and (x2, y2).

The pythagorean distance between them is sqrt((x1-x2)^2 + (y1-y2)^2). Leave out the sqrt if you just need a relative distance.

If you want to find a distance in grid tile units, then simply divide:

actual_distance/grid_size.

Answer 3

If you don't need exact distance, but only to check whether your object (x1,y1) is within given range from some point (x2,y2), you don't need sqrt at all. It would be enough to check the following:

(x1-x2)^2 + (y1-y2)^2 <= range * range

This goes directly from Euclidean distance formula and is very cheap to calculate