Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
2  
What exactly is wrong with calculating the difference between the two grid coordinates? –  bummzack Jun 29 '11 at 18:51
1  
I didn't think it would be accurate enough, as it's based on cells, and I needed a circular (elliptical on screen) area to be checked from the mouse pointer to the building, but I just tried and it seems to be basically ok, thanks. –  Phil Jun 29 '11 at 22:07
add comment

2 Answers

up vote 10 down vote accepted

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

L2 canvas

Euclidean Canvas

L2 tile

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)

L1 canvas

Taxicab Canvas

L1 tile

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 Canvas

L0 tile

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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