4
\$\begingroup\$

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

\$\endgroup\$
7
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Mar 8, 2013 at 19:39
  • \$\begingroup\$ 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. \$\endgroup\$
    – House
    Mar 9, 2013 at 0:51
  • \$\begingroup\$ @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? \$\endgroup\$
    – Konrad
    Mar 9, 2013 at 10:54
  • \$\begingroup\$ @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. \$\endgroup\$
    – Konrad
    Mar 9, 2013 at 10:56
  • \$\begingroup\$ It's the right way to do it, plus, it gives you a chance at more rep :) \$\endgroup\$
    – House
    Mar 9, 2013 at 14:51

4 Answers 4

3
\$\begingroup\$

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.

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

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 ) );
    }
}
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .