Re: [Navit-users] [PATCH] A* search for navit, nice speedup in many cases

[<hel...@ai...>]

> Hello again.
>
> I've discussed your patch with cp15, and here are his thoughts :
>
> It currently doesn't bring any improvement (even more, it might get
> worse), since we currently don't have an "abort" condition while
> flooding the graph.

Ah, so that is why it was so hard to get a difference. (My 4x speedup
probably was some glitch fixed by map changes then.)

I wondered about the stop condition, I just thought I didn't understand
all yet. But surely there is some stop condition? Calculating a short
route (50km) is much much faster than routing across all of Europe. You
can't possibly search the entire graph in all cases - then all routess
would be equally slow to compute?

> So A* is even a bit slower (since it requires additional computing)
Yes, but marginally. I tested this by adding the A* calculation but not
actually using it. There was no noticeable difference - 4s for a test
route either way.

than
> Dijkstra. I think I will add a flag to the routing code to tell it that
> it doesn't need to work further once the destination (actually the
> position) is reached, then we might get an improvement by using A*. But
> on the other hand, it will slow down re-routing considerably. Since we
> are flooding the graph completely right now, chances are high that the
> right path already exists in the graph when you leave your route. When
> we use an abort condition, this gets more unlikely.

A* does a directed search, but not that much directed. It will visit some
surroundings, so no problem unless you go so much off course that the
error is a significant fraction of the total distance. A* will do some
searching in the "wrong" direction, in case you need to go back a little
to get on a nice fast motorway. A* will avoid going 80% of the distance in
the wrong direction though.

I think it is ok to spread out the recomputations, instead of doing it all
at once. Unless testing shows a real problem on the road, that is. Getting
a fast search on a slow device might be nice, and A* with abort should do
that.

If you really want to pre-compute everything:
1. Start the search (A*) in a thread of its own. As soon as A* finds the
best way, notify the main thread which starts routing. Then keep searching
in the background, until the entire graph is flooded. (May take 30s on the
current world map - with a decent PC. Much more on a phone device. But no
problem (other than battery usage) if it goes on in the background.)

Further speedup idea:
It is possible to tag dead-end roads (and whole subgraphs of dead-ends
where a whole network of roads only has one connection to the "rest" of
the world.) A whole city on the end of a motorway might get tagged if
there is no other way out.

During the search - never move into any dead-end structure unless we know
that the goal is somewhere inside it, which is easily checked by checking
the tag on the goal road. This can save lots of time, especially on those
cross-continent routes.

Finding all dead-ends should be done during map conversion, not while
driving. It could be very time-consuming.

Helge Hafting