[Routing] speed of A* on mobile devices

[Dennis Luxen]

> I'm just not getting these problems with A* on mobile devices.

Tiny data set?

> My A*-based system (used in CartoType) will give a correct route in
> a second or two for a large city on an Android Galaxy Nexus.

Define large.

> It takes account of routing restrictions and uses customisable
> profiles so that you can favour or disfavour different road types and
> set estimated speeds. I believe the key to the problem is to load the
> entire route network into memory, using a suitably parsimonious
> representation (and of course re-use it; it is loaded only once);
> and

Yes, that's the problem. You just can't load everything into RAM on a
handheld-device beyond small'ish road networks of a couple thousand edge
segments.

> not to do any heap memory allocation during the routing process; all
> data manipulations are done in place.

This implies that during routing you will always use linear memory, i.e.
the size of your priority queue depends on the number of nodes.

> Another thing I found that gave a worthwhile speed-up was to use a
> carefully optimised priority queue for the list of open nodes.
>
> I'll be releasing a demo of this system as a free Android app very
> soon so that people can see for themselves. Anyone who wants to try
> it right now on Windows can download the CartoType .NET SDK, which
> is free for non-commercial use.
>
> Graham Asher
>
>
>
> _______________________________________________ Routing mailing list
>  Routing at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/routing
>