Wegfindung: Wie funktioniert sowas (theoretisch)

[yankee]

Zitat:

Zitat von everdream

Weiß jemand, nach welchem Prinzip diese Eingrenzung gemacht wird?

Ja, das ist auch in dem Buch erklärt, dass ich mittlerweile natürlich längst gelesen habe (sehr emphelenswert nebenbei ^^).
Also es gibt da sicherlich noch andere Möglichkeiten, aber zumindest eine, die gerne angewandt wird:

Wenn du zwei Punkt hast und du kennst bereits eine mögliche Entfernung zwischen den beiden Punkten, dann kannst du die beiden Punkte als Mittelpunkte für eine Ellipse verwenden. Die Summe der Entfernung der Ellipsenaussenseite (wie heisst das richtig? ^^) zu den beiden Mittelpunkten ist dabei immer deine bekannte Entfernung. (Klingt kompliziert, das ist aber nur so, weil das mit etwas Grafik wesentlich einfacher zu erklären wäre *grr*).
Dann weisst du, dass jedes mal, wenn du die Ellipse verlässt die Wegsuche abbrechen kannst, weil der dir bekannte Weg in jedem Fall kürzer ist.

Fragt sich nur, was du als "bekannte Entfernung" verwendest. Vielleicht einfach Luftlinie*2 und wenn er dann nichts findet, dann langsam vergrößern? Oder man nimmt wirklich erstmal ein vereinfachtes Netz (ein vorberechnetes mit wesentlich weniger Knoten) anhand dessen man die Entfernung abschätzen kann.

[everdream]

Also veranshaulicht eine Ellipse, implementiert wird eine Ar Grenwert. Ist ja wirklich simpel, wenn man es so löst. xD

Vielen Dank, das war alles, was ich wissen wollte. :thumb:

[Nuclear-Ping]

Über genetische Algorithmen können Routenplaner auch gesteuert werden.

[stoxx]

vielleicht hilft Dir ja das Animationsprogramm zum Traveling salesman Problem weiter :-)

http://www.swisseduc.ch/informatik/g...nch/index.html

[everdream]

Hach, TSP. ich liebe solche Probleme... :coder:

[christian_r]

Zitat:

Zitat von Speedmaster

Gabs hier im Forum schoneinmal,hier ist ein Tutorial wie sowas funktioniert!

Bei dem Link gibt es 4 PHP-Warnungen, weil er die "white.html" nicht finden kann. Schade.

[toms]

Zitat:

Zitat von christian_r

Zitat:

Zitat von Speedmaster

Gabs hier im Forum schoneinmal,hier ist ein Tutorial wie sowas funktioniert!

Bei dem Link gibt es 4 PHP-Warnungen, weil er die "white.html" nicht finden kann. Schade.

Das Tutorial "pathfinding" gibt's im wiki:

http://wiki.delphigl.com/index.php/Tutorial_pathfinding

[Luckie]

Guck mal hier: http://www.michael-puff.de/Developer/Delphi/Demos/ Da habe ich eine Demo zum A*-Algorithmus

[christian_r]

Ich muss mich gerade an den Labyrinth-Algorhythmus erinnern. "Wie kommt man am sichersten aus einem Labyrinth heraus? Indem man immer an der linken Wand entlanggeht." Allerdings würde dieser u. U. für die Strecke Hamburg - Berlin auch über München führen.

Danke für das Tutorial und den Algorhythmus.

[yankee]

Zitat:

Zitat von christian_r

Ich muss mich gerade an den Labyrinth-Algorhythmus erinnern. "Wie kommt man am sichersten aus einem Labyrinth heraus? Indem man immer an der linken Wand entlanggeht." Allerdings würde dieser u. U. für die Strecke Hamburg - Berlin auch über München führen.

Interessant... Jeder sagt immer an der linken Wand :-D.

Das ganze funktioniert allerdings nur mit "2-Dimensionalen" Labyrinthen. Also wenn da Brücken und Tunnel drin vorkommen, wie es im Straßennetz der Fall ist, kann es sein, dass du nur im Kreis läufst.
So Algorithmen kann man natürlich auch nur anwenden, wenn man alle existierenden Straßen kennt. Bei einem Labyrinth ist das ja in der Regel nicht der Fall. Da hast du mit Dijkstra leider keine Chance ;-).