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.

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:

enter image description here

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

enter image description here

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.

enter image description here

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

share|improve this question
2  
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 4

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.

share|improve this answer
    
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
up vote 1 down vote accepted

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 ) );
    }
}
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.