Routing algorithm differences between the Java code (legacy) and the C++ code (native)

[Fabien Nicollet]

Hello,

I am digging in the code and I would like to understand the differences between the Java algorithm for routing and the native one in C++.

From what I undestand, the Java code wasn't good enough, it had trouble with calculating routes more than 200km and would sometimes never finish.

On the other hand, what's referred to "native" routing in 1.9 is much better and can calculate routes up to 600km, faster than the old Java code.

I believe I have found the Java code on the Github repositories that is responsible for the routing:

https://github.com/osmandapp/Osmand/tree/master/OsmAnd-java/src/net/osmand/router

The logic seems to be mainly in 2 classes "BinaryRoutePlanner.java" and "RoutePlannerFrontEnd.java"

As for the C++ code, I am not sure I am looking at the right branch. Is the code from legacy_core?:

https://github.com/osmandapp/OsmAnd-core/tree/legacy_core

I can find the same classes, such as :

https://github.com/osmandapp/OsmAnd-core/blob/legacy_core/native/src/binaryRoutePlanner.cpp

There seem to be no algorithm differences between the two, it looks like the C++ code is a port of the Java code but then, I can't explain why it is so much faster and why it would work when the Java code doesn't.

Can something help me understand what's happening here ? Am I looking at the wrong code / implementation or is there some big difference that I missed?

Thanks a lot!

Fabien

[Osmandtrier]

I do not have your skills. I am trying to personalize my bicycle routing. But I can not read java and c++ code

I would say, I understand how a A*-algorithm is working. After my expirience with osmand, I think, it could be,because of a different change, the dev where thinking, C++ is better than java. But the change was only in C++.

After doing some tests with my personal routing, I would guess the change to transition_penality or/and the possibility to do a bidirectional calculation can cause the idea to change to c++. Look in the historics of routing.xml at the time, where the change was, and I am would be not amazed that you will find there a reason.

[Fabien Nicollet]

Thanks for your answer.

The Java code does a bidirectional calculation as well and uses the same routing.xml file so I am still unsure as to what the difference is between the two.

[Harry van der Wolf]

C++ is faster then java (be it sometimes only a little).

However, if you want to port OsmAnd also to IOS (and there are now beta builds) and Windows phone 8.1 (some early builds), you need to get rid of java.

I assume that's the main reason.

Harry

--
You received this message because you are subscribed to the Google Groups "Osmand" group.
To unsubscribe from this group and stop receiving emails from it, send an email to osmand+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Fabien Nicollet]

Thanks, 

i understand that it helps to have a C++ core for portability on other OS but I can't figure out why the C++ algorithm succeeds while the Java one can't finish the calculation. The algorithm looks identical and even if you let the Java one for minutes, it never actually finishes and there is not such a speed difference between C++ and Java. 

It just seems that the Java code get "stuck" but I can't understand why when a similar algorithm in a different language succeeds ...

Fabien

[Sabra Sharaya]

Maybe the system runs out of memory with no error message.

[Aceman444]

Yes, or there is some limit in OsmAnd that it kill the calculation when hitting a specified number of minutes.

Dňa sobota, 28. februára 2015 18:45:56 UTC+1 Sabra Sharaya napísal(-a):

[Harry van der Wolf]

I think Sabra is right. The java implementation is probably limited due to heap space limitations. That has always been an issue in the older versions.

--

[Fabien Nicollet]

That could be it, but when in Eclipse, I don't receive any OutOfMemory or HeapSpace errors from the program it just seems to try to load roads forever (from what I can see in log files). The distanceFrom and distanceTo are like stuck to about 3 kilometers, as if the routing algorithm couldn't get any further and kept trying and trying ...

I am having a hard time trying to debug the C++ code with like breakpoints and step-by-step. Even after following the instructions, the Windows NDK won't work correctly and doesn't allow me to debug properly, so I can't see differences doing step by step on both code like I originally wanted.

[Fabien Nicollet]

Turns out if you let the calculation run for ages (like half an hour or so), it succeeds. Your hint was actually the right one, if you drop the "memoryLimit" specific code, the calculation runs in about 30 seconds. It seems that the Java code is so tight on memory that it almost all the time clear his tileRoute cache to save memory, which means that the tileRoutes have to be fetched and parsed again even when searching again in the same area which is very costly.

There are some more differences between Java and native in the code, seems like the cache is saved on a different level (no "tileRoutes" in native), which could impact on performances. Performances are ok when a motorway can be found but pretty bad in rural zones.

[Osmandtrier]

Is somebody knowing whether they are using a closed list or a open list.

[Harry van der Wolf]

2015-03-13 13:37 GMT+01:00 Osmandtrier <stephan....@googlemail.com>:

Is somebody knowing whether they are using a closed list or a open list.

I'm not an expert at all but in time I did gain some knowledge.

As far as I know, the heuristic coefficient determines whether the set is closed or not. That is the difference between A* and Dijkstra.

That also the exact reason why the calculation is so slow with the default 1.0 (for car) and uses this enormous amount of memory. All possible routes are calculated.

If you use a heuristic coefficient >1 the calculations that meet the heuristic h "are closed" and not calculated anymore/again.

Again: that is exactly why you can only calculate up to approx. 400 km with the default h=1.0 on a 512MB phone, and up to approx. 800 km on a 512MB phone in 20-35% of the time.

So: the car navigation using h=1.0 is not using closed sets. The (current) cycling navigation using h=1.3 or h=1.4 is using closed sets.

Harry 

[Harry van der Wolf]

Sigh: typed too fast. :(

2015-03-13 14:14 GMT+01:00 Harry van der Wolf <hvd...@gmail.com>:

2015-03-13 13:37 GMT+01:00 Osmandtrier <stephan....@googlemail.com>:

Is somebody knowing whether they are using a closed list or a open list.

I'm not an expert at all but in time I did gain some knowledge.

As far as I know, the heuristic coefficient determines whether the set is closed or not. That is the difference between A* and Dijkstra.

That also the exact reason why the calculation is so slow with the default 1.0 (for car) and uses this enormous amount of memory. All possible routes are calculated.

If you use a heuristic coefficient >1 the calculations that meet the heuristic h "are closed" and not calculated anymore/again.

Again: that is exactly why you can only calculate up to approx. 400 km with the default h=1.0 on a 512MB phone, and up to approx. 800 km on a 512MB phone in 20-35% of the time.

Should have been: ..... and up to approx. 800 km on a 512MB phone in 20-35% of the time with h=1.3.

[Osmandtrier]

Am Freitag, 13. März 2015 14:14:33 UTC+1 schrieb Harry van der Wolf:

2015-03-13 13:37 GMT+01:00 Osmandtrier <stephan....@googlemail.com>:

Is somebody knowing whether they are using a closed list or a open list.

I'm not an expert at all but in time I did gain some knowledge.

As far as I know, the heuristic coefficient determines whether the set is closed or not. That is the difference between A* and Dijkstra.

That also the exact reason why the calculation is so slow with the default 1.0 (for car) and uses this enormous amount of memory. All possible routes are calculated.

If you use a heuristic coefficient >1 the calculations that meet the heuristic h "are closed" and not calculated anymore/again.

I am very sure that this is not correct. Because you can set hc up to ten and it  calculates so long as hc=1 set maxdefaultspeed in the profile very high ( for example 10000).

The hc cut of the priorisation of the prefered street, because the spread of the values getting smaller and so you need less calculation. For cyclist does using of hc mean, you are pushed on mainstreet instead you choosed in your routing.xml minor roads. (In other sligh polemic words, if you love life, do not use hc.)
 

[Harry van der Wolf]

Hi,

I'm not sure if I understand you correctly.

After my explanation you say

2015-03-13 20:36 GMT+01:00 Osmandtrier <stephan....@googlemail.com>:

That also the exact reason why the calculation is so slow with the default 1.0 (for car) and uses this enormous amount of memory. All possible routes are calculated.

If you use a heuristic coefficient >1 the calculations that meet the heuristic h "are closed" and not calculated anymore/again.

I am very sure that this is not correct. Because you can set hc up to ten and it  calculates so long as hc=1 set maxdefaultspeed in the profile very high ( for example 10000).

If you look at the articles written about A* (and its developments upon that) and Dijkstra, my explanation is exactly what happens. Also: If you set max default speed to 10000 and you leave the other speeds as is derived from the road tags in OSM, you will bias you model in such a way that it can't function correctly.

 

The hc cut of the priorisation of the prefered street, because the spread of the values getting smaller and so you need less calculation. For cyclist does using of hc mean, you are pushed on mainstreet instead you choosed in your routing.xml minor roads. (In other sligh polemic words, if you love life, do not use hc.)

This is not true. If you calculated with an h>1, it will use branches to calculate your route but if the branch is getting less optimal then another branch it will stop that branch and close it. With an hcof 1.0 it will continue calculating that branch (and sub branches) until it reaches its destination.

It could mean that it will take a main road, but not neccessarily. For cycling you might be right, but I think the road profile for cycling, which road to use, is not correct and that the hc is of less influence on the correct routing.

Some time ago some remarks were made also about the hc and you started experiementing with the hc for cycling. at the same time I did that for car routing (https://groups.google.com/forum/#!topic/osmand/nypUdYCW3BI)

Based on your own experiments and based on my experiments, I definitely believe that OsmAnd is using closed sets using an hc>1.

I also definitely think that OsmAnd's implementation is less optimal then the implementation in other routing engines.

In august 2014 I also did tests (https://groups.google.com/forum/#!topic/osmand/faBpDWxWSVk). At that time I mentioned that MapFactor Navigator Free did it much, much better (6th post in that thread): "Mapfactor Free: Skagen, Denmark - Malaga, Spain 3216 km, 74MB, 22 sec".

I have been using MNF for quite some time already as it calculates excellent routes and does it extremely fast. I only use OsmAnd for its excellent, most detailed maps for cycling and walking and only with external routing engines. 

I think the algorithm implementation is not optimal, but working fine for cars. The profiles for cycling are not optimal combined with a raised hc.

Harry

[Osmandtrier]

If you look at the articles written about A* (and its developments upon that) and Dijkstra, my explanation is exactly what happens. Also: If you set max default speed to 10000 and you leave the other speeds as is derived from the road tags in OSM, you will bias you model in such a way that it can't function correctly.

 

The hc cut of the priorisation of the prefered street, because the spread of the values getting smaller and so you need less calculation. For cyclist does using of hc mean, you are pushed on mainstreet instead you choosed in your routing.xml minor roads. (In other sligh polemic words, if you love life, do not use hc.)

This is not true. If you calculated with an h>1, it will use branches to calculate your route but if the branch is getting less optimal then another branch it will stop that branch and close it. With an hcof 1.0 it will continue calculating that branch (and sub branches) until it reaches its destination.

It could mean that it will take a main road, but not neccessarily. For cycling you might be right, but I think the road profile for cycling, which road to use, is not correct and that the hc is of less influence on the correct routing.

The value of a branch is calculated in this way

value=lenght/resulting-speed

 
Resulting speed = priority*speed*hc
If resulting speed> maxdefaultspeed than resulting speed = maxdefaultspeed

If maxdefaultspeed=speed of your most prefered way and priority=1
Choosing hc=1,5 means the real priority 0,66.

If the priority of the most disloved way (major road) is 0,5 and you have the nearly the same speed, like cyclist do, you are pushed tp the bad road.

So your prefered route is cut off, for cyclist it means the safe road.

[Max]

That also the exact reason why the calculation is so slow with the default 1.0 (for car) and uses this enormous amount of memory. All possible routes are calculated.

No, if the heuristic coefficient is 1, it is A*, if heuristic coefficient is bigger than 1 it is a "broken" A*, which does not find the optimal solution.
If the heuristic coefficient is 1, not all possible routes are calculated, actually the heuristic exists to limit the search space.
If the heuristic coefficient is 0, it is approximately Dijkstra, because there is no heuristic anymore in this case, which reduces the search space.
 

So: the car navigation using h=1.0 is not using closed sets. The (current) cycling navigation using h=1.3 or h=1.4 is using closed sets.

A* always uses closed sets (also if heuristic coefficient is 1).
If the heuristic coefficient is 1, the heuristic is admissible, if it is bigger than 1, the heuristic is not admissible anymore.
By definition A* finds the optimal solution, if the heuristic coefficient is bigger than 1, in most cases it will not find the optimal solution anymore, thus it is not A* anymore (it is a "broken" A*).

The routing engine uses the following heuristic (I don't consider precalculations which are only available for car routing), which estimates the minimal cost to the goal:
"heuristic coefficient" * "air distance to the goal" / "max. possible prioritized speed"
This heuristic never overestimates costs (admissible heuristic), if the heuristic coefficient is not bigger than 1.
If the heuristic overestimates costs A* is "broken" (not admissible heuristic), because it does not find the optimal solution anymore.

Regards,
Max

[Max]

I am very sure that this is not correct. Because you can set hc up to ten and it  calculates so long as hc=1 set maxdefaultspeed in the profile very high ( for example 10000).

If maxDefaultDpeed goes to infinity, the estimated costs (distance/infinity) go to zero, thus you don't have a heuristic anymore which reduces the search space.
A good heuristic never overestimated costs, but should also be as close as possible to the costs of the optimal route.
It should not underestimate the costs too much, because the more it underestimates the costs the bigger the search space will be (bigger search space means slower search).
 

The hc cut of the priorisation of the prefered street, because the spread of the values getting smaller and so you need less calculation.

If the spread of the prioritized speed value is smaller, it is possible to do a better estimation.
If you only have one speed value you get the closest estimation which does not overestimate the costs.
 

For cyclist does using of hc mean, you are pushed on mainstreet instead you choosed in your routing.xml minor roads.

The influence of the speed values and the priorities gets lower the higher the hc is, thus you will more and more get the straight way to the goal (shortest way), in many cases this will be bigger streets, because they are more likely the direct way to the goal (the don't have so much curves and corners).

Regards,
Max

[Max]

If you set max default speed to 10000 and you leave the other speeds as is derived from the road tags in OSM, you will bias you model in such a way that it can't function correctly.

The search space will be huge, but the model will not have an bias.
 

If you calculated with an h>1, it will use branches to calculate your route but if the branch is getting less optimal then another branch it will stop that branch and close it.

If hc > 1 the search will stop too early so that the optimal route (usually) will not be found.

With an hcof 1.0 it will continue calculating that branch (and sub branches) until it reaches its destination.

No, there will also be a limitation of the search space by the heuristic.
 

It could mean that it will take a main road, but not neccessarily.

True.
 

For cycling you might be right, but I think the road profile for cycling, which road to use, is not correct and that the hc is of less influence on the correct routing.

hc and maxDefaulSpeed are the two values which determine if you get an optimal route (according to the chosen speeds and priorities) or not.
They determine if the heuristic is admissible or not.

I also definitely think that OsmAnd's implementation is less optimal then the implementation in other routing engines.

I agree.

At that time I mentioned that MapFactor Navigator Free did it much, much better (6th post in that thread): "Mapfactor Free: Skagen, Denmark - Malaga, Spain 3216 km, 74MB, 22 sec".

I don't know Mapfactor free, but according to the mentioned time, I'm pretty sure they don't use contraction hierarchies (it would be much faster), but they definitely use heavy precalculations.
I guess they use entry and exit points and only calculate the route to and from these points.
To look up the route between an entry (near Skagen) and exit point (near Malaga) takes nearly zero time.
But this will limit the flexibility of the routing, but I think this is acceptable for car routing.
The advantage of a car road network is, that it has a good road topology.
Usually pedestrian and bicycle networks don't have such a good topology, but the calculated routes are much shorter, so this doesn't matter much.

Regards,
Max

[Max]

Resulting speed = priority*speed*hc

hc is not a speed multiplier, it defines how fast the algorithm thinks that a route is "optimal", even if it is not.
But at the end it has a similar effect, because the higher the hc the lower the effect of the speed and priority values.

[Harry van der Wolf]

Hi Max,

Thanks for explaining. I was under the impression that 1.0 was working like the hc=0 you explained and anything above 1.0 was limiting searches.

The routing in Osmand for cycling is pretty bad. Looking at the routing.xml in the resources repo (https://github.com/osmandapp/OsmAnd-resources/blob/master/routing/routing.xml#L336) this is also obvious as the heuristic coefficient is set to 1.5 (which makes it therefore fast but hardly optimal and as a result taking main roads). This was changed about 3 months ago or so.

I set it back to 1.0 in my routing.xml and did a few calculations for cycling. It is still not optimal, but much better than with 1.5 which made the routing simply unusable for "touristic" cycling, which is my preferred usage (and it is again much slower). 

If you want to use the shortest route the 1.5  is better I assume.

Harry

[Osmandtrier]

Okay but the claimed effect, you are pushed on unwished street still exist. If i do not want this cut off, I have to increase maxspeeddefault. But then increasing hc show very less effect saving calculationtime.

So the question is, why brouter needs lees time then Osmand using hc=1.8 with the same priority. Why can calculate brouter in a area with one of the highest Data density of osm a route over 60 km airdistance on a four year old defy, and Osmand collaps with hc=1.

Brouter uses Java. Osmand Java or C++(because C++ is quicker)

Conclusion, the implementaion of a*-algorithmen could be better.

[Max]

Okay but the claimed effect, you are pushed on unwished street still exist. If i do not want this cut off, I have to increase maxspeeddefault. But then increasing hc show very less effect saving calculationtime.

If you increase hc and maxSpeedDefault at once, they will nullify each other.
You can't combine both effects (fast calculation and optimal route).

So the question is, why brouter needs lees time then Osmand using hc=1.8 with the same priority. Why can calculate brouter in a area with one of the highest Data density of osm a route over 60 km airdistance on a four year old defy, and Osmand collaps with hc=1.

Brouter uses Java. Osmand Java or C++(because C++ is quicker)

Conclusion, the implementaion of a*-algorithmen could be better.

Brouter uses some nice tricks (algorithm and code).

[Osmandtrier]

Am Samstag, 14. März 2015 23:46:21 UTC+1 schrieb Max:

Okay but the claimed effect, you are pushed on unwished street still exist. If i do not want this cut off, I have to increase maxspeeddefault. But then increasing hc show very less effect saving calculationtime.

If you increase hc and maxSpeedDefault at once, they will nullify each other.
You can't combine both effects (fast calculation and optimal route).

The problem is not "Not optimal route" The problem is the resulting charakter of "not optimal". It is not random, it have a strong charakter. For cyclist and walkers this means to be pushed on the main streets. Some people would call it unsave routes.
 
Die Veränderungen sind nicht zufällig, sondern haben eine starke Tendenz, und das ist im Ergebnis für bestimmte Nutzer, dass man sie in mehr gefährliche Situationen bringt als gewünscht.

Ich habe den EIndruck, dass Du diese Aussage einfach nicht zur Kenntnis nimmst.

Nicht optimal kann mehr oder weniger blöd optimal sein. Und bei Osmand ist eher weniger optimal mehr blöd.

So the question is, why brouter needs lees time then Osmand using hc=1.8 with the same priority. Why can calculate brouter in a area with one of the highest Data density of osm a route over 60 km airdistance on a four year old defy, and Osmand collaps with hc=1.

Brouter uses Java. Osmand Java or C++(because C++ is quicker)

Conclusion, the implementaion of a*-algorithmen could be better.

Brouter uses some nice tricks (algorithm and code).

One person seems to be more clever than a whole bunch of dev.

 The most clever thing of the dev of brouter is, he knows the limits of his skills.

[Max]

Die Veränderungen sind nicht zufällig, sondern haben eine starke Tendenz, und das ist im Ergebnis für bestimmte Nutzer, dass man sie in mehr gefährliche Situationen bringt als gewünscht.

Natürlich entscheidet der Algorithmus nicht zufällig.

Ich habe den EIndruck, dass Du diese Aussage einfach nicht zur Kenntnis nimmst.

Ich habe diese nicht nur zur Kenntnis genommen, sondern sogar versucht das zu erklären.

Nicht optimal kann mehr oder weniger blöd optimal sein. Und bei Osmand ist eher weniger optimal mehr blöd.

Ich versuche es nochmal:

Es ist logisch nicht möglich mit dem hc oder maxDefaultSpeed zu bestimmen, welche nicht optimale Route der Router berechnet.

Das der Router dich oft auf gefährliche Straßen navigiert, wenn du ihm sagst er soll eine nicht optimale Route berechnen (hc > 1), liegt einfach daran, wie das Straßennetz aufgebaut ist.
Wenn du in den Daten alle gefährlichen Straßen in Radwege und alle Radwege in gefährliche Straßen umwandelst, so würde er dich wahrscheinlich auf die Radwege "zwingen", selbst wenn du jetzt auf die Idee kommen würdest, die gefährlichen Straßen (zuvor Radwege) zu bevorzugen.

Du verbietest dem Router mit einem hc > 1 alle für das Finden einer optimalen Lösung notwendigen Wegsegmente anzusehen (das macht dann die Berechnung schneller).
Auf Grund des Aufbaus des Straßennetzes findet der Router eben zuerst eher die gefährlichen Hauptstraßen (eher direkte Wege, weniger Wegsegmente, ...).
Der Router sieht dann nach, ob diese Wege schon den (durch den hc) herunter gesetzten Anforderungen genügen und stellt in vielen Fällen fest, dass dem so ist, er bricht also seine Suche ab und besucht somit die Radwege nicht mehr.
Du kannst dem Router jetzt nicht vorwerfen, dass er die Wegsegmente welche er (wegen des hc) nicht besucht hat, logischerweise gar nicht berücksichtigen kann.
Nun könntest du einwenden, der Router solle doch bitte erst die sicheren Wege ansehen, bevor er die gefährlichen Straßen berücksichtigt.
Genau das ist aber nicht möglich, denn wenn der Router nicht alle nötigen Wegsegmente (wegen des hc) besuchen darf, kann er auch nicht wissen, welches die sicheren Straßen sind, also ob es an dem jeweils untersuchtem Ort Radwege gibt oder nicht.
Also um zu wissen, dass es bessere Wege gibt, müsste er sich diese ansehen!
Möchtest du eine bessere Lösung, so musst du dem Router erlauben, mehr Wegsegmente zu besuchen (niedrigerer hc).

Wenn du willst, dass der Router dir eine optimale Route berechnet, dann setzte den hc auf 1.
Je größer der hc ist, umso weniger macht er was du willst, dafür ist er dann umso schneller.

[Harry van der Wolf]

My German is perfectly OK to read your mails and to speak German, but not to answer it in grammatically correct German so I switch back to English.

The bicycle speeds vary way less compared to car speeds: 11 to 18 apart from steps and ferry (and why does motorway have a higher speed compared to primary? That is ridiculous), compared to 25 to 130 for car speeds (apart from obstacles and ferries and the like).

These small differences in speed make it more tricky to create a good bicycle route. To overcome this I think the priorities of the roads for the cycling profile should vary way more (now from 0.5 to 1.6 in lines 431 to 477 in this version, apart from seps/stairs and likewise obstacles).

I think that when these road priorities in the cycling profile get a wider spread, say from 0.5 to 3.2 (or even more), instead of 0.5 to 1.6, one would get much better cycling routes. This to compensate the minor speed differences.

When looking at the brouter profiles like fastbike (https://github.com/abrensch/brouter/blob/master/misc/profiles2/fastbike.brf) I have the idea that priorities (or penalties if you approach it from the orther side) have much bigger difference.

Correct me if I'm wong.

Harry

--

[Harry van der Wolf]

And continuing on my own argument.

The routing itself is maybe OK but the "distinctive parameters" (don't have a better name) are way too narrow.

If this set of parameters for cycling get wider, one wouldcpossibly also increase the hc again.

Harry

[Fabien Nicollet]

Thanks everyone for the explanations, that wasn't really the point of the thread but I think I learnt a couple things :) 

I was more interested in the code part and differences between Java and Native code. Like the processIntersection function which is called thousands and thousands of times:

Java:

https://github.com/osmandapp/Osmand/blob/a18413bfdc975a9546f7c9a08a67d30705ac095a/OsmAnd-java/src/net/osmand/router/BinaryRoutePlanner.java#L710

C++:

https://github.com/osmandapp/OsmAnd-core/blob/legacy_core/native/src/binaryRoutePlanner.cpp#L793

There seem to be some slight differences between code algorithms, like the way that one uses an Iterator in Java and a pointer in C++. Would this kind of differences between codes make the difference between Java and Native or is the algorithm implemented in a different way? Because it looks like Native is a straight port from Java code with no algorithm changes and yet, it gives different results when executed (native is faster).

Fabien

[Osmandtrier]

Tha values mean, what they say. Saying primary 3,2 unclassified 1,0 means you want to go 3,2 Kilometer unclassified road instead of 1 km primary. You really want this not. The result will be the same way like unclassifified 1 and primary 2. If there is  enough distinction, there is no more result.be increase the spread. This only increase is the calculation time.

And that is the problem of the system. If you have senseful values, the calculation time ist slow. Increasing hc, calculation is getting quick. But the values are loosing their effect. So you increase the values. But so the calculation will get again slow. So you have to  increase the hc. Then you have to increase the spread. If you do one thing, it destroies the effect of the other setting. It is a kind of vivious circle.

Because this vicious circle the values in routing are so strange how they are.

[Osmandtrier]

Am Sonntag, 15. März 2015 14:47:59 UTC+1 schrieb Max:

Die Veränderungen sind nicht zufällig, sondern haben eine starke Tendenz, und das ist im Ergebnis für bestimmte Nutzer, dass man sie in mehr gefährliche Situationen bringt als gewünscht.

Natürlich entscheidet der Algorithmus nicht zufällig.

Er müsste so sein, dass Hauptstrassen nicht bevorzugt werden, was system immanent ist.

Ich habe den EIndruck, dass Du diese Aussage einfach nicht zur Kenntnis nimmst.

Ich habe diese nicht nur zur Kenntnis genommen, sondern sogar versucht das zu erklären.

Nicht optimal kann mehr oder weniger blöd optimal sein. Und bei Osmand ist eher weniger optimal mehr blöd.

Ich versuche es nochmal:

Es ist logisch nicht möglich mit dem hc oder maxDefaultSpeed zu bestimmen, welche nicht optimale Route der Router berechnet.

Das der Router dich oft auf gefährliche Straßen navigiert, wenn du ihm sagst er soll eine nicht optimale Route berechnen (hc > 1), liegt einfach daran, wie das Straßennetz aufgebaut ist

 

....

Du kannst dem Router jetzt nicht vorwerfen, dass er die Wegsegmente welche er (wegen des hc) nicht besucht hat, logischerweise gar nicht berücksichtigen kann.

 
Dem Router werfe ich nicht s vor, sonderm dem/n Entwickler.

Dass das Strassennetz in OSM dazu führt, dass Routen mit Hauptstrassenpräferenz mit dem A*-Algorithmus besonders schnell berechnet werden, ist mir schon länger bekannt.

Jetzt ist der A*-Algo in Osmand implementiert worden und er war für Autos immer zu langsam. Da kommt der hc dazu und die Hauptstrassen werden dadurch noch mehr bevorzugt.

Also das System ist rechenzeit bedingt nicht Fahrrad und Fußgängerfreundlich. Die Rechenzeitoptimierung bringt noch mehr unfreundlichkeit dür den Fußgänger.

Oder der Qualitätsverlust für den Radfahrer in der Berechnung ist bei weitem höher als für den Autofahrer bei gleichem hc.

Und jetzt kommen wir zu Brouter. Brouter bekommt eine bessere und schnellere Ergebnisse bei deutlich weniger Resourcen hin. Verwendet aber auch einen A*-Algorithmus. Das bedeutet die Architektur ist dort schlauer.

Wenn man hier jemand etwas vorwerfen kann, dann dem Entwickler. Nämlich dass er auf das falsche Pferd gesetzt hat, wie er das System implimentiert.

Hie und da mache ich was mit VisualBasic auf Anfängerbasis etwas für mich. Irgend wann wurde da etwas sehr langsam. Die Erklärung war, ich habe meine Dateien in XML-Dateien geschrieben. Ist halt schön einfach für einen DAU für mich.

Interessant finde ich zum Beispiel, dass ich die Kartendateien von Brouter nicht mit einem Texteditor lesen kann, die von Osmand schon. Das Tempooproblem liegt vielleicht darin, dass das Einlesen der Daten aufgrund ihrer Aufbereitung ziemlich lang dauert.

[Harry van der Wolf]

2015-03-16 8:52 GMT+01:00 Osmandtrier <stephan....@googlemail.com>:

Interessant finde ich zum Beispiel, dass ich die Kartendateien von Brouter nicht mit einem Texteditor lesen kann, die von Osmand schon. Das Tempooproblem liegt vielleicht darin, dass das Einlesen der Daten aufgrund ihrer Aufbereitung ziemlich lang dauert.

I have also opened the obf files with a text editor, but even though you can pretty much read what is in there they are still binary files. They are some SQLite derived format.

I don't think the file format is the time consuming factor. The files are also that big because they contain the most data compared to other nav apps. 

Some time ago I also wrote about tests using a Class-4 and a Class-10 SDcard. Upont calculation times of 10 seconds to 4 minutes it was only a few seconds between class-4 and class-10. Which means that reading the data is not the limiting factor at all. The inefficient calculation itself is by far the limiting factor.

End February/Early March we also discussed about this (https://groups.google.com/forum/#!topic/osmand/pE8Vl3m-klE). 

I also mentioned then that I tested splitting up the maps in the map, transport, routing and POI data and that didn't make a difference either: not on class-4 and neither on class-10 SDcards.

It is the calculation "engine" that is so terribly slow and memory hungry.

Harry

[Harry van der Wolf]

2015-03-15 21:06 GMT+01:00 Fabien Nicollet <fnic...@gmail.com>:

Thanks everyone for the explanations, that wasn't really the point of the thread but I think I learnt a couple things :) 

I was more interested in the code part and differences between Java and Native code. Like the processIntersection function which is called thousands and thousands of times:

Java:

https://github.com/osmandapp/Osmand/blob/a18413bfdc975a9546f7c9a08a67d30705ac095a/OsmAnd-java/src/net/osmand/router/BinaryRoutePlanner.java#L710

C++:

https://github.com/osmandapp/OsmAnd-core/blob/legacy_core/native/src/binaryRoutePlanner.cpp#L793

There seem to be some slight differences between code algorithms, like the way that one uses an Iterator in Java and a pointer in C++. Would this kind of differences between codes make the difference between Java and Native or is the algorithm implemented in a different way? Because it looks like Native is a straight port from Java code with no algorithm changes and yet, it gives different results when executed (native is faster).

Fabien

Sorry for stealing your thread. you are right. The other mails were relevant and informational but not on topic.

However, I'm afraid you wont't get an answer here as nobody is this deep into the code. The one currently in this thread that understands the code best is Max but I think that he can't answer your questions either.

If you really need answers you probably have to directly mail Victor or Alexey. 

Harry

[V S]

I can give you just short answer: the algorithm in Java and C++ try to be exactly the same. At least I try to keep it. It is hard to explain all details and usually it requires me 2-3 days to understand logic before I start really changing something there. It has a Trace mode for developers so it is slightly easier to understand engine code, but not much :)

routing.xml should be clear enough, I think

понедельник, 16 марта 2015 г., 10:33:00 UTC+1 пользователь Harry van der Wolf написал: