Dijkstra - Kürzester Weg

Hier könnt Ihr gute, von Euch geschriebene Codes posten. Sie müssen auf jeden Fall funktionieren und sollten möglichst effizient, elegant und beispielhaft oder einfach nur cool sein.
Benutzeravatar
Thorium
Beiträge: 1722
Registriert: 12.06.2005 11:15
Wohnort: Germany
Kontaktdaten:

Beitrag von Thorium »

Hm, sehr theoretisch, leider hab ich von Mathe echt wenig Ahnung.

Ich hab mir mal nen eigenen Pathfinding-Algo ausgedacht. Hatte aber eine große Schwäche. Der war gedacht für Tileengines nur leider war eine Gewichtung der Tiles dann sehr schwierig zu implementieren, was den Algo dann für meine damaligen Zwecke nutzlos gemacht hat.

Der Algo funktioniert grundlegend anders als A*, er schaut sich nicht jedes Tile einzeln an. Die Idee war es einen Algo zu machen, der mehr wie ein menschliches Gehirn vorgeht, also mehr aufs Ziel fixiert. Also man hat einen Startpunkt und einen Endpunkt, der Algo ermittelt dann alle Knotenpunkte des Pfades indem er eine direkte Linie vom Startpunkt zum Endpunkt zeichnet. Befindet sich ein Hindernis auf der Linie wird am Hindernis ein temporärer Knoten erzeugt und Linien entlang dem Hindernis gezeichnet. Der Pfad also aufgesplittet, bis zum Ende des Hindernises. Da wird geprüft ob eine direkte Linie zwischen dem vorherigen Knoten (Startpunkt in diesem Fall) und dem neuen Knoten besteht, wenn ja wird der temporäre Knoten entfernt. Und da beginnt es dann wieder von vorne, Line zum Endpunkt, etc. Am Ende wird der Pfad mit dem kürzesten Weg rausgesucht.

Leider hab ich die Konzeptzeichnungen nicht mehr. Hatte mir Teilmaps zum Test auf Papier gezeichnet, damals in der Schule, und dann manuell die Pfade ermittelt. Hat immer funktioniert. Der Vorteil zu A* ist, das der Algo Wasserdicht ist, der findet den Weg immer und das sollte auch ziemlich performant gehen. Nachteil ist halt das Gewichtung der Tiles sehr umständlich zu implementieren ist.
Zu mir kommen behinderte Delphine um mit mir zu schwimmen.

Wir fordern mehr Aufmerksamkeit für umfallende Reissäcke! Bild
Kaeru Gaman
Beiträge: 17389
Registriert: 10.11.2004 03:22

Beitrag von Kaeru Gaman »

[ot]
wer hat eigentlich den Namen erfunden?
heißt das nicht "Deichstraße"?
[/ot]
Der Narr denkt er sei ein weiser Mann.
Der Weise weiß, dass er ein Narr ist.
Little John

Beitrag von Little John »

Kaeru Gaman hat geschrieben:wer hat eigentlich den Namen erfunden?
Den Namen Dijkstra? Ob sich hier jemand so gut in niederländischer Namensforschung auskennt?
Kaeru Gaman hat geschrieben:heißt das nicht "Deichstraße"?
Ich kann nur sagen dass "Deichstraße" auf Plattdeutsch -- was ja dem Niederländischen sehr ähnlich ist -- "Diekstraat" heißt.

Gruß, Little John
Kaeru Gaman
Beiträge: 17389
Registriert: 10.11.2004 03:22

Beitrag von Kaeru Gaman »

"Dijk" wird "daik" ausgesprochen, ist meiner Ansicht nach die selbe Wurzel wie "Deich" und "Dike", und auch dieselbe Bedeutung.

vorstellen kann ich mir schon einen Zusammenhang:
eine Deichstraße läuft oben auf dem Deich entlang und folgt dem Fluß-/Küstenverlauf,
um möglichst viel Land einzudämmen.
hier kann man stark Abkürzen, wenn man an Knotenpunkten von Landzungen Direktverbindungen nutzt.
Bei Buchten hingegen ist kein Abkürzen möglich, weil man dort Wasser dazwischen hat.
insofern kann ich durchaus den Begriff "Deichstraßen-Algorithmus" nachvollziehen.
Der Narr denkt er sei ein weiser Mann.
Der Weise weiß, dass er ein Narr ist.
Little John

Beitrag von Little John »

Kaeru Gaman hat geschrieben:vorstellen kann ich mir schon einen Zusammenhang:
eine Deichstraße läuft oben auf dem Deich entlang und folgt dem Fluß-/Küstenverlauf,
um möglichst viel Land einzudämmen.
hier kann man stark Abkürzen, wenn man an Knotenpunkten von Landzungen Direktverbindungen nutzt.
Bei Buchten hingegen ist kein Abkürzen möglich, weil man dort Wasser dazwischen hat.
insofern kann ich durchaus den Begriff "Deichstraßen-Algorithmus" nachvollziehen.
:?:
Selbst wenn "Dijkstra" die Bedeutung "Deichstraße" hat, der Algorithmus heißt einfach nur nach dem Nachnamen seines Erfinders.

Gruß, Little John
Benutzeravatar
Xenos
Beiträge: 114
Registriert: 24.01.2006 20:33
Wohnort: Dresden(hin und wieder)
Kontaktdaten:

Beitrag von Xenos »

@thorium:

Ich denke, ich kann nachvollziehen, was du meinst. Auch das er sehr performancefreundlich ist, leuchtet mir ein. Das Problem mit dem Tile- gewicht könnte man umgehen, indem man den Algorithmus mehrfach anwendet und jedesmal tiles mit einem Gewicht > Grenzgewicht als Hindernis betrachtet. Das wiederholt man solange, bis man keinen Pfad mehr findet. Dann war die zuletzt gefundene Lösung wohl schon sehr gut.

Allerdings sind die Grenzgewichte mit Bedacht zu wählen. Beispielsweise, wenn man ein Feld mit dem Gewicht zwei hat, welches von Feldern des Gewichts eins umgeben ist:

Kommt man von Westen und will nach Norden oder Süden, ist es sinnvoller dieses Feld zu umgehen, will man jedoch nach Norden, ist es besser, direkt über dieses Feld zu gehen.

Alternativ kann man auch mit deinem vorgeschlagenen Algorithmus die wichtigen Knoten suchen und die Verbindung zwischen den Knoten mit einem anderen Algorithmus wie etwa A*.
gô ni itte wa gô ni shitagae.
(Wenn du in ein Dorf kommst, richte dich nach seinen Gepflogenheiten - jap. Sprichwort.)
Kaeru Gaman
Beiträge: 17389
Registriert: 10.11.2004 03:22

Beitrag von Kaeru Gaman »

Little John hat geschrieben:...der Algorithmus heißt einfach nur nach dem Nachnamen seines Erfinders.
is ja auchn handkäs, kann man ja riechen... /:->
Der Narr denkt er sei ein weiser Mann.
Der Weise weiß, dass er ein Narr ist.
Little John

Beitrag von Little John »

Kaeru Gaman hat geschrieben:
Little John hat geschrieben:...der Algorithmus heißt einfach nur nach dem Nachnamen seines Erfinders.
is ja auchn handkäs, kann man ja riechen... /:->
Ne, aber man kann den Link in meinem ersten Posting in diesem Thread anklicken. :D

Gruß, Little John
Benutzeravatar
Froggerprogger
Badmin
Beiträge: 855
Registriert: 08.09.2004 20:02

Beitrag von Froggerprogger »

Nach der Beschreibung von thorium würde aber in folgendem Szenario:

Code: Alles auswählen


          ##########
                   #
S                  #          Z
                   #
          ##########
mit S Start und Z Ziel folgender Weg gegangen:

Code: Alles auswählen

         |------------|
         |##########  |--|
         |--------|#     |--|
S-----------------|#        |--Z
                   #
          ##########
also erst bis zum Hindernis, dann drumrum und dann weiter zum Ziel.
!UD2
Benutzeravatar
Thorium
Beiträge: 1722
Registriert: 12.06.2005 11:15
Wohnort: Germany
Kontaktdaten:

Beitrag von Thorium »

Froggerprogger hat geschrieben:Nach der Beschreibung von thorium würde aber in folgendem Szenario:

also erst bis zum Hindernis, dann drumrum und dann weiter zum Ziel.
Nicht ganz. :)
Ohne die Zeichnungen ist das schwer zu erklären für mich, irgendwie.

Hab den Knoten mal Nummern verpasst.

Code: Alles auswählen

         4------------5
         |##########  |--|
         3--------2#     |--|
S-----------------1#        |--Z
                   #
          ##########
Die Lösung ist das die Knoten nur temporär erstellt werden und dann auf Optimierungsmöglichkeit geprüft werden. Das kann geschehen, indem geschaut wird ob es eine unterbrechensfreie Linie zurück zum startpunkt oder vorherigen Knoten gibt. Dann würdn die Knoten 1 und 2 wegoptimiert werden und eine Linie von S zu 3 oder S zu 4 gezeichnet werden.

Stell dir das wie eine Abtastung der Hindernisse vor. Du hast dann praktisch die Konturen des Hindernisses als Pfad und Optimierungen sollten sehr simpel durchzuführen sein.
Zu mir kommen behinderte Delphine um mit mir zu schwimmen.

Wir fordern mehr Aufmerksamkeit für umfallende Reissäcke! Bild
Antworten