I have now implemented the A* algorithm. The overhead of computing
estimates is negligible - if I reset the estimate to 0 after computing it,
I get the normal dijkstra timing. (8s to compute a route from Denmark to
Trondheim with my scandinavia-map on my computer.)

There is still a bug though - if I use the computed heuristics, the search
is 3 times _slower_, not faster as expected. So either the computed
heuristic is wrong, or I use the data in a wrong way.  Still, the slowly
computed route is correct.

I'll debug this some more before making a patch.

One question:
The weights in the graph is the time needed to travel, computed as
(edge length) / (speed for that kind of road), right?

The heuristic I use is supposed to be travel time along an ideal path
(straight line or great circle) from a point directly to the target which
is the current position. This must be an underestimate, never an
overestimate of the time. So I divide by what I think is the fastest speed
available.

Is this correct:

heuristic=transform_distance(map_projection(projectionstuff->street->item.map),
pos_c, &p->c)*36/highest_speed;

I found this formula somewhere else. I don't know what the "36" is for.
But it is used for other roads, so I assume it should be used here too.
The formula should get the same result as for a best-class straight-line
road form the route_grap_point p to the current position whose coordinate
is in pos_c

I assume the search is always from dst to pos?  If not, this will surely
be wrong. . .

projection_stuff is struct route_info *dst from route_graph_flood, I
assume the correct map projection information is there?
highest_speed is speedlist[0]. This could be wrong if the speeds aren't in
sorted order. I haven't found out where the speeds are set yet.