pathfinder script .. ideen oder anregungen

[kai]

hallo zusammen,

ich versuche in meinem game gerade einen vernüftigen algorythms zu finden um ein 'pathfinder' script zu ralisieren...
vielleicht eben ein bild zur veranschaulichung
[img] http://www.mounchain.com/scree.jpg [/img]
so ich möchte zum beispiel eine einheit von A nach B oder C ziehen..
da aber das wasser ( die blauen felder ) von einheiten nicht überquert werden können ( die türme in der mitte schon ) ...
die blauen nummern sind die feldnummern..
nun fällt mir auf anhieb eine möglichkeit ein:
ich suche alle möglichen strecken zwischen A und B und nehme dann die kürzeste .. aber da brauch ich ja für jeden move 1 woche rechnerleistung denn es gibt insgesamt 1 mio felder ...

kann mir jemand nen kleinen ( besseren) denkanstoss geben ..

vielen dank schonmal
kai

[*Markus]

Hallo,

ich verstehe dein Problem nicht. Falls deine Figuren felderweise bewegt werden können, musst du ja nur abprüfen, ob das nächste Feld ein Wasserfeld ist, oder nicht, und je nachdem reagieren?

Markus

[kai]

hi,

ja so einfach solls ja nu nich sein.
ist schon so das man einfach nur ein zielfeld angeben kann.
aber danke für den versuch..

cu
kai

[Cruz]

Hallo Kai,

ich weiss nicht wie viel du über algorithmische Geometrie weisst und demnach wie viel dir das Folgende sagt, aber...

Es gibt zwei sehr effiziente geometrische Ansätze in 2D einen kürzesten Pfad zu finden: der Sichtbarkeitsgraph und die sogenannten Shortest Path Maps. Die Konzepte sind relativ schnell zu verstehen, aber die Algorithmen für die Berechnung sind schon etwas aufwendiger.

Der Sichtbarkeitsgraph ist deutlich einfacher und auch noch flexibeler, daher rate ich dir den als erstes zu verfolgen. Wenn du es wirklich ernst meinst und dazu ansetzt, können wir gerne konkreter darüber reden.

Noch ein dritter Ansatz, der mir dazu einfällt, stammt aus der klassischen KI. Algorithmisch ist diese Lösung sehr simpel, aber von der Performance dem Sichtbarkeitsgraph weit unterlegen. Du brauchst dafür die Begriffe "Graph", "Breitensuche" und "Tiefensuche". Wenn du damit nicht vertraut bist, solltest du das jetzt grad mal nachholen.

Stelle dir dein Wabengitter als ein Graph vor. Jede Wabe ist mit den benachbarten Waben, die erreicht werden können (kein Wasser) mit einer Kante verbunden. Starte eine Breitensuche in dem Statknoten, wo die Spielfigur steht und suche nach dem Zielknoten des Feldes, wo die Figur hin will. Achte dabei darauf, dass du Zyklen elimierst, d.h. in deiner Suche niemals das selbe Feld zweimal betrachtest.

Probier den selben Ansatz auch mit einer Tiefensuche aus. Breitensuche und Teifensuche haben unterschiedliche Eigenschaften, was Laufzeit und Speicherbedarf angeht. Beide sind auf jeden Fall schon mal besser, als jeden erdenklichen Pfad auszuprobieren.

Die Breitensuche kannst du noch weiter tunen, indem du zwei Breitensuchen gleichzeitig anfängst, einmal vom Startknoten und einmal vom Zielknoten aus. Sobald sich die zwei Suchen "treffen", ist der Pfad gefunden. Mit der Tiefensuche funktioniert dieser Ansatz im Allgemeinen nicht.

Dann gibt es da noch den sehr populären A* (ja, A Stern heisst er) Algorithmus. Es ist auch eine Art Breitensuche, aber die Knoten werden mit ihrer Luftlinienentfernung vom Zielknoten gewichtet. Genaueres solltest du am besten selbst nachlesen.

Na dann viel Spaß,
Cruz

hallo zusammen,

ich versuche in meinem game gerade einen vernüftigen algorythms zu finden um ein 'pathfinder' script zu ralisieren...
vielleicht eben ein bild zur veranschaulichung
[img] http://www.mounchain.com/scree.jpg [/img]
so ich möchte zum beispiel eine einheit von A nach B oder C ziehen..
da aber das wasser ( die blauen felder ) von einheiten nicht überquert werden können ( die türme in der mitte schon ) ...
die blauen nummern sind die feldnummern..
nun fällt mir auf anhieb eine möglichkeit ein:
ich suche alle möglichen strecken zwischen A und B und nehme dann die kürzeste .. aber da brauch ich ja für jeden move 1 woche rechnerleistung denn es gibt insgesamt 1 mio felder ...

kann mir jemand nen kleinen ( besseren) denkanstoss geben ..

vielen dank schonmal
kai

[Biesterfeld]

Hej,

ich suche alle möglichen strecken zwischen A und B und nehme dann die kürzeste

Dein Problem ist ein wohl bekanntes Problem der theoretischen Informatik und gehört in das Gebiet der Graphentheorie.

Jenachdem wie dein Graph aufgebaut ist, wirst du einige Fallunterscheidungen treffen müssen, wie z.B. ob die Kanten gewichtet oder ungewichtet, gerichtet oder ungerichtet sind oder ob dein Graph zyklisch oder azyklisch ist.

Soweit ich das sehe handelt es sich um einen ungerichteten, ungewichteten zyklischen Graphen. In dem Fall suchst du also wahrscheinlich nach der Iterativen Tiefensuche. Eigentlich ziemlich leicht zu implementieren.

.. aber da brauch ich ja für jeden move 1 woche rechnerleistung denn es gibt insgesamt 1 mio felder ...

Zugegeben, 10^6 Knoten is schon etwas viel, insbesondere dann wenn fast alle von ihnen einen Grad von 6 haben. Da aber die iterative Tiefensuche immer zuerst den kürzesten Weg sucht, berechnest du nicht alle möglichen Pfade sondern wirklich nur bis du den ersten kürzesten gefunden hast.

Weiterhin kannst du die Laufzeit drastisch reduzieren, indem du von vornherein Knoten von der Suche ausschließt. Immrhin scheint es sich ja in deinem Fall um Punkte auf einer Karte zu handeln, die also auch Koordinaten haben. Du kannst also z.B. nur solche Felder auf der Landkarte zulassen die innerhalb eines bestimmten Radius um A und B liegen. Und steckst nur diesen Sub-Graphen in die Suche. Achte aber darauf, dass du den Radius nicht zu klein wählst, insbesondere dass sich die beiden Umreise um A und B auch überschneiden müssen.

Zuletzt ist anzumerken, dass der Algo mit einer Komplexität von [latex]O( | V | + | E | )[/latex] läuft, wobei [latex]V[/latex] die Anzahl der Knoten ist (in deinem Fall 1000000) und [latex]E[/latex] die Anzahl der Kanten (in deinem Fall maximal 3000000). Das ist eigentlich noch in einem überschaubaren Rahmen. Bei guter Implementierung sollte das schon passen.

Beste Grüße
Biesterfeld