route >80km is not calculated

[arne.anka]

navit is from debian/unstable (0.1.1.0+dfsg.1-1, no idea what svn version that correspondends to). using either an europe or sweden map from cloudmade or an europe map from osm (fetched via the osm bbox ulr listed in the wiki), calculating aroute bigger than approx 80km results in a completely wrong calculation: i started with a route from trelleborg to ulricehamn, that's about 400km. the route resulted in a blue dot inside central trelleborg. next attempt resulted in an l-shaped blue covering about 5km and ending about 1km in the sea. several attempst result in several different shapes (i expected it to be at least always the same shape), none longer that approx 5km.

trying a shorter route instead, trelleborg - malmö (40km) works. trying another with about 60km works too, and one with ca 80km. the next one with 97km (according to google) results in the above error again.

is there any parameter to make navit put out more instructive informations about what happens (and make it _not_ display those constant "vehicle_gpsd:vehicle_gpsd_try_open:gps_open failed for 'gpsd://localhost'. Retrying in 10 seconds. Have you started gpsd?" messages)?

[arne.anka]

true for svn2490, too.

[arne.anka]

some investigation later ... the newer navit.xml includes 4 predefined vehicles, all of them both enabled and active. setting all except Car to inactive allows to calculate longer routes. didn't test the other, but i guess, having more than one active vehicle confuses navit.

route trelleborg -- urlricehamn still doesn't work, but reverse -- ulricehamn -- trelleborg. i got the impression, that navit does not exactly cling to the highway, in particulay around malmö, but routes somewhere into the city and doesn't find a way out. if that's the case i think, the algorithm should try to stick to the highway in this case, resp to return to it, forgetting about the last part from the highway to the city.

anyway, it would probably be helpful, if the route's fragements are shown and maybe where no route is found a straight line is shown between the last known good point and the next one -- in extremis that would mean one straight line between trelleborg and ulricehamn, which imo is better than the current behaviour.

[arne.anka]

splitting the route t'borg -- u'hamn in parts (t'borg -- malmö, malmö -- göteborg, g'borg -- u'hamn) produces valid routes.

[flabrosse]

I may have the same problem, although the outcome is different. When calculating a route in the UK from 52.4141 -4.0859 to approx 51.8025 -3.0081 (on the A4042) I do get a route. If I go a bit further south (away from current position) along the same road, I don't get a road and navit outputs in the console: "navit:route_path_new:no route found, pos blocked".

This is using yesterday's svn and a recent openstreetmap map of Europe from cloudmade. I checked in OSM and the road is indeed a single item (not cut).

[drlizau]

I have a similar problem but have not checked the error messages which are generated. I did describe this on the navit-user list. I can make a route up to about 250km in length. If I set a destination more than that distance away navit can calculate a route when I get close to 250km from the destination. That route has "town-avoidance-behaviour" which tries to send me on a very long detour. I've tried this with a few versions and different maps, and triple checked that the route is joined on OSM. I also tried with setting maxspeed on roads involved which did not have maxspeed to test if that improved the routing, with no success.  https://sourceforge.net/mailarchive/forum.php?thread_name=200911210654.26359.edodd%40billiau.net&forum_name=navit-users

[kapiteined]

patch for route.c

[kapiteined]

I ran into the same problem, when routing along a large part "non highway"

i worked around this by applying the attached patch to route.c
I don't know what else this will break, so use at your own risk [[BR]]

[https://www.google.com/accounts/o8/id?id=aitoawmkw7qh8zqo5rtszg0qlehp5t_zvpfgz3m]

I am having the same issue as reported in #579 which looks like a duplicate of this bug. I've applied the patch, but the routing performance was poor.

The patch had changed the function route_calc_selection. route_calc_selection uses function route_rect to assemble a one way linked list which defines rectangle selections. These rectangles are used to reduce the size of the map data that are used for routing. The patch extends the areas for these rectangles and thus it gets more CPU/memory intensive.

On a PC the calculation delay cause by the patch becomes obvious, which means it is not satisfactory solution for the embedded platforms like nokia N810, or supported cell phones.

Can we get martin-s (the name associated with svn blame on these functions) to comment on this?

[https://www.google.com/accounts/o8/id?id=aitoawke3ydqlxkrjxetvkpfmrt3bhza4xqucwc]

This doesn't explain why I don't seem to have any problem in France but can't plan a long route in the UK.

I can't try the patch because I use Maemo packages on a N800.

[https://www.google.com/accounts/o8/id?id=aitoawmkw7qh8zqo5rtszg0qlehp5t_zvpfgz3m]

Replying to https://www.google.com/accounts/o8/id?id=aitoawke3ydqlxkrjxetvkpfmrt3bhza4xqucwc:

This doesn't explain why I don't seem to have any problem in France but can't plan a long route in the UK.

I can't try the patch because I use Maemo packages on a N800.

Please post the France coordinates you have used successfully. I would like to see the topology of the underlying map and which rectangles were selected. Yesterday I've inquired on the irc channel, and it seems nobody is working on this issue at the moment.

[https://www.google.com/accounts/o8/id?id=aitoawke3ydqlxkrjxetvkpfmrt3bhza4xqucwc]

Replying to https://www.google.com/accounts/o8/id?id=aitoawmkw7qh8zqo5rtszg0qlehp5t_zvpfgz3m:

Replying to https://www.google.com/accounts/o8/id?id=aitoawke3ydqlxkrjxetvkpfmrt3bhza4xqucwc:

This doesn't explain why I don't seem to have any problem in France but can't plan a long route in the UK.

I can't try the patch because I use Maemo packages on a N800.

Please post the France coordinates you have used successfully. I would like to see the topology of the underlying map and which rectangles were selected. Yesterday I've inquired on the irc channel, and it seems nobody is working on this issue at the moment.

Everything I've tried in the past has worked I think (although see below).

For example, from 4825.8453N 00157.7273E to Saumur works and is about 277.9km. From 5101.2593N 00211.8706E to again Saumur (624.2km) works fine and to Nantes, Avenue des Églantiers (684.4km) also works fine (however, to Nantes alone (no street) seems to fail).

In the UK, everything I have tried above roughly 100km has failed.

[http://wiki.navit-project.org/index.php/user:stabarinde]

So, let me get this straight;

• This issue has been known for 11 months.
• There is a kludgey fix, which has been around for 4 months.
• The scope of affected countries is either unknown or undeclared.
• The root cause is either unknown or undeclared.
• Any progress on root causing the issue or applying a fix is undeclared.
• Target date for the fix is undeclared.

So, what's going on? Basically, Navit works for a small selection of countries in the world. This means it *doesn't work*. The product cannot be a little bit broken. It's either broken or it isn't.

And yet, on the wiki page and the main page it says nothing about Navit not working in a number of countries.

I think the general populace can take a product that works but requires some in depth configuration, but a product that needs to be recompiled with a patch applied that they have to dig in a mailing list for is beyond most people.

I would imagine that this issue is getting all the priority the developers can muster. A glance at the current bug-list shows a lot of issues that effect unreleased builds or are minor UI quirks, but really route plotting is core functionality - without that you may as well be just looking at google maps offline. Objectively speaking, this is a stopper. It also effects a larger proportion of users, since it's in the wild (my version came down the pipe via the Ubuntu Lucid 10.04 LTS repos).

So, while you guys are working hard to fix the problem, here's what needs to happen;

• Update the front page, so that the issue is roundly addressed;
  • Explain the issue
  • List the countries affected
  • Offer a patched build to download for those affected.
  • Give step by step instructions on applying the patch for those who need to build it.
  • Give a target date for fixing the problem.
  • Use your news feed to give status updates.

This allows the average user to assess whether they want to spend the hours configuring a product that, at the end of the day, may not work for them. It tells them that if the answer to the previous question is no, then they can come back at a specific future date and get a better option. It also tells the more adventurous how to do something they might never have done before (i.e. compile software) - for example, even if you have route.c.diff, there are *two* route.c files in the SVN source. Most importantly, it tells them that the issue is being actively pursued, and that the developers are serious about this product.

For my part, I can confirm that the issue is present in Ireland as well. I used Cloudmade, the navit planet extractor and OSM maps converted using the maptool application (again from the Ubuntu Lucid repos), and in all cases no route was plotted, throwing the same error listed by the submitter.

[http://wiki.navit-project.org/index.php/user:nioui]

As far as I can tell there is no bug or unexpected behavior here as such, it's only due to the way Navit looks for a route.

Basically, computing a route in a graph with n point costs O(n×log n). So you don't want to route in a huge graph. Apparently, navit address this by restricting the map to a smaller area, and ignoring smaller road in the middle. More precisely, when routing from A to B, the following roads are considered:

• Major road in rectangle area around A and B.
• Intermediate roads in a square around A, and a square around B (40 km).
• Small roads in a small square around A, and a small square around B (10 km).

In most case, this should work correctly: you will use a major road between A and B, and small roads to go from A to the major road, and from the major road to B. It also works well for small distances, because everything fits in the small squares.

However, it fails if you travel long distance (more than 80km) and no major roads are available in the middle. A good example would be going from Santa Maria, CA to Bakersfield, CA (note that a major road is actually available, but it does not fit in the first rectangle containing A and B).

The patch proposed by kapiteined address this by expanding the areas around A and B where smaller road are considered (to respectively 100km and 400km). It should work correctly, but result in a much longer routing time, probably unacceptable for handheld devices.

I'm attaching a patch that tries to solve this issue in a slightly different way. Instead of changing the parameters for all the routings, I only try with enlarged parameters when the first routing fails with standard parameters. I decided to change the parameters by including intermediate roads in the rectangle containing A and B, because it seems to address the main cause of problem: if there is no major road between A and B, we allow smaller ones.

This patch seems to work well for me, but I'm not sure I'm doing everything correctly, and it is quite possible that some structures get corrupted in some cases. I'd be glad if someone could review it...

[http://wiki.navit-project.org/index.php/user:nioui]

If routing fails, try again with more roads included.

[http://wiki.navit-project.org/index.php/user:flabrosse]

I initially reported that I had no problem in France. This is wrong. I have used navit a lot up to Friday evening in France and the UK. I had similar problems in France too. However, that seemed to be over much longer distances.

I think the idea of the 3 stage route planning is broken. One can specify weights for the different types of roads one wants to take. Not wanting to take any motorways, I tried to disable them all together. That doesn't work. Also, if there is a motorway in the vicinity, then navit will want you to take it, even if that implies a large detour. That has occurred to me over and over again. As stabarinde was saying, this makes navit not really usable because you can't trust it to:

• find a route, or
• that the route indeed makes sense.

Not long ago, somebody suggested to use the A* search method. Maybe that would be much better.

[http://wiki.navit-project.org/index.php/user:number6]

I was probably that someone!

The current algorithm, Dijkstra, is inefficient. Well, that's a lie.

The current algorithm is actually very good at finding all possible routes, but it's slow and memory hungry - not something we want.

A* is far far faster, often an order of magnitude and would hopefully not be so CPU and memory hungry.

Sure, changing the "sel->next=route_rect" line in route.c to a higher number, or applying the Route Harder Patch fixes the problem, but the fact remains that Dijkstra is a slow algorithm.

[http://wiki.navit-project.org/index.php/user:tegzed]

I also suggested A* some 2 month ago in a forum topic:

 http://sourceforge.net/projects/navit/forums/forum/512959/topic/3746837 Perhaps I posted it to the wrong place.

Maybe one problem is to handle the case when the vehicle leaves area with roads that are flooded. In this case additional flooding should be done which can hurt performance during navigation. Current solution may have more control over the flooded area. In a previous irc discussion Cp15 told that performance of creating the graph is more problematic than flooding itself. Maybe some benchmarks would be useful and improve graph creation if its possible.

[http://wiki.navit-project.org/index.php/user:number6]

May I get your A* patch for testing purposes?

[http://wiki.navit-project.org/index.php/user:tegzed]

Hello Number6,

It's not a patch for navit, just a test program. Just parsed some OSM xml data with my simple separate commandline c++ program and run routing with dijkstra and A* on the data. If you are interested I can send you the program, however you may find better (and more readable) examples on these algorithms on the net.

[http://wiki.navit-project.org/index.php/user:flabrosse]

Replying to http://wiki.navit-project.org/index.php/user:number6:

The current algorithm is actually very good at finding all possible routes, but it's slow and memory hungry - not something we want.

A* is far far faster, often an order of magnitude and would hopefully not be so CPU and memory hungry.

Sure, changing the "sel->next=route_rect" line in route.c to a higher number, or applying the Route Harder Patch fixes the problem, but the fact remains that Dijkstra is a slow algorithm.

I would not say it's very good. If I understand it well, it relies on either having a motorway close enough to the current position and destination or on the the destination and current position to be close enough. The "close enough" is a threshold that is a compromise rather arbitrarily set (and I understand that recently a patch was introduced that changes it if no route was found).

However, there are places in the world where motorways are sparse and far away. Where I live (Wales) is one of them. So either the threshold is set to a long distance (and the routing is not that efficient) or I fail to have a route.

There is another failure of the approach: I cannot get a route that avoid motorways if there is one around. In fact, in some cases I've seen routes being planned that were just plain wrong, simply because there was a motorway close enough (that was with a weight for motorways as low as it could go to not fail (1)).

In fact, if you've ever played with a "proper" sat nav system, it can take these several minutes to plan a long route. I appreciate how fast navit is at planning the same route, but in many cases it fails, making it not so useful. Somehow I would prefer something that takes a long time but succeeds to something that simply fails.

Just my view ;-)

[http://wiki.navit-project.org/index.php/user:number6]

I should have clarified. From a mathematical standpoint, Dijkstra is a very good algorithm - albeit slow. Poor implementation, non-complete data and limited resources will easily affect the way it works.

I'm in the same situation as you, flabrosse. I am rather far from a motorway and "regional" roads in Ireland range from very very good (near "National" roads) to the down right impassible - that's a completely different matter though!

As an aside, I would happily wait 5 mintues for the "best" initial routing to my destination.

I am still of the belief that A* would be a better algorithm.

[http://wiki.navit-project.org/index.php/user:flabrosse]

On the other hand, A*, IIRC, will not give you the best route, only a good one (it is a greedy search, isn't it?). In practice, I don't think this is a big inconvenience.

I agree that the quality of the roads is another issue (and to some extent a problem with the data). However, the reliance on motorways in the 3 tier routing is the issue of the thread. And A* might solve that problem.

[http://wiki.navit-project.org/index.php/user:drlizau]

Replying to http://wiki.navit-project.org/index.php/user:flabrosse:

My problem may be the same or may be different, but it also relates to calculating the route. There is a current default in the route calculation which avoids towns. In Australia roads join towns rather than divert around them, so eventually a long route fails because there is not a logical solution without going through a town. Sometimes a route can be found to a point past the town, but the diversion may be of the order of hundreds of kilometers. Example: Find route between Wollongong (-34.425529 150.890967) and Griffith (-34.288559 146.047760). This fails on progressive extension of the route at Stockinbingal (-34.501841 147.889103). Routing through Stockinbingal is refused by the navigation engine, and no route around Stockinbingal can be found. navit:route_path_new:no route found, pos blocked.

A previous irc discussion mentioned that towns were avoided in the current code, but this was not always the case. I am thinking of restoring the old code as an option which can be set in navit.xml so that routing through towns can be available.

[http://wiki.navit-project.org/index.php/user:flabrosse]

While looking through a recent default config file, I discovered the option destination_distance. I tried to look for an explanation for it and couldn't. However, the name and the default value (50) made me think that this was the size of the area outside of which only major roads were used for the route planning. All excited by that, I tried a long route that normally fails, and it failed. I then changed the value from 50 to 500 which should have been plenty for the route I was looking for, and it still failed.

My questions are:

• what is this option and has it got anything to do with that?
• has anything been done on that problem?

Cheers

[https://wiki.navit-project.org/index.php/user:korrosa]

Replying to http://wiki.navit-project.org/index.php/user:flabrosse:

While looking through a recent default config file, I discovered the option destination_distance. <snip>

My questions are:

• what is this option and has it got anything to do with that?
• has anything been done on that problem?

From route.c:

int destination_distance;	/**< Distance to the destination at which the destination is considered "reached" */

So, unfortunately not a solution for this ticket!

[https://wiki.navit-project.org/index.php/user:ziaou]

The patch submitted by nioui seems to be the most easy solution to keep a fast route calculation, and to guarantee that a route will always be found to destination. In most cases, the calculation time will not be increased.

Without any modification of route calculation method, some towns like Brest (in France) are unreachable because too far from a motorway.

I have tested this modification on a eeepc 901 (800MHz) to go from Toulouse to Brest and I think that the calculation time could be acceptable.

The most important thing is to have a functional software first.

[https://wiki.navit-project.org/index.php/user:flabrosse]

Replying to https://wiki.navit-project.org/index.php/user:ziaou:

The most important thing is to have a functional software first.

I could not agree more with that.

However, this is not the solution because it still forces routes to use motorways for the middle section for trips that are longer than the 2 * 50km threshold. This is annoying because:

• you cannot not use motorways (something that all satnav systems offer)

• if your ideal route is just above the threshold and there is a motorway in sight, the selected route will use it even if that makes a huge detour (I came across an example like that last summer which I could try to find again if anyone can use the example to improve things).

[https://wiki.navit-project.org/index.php/user:ziaou]

Replying to https://wiki.navit-project.org/index.php/user:flabrosse:

However, this is not the solution because it still forces routes to use motorways for the middle section for trips that are longer than the 2 * 50km threshold

I agree with you.

Perhaps it's possible to enable major ways (motorway, trunk, primary) instead of only motorway for the middle section. As I understand, it is what is done in the patch when the route is not found at the first try. It will take more calculation time but the result could be best.

[https://wiki.navit-project.org/index.php/user:flabrosse]

Replying to https://wiki.navit-project.org/index.php/user:ziaou:

Perhaps it's possible to enable major ways (motorway, trunk, primary) instead of only motorway for the middle section. As I understand, it is what is done in the patch when the route is not found at the first try. It will take more calculation time but the result could be best.

If that is indeed what the patch does, why isn't it included? This seems like a sensible solution.

[https://wiki.navit-project.org/index.php/user:ziaou]

Replying to https://wiki.navit-project.org/index.php/user:flabrosse:

If that is indeed what the patch does, why isn't it included? This seems like a sensible solution.

What the patch does :

• first try : only motorway in the middle section
  • advantage : fast calculation
  • drawback : no route found if point is to far from motorway, always use motorways
• second try if first failed : enable other ways in the middle section
  • advantage : always find a route, could propose route without motorway in some cases
  • drawback : slow calculation, could be too heavy for handset

In my configuration, I have patched route.c to use only use the second try. It take more time to calculate route but the result is pretty good.

It could be interesting to test this configuration on a handset. Perhaps this patch is not applicable on it because of too many node to take in account for calculation.

[https://wiki.navit-project.org/index.php/user:tegzed]

Hello,

Woglinde (on #navit irc channel) has plans to pluginize the routing engine and fit it to the existing plugin infrastructure. I think this would be a good direction, in this way anybody could choose her/his best routing strategy and parameters of the routing engine (like routing numbers, the used road types etc.) in config time. Of course presets for typical scenarios can be offered to the user who then can choose from them.

[http://tryagain.myopenid.com/]

http://trac.navit-project.org/ticket/876 has a patch with different approach to the problem. It's scientifically based!

[http://wiki.navit-project.org/index.php/user:mvglasow]

I recently had the same problem when trying to route from Vienna to Vilnius: no route was found until I was about 200 km from my destination.

Reproducing the problem at home, showing the route graph, I found that the nodes assigned a weight were all within 200 km from Vilnius; all the others were empty.

Reasons: from Vilnius to the Polish border, the roads are partly motorways, the rest are trunk roads. The whole way through Poland (several hundred km) are almost completely primary roads, with only a few pieces of motorway or trunk roads. Nothing is found because apparently primary roads are not considered for long-distance navigation.

As far as I know, OSM uses highway=primary for roads of national importance which don't meet motorway or trunk criteria. Some countries do not have a dense network of the latter two roads and long-distance traffic needs to use primary roads.

For this reason, I believe these three categories of roads (motorway, trunk, primary) should always be considered for long-distance routing. It will increase the size of the route graph (more roads, hence more edges and vertices), but due to cost differences, highways will quickly "win" where they are available and a feasible alternative.

[http://wiki.navit-project.org/index.php/user:mvglasow]

As for Dijkstra versus A*: A* is basically a modified Dijkstra algorithm. It operates on the same graphs, and flooding a graph completely (examining every node) will give the exact same results with either algorithm.

This means nothing is saved in terms of memory requirements for the route graph.

The improvement of A* is that it selects the next node to examine by different criteria: Dijkstra chooses the node with the lowest cost. A* chooses the cost where the sum of its cost and a heuristic (lowest possible cost to destination) is lowest. Because of this, the destination node tends to get examined sooner than with Dijkstra.

As I understand it, Navit calculates the cost of a way segment as an estimate of the time needed to travel from one end to the other, based on its length, a speed estimate (configured in navit.xml) plus some penalties for traffic congestion etc.

A valid heuristic would thus be to take the distance between the node and the route destination, divided by the highest speed defined for any way type, and not taking into account any penalties.

It would require some code changes: we would still need to store the cost for each node, for nodes on the open list we would also need to store their cost+heuristic. This means nodes on the open list will take up some more memory. Also, we'd need to calculate the heuristic for each node we put on the open list. It would probably take some tests to find out how much of a difference that makes (the time gain most likely varies from route to route).

[https://wiki.navit-project.org/index.php/user:tryagain]

Replying to http://wiki.navit-project.org/index.php/user:mvglasow:

Reasons: from Vilnius to the Polish border, the roads are partly motorways, the rest are trunk roads. The whole way through Poland (several hundred km) are almost completely primary roads, with only a few pieces of motorway or trunk roads. Nothing is found because apparently primary roads are not considered for long-distance navigation.

As far as I know, OSM uses highway=primary for roads of national importance which don't meet motorway or trunk criteria. Some countries do not have a dense network of the latter two roads and long-distance traffic needs to use primary roads.

At #876 there was described a similar problem, and my first patch made highway=primary roads eligible for distant routing. But that patch was partially reverted back because of performance problems found by cp15. So now we have least significant roads for distant routing being highway=trunk.

BTW, highway=trunk definition at  http://wiki.openstreetmap.org/wiki/Tag:highway%3Dtrunk seems to allow to tag it on any important road. But country-wide [bad] practices sometimes add more requirements to roads it is placed on. For example, I don't know why in Czech Republic and Denmark one should use this tag only for roads that in other countries are tagged as higway=<anything> and motorroad=yes ( http://wiki.openstreetmap.org/wiki/Tag:motorroad%3Dyes). There's no highway=trunk specifics described for Poland.

The definition of highway=primary at  http://wiki.openstreetmap.org/wiki/Tag:highway%3Dprimary doesn't give any clue if that road should or can be used for distant routing. It's just "a major highway linking large towns".

Comparing two above definitions I'd say it's better to place higway=trunk tags on all roads you name and don't touch the navit code.

But having that country-dependent tag usage practices we probably have to use some sophisticated logic to decide if given highway=primary is eligible for distant routing or not. That decision can be done on country-by-country basis, or adaptive, by checking if highway=primary density (number of such roads per square km) is less than some value.

[http://wiki.navit-project.org/index.php/user:mvglasow]

Well, changing common tagging practice is not an easy task either, nor do I want to start edit wars on OSM. Also, I'm wondering if that's maybe even a borderline case of tagging for the renderer.

In some countries (Italy I know for sure) there is a clear-cut difference between primary and trunk, which has to do with traffic regulations, including speed limits, and thus also has an impact on routing. So having this distinction is even beneficial for routing. Btw, this exists also for Poland, look here:  http://wiki.openstreetmap.org/wiki/Key:highway#International_equivalence

Also, the definition of primary may not specify it as being of national importance, but many national tagging schemes (e.g. Austria, France, Germany, Italy, Poland, Sweden; see above link) map "primary" to road categories which do effectively fall into this category.

If making primary roads eligible for long-distance routing induces performance problems, then I would suggest looking at two things:

• In the route graph I sometimes see a couple of nodes in the middle of a road. The correspond to OSM nodes (because the road is curved) but they are not junctions, hence they are not needed for the graph (the graph needs nodes only where two paths split or join). It seems the graph is not optimized in that respect, which would lead to generic performance issues. With this optimization, we might get enough "elbow room" for primaries. It would require pre-processing at some point but would decrease the number of nodes in the graph, reducing both memory consumption and execution time.

• Adaptive inclusion/exclusion of primaries, as you suggested. We can either include primaries by default and drop them if the graph gets too large, or exclude them by default and include them only if the network of higher-rated roads is not dense enough.

[http://linesoff.myopenid.com/]

Before I knew about this ticket, I spend a lot of time wondering, why navit delivered routes, which make great detours (or delivered no route). Now this is clear.

But I'd like to emphasize, that the two step approach mentioned above will not be a solution for those cases, when Navit makes a great detour using a motormay, because the second step is not performed. I found several starts+destinations (in the area of D-A-CH), where the Navit-route starts in the opposite direction of a realistic route. At the moment the routing for long trips is not for practical use.

But I hope, a suitable solution for long trips will be found. ( Soon ? )

[http://wiki.navit-project.org/index.php/user:tegzed]

use more detailed map for routing

[http://wiki.navit-project.org/index.php/user:tegzed]

Hello, I attached a one-liner patch that I use for routing (detailed_route_map.diff). Routing uses map extracts as described here:  http://wiki.navit-project.org/index.php/Routing. This patch increases the detail level(from 4 to 6) of the outer most rectangle.(the one that does include the position and destination point with an additional 25% at the ends). (The route_harder patch increases the detail to 8 for this rectangle in the second step) This one-liner is a version of the two-step patch that starts with the detailed version(avoiding the above problems). This works quickly and correctly on my android device (motorola defy). I could do routing from Hungary to Stuttgart without problems. I think the best solution would be to let the user select presets about the detail and range of he route map rectangles from navit.xml, so navit can be configured for low memory devices and more advanced hardwares too without recompilation. The constants (or some similar quantities derived from the constants) used in route.c between lines 958 and 965 should be made configurable from xml.

[http://wiki.navit-project.org/index.php/user:mvglasow]

would that include primary roads in routing, then? (What order/detail level would a highway=primary have? where is the mapping between these two done?)

[http://wiki.navit-project.org/index.php/user:tegzed]

If I'm understanding the code well, the order depends on the "length" (or more precisely the quadtree level) of the way not the osm tags(which is mapped to navit item type). The longer the way the lower the quadtree level (it can only fit in a bigger quadtree tile). So the patch allows shorter ways (that have higher order value) to be used.

[http://wiki.navit-project.org/index.php/user:tryagain]

phase34_process_file() of navit/maptool/misc.c assigns maximum item order (tile depth) based on its navit type. So, for example, shortest items of type ramp will have order=8. Order may become lower for lengthy items.

OSM attribute to item type correspondence is given by attrmap array of navit/maptool/osm.c.

So there's no central place where mapping between order and OSM type is done, but it's quite simple to deduct that correspondence.