route berechnen?

[Newbie44]

Hallo,

ich hab mal eine frage an alle hier, die sich mit navigation schon mal beschäftigt haben. es geht nicht um eine spezielle programmiersprache (is ja eh alles sehr ähnlich)

Wie macht man einen Navigationsalgorythmus? Hat jemand schon mal sowas gemacht, bzw hat es vor das ganze zu machen? Ich bin heute nämlich mit nem Navigationssystem gefahren und finde es einfach nur genial.

Die Route war perfekt, schön kurz und ich bin rechtzeitig angekommen.

Jedoch wie sieht so ein algorythmus aus?

gruß

sebastian

[Matze]

Hi,

der A*-Algorithmus, den ich für mein Snake nutze, falls du das mitverfolgt hast, kann auch für Navis eingesetzt werden. Siehe hierzu auch das Beispiel von Wikipedia.

Edit: Wieso geht denn diese URL nicht mit den [url]-Tags? Naja, dann so: http://de.wikipedia.org/wiki/A*-Algorithmus#Beispiel

[Newbie44]

hey danke, wusste gar nicht das es schon so nen algo gibt. aber ich finde es echt beeindruckend was heutzutage schon alles möglich ist. aber seit ich auf die navigation gekommen bin, find ich es spannend wie das alles funktioniert.

Bin mal gespannt auf das Galileo Navigationssystem

ach ja dann noch ne frage, kennt jemand ne navigationssoftware die opensource ist, damit man sich das ganze mal ansehen kann?

@Matze

Hab leider dein Thema nicht verfolgt, bin ja auch nur noch selten online

[Der_Unwissende]

HI,
der konkrete Algorithmus dürfte sicherlich je nach System etwas anders ausfallen, aber an sich kannst Du Dich ganz einfach vom Routing insperieren lassen. Daten von einer IP-Adresse an eine andere zu leiten ist selten direkt möglich, auch hier geht es also um nichts anderes als eine Route (einen Weg) zu finden. Zudem wird beim Routing auch gleich versucht Staus u.Ä. zu berücksichtigen.

Bei Navigationssystemen dürfte der Ansatz prinzipiell ähnlich funktionieren (ohne Gewähr!). An sich bietet es sich aber schon an, dass Du einfach mit Graphenalgorithmen arbeitest. Dabei wird nicht jede Straße gleich bewertet, man wird sicherlich eher mit verschieden großen Rastern arbeiten (z.B. lässt sich der kürzeste Weg von einer Stadt in eine andere getrennt vom Weg in den jeweiligen Städten betrachten!). Ähnlich dürfte es dann wiederum in einzelnen Städten aussehen, da gibt es schließlich auch wieder Bezirke (bzw. eine Rasterung), so dass man erstmal nur die kürzeste (besser gesagt schnellste/kostengünstigste) Route in den entsprechenden Sektor sucht und erst von dem Punkt aus weiter ins Detail geht (die eigentliche Straße).

Gruß Der Unwissende

[roter Kasten]
A*, Dijkstra, ... sind dann alles mögliche Algorithmen um einen kürzesten Weg zu finden. Wie gesagt, Graphenalgorithmen eben
[/roter Kasten]

[leddl]

Zitat von Newbie44:

hey danke, wusste gar nicht das es schon so nen algo gibt.

Wie sollte dein Navi doch sonst geleitet haben? Und warum fragst du dann danach?

[Udontknow]

Hallo!

In diesem Tutorial habe ich mal per Backtracking die Wegfindung realisiert, vielleicht hilft es ja.

Cu,
Udontknow

[Newbie44]

Zitat von Der_Unwissende:

HI,
man wird sicherlich eher mit verschieden großen Rastern arbeiten

da is was dran mit den rastern, is mir auch aufgefallen, das navi zeigt ja nicht alle straßen auf einmal an, in den verschiedenen zoom größen. je näher man rangeht, desto mehr details findet man.

es könnte auch so sein, das das navi erst die großen strassen berechnet, und dann die kleinen, sprich erst den groben weg, und den dann noch optimiert.

wäre das denkbar oder zu unhandlich?

[Matze]

Zitat von Newbie44:

wäre das denkbar oder zu unhandlich?

Ich vermute, das Navi schaut erst nach den Straßen, auf denen am schnellsten gefahren werden darf (Autobahnen, Bundesstraßen, Land-/Kreisstraßen), sofern diese nicht zu allzu großen Umwegen führen. Dann werden kleinere Straßen berücksichtigt, wenn es beispielsweise durch Orte geht oder man in Zielnähe ist bzw. auf dem Weg zu Schnellstraßen. Natürlich müssen Einbahnstraßen berücksichtigt werden.

Das fand ich kürzlich so faszinierend: Das Navi lotste uns einmal im Kreis herum und ich wunderte mich, was das soll, habe dann jedoch gesehen, dass man nicht direkt links abbiegen durfte, wo wir hin mussten und so machte das Navi einen intelligenten Bogen.

[Newbie44]

das stimmt, das wäre die beste lösung zum navigieren. aber wenn man mal mit knotenpunkten rechnet, nur mal bei autobahnen, das sind ja da schon viele, aber es gibt enorm viele knotenpunkte die man beachten müsste.

das navi müsste die ja alle durchprüfen, was jetzt der beste weg wäre, eigentlich müsste dsa ja länger dauern, es geht aber immer unheimlich schnell, das is das was mich so wundert.

scheint ein ziemlich schneller algorithmus zu sein

[leddl]

Zitat von Matze:

Ich vermute, das Navi schaut erst nach den Straßen, auf denen am schnellsten gefahren werden darf (Autobahnen, Bundesstraßen, Land-/Kreisstraßen

Das kommt natürlich drauf an, was der Zweck der Routenberechnung ist
Im Normalfall kannst du zwischen schnellster und kürzester Route (und evtl. noch diverse anderen) wählen. Ich zB lasse immer die kürzeste berechnen und manchmal verbiete ich Autobahnen sogar komplett, da ich ganz genau weiß dass ich auf Bundes- und Landstraßen *hüstel* ein bißchen schneller unterwegs bin, als das Navi es vorsieht
Und dann werden aber wirklich nicht unbedingt die größten möglichen Straßen gewählt, sondern dann findet man sich ganz schnell auch mal auf nem kleinen Feldweg wieder, weil man damit die 100m Umweg einer Kurve spart

//Edit:

Zitat von Newbie44:

das stimmt, das wäre die beste lösung zum navigieren. aber wenn man mal mit knotenpunkten rechnet, nur mal bei autobahnen, das sind ja da schon viele, aber es gibt enorm viele knotenpunkte die man beachten müsste.

das navi müsste die ja alle durchprüfen, was jetzt der beste weg wäre, eigentlich müsste dsa ja länger dauern, es geht aber immer unheimlich schnell, das is das was mich so wundert.

Ich gehe davon aus, dass bereits durch heuristische Verfahren ein ungefährer Weg errechnet wird, wodurch dann sehr viele Wege gar nicht mehr berechnet werden müssen. Wenn dann noch die dynamische Programmierung angewendet wird, fallen wieder einige Wege weg, so dass die endgültige Menge an vollständig zu berechnenden Wegen halbwegs überschaubar sein wird.