Shortest distance between points on a toroidally wrapped (x- and y- wrapping) map?
- by mstksg
I have a toroidal-ish Euclidean-ish map. That is the surface is a flat, Euclidean rectangle, but when a point moves to the right boundary, it will appear at the left boundary (at the same y value), given by x_new = x_old % width
Basically, points are plotted based on:
(x_new, y_new) = ( x_old % width, y_old % height)
Think Pac Man -- walking off one edge of the screen will make you appear on the opposite edge.
What's the best way to calculate the shortest distance between two points? The typical implementation suggests a large distance for points on opposite corners of the map, when in reality, the real wrapped distance is very close.
The best way I can think of is calculating Classical Delta X and Wrapped Delta X, and Classical Delta Y and Wrapped Delta Y, and using the lower of each pair in the Sqrt(x^2+y^2) distance formula.
But that would involve many checks, calculations, operations -- some that I feel might be unnecessary.
Is there a better way?
