✔ Algorithmus - Weg finden

T

thomy800

Erfahrenes Mitglied
Hi,

ich bin auf der Suche nach einem geeigneten Algorithmus, den kürzesten Weg von A nach B zu finden.
Meine Umgebung (2D) besteht
a) aus Vektoren in einer Liste. Dies sind Linien mit einem Anfang und einem Ende, die bunt auf dem Feld verteild sind.
b) zusätzlich habe ich ein n*m-Feld aus boolischen Werten, wo diese Linien eingetragen sind.
Ich denke, man braucht dafür nur a) oder b) ...

Ich habe natürlich mal gegoogelt, aber irgendwie finden sich da für meinen Fall nur unpassende Algorithmen, die von Knoten ausgehen (wie A-stern etc.)...
Kann mir jemand was geeigneteres empfehlen?

MfG thomy800
 
Hmm.. die beiden Links sind aber genau das, was nicht geht. Mein Problem liegt nicht umbedingt darin, den kürzesten weg zu finden, sondern viel eher, überhaupt einen zu finden, der nicht kollidiert.
Ich habe mal ein Bild erstellt, wo Beispiellinien (die Hindernisse) eingetragen sind, und 2 Wege, die als Resultat ausgespuckt werden sollten.
Der Knackpunkt ist z.B. so eine Kurve. Würde ich dem Weg das Ende der Linie als Zwischenpunkt übergeben, dann hätte ich automatisch eine Kollision, was der Algorithmus ja gerade versucht zu vermeiden. Also muss ich einen gewissen Abstand einhalten. Aber in welche Richtung soll der Abstand gehen? senkrecht/waagerecht zur Linie? Oder mehrere zwischenPunkte in eine Kurve einfügen? Wenn ja, wie soll die Kurve aussehen? Ich weiß ja beim generieren des Wegs noch nicht, wie die nächste Linie aussieht, und die nächste Linie ist ja von der Kurve abhängig..
War das etwas verständlich?^^
 

Anhänge

  • weg.png
    weg.png
    4,9 KB · Aufrufe: 69
Zuletzt bearbeitet:
Dann musst du das Problem eben auf eines reduzieren, das mit Dijkstra lösbar ist. Dazu erstellst du aus deinem Problem einen Graphen, der als Knoten die Endpunkte aller „Mauern“ sowie den Start- und Endpunkt hat. Eine Kante zwischen zwei Knoten hat es genau dann, wenn diese durch eine gerade Linie miteinander verbunden werden können. Kantengewichte sind einfach die Distanz zwischen zwei Punkten. Der kürzeste Weg auf diesem Graphen ist auch der kürzeste Weg für dein Problem.
 
Hallo,

du könntest dir einen Graphen derart definieren:

  • Die Knotenmenge enthält genau den Start und das Ziel sowie sämtliche Eck-/Endpunkte deiner Streckenzüge.
  • Zwei Knoten sind genau dann über eine Kante verbunden, wenn sie sich „sehen“ können, also die direkte Verbindungslinie kein Hindernis schneidet. Zwei Knoten, zwischen denen eine Strecke verläuft, sollen auch über eine Kante verbunden sein.
  • Das Kantengewicht ist einfach der euklidische Abstand der jeweiligen Knoten.

Darauf kannst du dann Dijkstra, A*, etc. anwenden.

Grüße,
Matthias

\edit: Ach, zu langsam.
 
Hallo,

mir ist gerade aufgefallen, dass es doch nicht ganz so einfach ist. Würde man den Graphen so wie von SilentWarrior und mir vorgeschlagen aufbauen, könnte man an Eckpunkten von Hindernissen durch diese hindurchlaufen. Man kann das Problem aber lösen, indem man für solche Eckpunkte mehrere Knoten erzeugt. Ich hab grade keine Zeit mir zu überlegen, wie das dann genau vonstatten gehen müsste. Aber nur mal als Warnung, dass der von uns geschilderte „naive“ Ansatz nicht funktionieren wird.

Grüße,
Matthias
 
Ich würde einfach für jede Mauer zwei Kanten und entsprechend vier Knoten machen. Die beiden Endknoten werden verbunden, wenn keine andere Mauer anliegt (und somit der Weg zur anderen Seite der Mauer nicht versperrt ist.
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück