What is a good benchmark for A* (AStar)?

Question

I wrote myself an A*, it works quite well and now comes the time to evaluate its performance (potentially against other solutions to see how it performs).

For both having visual feedback and fun I use it as an image maze solver. First - I know this is not what A* has been primarily designed for, but I think it is quite a good way (yet not the only one) to test it. Agree ? I've kept it very simple : white pixels are nodes and other colours are walls.

I've thought of throwing this maze (large picture) at it, but I know that it will

• obviously take some time, because it has more than 3 000 000 edges (and a bit less than half as walls, but still)
• not necessarily be a good indicator, over-sized environment

To sum up : what kind of environment is a good stress-test for A* ? What's the order of magnitude of graphs in applicative A* (in games for example) ?

Answer 1

A good stress test is a digital road network for
1) part of a big country (like spain, france, germany) , then
2) The whole country. (some million nodes)

OpenStreetMap provides such data, but it is much work to import that to a graph.