There is a fully-tested implementation of A* (as well as several other shortest path implementations) in the Boost C++ libraries (the Boost graph library), as well as a comprehensive framework for representing the graphs. It takes very little time to get A* up and running using these - and IMHO it is always preferable to use a good library (as long as it fits) rather than to code your own implementation - no need to reinvent the wheel. There are also python bindings for the library, for those who'd rather prototype in a scripting language - but with the benefit of a compiled implementation for the A* algo.
The BGL: http://www.boost.org/libs/graph/doc/table_of_contents.html Python bindings: http://www.osl.iu.edu/~dgregor/bgl-python/ An AStar example: http://www.boost.org/libs/graph/example/astar-cities.cpp Alex Nic Roets wrote: >> Would it break anything to even use sqr(dx)+sqr(dy) instead of >> sqrt(sqr(dx)+sqr(dy)) ? >> > > If dx is in degrees or radias, you'll end up with Dijkstra and if it's > meters, the routing will be worse than my mom. > > If you want to get rid of the squareroot, you can try variations of > the "taxi-cab" metric like |x|/2 + |y|/2 or max(|x|,|y|) also known as > the l_1 and l_infinite norms. > > I see Jon when for all out great circle distances which is > computationally intensive and theoretically more accurate, but > practically much less important than penalizing right turns. > > The next level would be to cut the map into regions / tiles and > precompute lower bounds on the shortest / fastest path. At run time > those lower bounds are then fed into the heuristic. But that > improvement will only improve the speed a few percent. > > If you have enough memory (say 100 bytes per segment) you can write a > C version without hashing. Then the only "slow" part is the priority > queue (heap). > > _______________________________________________ > Routing mailing list > [email protected] > http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing > > _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
