RPG-Maker Quartier

Hey Leute

Es tut mir Leid, dass ich nicht groß nach diesem Topic gesucht hab, denn so speziell, wie mein Anliegen ist, denke ich nicht, dass ich es finden werde

Und zwar geht es um folgendes:
Ich habe mir ein par Gedanken gemacht, wie mein ein relativ simples Pathfinding in den RPG Maker einbauen kann (ich weiß, es wurde schon realisiert, aber es ist alles andere als simpel meiner Meinung nach)

es sollte in etwa wie folgt funktionieren:

Ich gehe erst einmal davon aus, dass sich der Charakter in 8 Richtungen bewegen kann (es lässt sich also auch vereinfacht mit 4 Richtungen machen).

Die Grundlage des Pathfinding sollen Knotenpunkte sein, die man in direkter verbindung mit den 8 Richtungen erreichen kann (also entweder ist bei der Differenz der beiden Start- und Zielkoordinaten entweder der Y oder der X Wert 0 oder die Beträge der Differenzen der Y und X Werte sind gleich groß, kann man mir noch soweit folgen ?)

Wenn nun keine direkte Verbindung von Start- und Zielpunkt über die 8 Wege möglich sind, setzt man Knotenpunkte, die man direkt ansteuern kann über die 8 Richtungen und zwischen den Punkten darf natürlich kein Hindernis sein.
Man fängt an, den kürzesten Pfad mit nur einem Knotenpunkt zu finden.
Dazu versucht man einen Punkt zu finden, der mit den 8 Richtungen sowohl vom Startpunkt als auch vom Zielpunkt zu erreichen ist.
Wenn einem dies gelingt, versucht man diese Strecke noch zu optimieren. Man erhält nun 2 Strecken, einmal die Strecke Startpunkt (SP) zum Knotenpunkt (KP) und die Strecke KP zum Zielpunkt (ZP).
Nun untersucht man, ob es zwischen den 2 Strecken eine direkte Verbindungen gibt, die wiederum mit den 8 Richtungen zu erreichen ist. (Bei dem 4 Wege Pathfinding würde die Optimieren glaube ich mal wegfallen, da dies dort nicht möglich ist).
Wenn man nun keinen Punkt für den KP gefunden hat, versuchst man es mit 2 KP.
Diese Versucht man nun parallel zu verschieben, sodass der erste KP einen direkte Verbindung zum SP und zum zweiten KP besitzt und sodass der zweite KP eine Verbindung zum ersten KP und zum ZP hat.
Hat man das geschafft, erfolgt wieder Die Optimierung wie oben beschrieben, nur, dass man 3 Strecken untersuchen muss.

Soweit würde das ganze auch schon für ein simples Pathfinding reichen.

Die Vorteile würde ich hier nun darin sehen, dass die Rechenzeit nun sehr gering zu sein scheint, auch bei längeren Wegen und das es meine Meinung nach relativ leicht zu programmieren ist.

Natürlich hat das ganze auch Nachteile.
Das System versagt zum Beispiel bei sehr komplizierten Mapping. Hierzu müssten dann 3, 4 oder mehr Knotenpunkte benutzt werden.

Ich bitte euch um Kritik und auch Verbesserungsvorschläge !
Es währe auch super, wenn mir jemand sagen könnte, wie man die 3 (oder sogar 4) Knotenpunkte setzen könnte, sodass dieses Pathfinding auch noch verbessert wird und vielseitiger einsetzbar ist.

Vielen Dank erstmal fürs durchlesen !

Ich hatte auch schonmal solch eine überlegung gemacht, es dann aber mangels Lust dann doch nicht umgesetzt^^

Ich würde allerdings behaupten, dass es in jeder Hinsicht einfacher ist, erstmal nur 4 Wege zu nehmen. Anstatt dann immer nur in eine Richtung zu schauen sollte man da lieber immer 2er-Wege nehmen, also erst schauen, ob man so zum Ziel kommt, dass man erst den kompletten X-Weg und dann den Y-Weg nimmt oder umgekehrt, das gleiche müsste man dann sowieso auch im 8-Wege-System machen bloß dass es da halt mehr Abfragen sind (man verdoppelt zwar die Möglichkeiten einer direkten Verbindung ungefähr, aber es bleibt trotzdem noch ne Menge Raum übrig, den man nur über 2 Bewegungen erreicht erreicht).

Bei den Knotenpunkten gibt es dann natürlich auch wieder verschiedene Möglichkeiten. Entweder setzt man sie halt direkt in die Hindernisse hinein oder man baut sie halt immer nur an die Ecken. Ich würde davon abraten, die sachen direkt in die hindernisse zu bauen, da man dafür bei verwinkelten Räumen immer etwas mehr oder es sieht halt dümmer aus^^



Nehmen wir mal an, man steht an S und will nach Z und hat nur die beiden Punkte A und B. Der einfachste Weg wäre es, einfach mit 3 Bewegungen um die Wand herum zu gehen. Wenn man jetzt allerdings sagt, dass immer nur 2er Bewegungen erlaubt sind, dann muss die Figur erst runter nach B laufen um dann mit 2 weiteren Bewegungen wieder nach oben zu laufen. es Funktioniert zwar, sieht aber extrem doof aus^^ Um den langen Weg zu umgehen sollte am besten noch C dazu geschaltet werden. Anstatt jetzt zwei mal komplett durch den Raum zu laufen geht er halt direkt herum, wie man es erwarten würde. Man kann jetzt zwar noch A da lassen, weil es generell den oberen Bereich noch so abdeckt, dass es die optimalen Wege findet, allerdings kann man diesen auch auf D setzen um einen einheitlicheren Stil zu haben (vorallem Codetechnisch müsste man beim Punkt A die Codepassagen rausnehmen, welche zuerst den Abstand auf der X-Ebene überprüfen, weil man so oder so nicht zur seite gehen kann^^)

Sowas muss man dann allerdings halt immer auf die jeweilige Situation zuschneiden und Punkte finden, die Möglichst effizient abgelaufen werden können und Ecken eignen sich dazu immer besser als Wände (vorallem, weil man immer um mehrere Ecken umherschauen kann)

Um den kürzesten Weg zu finden sollte man dann halt auch immer alle Punktekombinationen abgehen und überprüfen, welcher der kürzeste ist

Das war damals jedenfalls meine Idee^^ Wenn man es noch etwas schneller haben will, dann sollte man natürlich auch immer die Abfragen zwischen zwei knotenpunkten rausnehmen, die einander sowieso nicht erreichen können und das ganze System funktioniert natürlich auch nur dann, wenn sich keine beweglichen Objekte in den Weg stellen, falls es also für ein Taktik-RPG genutzt werden soll, indem viele einheiten herumstehen, durch die man nicht hindurch gehen kann, dann sollte man schon ein richtiges Pathfinding-System nehmen, welches alle Möglichkeiten abgehen kann, da nicht jede einheiten Knotenpunkte mit sich rumtragen kann^^

Eine Garantie, dass das System so funktioniert oder stabil und schnell läuft gibt es von mir aber nicht, da es bisher nur auf einem Blatt gebaut und getestet wurde^^

Deine Überlegungen sind an sich auch nicht schlecht, nur das Problem für mich dabei ist, dass ich dieses Pathfinding eben genau für ein Spiel machen will, wo es bewegliche Objekte gibt (Gegner etc.) ^^
Es soll halt für ein normales Game gemacht sein, wo auch mal nen NPC in die Quere kommen kann und das System trotzdem nicht versagt.

Aber zwischen deinen und meinen Knotenpunkten gibt es nen kleinen Unterschied.
Du würdest sie ja direkt auf der Map festlegen schon bevor das Spiel startet, bei mir sollten die eher je nach Situation erstellt werden, je nachdem, wo sich der Held Halt gerade befinden.
und wenn man dann auch normal Mappen würde und nicht nur Wände dort hinbaut sondern auch mal nen par Bäume, dann steigst die Anzahl der Knotenpunkte mal schnell ganz hoch

Aber trotzdem danke für den Vorschlag, das hat mich direkt mal auf eine neue Idee gebracht.

Das Problem mit beweglichen Objekten ist halt, dass man nach jeder abgeschlossenen Bewegung immer die neuen Knotenpunkte berechnen muss und vorallem muss man dabei auch berücksichtigen, wo jemand steht und wann jeder Punkt abgegangen werden kann, was letztendlich in großem Rechenaufwand endet. Und wenn man sie immer auf die Heldposition festlegt wird man auch schnell merken, dass man sie Punkte an die immer gleichen Positionen packt (halt da, wo sie am sinnvollsten für jede Position sind^^)

Man könnte natürlich auch die Idee mit den Knotenpunkten von oben beibehalten, die Wege dahin dann allerdings über ein richtiges Pathfinding zu nehmen. Allerdings sollte dann in den einzelnen Bereichen immer ein richtiges Pathfindingscript benutzt werden. Mit Variablen Knotenpunkten wird es halt einfach nur komplizierter, weil oft gerechnet wird für Sachen, die man eventuell gar nicht braucht (zB wenn ein Char 2 Schritte nach rechts bewegt wird muss trotzdem nochmal jeder Knotenpunkt darauf kontrolliert werden, ob es zu viele sind oder ob irgendwo einer fehlt)

Und bei solchen Scripten ist es sowieso immer schwieriger, mehr wege zu machen, weil dadurch auch ein vielfaches an Speicher bzw Abfragen benötigt werden für die neuen Bewegungsmöglichkeiten (was in Event-Scripten gleichzeitig viel Copy&Past&Edit bedeutet^^)

und falls die Einheiten nur einen geringen Bewegungsradius haben, dann würde ich generell auf Knotenpunkte verzichten und die Wege direkt mit einem einfachen Pathfinding-Script berechnen lassen, da es erst ab größeren Entfernungen etwas aufwändiger wird^^