I'm very impressed with navit's speed and function - it's very quick to find a pretty good route round parts of the UK using my Raspberry Pi
Which is great, because I aim to use it to build a SatNav for my old Jaguar XJS.
But... I read the discussion in
bug #456 about routing algorithms. That says it uses Dijkstra, but that's not 100% of the story; it looks at a
restricted part of the map - by default detailed (great depth) areas about the start, each waypoint, and end, and less detailed (low depth) in a larger area encompassing all those points. If that larger area isn't big enough, navit misses the best route.
Let's be specific. Use the UK map, find a route from
Land's End to Milford Haven. It gives an error message; it needs a waypoint at say Bristol to get a route. The cause is the Severn estuary bisecting the map area that navit looks at.
Increasing the size of that large-but-less-detailed area helps, but slows navit down.
As discussed in that bug, there's a
well-known enhancement to the routing algorithm, "A*", which may allow navit to search the whole map without loosing performance. route.c looks like it could be changed to use A* relatively easily. I've started trying to code this (following the instructions for building navit in Eclipse), and will submit
a patch if I can get it working.
Please can someone comment on the following approach to this:
IIUC, it now builds a graph for the areas (described above) by repeated calls to route_graph_update(), and then calls route_graph_flood() for the Dijsktra search. For A*, it would follow paths (still starting at the destination), and each time it hit a new point
(a) if necessary call route_graph_update() to ensure it had all the map data (at a great depth),
(b) calculate the straight-line distance for that point to the starting point, and
(c) do the A*/Dijsktra stuff.
The fiddly part is deciding step (a) if it needs to load more map data. It also needs route_graph_update() to leave existing path information untouched.
A simple approach is to load say
10km squares centred on the point, and record these squares in a table. Each time it hits a new point (where the distance in (c) is not yet calculated) look to see if it's in a square already loaded. This would be better if the squares it loaded had some relationship with the underlying map data, but that would tie the routing to a particular map implementation.
Passing through a waypoint might cause a problem, as the algorithm would meet points whose distances have been calculated for the preceding waypoint, but presumably that's already handled with the
existing Dijkstra implementation.
The above approach to A* might produce
a worse route than now, since it would try minor roads and cart tracks in the middle of a long journey. That's a question of the cost function that's being optimized (distance or time), and there are ways to attack that. I have an approach that I want to try (the original purpose that brought me to navit), but there's not a lot of point without removing the current algorithm's filtering out paths with great depth.
Is this totally mad
- we could combine A* with part of the current approach, to limit the search depth when far from the waypoints.