Denkanstoß bezügl. Algorithmus

[*Markus]

Hallo,

ich hätte wieder mal eine mathematische Frage. Ich möchte einen Algorithmus programmieren, mit dessen Hilfe der blaue Punkt den Weg zum roten Punkt findet, wobei auf den Weg dorthin verschiedenen Hindernissen auszuweichen ist.

Ich könnte mir das so vorstellen, dass der Punkt den bestmöglichen Weg schon vorher kennen muss und nicht erst auf gut Glück geradlinig loswandert und bei einem Hindernis zwischen rechts und links entscheidet, wobei ich zur Zeit auch nicht wüsste wie man entscheiden kann, welche Richtung besser ist (vielleicht 5px in jede Richtung dazu rechnen, die "Luftlinie" zwischen den beiden Entscheidungen und dem roten Punkt berechnen und den Punkt in jene Richtung wandern lassen, welche die kürzere Luftlinie hat).
Wenn der Punkt hingegen den Weg schon vorher kennt, muss die Strecke mit allen möglichen Kurven bereits vorher berechnet werden, damit der Punkt weiß welche "Koordinaten" er Schritt für Schritt abwandern muss.
Ich weiß aber ehrlich gesagt nicht, wie ich so eine Strecke errechnen kann.
Falls jemand diesbezüglich ein paar Tipps hat, oder es bessere Möglichkeiten gibt dies zu bewerkstelligen, ich bin ganz Ohr.

Markus

[Christian Seiler]

Hallo Markus,

Falls jemand diesbezüglich ein paar Tipps hat, oder es bessere Möglichkeiten gibt dies zu bewerkstelligen, ich bin ganz Ohr.

Du kannst Dir den Dijkstra-Algorithmus ansehen - oder auch die Alternativen, die am Ende des Wikipedia-Artikels besprochen werden.

Um das auf Dein Problem zu übertragen: Du teilst Deine Karte in lauter diskrete Punkte auf. Jeder Punkt wäre ein Knoten in dem Graphen, den Du in Dijstra oder irgend einen anderen Algorithmus steckst. Jeder Nachbarpunkt ist nun mit jedem anderen Nachbarpunkt verbunden (also links, rechts, oben, unten und evtl. noch schräg). Diese Verbindungen bekommen dann verschiedene Gewichte:

* Jeder Punkt, der sich nicht auf einem Hindernis befindet, bekommt
   folgende Gewichte für die Verbindungen für die Nachbarpunkte:

* 1 wenn der Nachbarpunkt links, rechts, oben oder unten davon ist.
    * Wurzel(2) wenn der Nachbarpunkt schräg zu dem Punkt liegt
    * Unendlich (oder zumindest eine Zahl die größer ist als der Umfang des
      Hindernisses) wenn der Nachbarpunkt sich auf einem Hindernis befindet.

* Jeder Punkt, der sich auf einem Hindernis befindet, bekommt für alle
   seine Verbindungen ein unendliches Gewicht.

Und auf das ganze wendest Du dann Dijkstra oder einen anderen Algorithmus an.

Das wäre die Braindead-Variante. Wenn Du es etwas besser machen willst könntest Du z.B. für Punkte, die sich auf Hindernissen befinden, schonmal gar keine Knoten anlegen, das würde den Graphen deutlich in der Größe reduzieren, hätte aber den gleichen Effekt.

Wenn Dein Graph dennoch sehr bleibt (trotz Entfernens der Hindernisse) könntest Du Dir überlegen, ob Du nicht dort, wo es möglich ist, größere Quadrate, die kein Hindernis enthalten, zu einem einzigen Knoten zusammenzufassen und entsprechend die Gewichte anzupassen. Das würde die Größe des Graphen drastisch reduzieren, dafür hättest Du jedoch Genauigkeitseinbußen - denn wenn zwei Wege um ein Hindernis sich nicht stark unterscheiden könntest Du dann evtl. das falsche Ergebnis erhalten. Außerdem wäre der Weg dann immer von Mittelpunkt zu Mittelpunkt dieser Quadrate, was auch nicht immer optimal ist. Wenn die Quadrate dann auch noch angrenzen, die Verbindungslinie aber über ein kleines Stück Hindernis führt, wäre das auch nicht ideal. Du könntest auch ein mehrstufiges Verfahren verwenden indem Du mit groben Varianten erst die zwei oder drei kürzesten Wege findest (dazu müsstest Du Dijkstra halt etwas abwandeln) und dann einen Graph erzeugen, der genau ist, aber nur aus kleineren Punkten der Quadrate besteht, die Du beim ersten Mal erhalten hast und dann auf diesen Teilgraphen Dijkstra nochmal loslassen - das würde enorm viele Knoten an Teilen der Karte sparen, die für den Weg sowieso nicht relevant sind. Beachte aber, dass es für solche Verfahren, die von grob nach fein gehen immer irgendwelche Grenzfälle gibt, wo sie nicht mehr 100%ig stimmen, weil es eben doch eine Näherung ist.

Das nur mal so als generelle Anregungen zu Deinem Problem, wie kompliziert Du es machen willst, liegt an Dir.

Viele Grüße,
Christian

[*Markus]

Hallo,

guter Tipp. Ich weiß nicht warum, aber die Graphentheorie habe ich bisher wohl verdrängt. =) Ich denke, dass ich damit die Lösung finden werde.

Markus

[Detlef G.]

Hallo Markus

ich hätte wieder mal eine mathematische Frage. Ich möchte einen Algorithmus programmieren, mit dessen Hilfe der blaue Punkt den Weg zum roten Punkt findet, wobei auf den Weg dorthin verschiedenen Hindernissen auszuweichen ist.

Vielleicht kann dir das Archiv Denkanstöße geben:
Denkanstoss bei A-Stern Algorithmus
pathfinder script .. ideen oder anregungen
Verbesserung des *-Algorithmus
Von A nach B im Koordinatensystem vorbei an Hindernissen

Auf Wiederlesen
Detlef

[*Markus]

Hallo,

Von A nach B im Koordinatensystem vorbei an Hindernissen

Ich hätte nie zu denken gewagt, dass meine Frage schon mal gestellt wurde, v.a. weil es sich nicht mal um ein Standardthemengebiet handelt.
Vielleicht sollte ich wirklich jede noch so ungewöhnliche Frage zuerst nachschlagen.

Markus