Looking for pathing algorithms for maps without edges

Question

I have 2D world maps that are basically Mercator-Like projections, (If you walk west long enough you end up east of where you started)

Question I have: Can you use A* for computing paths on these types of maps as well?

I can't think of any reason why you couldn't (I'm thinking that you would simply represent the edge map nodes such that the North, South, East, Wed, "border" nodes simply connected to the opposite side).

Thanks in advance, if anyone has seen something like this before or can give me a few hints I would appreciate it.

Answer 1

Pathfinding algorithms don't really care about global topology of the map. The only tricky part is to get a good estimator for A* but using the 3D distance should be ok if your map is indeed a surface in a 3d space and step cost is step length.

Your map can have all sort of strange "connections" (including for example knotted bridges) and this will not be a problem if you implement A* correctly.

Answer 2

I can't imagine why a Mercator-Like projections would cause a problem for A*, as long as your heuristic function approximates distances correctly. I think something along the below function should work fine

float heuristic(point from, point to, size mapsize) {
    float x = from.x - to.x;
    if (abs(x) > mapsize.x/2)
        x = mapsize.x - x;
    float y = from.y - to.y;
    if (abs(y) > mapsize.y/2)
        y = mapsize.y - y;
    return sqrt(x*x+y*y);
}

Answer 3

Edited: I realize know I was misled by the non-graph theoretical) use of the word edge (where the question title strongly suggested a graph algorithm question :))

_{Why do you suppose there are no edges? There are many logical discrete locations that you could model, and limited connections between (i.e. not where a wall is :)). There you go: you have your edges.}

What you probably mean is that you don't want to represent your edges in data (which you don't have to, but still there are the logical edges that connect locations/points.)

That said:

you ask whether someone has seen things like this before. I vaguely recall seeing something relevant to this in Knuths Dancing Links article (DLX) which is an implementation technique for A* algorithms.

• http://en.wikipedia.org/wiki/Dancing_Links
• original publication [PDF]

The article specifically treats states as 'cells' (in a grid) with east/west/north/south links. It's been a long time so I don't quite recall how you would map (no pun intended) your problem on that algorithm.

The dance steps. One good way to implement algorithm X is to represent each 1 in the matrix A as a data object x with five fields L[x]; R[x]; U [x]; D[x]; C[x]. Rows of the matrix are doubly linked as circular lists via the L and R fields ("left" and "right"); columns are doubly linked as circular lists via the U and D fields ("up" and "down"). Each column list also includes a special data object called its list header.