nicht angemeldet
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