Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
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
5  
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
1  
@crazy: Look up "torus" on Wikipedia... –  Kerrek SB Nov 15 '11 at 15:43
show 2 more comments

migrated from stackoverflow.com Nov 16 '11 at 1:59

This question came from our site for professional and enthusiast programmers.

6 Answers

up vote 8 down vote accepted

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
share|improve this answer
1  
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
1  
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
add comment

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}: enter image description here

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!

share|improve this answer
1  
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
1  
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. –  romkyns Nov 18 '11 at 10:15
add comment

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));
share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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
share|improve this answer
    
This code is slightly better than Toomai's but doesn't work either. –  Sam Hocevar Nov 16 '11 at 13:49
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.