Das Rpg-Maker interne Wayfinderscript

[Dr.Brain]

Moin!
Ich hab mich schon des öfteren mit Wayfinding und Waypoints beschäftigt, bin aber meist zu dem Schluss gekommen, dass es wohl nicht möglich ist unabhängig von pos usw. den weg zum helden zu bestimmen.
Jetzt klick ich mal beim event auf move to hero (bei den bewegungsarten)
und der läuft trotz hinderniss relativ gut zu meinem held...*:0*
kanntet ihr diese möglichkeit schon? ich nicht, das macht einiges am tactic ks leichter! allerdings läuft das event wenn man als einzelnen move move toward hero eingibt stur gegen jedes blöde hindernis...man sind die leute von asc2, enterbrain blöd!*g*

[Smokie-Steel]

Ja, wusste ich schon... aber bestimmte Hindernisse kann der NPC trotzdem nicht umgehen. Z.b "U" förmige... er läuft glaub höchstens 1 schritt zurrück um das teil zu umgehen aber wenn das "U" 2 chips hoch geht packt er es nicht.
Mit Waypoints dürfte das aber möglich sein.

[DR_Zeph]

dumpf >_>

Pointer und eine ne Menge Variablen und ein Pathfindingskript ist imo kein Prob,
Lachsen hat sowas mal bei uns im Quatier im Tech-Talk umgesetzt, nya Ergebnis war ein Skript welches ein Weg für ein Event für bis zu 100 Schritten berechnet, [Der beste weg wird dabei herausgefiltert],
nya, lange rede kurzer Sinn,


http://forum.rpg2000.4players.de/viewtopic.php?t=59760

[Oburi]

Guck dir mal das Hintereinanderlaufenskript an. Gezielt bei Person 3. Sie orientiert sich an Person 2 und geht immer auf sie zu. Da hatte ich die Lösung für mein 3 Player SoM KS. Du nimmst von nem Wegpunkt (Event) die Koordinaten und nimmst die deines Charas. Dann vergleichste bei mehreren Wegpunkten die Variablen so:
Hero X - WP 1 X
Hero Y - WP 1 Y
Hero X - WP 2 X
Hero Y - WP 2 Y
und dann weißt du welcher näher dran ist. Dann machste es so, das der Held die Größenwerte abfragt. Wenn WP 1 X kleiner ist als Hero 1 X dann machste Step up und so weiter und so fort. Ist etwas kompliziert für Anfänger, aber wenn man eigene KSe schreiben kann, ist das nicht viel schwerer... ^^

EDIT: Mist DR_Zeph hat schneller geantwortet.. Das von Lachsen kenn ich noch net. Mal ansehen. Vlt. ist es ja so wie ich meine... Dann haste sogarn Beispiel.

[Smokie-Steel]

Schade das rapidshare benutzt wurde, das skript kann man nichmehr downloaden. Würde mich echt interessieren wie das genau umgesetzt wurde. Und in nem skript kapiert mans meist besser als mit erklärungen.

[DR_Zeph]

nya, Oburi hat es eigentlich für den Anfang schonmal erklärt,
hinzukommt nun eine abfrage für eine Terrain ID,
dadurch wird halt geschaut, ob der nächste zu machende schritt gemacht werden kann, oder nicht,
wenn nicht, wird geschaut, wo man noch hingehen könnte, also statt nach links, nach rechts,
nun wird weiter für die bewegung nach rechts der Gang gescheckt, und immer die Bewegung in einer Variable gespeichert, etc.
das ganze ist imo sehr simpel, da man die ganze abfrage nur einmal coden muss, und das ganze dank pointer sich für jeden schritt überträgt,

[Smokie-Steel]

Ne, die Methode von lachsen ist so wie ich es verstanden hab weitblickender, denn sie berechnet im vorraus alle möglichen wege und nimmt den kürzesten.

[Ryo Saeba 1000]

Lest euch doch einfach mal meinen dicken Post durch o.O
Ich hab die A* Methode, auf der Lachsen's finales Pathfinding-Script basierte, so schön erklärt ...
wenn ich mal Lachsen zitieren darf:

Boar, selten hab ich so schnell nen Skript fertig bekommen... und das auf anhieb.
(Muss wohl daran liegen, dass ich nach der Anleitung, die Ryo Saeba gezeigt hat, geskriptet habe... ja XD)

Diese A*-Methode ROCKT!


Also, denke, dass kann man selber hinkriegen, wenn man sich ein bisschen eingehender mit Makertechnik befasst hat. Ich quote mich am besten nochmal selber:




A* (A-star) Pathfinding Methode

Afair einer der besten Pathfinding Algorithmen, den ich hier mal vorstellen möchte. Es handelt sich um reine Theorie und ist nicht programmspezifisch. Hier geht es wirklich um die Grundlagen und Anfänge. Dazu versuche ich mich an einer Übersetzung der wichtigsten Punkte eines Artikels aus dem Netz. Deswegen könnte das dem ein oder anderen ziemlich bekannt vorkommen. Der Original englische Text stammt btw von Patrick Lester. (URL findet sich im Anhang)
Los geht's^^

Wir wollen von Punkt A (grün) zu Punkt B (rot), dazwischen liegt ein Hindernis (blau).
http://www.policyalmanac.org/games/aStarT1.jpg

Beginn der Suche
Wir fangen bei Punkt A an und untersuchen die anliegenden Felder und dann von da aus weiter, bis wir zum Ziel gelangen.

1. Wir fügen Feld A zu unserer Liste "Offen" hinzu. (In dieser Liste befindet sich jetzt nur dieses eine Feld, später kommen aber weitere Felder hinzu, die wir untersuchen wollen.)
2. Wir suchen alle Felder die an Feld A angrenzen (mit "einem Schritt" erreichbar sind -> 8 Felder da Diagonal-Movement angenommen wird) und ignorieren alle Felder die man nicht betreten kann (Wasser, Wände, usw.). Die Felder die betretbar sind, werden unserer Liste "Offen" hinzugefügt (in unserem Fall sind das alle 8). Dann speichern wir noch für all diese 8 Felder, das Feld A als unser "Herkunftsfeld".
3. Dann streichen wir Feld A aus unserer Liste "Offen" heraus und tragen es in eine zweite Liste "Zu" ein. In diese Liste kommen Felder, die erstmal nicht mehr überprüft werden müssen.

Grafisch veranschaulicht kann das dann so aussehen:
Das dunkelgrüne Feld in der Mitte ist unser Startfeld A, jetzt hellblau umrandet, um anzuzeigen, dass es in der Liste "Zu" steht. Alle umliegenden Felder sind hellgrün umrandet um anzuzeigen, dass sie in der "Offen" Liste stehen und noch geprüft werden. Der graue Zeiger in jedem anliegenden Feld, verweist auf das "Ursprungsfeld" (in diesem Fall Feld A).

http://www.policyalmanac.org/games/aStarT2.jpg

Als nächstes suchen wir uns ein Feld aus der Lite "Offen" und wiederholen mehr oder weniger den obigen Prozess.
Aber welches Feld nehmen wir? -> Das mit dem niedrigsten F-Wert.

"Path Scoring" (die Bewertung der möglichen Wege)
Das Problem herauszufinden welches Feld man als nächstes nimmt, berechnet sich durch folgende Formel:
F=G+H

wobei
G = die Bewegungskosten um sich von Starfeld A zu einem beliebigen Feld zu bewegen, dem Pfad folgend, der generiert wurde um das Feld zu erreichen.
H = die geschätzten Bewegungskosten von diesem gegebenen Feld zum Ziel (Feld B). H wird also nur geschätzt. Es gibt viele Wege H zu berechnen und einer wird hier erläutert werden.

Jetzt kommen wir zur Berechnung an einem Beispiel. Wir ordnen jedem Schritt in horizontaler oder vertikaler Richtung den Wert 10 zu und jedem Schritt in diagonaler Richtung den Wert 14. Um also den Wert von G zu erhalten, müssen wir den G-Wert des Ursprungsfeldes nehmen und entweder 10 oder 14 hinzufügen.
H berechnen wir nach der "Manhatten Methode" die folgendermaßen funktioniert: wir errechnen die Gesamtanzahl Felder die wir uns in horizontaler und vertikaler Richtung bewegen und ignorieren dabei diagonale Bewegungen und Hindernisse. Dann multiplizieren wir diese Gesamtzahl mit 10.
F berechnen wir dann wie gesagt indem wir G und H addieren.
Hier wieder eine grafische Darstellung, bei der die Werte in die jeweiligen Felder eingetragen wurden. In den Feldern steht F linksoben, G linksunten, und H rechtsunten.

http://www.policyalmanac.org/games/aStarT3.jpg

Weiterführung der Suche
Um die Suche fortzusetzen, nehmen wir uns jetzt das Feld mit dem niedrigsten F-Wert.

4. Wir nehmen das Feld aus unserer Liste "Offen" heraus und fügen es in die Liste "Zu" ein.
5. Wir untersuchen alle anliegenden Felder und ignorieren die, die nicht betreten werden können und Felder die sich in der Liste "Zu" befinden. Alle anderen untersuchten Felder werden zur Liste "Offen" hinzugefügt, wenn sie sich nicht schon in dieser Liste befinden. Dann speichern wir noch für diese Felder, das in Punkt 1 ausgewählte Feld als unser "Herkunftsfeld".
6. Wenn ein anliegendes Feld sich schon in der Liste "Offen" befindet, dann untersuchen wir, ob dieser Weg zu diesem Feld ein besserer ist. In anderen Worten, ob der G-Wert dieses Feldes niedriger ist, als wenn wir das aktuelle Feld nutzen um dorthin zu gelangen. Wenn nicht, machen wir nichts.
Andererseits, wenn der G-Wert des neuen Pfades niedriger ist, ändern wir das Herkunftsfeld des anliegenden Feldes zum ausgewähltem Feld (im obigen Diagramm, ändern wir die Richtung des Zeigers, sodass dieser zum ausgewählten Feld zeigt. Zum Schluss berechnen wir die F und G-Werte für dieses Feld neu).

Da das vielleicht etwas konfus war, hier nochmal am Bsp. erklärt wie diese Schritte funktionieren.
Von unseren 9 Anfangsfeldern haben wir noch 8 übrig, die in der Liste "Offen" stehen, nachdem unser Startfeld zur Liste "Zu" hinzugefügt wurde. Von diesen 8, ist das mit dem niedrigsten F-Wert das Feld direkt rechts neben unserem Startfeld (F=40). Also wählen wir das als unser nächstes Feld aus. Es ist deshalb im nächsten Diagramm hellblau umrandet.

http://www.policyalmanac.org/games/aStarT4.jpg

Zuerst nehmen wir es nun aus unserer Liste "Offen" und fügen es in die Liste "Zu" ein (deshalb ist es jetzt hellblau unterlegt). Dann prüfen wir die anliegenden Felder. Die drei Felder rechts sind "Wandfelder" und werden ignoriert, ebenso das Feld genau links (unser Startfeld A) welches sich ja auf der Liste "Zu" befindet.
Die anderen vier Felder sind bereits auf der Liste "Offen", also müssen wir prüfen ob die Wege zu diesen Feldern besser sind, wenn wir dieses Feld nutzen um zu ihnen hin zu gelangen, wobei wir den G-Wert als Maßstab nehmen. Prüfen wir zuerst das Feld direkt über unserem ausgewählten Feld. Dessen aktueller G-Wert ist 14. Wenn wir stattdessen über das aktuelle Feld gehen würden um dorthin zu gelangen, wäre der G-Wert 20 (10, was dem G-Wert des aktuellen Feldes entspricht, plus 10 für einen weiteren Schritt vertikal nach oben). Ein G-Wert von 20 ist höher als 14, also ist dies kein besserer Weg. Das sieht man auch, wenn man auf's Diagramm sieht. Es geht schneller zu diesem Feld zu gelangen, wenn man direkt einen Schritt diagonal nach rechtsoben geht, anstatt erst ein Feld nach rechts und dann noch ein Feld nach oben.
Wenn wir diesen Vorgang für alle 4 Felder, die bereits auf unserer Liste "Offen" stehen, wiederholen, stellen wir fest, dass sich kein Weg verbessert, wenn wir über das aktuelle Feld gehen, also ändern wir nichts. Da wir nun fertig sind mit allen anliegenden Feldern, können wir nun zum nächsten Feld wechseln.
Also gehen wir wieder durch unsere Liste "Offen" in der sich jetzt noch 7 Felder befinden und suchen wieder das mit dem niedrigsten F-Wert. Interessanterweise sind es diesmal 2 Felder (mit einem F-Wert von jeweils 54). Welches nehmen wir? Eigentlich egal, aber wenn man auf Geschwindigkeit achten will, kann es von Vorteil sein, dass Feld zu nehmen, was man als letztes zur Liste "Offen" hinzugefügt hat.
Wir nehmen das Feld gleich darunter und eins rechts vom Startfeld wie in der nächsten Darstellung.

http://www.policyalmanac.org/games/aStarT5.jpg

Wenn wir nun die anliegenden Felder untersuchen, stellen wir fest, dass genau rechts ein "Wandfeld" ist, welches wir ignorieren. Genauso das Feld unter dem Wandfeld. Warum? Da wir, um dieses zu erreichen, durch die Ecke der Wand "hindurchgehen" müssten. Deswegen sollte man da drumherum gehen müssen. (Diese Regel ist optional und kann natürlich nach belieben abgeändert werden).
Somit bleiben noch fünf andere Felder. Die zwei Felder unten sind noch nicht in der Liste "Offen" also fügen wir sie hinzu und das aktuelle (ausgewählte) Feld wird als ihr Herkunftsfeld gespeichert. Von den restlichen drei Feldern sind zwei bereits in der Liste "Zu", nähmlich das Startfeld A und das Feld genau über dem aktuellen Feld (beide hellblau umrandet), also ignorieren wir die Beiden. Bleibt noch das Feld genau links neben dem aktuellen Feld, bei dem wir prüfen, ob der G-Wert niedriger ist, wenn wir über das aktuelle Feld gehen um dorthin zu gelangen. Da das nicht der Fall ist, sind wir fertig und sind nun bereit, das nächste Feld aus unserer Liste "Offen" zu wählen.

Wir wiederholen diesen Vorgang bis wir das Zielfeld zu unserer Liste "Offen" hinzufügen. An diesem Punkt dürfte das ungefähr wie in folgendem Diagramm aussehen.

http://www.policyalmanac.org/games/aStarT6.jpg

Zu sehen ist, dass das "Herkunftsfeld" des Feldes zwei Kästchen unter dem Starfeld sich gegenüber der vorigen grafischen Darstellung geändert hat. Vorher hatte es einen G-Wert von 28 und zeigte auf das Herkunftsfeld nach Rechtsoben. Jetzt jedoch hat es einen Wert von 20 und zeigt auf das Herkunftsfeld genau nach Oben. Dies passierte irgendwann auf dem Weg zum Ziel, als der G-Wert geprüft wurde und herauskam dass er niedriger ist, wenn ein neuer Weg genommen wird - sodass das Herkunftsfeld gewechselt wurde und die G und F-Werte neu berechnet wurden. Auch wenn das bei diesem Beispiel keinen Unterschied zu machen scheint, gibt es viele Situationen wo dieses "Geprüfe" den Unterschied macht, ob man den schnellsten Weg zum Ziel findet oder nicht.

So.. wie legen wir jetzt den Pfad fest? Einfach beim roten Feld (Ziel B) anfangen und rückwärts von einem Feld zum nächsten Herkunftsfeld bewegen und den Zeigern folgen. Das bringt einen zurück zum Startfeld und das ist der fertige Weg. Es sollte wie in folgender Darstellung aussehen.

http://www.policyalmanac.org/games/aStarT7.jpg

Zusammenfassung der A* Methode

1) Füge das "Startfeld" zur Liste "Offen" hinzu.

2) Wiederhole Folgendes:

a) Suche das Feld mit dem niedrigsten F-Wert aus der Liste "Offen". Wir bezeichnen dies als aktuelles Feld.
b) Wechsle es in die Liste "Zu"

c) Für jedes der 8 Felder die an diesem aktuellen Feld anliegen …

* Wenn es nicht begehbar ist oder auf der Liste "Zu", ignoriere es. Andernfalls mache Folgendes.
* Wenn es nicht auf der Liste "Offen" ist, füge es zur Liste "Offen" hinzu. Speichere das aktuelle Feld als "Herkunftsfeld" dieses Feldes. Speichere die F, G und H-Werte des Feldes.
* Wenn es schon auf der Liste "Offen" ist, überprüfe, um zu sehen, ob dieser Weg zu diesem Feld besser ist, mit dem G-Wert als Maßstab. Ein niedriger G-Wert bedeuted, dass dies ein besserer Weg ist. Wenn dies der Fall ist, tausche das Herkunftsfeld des Feldes mit dem aktuellen Feld, und berechne die G und F-Werte des Feldes neu. Wenn du deine Liste "Offen" nach F-Werten sortierst hälst, musst du sie wegen der Änderung eventuell neu sortieren..

d) Halte an, wenn du:

* Das Zielfeld zur Liste "Offen" hinzufügst, in welchem Fall der Weg gefunden wurde, oder
* es nicht geschafft hast, das Zielfeld zu finden, und die Liste "Offen" leer ist. In diesem Fall gibt es keinen Weg.

3) Speichere den Weg. Arbeite dich rückwärts vom Zielfeld, indem du von Feld zu Feld zu den jeweiligen Herkunftsfeldern zurückgehst, vor, bis du das Startfeld erreichst. Dies ist dann dein Weg.


Anhang
Für weiterführende Infos und den englischen Originaltext schaut hier vorbei:
http://www.policyalmanac.org/games/aStarTutorial.htm

Hoffe ich konnte es einigermaßen verständlich verfassen, ist aber wie gesagt nicht programmspezifisch, und somit auf eigentlich jede Programmiersprache übertragbar. Deshalb sollte man es mit dem RPGMaker umsetzen können.