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

Nic Roets nroets at gmail.com
Wed Nov 21 00:59:06 GMT 2007


> 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).




More information about the Routing mailing list