Denkanstoß bezügl. Algorithmus

[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