Hallo und herzlich willkommen! Tutorials.de ist eine Hilfe-Community mit dem Motto User helfen Usern. Als Gast verfügst Du über Schreibrechte in unseren Foren und Blogs. Du kannst dich aber gerne auch kostenlos registrieren und Teil unserer Gemeinschaft werden! Viel Spaß & Erfolg bei der Vermehrung deines Wissens :-)
Themen: 242.975 | Beiträge: 1.352.293 | Mitglieder: 169.418 (Stand 28.01.10) | Fragen zur Nutzung von Tutorials.de? Nutzungsregeln | Kontaktformular | Impressum
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?
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?
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.
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.
__________________ „Gib einem Menschen einen Fisch, und er wird für einen Tag satt. Lehre ihn Fischen, und er wird ein Leben lang satt.“
“For every complex problem, there is an answer that is short, simple and wrong.”
“Pessimism is safe, but optimism is a lot faster!”
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
__________________ „Gib einem Menschen einen Fisch, und er wird für einen Tag satt. Lehre ihn Fischen, und er wird ein Leben lang satt.“
“For every complex problem, there is an answer that is short, simple and wrong.”
“Pessimism is safe, but optimism is a lot faster!”
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.
@ SilentWarrior:
Ich glaube daraus lässt sich was machen
Man kann zusätzlich zu den Linien beim Generieren Rechtecke erstellen, wo die Linie die Mittellinie bildet. Die Rechtecke können dann die Breite 1 (2 Kanten) bekommen und die Länge der Linie (die anderen 2 Kanten).
An den 4 ecken kommen jeweils Knoten im Abstand r (vorrausgesetzt, sie liegen nicht in oder zu dich an einer anderen Wand). So ist gewehrleistet, dass ein Objekt zwischen den Lücken auch durch passt.
@ Thomas Darimont:
An was für Daten denkst du da? Ein Bildchen hatte ich ja schon erstellt (wo dementprechend Bsp-Daten eingetragen sind).
@ Thomas Darimont:
An was für Daten denkst du da? Ein Bildchen hatte ich ja schon erstellt (wo dementprechend Bsp-Daten eingetragen sind).
Ich meine ein konkretes Beispiel mit Daten zu deinem Szenario:
Zitat:
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.
Das Bild hilft dein Problem zu beschreiben... aber ohne sich erst selber Beispieldaten zu machen kann man dein Problem nur theoretisch bearbeiten...
Du könntest dir ja ein sinnvolles Datenformat ausdenken und dein Beispiel darin beschreiben. Dann kann man mit diesen Beispieldaten rumspielen.
ich dachte da eher an ein textformat (ähnlich wie wir es auch bei unseren coding quizes machen) das man leicht im programm einlesen kann.
Will man jetzt Beispiel nachmachen muss man die Linien / Punktkoordinaten erst noch aus dem Bild rausfummeln... den Schritt könntest du uns ersparen
Antworten (über Gastzugang)
Linear-Darstellung
