CODEWITHSUNDEEP
algorithm2d
Loadex
Loadex

Reputation: 1512

Calculating distance between 2 points on a circular map

I'm currently trying to create a video game where characters are AI and are in a circular map with ressources on it.

I'm currently trying to calculate the shortest distance betwing 2 points on this map but my problem is that the map is circular : for example

if my map is 20*20 and i m in (0,0) the (19,0) point has a distance on 1 only. I've been looking on the internet but i didn't found answers for my problem. I have to take care of the orientation (North South west East) of my character too, in he has to turn to go to the point, the distance has to be longer.

Is there an existing formula ?

Thanks for reading !

Upvotes: 8

Views: 2266

Answers (2)

amit
amit

Reputation: 178411

The problem remains a shortest path problem in a graph, you just need to add edges for the circular map:

G = (V,E) where V = {all squares} and E = { (u,v) | [(u.x + 1 % 20 = v.x or u.x -1 % 20 = v.x) and u.y == v.y] or ... [same for y] }

What the mathematical notation above says: there is an edge between two squares if (and only if), the difference between their x or y cordinates is 1 or -1 in Z20 (modolus 20 ring). Since the ring Z20 is circular itself - it solves the circularity problem of the map.

Given this graph you can use BFS to find the shortest path from a single source (no need for dijkstra's algorithm because the graph is unweighted)

Note: If there are not obstacles, just calculate it using your regular distance function, but use the Z20 ring instead of the Z field in your math.

Upvotes: 3

RiaD
RiaD

Reputation: 47619

For every coordinate choose the minimal distance, and then use it as usual.

int dx = min(abs(x0-x1),20-abs(x0-x1));
int dy = min(abs(y0-y1),20-abs(y0-y1));

For euclid distance :

double dist = sqrt(dx * dx + dy * dy);

For Manhattan distance:

int dist = dx + dy;

Upvotes: 5

Related Questions