Distance between two points with staggered isometric coordinate system

Question

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

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
– Steven Stadnicki, Commented Mar 8, 2013 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. — House
– House, Commented Mar 9, 2013 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
– Konrad, Commented Mar 9, 2013 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
– Konrad, Commented Mar 9, 2013 at 10:56
It's the right way to do it, plus, it gives you a chance at more rep :) — House
– House, Commented Mar 9, 2013 at 14:51

AtkinsSJ · Accepted Answer · 2013-03-08 16:38:45Z

3

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.

edited Mar 8, 2013 at 16:38

answered Mar 8, 2013 at 14:04

AtkinsSJ

1313 bronze badges

\$\begingroup\$ Thanks for the help! With a couple of changes this proved to be the answer. I'll add the solution above. :-) \$\endgroup\$

Konrad
– Konrad

2013-03-08 16:20:48 +00:00
Commented Mar 8, 2013 at 16:20
\$\begingroup\$ So you have xDiff and yDiff but then your formula is ( v/2 + h)? \$\endgroup\$

bummzack
– bummzack

2013-03-08 16:34:30 +00:00
Commented 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
– AtkinsSJ

2013-03-08 16:39:37 +00:00
Commented Mar 8, 2013 at 16:39

Add a comment |

Community · Accepted Answer · 2017-04-13 12:18:45Z

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 ) );
    }
}

Frederik · Accepted Answer · 2013-03-08 13:43:32Z

0

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.

answered Mar 8, 2013 at 13:43

Frederik

101

Add a comment |

ioanD · Accepted Answer · 2013-03-09 11:21:14Z

0

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.

answered Mar 9, 2013 at 11:21

ioanD

1214 bronze badges

Add a comment |

Stack Exchange Network

Distance between two points with staggered isometric coordinate system

4 Answers 4

You must log in to answer this question.

Linked

Hot Network Questions

Distance between two points with staggered isometric coordinate system

4 Answers 4

You must log in to answer this question.

Linked

Related

Hot Network Questions