Dijkstra - Kürzester Weg
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.
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!
Wir fordern mehr Aufmerksamkeit für umfallende Reissäcke!
-
- Beiträge: 17389
- Registriert: 10.11.2004 03:22
Den Namen Dijkstra? Ob sich hier jemand so gut in niederländischer Namensforschung auskennt?Kaeru Gaman hat geschrieben:wer hat eigentlich den Namen erfunden?
Ich kann nur sagen dass "Deichstraße" auf Plattdeutsch -- was ja dem Niederländischen sehr ähnlich ist -- "Diekstraat" heißt.Kaeru Gaman hat geschrieben:heißt das nicht "Deichstraße"?
Gruß, Little John
-
- Beiträge: 17389
- Registriert: 10.11.2004 03:22
"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.
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.
Der Weise weiß, dass er ein Narr ist.
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
@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*.
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.)
(Wenn du in ein Dorf kommst, richte dich nach seinen Gepflogenheiten - jap. Sprichwort.)
-
- Beiträge: 17389
- Registriert: 10.11.2004 03:22
- Froggerprogger
- Badmin
- Beiträge: 855
- Registriert: 08.09.2004 20:02
Nach der Beschreibung von thorium würde aber in folgendem Szenario:
mit S Start und Z Ziel folgender Weg gegangen:
also erst bis zum Hindernis, dann drumrum und dann weiter zum Ziel.
Code: Alles auswählen
##########
#
S # Z
#
##########
Code: Alles auswählen
|------------|
|########## |--|
|--------|# |--|
S-----------------|# |--Z
#
##########
!UD2
Nicht ganz.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.
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
#
##########
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!
Wir fordern mehr Aufmerksamkeit für umfallende Reissäcke!