Search for trajectory algorithms for maps without edges

Question

I have 2D world maps, which are basically projections similar to the Mercator, (if you go west long enough, you will find yourself east of where you started)

Question: Do you have the opportunity to use A * to calculate the paths on these types of maps?

I can’t think of any reason why you couldn’t (I think you just represent the nodes of the edge map, so the nodes "North", "South", "East", "Wednesday", "border" are simply connected to the opposite side).

Thanks in advance, if someone has seen something like this before or can give me some advice, I would appreciate it.

Answer 1

Path finding algorithms really don't care about the global map topology. The only difficult task is to get a good grade for A *, but using 3D distance should be fine if your map is really a surface in three-dimensional space and the step cost is the step length.

There may be all kinds of strange “connections” in your map (including, for example, nodal bridges), and this will not be a problem if you correctly implement A *.

Answer 2

I cannot imagine why Mercator-Like predictions will cause a problem for A * if your heuristic function approximates distances correctly. I think something at the bottom of the 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 understand that I was misled by a non-graphical theory) using the word edge (where the title of the question strongly suggested a question with a graph algorithm :))

_{Why do you think there are no ribs? There are many logical discrete locations that you could simulate, and limited connections between (that is, not where the wall is :)). Here you are: you have your own edges.}

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

What did you say:

you ask if anyone has seen this before. I vaguely remember that I saw something related to this in a Knuths Dancing Links (DLX) article, which is a method for implementing A * algorithms.

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

The article considers states as “cells” (in a grid) using east / west / north / south connections. It has been a long time, so I don’t quite remember how you would choose (not a pun) your problem with this algorithm.

Dance steps . One of the good ways to implement algorithm X is to represent each 1 in matrix A as a data object x with five fields L [x]; [X]; U [x]; D [x]; C [x]. Matrix rows are connected twice as circular lists through the L and R fields ("left" and "right"); the columns are double linked as circular lists across the U and D fields (up and down). Each column in the list also includes a special data object called its list header.