[Routing] A-Star meet-in-the-middle

Nic Roets nroets at gmail.com
Tue Nov 20 21:13:11 GMT 2007

My 2c worth for faster routing :

* Rewrite in C and use hash tables.
* Change the A* heuristic from sqrt(sqr(dx)+sqr(dy)) to 1.1*sqrt(...)
or larger. This acknowledges that roads the shortest route between two
points is usually 10% longer than a straight route. And if you're
wrong the route may be slightly suboptimal, who cares.

(Why aren't we discussing the important issues, like adding a penalty
to right turns at intersections... ?)

More information about the Routing mailing list