# Distance between two points with staggered isometric coordinate system

I don't think this exact question has been asked already (I've done a lot of searching but come up empty).. I am trying to work out what would be described as the 'L0 Tile' distance between two points in my game in tiles.

My coordinate system is as below:

And this is the effect I'm looking for when calculating distance from a central point:

The problem is I keep running into boundary conditions when trying to come up with a better solution than just 'walking' between the two positions and counting the steps.

The code I have at the moment only works if the direction between the two points is perfectly vertical, horizontal or diagonal:

``````if( fIsVertical )
{
// Vertical distance calculation

nDistance = nYDifferenceTiles / 2;

}
else if( fIsHorizontal )
{
// Horizontal distance calculation

nDistance = nXDifferenceTiles;
}
else
{
// Diagonal distance calculation (slightly more headache-prone)

bool fIsPerfectDiagonal = false;

if( nYDifferenceTiles % 2 == 0 )
{
// Irrespective of W or E path these values are always the same

if( nXDifferenceTiles * 2 == nYDifferenceTiles )
{
fIsPerfectDiagonal = true;
}
}
else
{
// Values for X when Y is odd are slightly different..

if( fNorthWestOrSouthWest )
{
// Handle the West paths
if( nXDifferenceTiles == ( nYDifferenceTiles - std::floor( nYDifferenceTiles / 2.0 ) ) )
{
fIsPerfectDiagonal = true;
}
}
else
{
// Handle the East paths
if( nXDifferenceTiles == ( nYDifferenceTiles - std::ceil( nYDifferenceTiles / 2.0 ) ) )
{
fIsPerfectDiagonal = true;
}
}
}

// Now we've calculated whether we are on a perfect diagonal
// line from the origin we can decide how to calculate the distance

if( fIsPerfectDiagonal )
{
// If exact diagonal this works well
nDistance = std::max< int >( nYDifferenceTiles, nXDifferenceTiles );
}
else
{
// ? - problem
}
}
``````

So in the diagram below, the green tiles are correctly calculated but for the red ones I have to fall back to my quick and nasty code to walk the distance.

Despite trying a good few things I'm still no closer to having a simple and quick way of calculating the distance. I'm sure this problem has to have been addressed before and that I'm missing something probably obvious. Please help! :)

-
This doesn't answer your question so I'm leaving it as a comment, but a strong recommendation: I would decouple your internal coordinate system for addressing tiles - which should arguably be just a straight grid - from the way that they're displayed. There are just so many advantages to having a clean uniform gridding on your cells - this is an obvious one, but even just stepping from cell to cell, calculating distances, etc. will be so much easier that I suspect you'll be happier in the long run. – Steven Stadnicki Mar 8 '13 at 19:39
Rolled back your changes. Solutions go in the answers section, not the question area. If you want to provide an answer, add it as an answer. – Byte56 Mar 9 '13 at 0:51
@StevenStadnicki everything that has a position in the game has an EntityPos structure containing 3D co-ordinates of the object. This is entirely decoupled from the rest of the logic. I have helper functions which handle transforming the postion across the different axis. I'm not entirely sure if this is what you mean, if not - could you elaborate further? – Konrad Mar 9 '13 at 10:54
@Byte56 I'm sure I've seen answers inline like this on other SO sites, at any rate I've added the solution below as you suggested. – Konrad Mar 9 '13 at 10:56
It's the right way to do it, plus, it gives you a chance at more rep :) – Byte56 Mar 9 '13 at 14:51

## 4 Answers

Let xDiff be the difference between the x coordinates, and yDiff be the difference between the y coordinates.

The tile distance is ( yDiff/2 + xDiff ) rounded up to the nearest integer.

-
Thanks for the help! With a couple of changes this proved to be the answer. I'll add the solution above. :-) – Konrad Mar 8 '13 at 16:20
So you have `xDiff` and `yDiff` but then your formula is `( v/2 + h)`? – bummzack Mar 8 '13 at 16:34
Sorry bummzack, I messed-up. xDiff is h, yDiff is v. (I've ammended my answer) – AtkinsSJ Mar 8 '13 at 16:39

Answering question to provide full solution building on the answer from AtkinsSJ (thanks a lot for the nudge in the right direction) to address a couple of edge cases.

``````if( fIsNorthOrSouthWest )
{
// Special case when the second position is to the left of the first

if( rPos1.m_y % 2 == 0 )
{
nDistance = static_cast< int >( std::floor( ( nYDifferenceTiles / 2.0 ) + nXDifferenceTiles ) );
}
else
{
nDistance = static_cast< int >( std::ceil( ( nYDifferenceTiles / 2.0 ) + nXDifferenceTiles ) );
}
}
else
{
if( rPos1.m_y % 2 == 0 )
{
nDistance = static_cast< int >( std::ceil( ( nYDifferenceTiles / 2.0 ) + nXDifferenceTiles ) );
}
else
{
nDistance = static_cast< int >( std::floor( ( nYDifferenceTiles / 2.0 ) + nXDifferenceTiles ) );
}
}
``````
-

What about distance=min(dx,dy) ?

Assume the center (0,0) is cx,cy and x,y is the tile you want to test.

Then dx=cx-x and dy=cy-y.

-

You can declare a matrix witch contains each isometric cell, then calculate the distance between the two points in the matrix, just like this: dist=sqrt( ( (x1 - x2 ) * ( x1 - x2 ) ) + ( ( y1 - y2 ) * ( y1 - y2 ) ) )

...sorry for the spelling.

-