Hi Nic, Nic Roets wrote: > > * Rewrite in C and use hash tables.
While we're still at the stage of working out which algorithms to use how, I much prefer using ruby/similar. Prototyping is far easier. When it's clear what's best, a C implementation may be worthwhile. > * 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. Tried it. 1.1 is too high, you easily get suboptimal routes. I then tried a similar approach: distance > 100km -> distance*1.2 distance > 50km -> distance*1.1 distance > 10km -> distance*1.05 distance <= 10km -> distance I tried this with varying factors/limits. Depending on the parameters, the result was (in general terms) that it produced suboptimal routes or that it didn't help too much with speed. I didn't find a happy medium for my test routes. > (Why aren't we discussing the important issues, like adding a penalty > to right turns at intersections... ?) Because we didn't yet work out which algorithm to use to get acceptable speed on long routes. Once you've got this and solved the less-knotty-but-still-not-trivial problem of whether you want to penalise right (UK) or left (Europe, US) turns, actual implementation should be simple. -- Jon _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
