Sign in to follow this  
Barius

Distance on a wrap-around field (SOLVED)

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 = dx
int 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 this post


Link to post
Share on other sites
Quote:
Original post by Solias
You 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 :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this