# Finding direction of travel in a world with wrapped edges

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.

• What are the coordinates for the T in the top right? – Adhemar Nov 15 '11 at 15:22
• I have never seen a game with diagonal wrapping. Usually you have one wrap for each direction (N,E,S,W). – Björn Pollex Nov 15 '11 at 15:23
• Any game that has both horizontal and vertical wrapping has diagonal wrapping by default. – Toomai Nov 15 '11 at 15:31
• Think of each coordinate as living on a circle, and figure out the shorter of the two possible distances for each coordinate individually. – Kerrek SB Nov 15 '11 at 15:32
• @crazy: Look up "torus" on Wikipedia... – Kerrek SB Nov 15 '11 at 15:43

## 6 Answers

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

• You need some work on the signs of dx and dy as the code as is will break if T.X is less than S.X or T.Y is less than X.Y. Other than that this is the best solution IMHO. – Scott Chamberlain Nov 15 '11 at 16:00
• Right then I'll fix that. – Toomai Nov 15 '11 at 16:28
• Still got a few errors on what the sign of dx and dy will be when all is said and done, mind if I edit? – Scott Chamberlain Nov 15 '11 at 16:38
• Why is this the accepted answer?? It doesn't even work. Suppose MapX is 100, T.X is 90 and S.X is 10. dx should clearly be 20, but this algorithm will return 30! – sam hocevar Nov 16 '11 at 13:46
• Ugh this is what happens when you don't have to opportunity to test code before posting it. Will fix. If someone finds another error with this I'll probably just delete it before too many people get mislead. – Toomai Nov 16 '11 at 16:06

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!

• You can do better than that: if abs(Tx-Sx) < Wx/2, then i=0 is optimal; otherwise the optimal choice is i=-1 or i=1, depending on the sign of Tx-Sx. Same goes for Ty-Sy and j. – Ilmari Karonen Nov 16 '11 at 4:41
• This answer is incredibly complicated for such a simple problem. There is no need to use linear search when the minimal value can be calculated directly. – sam hocevar Nov 16 '11 at 10:25
• Nice pic, but the algorithm suggested doesn't deserve any of the upvotes this answer has received. – RomanSt Nov 18 '11 at 10:15

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

• Thanks! GLSL version: vec2 toroidalNearestWay (vec2 from, vec2 to, vec2 mapSize) { return (mod((to - from + 3.0 * mapSize / 2.0), mapSize)) - mapSize / 2.0; } – 1j01 Jul 4 '18 at 4:46

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.

• Smart idea about comparing the squared distance value before taking the sqrt! – Scott Chamberlain Nov 15 '11 at 15:54
• Ah I see, @Kol has a similar answer with a more mathematical explanation, thanks this gives me something to work with – crazy Nov 15 '11 at 16:03
• Comparing the squared distance may be smarter than taking the sqrt, but using the Manhattan distance is even smarter since it requires no multiplication at all. – sam hocevar Nov 16 '11 at 10:30

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.

• I don't think this is right, or I've completely misunderstood you. One of the two. – Mooing Duck Nov 15 '11 at 23:27

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

• This code is slightly better than Toomai's but doesn't work either. – sam hocevar Nov 16 '11 at 13:49
• Also, you need to understand why you had to do these changes. It's not because your coordinate system starts with y at the top. It's because the desired behaviour is supposedly to wrap coordinates at the world edge, whereas the code you reused mirrored the coordinates at each boundary. – sam hocevar Nov 16 '11 at 14:13