I would expect start == goal to return just an empty path (length 0).

Could it be that you're still too slow, and that you're exceeding some time-limit they're enforcing?

What about trying to just generate a bunch of maps, and for those maps generating every single path possible (from all starts go to all ends), seeing if something fails.

EDIT: Something else to consider -- if you reverse the path, do you get the same path-length in all scenarios? If there's a mis-match, then you have a bug.

Nope timeout is actually something it tells you. I got that before but not anymore. It's really fast now:)

How would I generate random maps and then see if it fails (when it shouldn't)? Often there is no valid path in a randomly filled map.

All path-length seem to be fine. Here are some tests I made. Still cannot figure out why it tells me "wrong answer"...

When I solved this problem I used maps and benchmarks from http://www.movingai.com/benchmarks/ to find any bugs in my implementation. These are nice because you get problems and the correct minimal path length with them.

If there's nothing wrong with the pathfinding, it might be something about the output format, IIRC that was somewhat tricky to get right for all cases. Make sure the output is still correct if you search for multiple paths without any additional cleanup in main().

Can this be related to the "problem":

Changing the wall (obstacle) where it doesnt pass with the end path anyway (but still nodes it considers) slightly changes the end path. It changes between two different path of equal length though so both paths should be fine.

I tried to get well into your code but I didn't.

Just a small tip: Neighbourhood operations are frequent. Do not check on the boundaries, add +1 (or more) size to your map. This will save you code and you can render it nicely.

Can this be related to the "problem":

Changing the wall (obstacle) where it doesnt pass with the end path anyway (but still nodes it considers) slightly changes the end path. It changes between two different path of equal length though so both paths should be fine.

Who knows? I don't think we can read the mind of whoever set you this task. Perhaps contact them with your concerns. It's not an intrinsic issue for A* though - there can be multiple shortest paths and as long as you find one of them, the algorithm is probably correct.

Are you supposed to support diagonal movement? If not, were you given any other criteria to follow (e.g. minimal turns in the path)?

If you want to avoid variations like this then you will want to ensure that the sorting order of nodes is consistent, even when the scoring is the same - for example, by using the x and y coordinates as a tie-breaker.

No other critieria. Diagonal movement was not to be allowed, so I just made that an option that is off by default.

It's very strange indeed. I've contacted them and given them my current code, we'll see if I burned my chances or not!

Stop allocating and deallocating the std::vectors closedMap, openMap, and dirMap.
Store them somewhere persistent and pass them into the function, being sure to clear() them each time (or just ::memset() them to 0 if the map size has not changed).


L. Spiro

So, this does not allow diagonal movement? I thought, that is all the complication is about.

I do not use any of containers for this because I honestly see no reason, yet it works very fast. The only one it could be is the front of the wave (vector).

What these priority queue and vector operations are?

You make a 2D array, mark it, and if you need the whole path, do it like:

Left: 0, 1, 2, 3, ...

Top: 1000, 1001, 1002, 1003, ...

Right: 2000, 2001, 2002, ...

then retrieve the way back, that is much less operations.

Don't you?

Keep in mind that A* is not a grid search algorithm, it's a general graph search algorithm.

If you want to search grids there are known techniques like JPS+ that are vastly more efficient.

If you want the flexibility to search a graph, though, you need a more robust and "literal" version of A*.