# Distance on a wrap-around field (SOLVED)

This topic is 4248 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello, I'm trying to find a good way to define distance between two points in a 2D world that wraps around at the sides (like Asteroids). It shouldn't "favor" directions like e.g. the "Manhattan" distance does. My intuition tells me it should be the length of the shortest line between two points. But since a line can wrap around, I'm not sure how I could calculate that. Any ideas? [Edited by - Barius on June 7, 2006 12:37:25 PM]

##### Share on other sites
Why not do this:

1) choose one point to be the anchor point
2) compute the distance to the other point---the version to the left of the anchor
3) compute the distance to the other point---the wraparound version to the right of the anchor
4) choose the shortest of 2 or 3
5) if 2 and 3 are equal, choose 2.

?

##### Share on other sites
Well, Graham beat me to it, but I drew a little diagram so I'll post it anyway:

Basically you 'project' each point into each of the four adjacent 'virtual' screen areas, for a total of 5 versions each of the two points, and then find the closest pair or pairs. From there you can find the minimum distance, and perhaps other information useful for enemy AI or what have you.

##### Share on other sites
You are missing some cases, what if you wrap around two edges at once? There should be 9 cases instead of 5.

I think you can simplify this however. Of the 9 possible locations for the destination point, only 4 are interesting. If the destination point is to the left of the start, you wouldn't ever wrap around the left side, only the right. Same for the y componenet. This gives us a situation like:

         |          |           |    D01    |  D11---------+---------       S |          |           |  D00    |  D10

Even though you are using the distance formula to find the actual distance, the choice of destination point is independant in the x and y directions. First decide if you want to wrap in x, then in y. This gives you the closest destination. Then you can directly calculate the distance.

If the abs of x distance between S and D00 is greater than half the width of the screen then it will be closer to wrap in the x direction. The sign of this distance would tell you which way to wrap. You can do the same thing in the y direction.

int xDist = dx - sx;int yDist = dy - sy;int x = dxint y = dy;if(xDist > width/2) { // dx too far to the +x  x -= width; }else if(xDist < -width/2) { // dx too far to the -x  x += width;}if(yDist > height/2) { // dy too far to the +y  y -= height; }else if(yDist < -height/2) { // dy too far to the -y  y += height;}return sqrt((x - sx) * (x - sx) + (y - sy) * (y - sy));

##### Share on other sites
Quote:
 Original post by SoliasYou are missing some cases, what if you wrap around two edges at once?
Are you sure? Here's an example of a 'wraps around both edges' case:

In this example at least, the correct direction and distance is still returned, and just looking at it, I still can't think of a case where this approach would fail.

Also, in my previous post I was just trying to present the concept, not to address implementation; I wasn't proposing that testing all possible pairs would actually be required. In any case, your implementation looks good and is probably just what the OP is looking for :)