Wegfindung: Wie funktioniert sowas (theoretisch)

[yankee]

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.