Motion planning (Bewegungsplanung)

Bewegungsplanung hilft dir bestimmte Instanzen von einer gegebenen Stelle zu einer anderen Stelle zu bewegen, wobei Kollisionen mit bestimmten anderen vermieden werden (Wände zum Beispiel). Bewegungsplanung ist ein schwieriges Problem. Es ist unmöglich allgemeine Funktionen bereitzustellen, die in allen Situationen zufriedenstellend arbeiten. Auch sind die Berechnungen für kollisionsfreie Bewegungen recht zeitaufwändig. Deshalb sei sorgsam wie und wann Du es einsetzt. Bitte behalte diese Anmerkungen immer im Hinterkopf, wenn du irgendeine folgender Funktionen verwendest.

Verschiedene Arten der Bewegungsplanung werden vom Game Maker bereitgestellt. Die einfachste Art lässt eine Instanz einen Schritt in Richtung Zielposition machen, direkt und gradlinig, wenn möglich - aber auch in anderer Richtung, falls erforderlich. Diese Funktionen sollten im "step event" einer Instanz verwendet werden. Sie korrespondieren mit den Bewegungsplanungsaktionen ("motion planning actions"), die auch verfügbar sind:

mp_linear_step(x, y, stepsize, checkall) Diese Funktion lässt die Instanz einen Schritt in Richtung der angegebene Stelle (x,y) ausführen. Die Schrittweite des Schrittes wird durch "stepsize" angezeigt. Wenn die Instanz sich schon an der Stelle befindet, wird sie sich nicht weiter bewegen. Wenn "checkall" wahr ("true") ist stoppt die Instanz, sobald sie auf eine Instanz irgendeinenes Objektes trifft. Wenn es nicht wahr ("false") ist, stoppt sie nur, wenn eine "solid" Instanz getroffen wird. Beachte, dass diese Funktion nicht versucht Umwege zu machen, wenn sie auf Hindernisse stößt. Sie schlägt einfach fehl in diesem Fall. Die Funktion gibt wieder, ob die Zielposition erreicht wurde.
mp_linear_step_object(x, y, stepsize, obj) Dasselbe wie die obige Funktion, diesmal wird aber nur obj als Hindernis gesehen. obj kann ein Objekt oder eine Instanz sein.
mp_potential_step(x, y, stepsize, checkall) Wie voranstehende Funktion, lässt auch diese Funktion die Instanz einen Schritt auf eine bestimmte Position hin machen. Aber diesmal versucht sie Hindernisse zu umgehen. Wenn die Instanz mit "solid" Instanz (oder irgendeiner, wenn "checkall" "true (wahr) ist) zusammen zu stoßen droht, wird sie die Richtung ändern, um die Instanz zu meiden und es umgehen. Diese Näherung unterliegt keiner garantiert funktionierenden Arbeitsweise aber in den meisten einfachen Fällen bewegt es die Instanz effektiv auf die Zielposition. Die Funktion gibt an, ob das Ziel erreicht wurde.
mp_potential_step_object(x, y, stepsize, obj) Dasselbe wie die obige Funktion, diesmal wird aber nur obj als Hindernis gesehen. obj kann ein Objekt oder eine Instanz sein.
mp_potential_settings(maxrot, rotstep, ahead, onspot) Die vorherige Funktion verrichtet ihre Arbeit, indem sie eine Anzahl von Parametern verwendet, welche mit dieser Funktion verändert werden können. Prinzipiell funktioniert diese Methode wie folgt. Zuerst wird versucht, das Ziel auf direktem Weg zu erreichen. Es wird eine Anzahl von Schritten vorausgeschaut, was mit dem Parameter "ahead" (voreingestellt auf 3) festgelegt werden kann. Vermindern dieses Wertes führt dazu, dass die Instanz die Richtungsänderung später beginnt. Erhöhen bedeutet eine frühere Richtungsänderung. Falls diese Prüfung zu einer Kollision führt, schaut sie nach anderen Richtungen, die mehr links oder rechts, von der bestmöglichen Richtung liegen. Dies macht sie in Schritten der Größe "rotstep" (voreingestellt 10). Vermindern dieses Wertes ermöglicht der Instanz mehr Bewegungsmöglichkeit, ist aber langsamer. Der Parameter "maxrot" ist ein wenig schwierig zu erklären. Die Instanz besitzt eine aktuelle Bewegungsrichtung ("direction"). maxrot (voreingestellt 30) gibt die Abweichung zur aktuellen Bewegungsrichtung an, die maximal in einem Schritt geändert werden darf. Auch wenn sie sich beispielsweise direkt zum Ziel bewegen könnte, macht sie es nur so, dass die maximale Abweichung der Bewegungsrichtung nicht überschritten wird. Falls Du "maxrot" hoch ansetzt, kann die Instanz die Bewegungsrichtung mehr ändern in einem Schritt. Dies macht es einfacher einen kurzen Weg zu finden aber der Weg wird hässlicher sein. Falls Du aber den Wert kleiner machst, wird der Weg geschmeidiger aber möglicherweise mit längeren Umwegen (manchmal wird das Ziel auch garnicht erreicht). Falls kein Schritt gemacht werden kann, hängt das Verhalten vom Wert des Parameters "onspot" ab. Wenn "onspot" wahr (true) ist (der voreingestellte Wert), wird die Instanz auf dem Fleck um den Betrag, der durch "maxrot" vorgegeben ist, rotieren. Falls der Wert unwahr (false) ist, findet keine Bewegung statt. Den Wert auf "false zu setzen ist beispielsweise nützlich für Autos, setzt aber die Wegfindungschancen herab.

Beachte bitte, dass die Potenzial_Näherung nur lokale Informationen verwendet. Somit wird nur eine Lösung gefunden, wenn diese lokalen Informationen hinreichend sind, die richtige Richtung der Bewegung zu bestimmen. Es wird beispielsweise scheitern, einen Weg aus einem Labyrinth zu finden (fast immer).

Die zweite Art von Funktionen berechnet einen kollisionsfreien Weg für die Instanz. Sobald der Weg kalkuliert worden ist, kannst Du ihn der Instanz zuweisen, damit sie aufs Ziel zubewegt wird. Die Berechnung des Pfads nimmt einige Zeit in Anspruch aber dafür wird danach die Abschreitung des Pfads zügig sein. Dies gilt selbstverständlich nur, wenn sich die Situation nicht in der Zwischenzeit verändert. Zum Beispiel, wenn Hindernisse sich verändern, musst du den Weg wahrscheinlich neu berechnen. Beachte auch hier, dass diese Funktionen fehlschlagen können. Diese Funktionen sind nur in der registrierten Funktion vom Game Maker verfügbar.

The Die ersten beiden Funktionen verwenden lineare-Bewegung- und Potential-Feld-Näherung, die auch für die "step"-Funktionen verwendet werden.

mp_linear_path(path, xg, yg, stepsize, checkall) Diese Funktion berechnet einen geradlinigen Weg für die Instanz von der aktuellen Position zur Position (xg,yg), wobei die angegebene "stepsize" verwendet wird. Sie gebraucht Schritte (steps) wie in der Funktion mp_linear_step(). Der angegebene Pfad (path) muss schon existieren und wird durch einen neuen Pfad überschrieben. (In einem späteren Kapitel wird das Erstellen und Vernichten von Pfaden erläutert.) Die Funktion gibt an, ob ein Pfad gefunden wurde. Die Funktion stoppt und berichtet das Fehlschlagen, wenn kein direkter Pfad zwischen Start und Ziel existiert. Wenn sie fehlschlägt wird trotzdem ein Pfad definiert, der bis zu der Stelle verläuft, an der die Instanz blockiert wurde.
mp_linear_path_object(path, xg, yg, stepsize, obj) Dasselbe wie die obige Funktion, diesmal wird aber nur obj als Hindernis gesehen. obj kann ein Objekt oder eine Instanz sein.
mp_potential_path(path, xg, yg, stepsize, checkall, factor)  Diese Funktion berechnet einen Pfad für die Instanz von der aktuellen Position und mit der momentanen Orientierung zur Position (xg,yg), wobei die angegebene Schrittweite (stepsize) verwendet wird und versucht wird Kollisionen mit Hindernissen zu vermeiden. Sie verwendet Potential-Feld-Schritte, wie in der Funktion mp_potential_step() und zusätzlich die Parameter die mit der Funktion mp_potential_settings() eingestellt werden können. Der angegebenen Pfad muss schon vorhanden sein und wird durch einen neuen Pfad überschrieben. (In einem späteren Kapitel wird das Erstellen und Vernichten von Pfaden erläutert.) Die Funktion gibt an, ob ein Pfad gefunden wurde. Um zu vermeiden, dass die Funktion endlos weiterrechnet, musst Du einen Längenfaktor (length factor) größer 1 bereitstellen. Die Funktion stoppt und berichtet das Fehlschlagen, wenn sie keinen kürzeren Pfad, zwischen Start und Ziel, kleiner als dieser faktorabhängigen Distanz findet. Ein Faktor von 4 ist normalerweise ausreichend aber wenn Du lange Umwege erwartest, kannst Du ihn möglicherweise verlängern. Wenn sie fehlschlägt, wird trotzdem ein Pfad erstellt, der in Richtung des Zielpunktes weist, ihn aber nicht erreicht. mp_potential_path_object(path, xg, yg, stepsize, factor, obj) Dasselbe wie die obige Funktion, diesmal wird aber nur obj als Hindernis gesehen. obj kann ein Objekt oder eine Instanz sein.

Die anderen Funktionen verwenden einen wesentlich komplexeren Mechanismus, wobei eine Gitter-basierte Näherung genutzt wird (manchmal A* Algorithmus genannt). Es ist erfolgreicher in der Wegfindung (obwohl es auch manchmal fehlschlagen kann) und findet kürzere Pfade aber es erfordert mehr Aufwand von deiner Seite. Die Grundlegende Idee ist folgende. Zuerst legen wir ein Gitter über den (relevanten Teil des) Raum. Du kannst wählen zwischen einem feinmaschigen Gitter (was langsamer sein wird) oder einem groben Gitter. Als nächstes bestimmen wir für alle relevanten Objekte die Gitterzellen, die sie überlappen (sowohl "bounding boxes" alsauch präzise Prüfung können verwendet werden) und markieren diese Zellen als verboten. Somit wird eine Zelle als verboten markiert, sogar wenn sie nur teilweise von einem Hindernis überdeckt wird. Schließlich spezifizieren wir eine Start- und eine Zielposition (welche innerhalb der freien Zellen liegen müssen) und die Funktion berechnet den kürzesten Pfad (eigentlich dicht am kürzesten) zwischen diesen. Der Pfad wird durch die Zentren der freien Zellen verlaufen. Wenn also die Zellen groß genug sind, so dass die im Zentrum platzierte Instanz vollständig innerhalb liegt, wird es erfolgreich sein. Diesen Pfad kannst du nun einer Instanz übergeben, damit sie ihm folgt. Die Gitter-basierte Näherung ist sehr mächtig (und wird in vielen professionellen Spielen angewandt) aber es erfordert sorgsames Bedenken von dir. Du musst bestimmen, welche Gebiete und Zellgrößen ausreichend sind, um das Spiel zu lösen. Auch musst du festlegen, welche Objekte gemieden werden müssen und ob präzise Kollisionsprüfung wichtig ist. All diese Parameter beeinflussen stark die Effizienz dieser Näherung.

Insbesondere die Größe der Zellen ist entscheidend. Erinnere dich daran, dass die Zellen groß genug sein müssen, um das sich bewegende Objekt, was mit seinem Bezugspunkt (origin) im Zentrum der Zelle liegt, ganz zu umfassen. (Sei sorgsam mit der Position des Bezugspunkts des Objektes. Realisiere auch, dass du den Pfad verschieben kannst, wenn der Bezugspunkt des Objektes nicht in dessen Zentrum liegt!) Andererseits bestehen mehr mögliche Pfade, je kleiner die Zellen sind. Wenn du die Zellen zu groß machst, werden Öffnungen/Durchgänge zwischen den Hindernissen möglicherweise verschlossen, weil alle Zellen ein Objekt schneiden.

<>Die Funktionen für die Gitter-basierte Näherung sind folgende:

mp_grid_create(left, top, hcells, vcells, cellwidth, cellheight) Diese Funktion erstellt das Gitter. Sie gibt einen Index zurück, der bei allen anderen Aufrufen verwendet werden muss. Du kannst mehrfache Gitter-Strukturen zur selben Zeit erstellen und verwalten. "left" und "top" geben die Position der linken oberen Ecke des Gitters an. "hcells" und "vcells" geben die Anzahl der horizontalen und vertikalen Zellen an. Schließlich geben "cellwidth" und "cellheight" die Größe der Zellen an.
mp_grid_destroy(id) Zerstört das angegebene Gitter und gibt belegten Speicher frei. Vergiss nicht dies aufzurufen, sobald Du das Gitter nicht mehr benötigst.
mp_grid_clear_all(id) Markiert alle Zellen des Gitters als frei.
mp_grid_clear_cell(id, h, v) Markiert die angegebene Zelle . Zelle 0,0 ist die linke obere Zelle als frei.
mp_grid_clear_rectangle(id, left, top, right, bottom) Markiert alle Zellen die das angegebene Rechteck schneiden (in Raumkoordinaten) als frei.
mp_grid_add_cell(id, h, v) Markiert die angegebene Zelle als verboten. Zelle 0,0 ist die linke obere Zelle.
mp_grid_add_rectangle(id, left, top, right, bottom) Markiert alle Zellen die das angegebene Rechteck schneiden als verboten.
mp_grid_add_instances(id, obj, prec) Markiert alle Zellen die eine Instanz des angegebenen Objektes schneiden als verboten. Du kannst auch eine individuelle Instanz verwenden, indem du "obj" die id der Instanz zuweist. Ferner kannst du das Schlüsselwort "all" angeben, um alle Instanzen aller Objekte anzugeben. "prec" gibt an, ob präzise Kollisionsprüfung verwendet werden soll (funktioniert nur, wenn präzise Prüfung für das von der Instanz verwendete sprite aktiviert ist).
mp_grid_path(id, path, xstart, ystart, xgoal, ygoal, allowdiag) Berechnet einen Pfad durch das Gitter. "path" muss einen existierenden Pfad angeben, der durch den Computerpfad ersetzt wird. "xstart" und "ystart" geben den Start und "xgoal" und "ygoal" das Ziel an. "allowdiag" gibt an, ob diagonale Bewegung zulässig ist statt nur horizontaler oder vertikaler. Die Funktion gibt wieder, ob sie erfolgreich einen Pfad gefunden hat. (Beachte, dass der Pfad unabhängig von der aktuellen Instanz ist; es ist ein Pfad durch das Gitter, nicht ein Pfad für eine besondere Instanz.)
mp_grid_draw(id) Diese Funktion zeichnet das Gitter, wobei freie Zellen grün eingefärbt sind und verbotene werden rot gezeichnet. Diese Funktion ist sehr langsam und steht nur zur Fehlersuche zur Verfügung.