I am using a Isometric slide map style to draw my game, one of the problems with doing this is the coordinate system is a bit different than a standard X / Y axis for figuring out movement etc.

[attachment=5073:Untitled.png]
To figure out distance you need to do tilewalks because as shown in this picture the coordinate system is a bit strange!

So basically I want to draw an overlay with the amount of movable spaces so players can see how far they are moving... Well after much coding I came up with a very complicated solution to a very easy to solve problem and I was wondering if anyone could help me find an easier way.

I wrote a function to do a standard tilewalk given a set of coordinates and returns the next space you would be on depending on what direction you move (compass directions)
here is that function (below)

But the problem is as you go up in movements it takes way more processing, exponentially more, for a movement of 10 spaces it takes over 30k lookup's to see if that tile is already on the list (99.9999% of them are already on the list but the cost to look up if they are is what is killing me)


POINT OverlayManager::TileWalk(int Direction, int Xstart,int Ystart) //walks in a direction returns new space
{
POINT NewLoc;
switch (Direction)
{
case DIRN: //NORTH
{
if(Xstart&1) //if X is odd we need a special case to also make X less
{
if(Ystart&1) // if y is odd also
{
NewLoc.x = Xstart +1;
NewLoc.y = Ystart -1;
}
else //else y is even
{
NewLoc.x = Xstart;
NewLoc.y = Ystart -1;
}
}
else //X is even
{
if(Ystart&1) // if y is odd also
{
NewLoc.x = Xstart +1;
NewLoc.y = Ystart -1;
}
else //else y is even
{
NewLoc.x = Xstart;
NewLoc.y = Ystart -1;
}
}
}break;
case DIRE: //East
{
if(Xstart&1) //if X is odd we need a special case to also make X less
{
if(Ystart&1) // if y is odd also
{
NewLoc.x = Xstart +1;
NewLoc.y = Ystart +1;
}
else //else y is even
{
NewLoc.x = Xstart;
NewLoc.y = Ystart +1;
}
}
else //X is even
{
if(Ystart&1) // if y is odd also
{
NewLoc.x = Xstart +1;
NewLoc.y = Ystart +1;
}
else //else y is even
{
NewLoc.x = Xstart;
NewLoc.y = Ystart +1;
}
}

}break;
case DIRS: //South
{
if(Xstart&1) //if X is odd we need a special case
{
if(Ystart&1) // if y is odd also
{
NewLoc.x = Xstart ;
NewLoc.y = Ystart +1;
}
else //else y is even
{
NewLoc.x = Xstart -1;
NewLoc.y = Ystart +1;
}
}
else //X is even
{
if(Ystart&1) // if y is odd also
{
NewLoc.x = Xstart ;
NewLoc.y = Ystart +1;
}
else //else y is even
{
NewLoc.x = Xstart -1;
NewLoc.y = Ystart +1;
}
}

}break;
case DIRW: //West
{
if(Xstart&1) //if X is odd we need a special case
{
if(Ystart&1) // if y is odd also
{
NewLoc.x = Xstart ;
NewLoc.y = Ystart -1;
}
else //else y is even
{
NewLoc.x = Xstart -1;
NewLoc.y = Ystart -1;
}
}
else //X is even
{
if(Ystart&1) // if y is odd also
{
NewLoc.x = Xstart ;
NewLoc.y = Ystart -1;
}
else //else y is even
{
NewLoc.x = Xstart -1;
NewLoc.y = Ystart -1;
}
}

}break;

}
return NewLoc;
}


And what I do is I have a base function to add our start location and tile walk in every direction and build up a lookup vector that only contains the tiles we have determined are in the overlay.

void OverlayManager::AddStandardMovementOverLay(int OriginX, int OriginY, int MoveSpaces, int OffSetX, int OffSetY)
{
OverLays.clear(); //clear out other overlays

CurrentOffSetX = OffSetX;
CurrentOffSetY = OffSetY;

int X = OriginX;
int Y = OriginY;
AddSingleOverLay(X, Y);

for(int a=0;a<4;a++) //For each direction
{

AddAllNodes(a, X, Y, MoveSpaces-1);

}

}


void OverlayManager::AddSingleOverLay(int X, int Y)
{
if(IsOnList(X,Y) == false) //don't add duplicates
{
OTILE NewTile;
NewTile.colour = D3DCOLOR_ARGB(255,255,255,255);
NewTile.mapx = X;
NewTile.mapy = Y;
NewTile.onscreenx = 0;
NewTile.onscreeny = 0;

OverLays.push_back(NewTile);

}

}



void OverlayManager::AddAllNodes(int Dir, int StartX, int StartY, int Moves)
{

POINT Current;
Current.x = StartX;
Current.y= StartY;
if (Moves == 0)
{
return;
}
switch (Dir)
{
case DIRN: //NORTH
{
Current = TileWalk(DIRN, Current.x, Current.y);
AddSingleOverLay(Current.x, Current.y);
//for(int i=0;i<Moves;i++)
//{
AddAllNodes(DIRN, Current.x, Current.y, Moves -1);
AddAllNodes(DIRE, Current.x, Current.y, Moves -1);
AddAllNodes(DIRW, Current.x, Current.y, Moves -1);
//}
}break;
case DIRE: //EAST
{
Current = TileWalk(DIRE, Current.x, Current.y);
AddSingleOverLay(Current.x, Current.y);
//for(int i=0;i<Moves;i++)
//{
AddAllNodes(DIRE, Current.x, Current.y, Moves -1);
AddAllNodes(DIRN, Current.x, Current.y, Moves -1);
AddAllNodes(DIRS, Current.x, Current.y, Moves -1);
//}
}break;
case DIRS: //South
{
Current = TileWalk(DIRS, Current.x, Current.y);
AddSingleOverLay(Current.x, Current.y);
//for(int i=0;i<Moves;i++)
//{
AddAllNodes(DIRS, Current.x, Current.y, Moves -1);
AddAllNodes(DIRE, Current.x, Current.y, Moves -1);
AddAllNodes(DIRW, Current.x, Current.y, Moves -1);
//}
}break;
case DIRW: //West
{
Current = TileWalk(DIRW, Current.x, Current.y);
AddSingleOverLay(Current.x, Current.y);
//for(int i=0;i<Moves;i++)
//{
AddAllNodes(DIRN, Current.x, Current.y, Moves -1);
AddAllNodes(DIRW, Current.x, Current.y, Moves -1);
AddAllNodes(DIRS, Current.x, Current.y, Moves -1);
//}
}break;
}

}

Edit: I fixed a huge bug in my addallnodes code, it made it faster but im still interested in seeing other solutions!(from 1 million to 30k lookup's)

I am using a Isometric slide map style to draw my game, one of the problems with doing this is the coordinate system is a bit different than a standard X / Y axis for figuring out movement etc.

[attachment=5073:Untitled.png]
To figure out distance you need to do tilewalks because as shown in this picture the coordinate system is a bit strange!

I wrote a function to do a standard tilewalk given a set of coordinates and returns the next space you would be on depending on what direction you move (compass directions)

But the problem is as you go up in movements it takes way more processing, exponentially more, ...

I really would recommend re-doing your coordinate system to what you referred to as a "standard X/Y axis" format. That will allow you to optimize the distance function from exponential time to a constant time!


Don't let that 45 degrees rotation in rendering distract the logic part of it. Just imagine your map rotated back 45 degrees, that means your NORTH is towards up-right on the map, EAST to down-right, SOUTH is down-left, and WEST is up-left. So if you go NORTH, you just do y++, EAST = x++, SOUTH = y--, and WEST = x--.

I really would recommend re-doing your coordinate system to what you referred to as a "standard X/Y axis" format. That will allow you to optimize the distance function from exponential time to a constant time!

I am so far past the brink that it would be easier to completely start over at this point unfortunately.
Limiting the movement to below 6 takes mere milliseconds, upwards to 10 movement spaces can take 3 whole seconds.

I just remembered:
I found a resource a long time ago that used some bit shifting on this style of ISO map coordinate system to convert it to a standard coordinate system for pathfinding but I cannot find it again :/

I have days/months? worth of development time in a mouse mapping system, animation, particle system,etc, all built around this style of coordinate system
not to mention a map editor also.

Then you could try covering the map with a double coordinate system, like follows: http://imageshack.us...2/unledefs.jpg/

Call the black coordinates CARTESIAN coordinates, in which it is easy to move in different compass directions just by incrementing or decrementing x and y.

Denote by STRANGE the red coordinates you are using.

Then you have a bijective mapping from a pair of STRANGE coordinates (x,y) to CARTESIAN coordinates (X,Y) as follows:



X=x-y/2 (using integer division)
Y=x+y/2 (using integer division)



and the reverse



x=(X+Y)/2 (using integer division)
y=Y-X



Now, to compute movements on the map, transform your input STRANGE coordinates (x,y) to CARTESIAN (X,Y), then move e.g. 5 units north to get (X+5,Y), then convert this back to STRANGE (which gives in this case ( (X+Y+5)/2, y-5) ).

This is also constant time, and note that it doesn't require looping, since you can add arbitrary values to cartesian (X,Y), e.g. 4 units north and 7 units east is (X+4,Y+7).

Wow, I can't wait to try that out, you make it seem so easy!

I never even though about a conversion to a standard Cartesian system, or that it would even be possible!
Thank you so much!
If you ever happen to make it over to Whidbey Island I will buy you a beer =)

I wrote a test application to try this out and im not getting expected results maybe you can see what I am doing wrong?

// test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{

int x1 = 4;
int y1 = 17;


int CartX1 = x1-(y1/2);
int CartY1 = x1+(y1/2);


cout << "CartX1: " << CartX1 << endl;
cout << "CartY1: " << CartY1 << endl;

CartX1 +=5; //add +5 to X

int SCordX1 = ( CartX1+CartY1)/2;
int SCordY1 = CartY1 - CartX1;

cout << "SCordX1: " << SCordX1 << endl;
cout << "SCordY1: " << SCordY1 << endl;


system("pause");
return 0;
}



The results I get are:

CartX1: -4
CartY1: 12
SCordX1: 6
SCordY1: 11

Where SCordX1 should = 7 and
SCordY1 should = 12

I did a little reasoning and came up with this formula:

distance from tile 1 at (x1, y1) to tile 2 at (x2, y2) assuming all directions have the same movement cost is

abs(x2 - x1) + ceiling(abs(y2 - y1) / 2)

It worked with the coordinates I tested based on your map.

Derived from finding out that:
1. if y1 = y2 then d = abs(x2 - x1)
2. if x1 = x2 then d = ceil(abs(x2 - x1) / 2)
and then just guessing that since 2 included one as a subcase, that it might just work for everything. Turned out it seems to have done so.

Not sure how that corresponds to clb's post. I suspect if you plug his formula's into the cartesian distance formula you will get my result. I started but got somewhere messy. Might try some more.

Sleeping over the night, I suspect I got the rounding off on the conversion. This might work correcly?



(X,Y) CARTESIAN to (x,y) STRANGE

x=(X+Y)/2
y=Y - X


and the opposite:
X=x-y/2
Y=x+(y+1)/2


That gives the wanted (7,12) on the example you gave me, but I didn't try out other values, so be sure to test it out properly.

Thank you guys for your help, this works fantastically!
going from several seconds to less than 1 millisecond to calculate distances is amazing ! =p