PureBoard

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.

[ot]
wer hat eigentlich den Namen erfunden?
heißt das nicht "Deichstraße"?
[/ot]

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

"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.

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*.

Little John hat geschrieben:...der Algorithmus heißt einfach nur nach dem Nachnamen seines Erfinders.

is ja auchn handkäs, kann man ja riechen...

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.

Gruß, Little John

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.

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. 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.