Finding direction of travel in a world with wrapped edges

Question

I need to find the shortest distance direction from one point in my 2D world to another point where the edges are wrapped (like asteroids etc). I know how to find the shortest distance but am struggling to find which direction it's in.

The shortest distance is given by:

int rows = MapY;
int cols = MapX;

int d1 = abs(S.Y - T.Y);
int d2 = abs(S.X - T.X);
int dr = min(d1, rows-d1);
int dc = min(d2, cols-d2);

double dist = sqrt((double)(dr*dr + dc*dc));

Example of the world

                   :         
                   :  T    
                   :         
    :--------------:---------
    :              :
    :           S  :
    :              :
    :              :
    :  T           :
    :              :
    :--------------:

In the diagram the edges are shown with : and -. I've shown a wrapped repeat of the world at the top right too. I want to find the direction in degrees from S to T. So the shortest distance is to the top right repeat of T. but how do I calculate the direction in degreed from S to the repeated T in the top right?

I know the positions of both S and T but I suppose I need to find the position of the repeated T however there more than 1.

The worlds coordinates system starts at 0,0 at the top left and 0 degrees for the direction could start at West.

It seems like this shouldn’t be too hard but I haven’t been able to work out a solution. I hope somone can help? Any websites would be appreciated.

Answer 1

You'll have to tweak your algorithm a bit to calculate the angle - currently you only record the absolute difference in position, but you need the relative difference (i.e. can be positive or negative depending on positioning).

int dx = T.X - S.X; // difference in position
int dy = T.Y - S.Y;

if (dx > MapX / 2) // if distance is bigger than half map width, then looping must be closer
    dx = (dx - MapX) * -1; // reduce distance by map width, reverse 
else if (dx < -MapX / 2) // handle the case that dx is negative
    dx = (dx + MapX) * -1;

//Do the same for dy
if (dy > MapY / 2)
    dy = (dy - MapY) * -1;
else if (dy < -MapY / 2)
    dy = (dy + MapY) * -1;

double dist = sqrt(dy*dy+dx*dx); // same as before
double angle = atan2(dy,dx) * 180 / PI; // provides angle in degrees

Answer 2

In such a world there are infinite number of paths from S to T. Let's denote the coordinates of T by (Tx, Ty), the coordinates of S by (Sx, Sy), and the size of the world by (Wx, Wy). The wrapped coordinates of T are (Tx + i * Wx, Ty + j * Wy), where i and j are integers, that is, elements of the set {..., -2, -1, 0, 1, 2, ...}. The vectors connecting S to T are (Dx, Dy) := (Tx + i * Wx - Sx, Ty + j * Wy - Sy). For a given (i, j) pair, the distance is the length of the vector, sqrt(Dx * Dx + Dy * Dy), and the direction in radians is atan(Dy / Dx). The shortest path is one of the 9 paths, where i and j are in {-1, 0, 1}:

The i and j values for the shortest path can be determined directly:

int i = Sx - Tx > Wx / 2 ? 1 : Sx - Tx < -Wx / 2 ? -1 : 0;
int j = Sy - Ty > Wy / 2 ? 1 : Sy - Ty < -Wy / 2 ? -1 : 0;

Thank you, @IlmariKaronen, @SamHocevar and @romkyns for your help!

Answer 3

Compute one possible direction vector, even if it's not the shortest, then wrap its X coordinate so that it is in the [-MapX/2,MapX/2] range, and same for Y:

int DirX = (T.X - S.X + 3 * MapX / 2) % MapX) - MapX / 2;
int DirY = (T.Y - S.Y + 3 * MapY / 2) % MapY) - MapY / 2;

That's it! You also get the distance without further calculations:

double dist = sqrt((double)(DirX*DirX + DirY*DirY));

Answer 4

I guess there are a number of ways to do this. Here are 2 I can think of off the top of my head:

#1: Handle cases manually

There are exactly 10 cases that can happen:

• It's in the same tile as S
• It's in any of the 8 surrounding tiles
• It's not found at all.

For each of the surrounding tiles though, they are permutations of different calculations for the X or Y distance component. Because it's a finite number of cases, you can just hard-code how to calculate them, and find the shortest distance between all of them.

Here's an illustration of 2 cases for finding dx. Case 1, where T is in the same tile as S, dx is just S.x - T.x. For the tiles to the right, dx will be calculated as TileWidth - S.x + T.x.

               :         
               :  T    
               :         
:--------------:---------
:              :
:           S  :
:  |--------|--:--|
:dx=(S.x-T.x) dx=(TileWidth-S.x+T.x)
:  T           :
:              :
:--------------:

As a small optimization, find the minimum distance before you take a square root. Then you save yourself up to 7 sqrt calls.

#2: Abstract the coordinates

If you need to do something more spacially "fluid", like a path-finding algorithm, just abstract the coordinates so your path finding algorithm doesn't even realize the world is made of repeating tiles. The path-finding algorithm could go infinitely in any direction theoretically (ok well you'll be limited by numeric limits, but you get the point).

For simple distance calculation, don't bother doing this.

Answer 5

Don't bother with the "9 directions". The reason is that there are 5 degenerate cases amongst those 9: "straight north", "straigt west", "straight south", "straight east" and "identical". For instance, straight north is degenerate because it represents the case where northwest and northeast join and produce the same result.

Thus, you have 4 directions to calculate, and can just pick the minimum.

Answer 6

Thanks for all the answers in the end I used Toomai edited by Scott Chamberlain. I had too make a few changes due to the fact that my coordinate system starts with y at the top left and increases as you move down (basically inverted compared to normal graph coordinates for y).

I've posted in case anyone else finds this page and has the same reversed y system.

  int dx = T.X - S.X; // difference in position
int dy = S.Y - T.Y;

if (dx > MapX / 2) // if distance is bigger than half map width, then looping must be closer
    dx = (dx - (MapX / 2)) * -1; // reduce distance by half map width, reverse 
else if (dx < -MapX / 2) // handle the case that dx is negative
    dx = (dx + (MapX / 2)) * -1;

//Do the same for dy
if (dy > MapY / 2)
    dy = (MapY - dy)) * -1;
else if (dy < -MapY / 2)
    dy = (dy + MapY);

double angle = atan2(dy,dx) * 180 / PI; // provides angle in degrees

angle = 180 - angle; //convert to 360 deg