Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Game Development
  2. Programming
Gamedevelopment

Die Datenstruktur der Aktionsliste: Geeignet für Benutzeroberfläche, KI, Animationen und mehr

by
Difficulty:IntermediateLength:LongLanguages:

German (Deutsch) translation by Valentina (you can also view the original English article)

Die Aktionsliste ist eine einfache Datenstruktur, die für viele verschiedene Aufgaben in einer Spiel-Engine nützlich ist. Man könnte argumentieren, dass die Aktionsliste immer anstelle einer Form von Zustandsmaschine verwendet werden sollte.

Die gebräuchlichste (und einfachste) Form der Verhaltensorganisation ist eine endliche Zustandsmaschine. Normalerweise werden sie mit Switches oder Arrays in C oder C++ oder mit Anweisungen von if und else in anderen Sprachen implementiert. Zustandsautomaten sind starr und unflexibel.  Die Aktionsliste ist ein stärkeres Organisationsschema, da sie auf klare Weise modelliert, wie Dinge normalerweise in der Realität passieren. Aus diesem Grund ist die Aktionsliste intuitiver und flexibler als eine Zustandsmaschine.


Schneller Überblick

Die Aktionsliste ist nur ein Organisationsschema für das Konzept einer zeitgesteuerten Aktion. Aktionen werden in einer FIFO-Reihenfolge gespeichert.  Dies bedeutet, dass beim Einfügen einer Aktion in eine Aktionsliste die zuletzt in die Vorderseite eingefügte Aktion die erste ist, die entfernt wird. Die Aktionsliste folgt nicht explizit dem FIFO-Format, bleibt aber im Kern das gleiche.

Bei jeder Spielschleife wird die Aktionsliste aktualisiert und jede Aktion in der Liste wird der Reihe nach aktualisiert. Sobald eine Aktion abgeschlossen ist, wird sie aus der Liste entfernt.

Eine Aktion ist eine aufzurufende Funktion, die irgendwie irgendwie funktioniert. Hier sind ein paar verschiedene Arten von Bereichen und die Arbeit, die Aktionen in diesen Bereichen ausführen können:

  • Benutzeroberfläche: Anzeigen von kurzen Sequenzen wie "Erfolge", Abspielen von Animationen, Durchblättern von Fenstern, Anzeigen von dynamischem Inhalt: Bewegen; drehen; Flip; verblassen; allgemeines Tweening.
  • Künstliche Intelligenz: Warteschlangenverhalten: Bewegen; warten; patrouillieren; fliehen; Attacke.
  • Ebene Logik oder Verhalten: Plattformen verschieben; Hindernisbewegungen; Ebenen verschieben.
  • Animation/Audio: Abspielen; halt.

Geringfügige Dinge wie Pfadfindung oder Flockung werden mit einer Aktionsliste nicht effektiv dargestellt. Kampf und andere hochspezialisierte, spielspezifische Gameplay-Bereiche sind auch Dinge, die man wahrscheinlich nicht über eine Aktionsliste implementieren sollte.


Aktionsliste-Klasse

Hier ist ein kurzer Blick auf die Datenstruktur der Aktionsliste. Bitte beachten Sie, dass genauere Details später im Artikel folgen werden.

Es ist wichtig anzumerken, dass die tatsächliche Speicherung jeder Aktion keine tatsächliche verknüpfte Liste sein muss - etwas wie der C++ std::vector würde perfekt funktionieren. Ich persönlich bevorzuge es, alle Aktionen innerhalb eines Allokators und Linklisten zusammen mit intrusiv verknüpften Listen zusammenzufassen.  Normalerweise werden Aktionslisten in weniger leistungsabhängigen Bereichen verwendet, sodass eine aufwändige datenorientierte Optimierung beim Entwickeln einer Aktionslisten-Datenstruktur wahrscheinlich nicht erforderlich ist.


Die Aktion

Die Crux dieses ganzen Shebangs sind die Handlungen selbst. Jede Aktion sollte vollständig in sich abgeschlossen sein, so dass die Aktionsliste selbst nichts über die internen Elemente der Aktion weiß.  Das macht die Aktionsliste zu einem äußerst flexiblen Werkzeug. Eine Aktionsliste kümmert sich nicht darum, ob sie Benutzeroberflächenaktionen ausführt oder die Bewegungen eines modellierten 3D-Charakters verwaltet.

Eine gute Möglichkeit zum Implementieren von Aktionen ist eine einzige abstrakte Schnittstelle. Einige spezifische Funktionen werden vom Aktionsobjekt für die Aktionsliste verfügbar gemacht. Hier ein Beispiel, wie eine Basisaktion aussehen kann:

Die Funktionen OnStart() und OnEnd() sind hier wesentlich. Diese beiden Funktionen müssen ausgeführt werden, wenn eine Aktion in eine Liste eingefügt wird bzw. die Aktion beendet wird. Diese Funktionen ermöglichen, dass Aktionen vollständig in sich abgeschlossen sind.

Blockieren und Nicht-Blockieren der Aktionen

Eine wichtige Erweiterung der Aktionsliste ist die Möglichkeit, Aktionen als blockierend oder nicht blockierend zu kennzeichnen. Der Unterschied ist einfach: Eine Blockierungsaktion beendet die Aktualisierungsroutine der Aktionsliste und es werden keine weiteren Aktionen aktualisiert. 

Eine nicht blockierende Aktion ermöglicht die Aktualisierung der nachfolgenden Aktion.Ein einzelner boolescher Wert kann verwendet werden, um zu bestimmen, ob eine Aktion blockiert oder nicht blockiert. Hier ist ein Psuedocode, der die update-Routine einer Aktionsliste demonstriert:

Ein gutes Beispiel für die Verwendung von nicht blockierenden Aktionen wäre, dass einige Verhalten gleichzeitig ausgeführt werden. Wenn wir beispielsweise eine Reihe von Aktionen zum Laufen und Winken von Händen haben, sollte der Charakter, der diese Aktionen ausführt, in der Lage sein, beide gleichzeitig auszuführen.  Wenn ein Feind vor der Figur flieht, wäre es sehr dumm, wenn er laufen müsste, dann stoppen und mit den Händen winken, dann weiter rennen.

Wie sich herausstellt, passt das Konzept der Blockierung und Nichtblockierung von Aktionen intuitiv zu den meisten einfachen Verhaltensweisen, die in einem Spiel implementiert werden müssen.


Fallbeispiel

Wir zeigen ein Beispiel dafür, wie eine Aktionsliste in einem realen Szenario aussehen würde. Das hilft, Intuition zu entwickeln, wie eine Aktionsliste verwendet wird und warum Aktionslisten nützlich sind.

Problem

Ein Gegner in einem einfachen Top-Down-2D-Spiel muss hin und her patrouillieren. Immer wenn sich dieser Feind in Reichweite des Spielers befindet, muss er eine Bombe auf den Spieler werfen und seine Patrouille anhalten.  Es sollte eine kleine Abklingzeit geben, nachdem eine Bombe geworfen wurde, wo der Feind völlig still steht.  Wenn sich der Spieler noch in Reichweite befindet, sollte eine andere Bombe gefolgt von einer Abklingzeit geworfen werden. Wenn sich der Spieler außerhalb der Reichweite befindet, sollte die Patrouille genau dort weitermachen, wo sie aufgehört hat.

Jede Bombe sollte durch die 2D-Welt schweben und sich an die Gesetze der auf Fliese basierenden Physik im Spiel halten.  Die Bombe wartet nur, bis der Zündzeitpunkt abgelaufen ist und springt dann hoch. Die Explosion sollte aus einer Animation, einem Sound und einer Entfernung der Kollisionsbox der Bombe und des visuellen Sprites bestehen.

Das Erstellen einer Zustandsmaschine für dieses Verhalten ist zwar möglich und nicht zu schwer, erfordert jedoch einige Zeit. Übergänge von jedem Status müssen von Hand codiert werden. Wenn Sie die vorherigen Status speichern, um später fortfahren zu können, kann dies zu Kopfschmerzen führen.

Aktionsliste-Lösung

Glücklicherweise ist das ein ideales Problem, das mit Aktionslisten gelöst werden kann. Stellen wir uns zunächst eine leere Aktionsliste vor. Diese leere Aktionsliste wird eine Liste von "to do"-Aufgaben enthalten, die der Feind ausführen muss. Eine leere Liste zeigt einen inaktiven Feind an. 

Es ist wichtig, darüber nachzudenken, wie das gewünschte Verhalten in kleine Nuggets unterteilt werden kann. Das erste, was Sie tun müssen, ist das Verhalten der Patrouillen.  Nehmen wir an, der Feind sollte eine Distanz entfernt patrouillieren, dann rechts die gleiche Distanz und dann wiederholen.

So könnte die patrol left-Aktion aussehen:

PatrolRight sieht fast identisch aus, die Richtungen sind umgedreht. Wenn eine dieser Aktionen in die Aktionsliste des Feindes aufgenommen wird, patrouilliert der Feind tatsächlich links und rechts unendlich.

Hier ist ein kurzes Diagramm, das den Ablauf einer Aktionsliste mit vier Momentaufnahmen des Status der aktuellen Aktionsliste für das Patrouillieren zeigt:

ActionListPatrol2

Der nächste Zusatz sollte die Erkennung sein, wenn sich der Spieler in der Nähe befindet. Das kann mit einer nicht blockierenden Aktion durchgeführt werden, die niemals abgeschlossen wird.  Diese Aktion überprüft, ob sich der Spieler in der Nähe des Feindes befindet. Wenn dies der Fall ist, wird eine neue Aktion namens ThrowBomb direkt vor sich in der Aktionsliste erstellt. Es wird auch eine Delay-Aktion direkt nach der ThrowBomb-Aktion platziert.

Die nicht blockierende Aktion wird dort gespeichert und aktualisiert. Die Aktionsliste aktualisiert jedoch alle nachfolgenden Aktionen.  Blockierungsaktionen (z. B. Patrol) werden aktualisiert, und die Aktionsliste beendet alle nachfolgenden Aktionen. Denken Sie daran, dass diese Aktion nur dazu dient, um zu sehen, ob sich der Spieler in Reichweite befindet und die Aktionsliste niemals verlässt!

So könnte diese Aktion aussehen:

Die ThrowBomb-Aktion ist eine Blockierungsaktion, die eine Bombe auf den Spieler wirft. Es sollte wahrscheinlich eine ThrowBombAnimation folgen, die blockiert und eine feindliche Animation abspielt, aber ich habe das der Prägnanz wegen ausgelassen.  Die Pause hinter der Bombe wird für die Animation stattfinden und warten, bevor sie fertig ist.

Schauen wir uns ein Diagramm an, wie diese Aktionsliste beim Aktualisieren aussehen könnte:

Blue circles are blocking actions. White circles are non-blocking actions.
Blaue Kreise blockieren Aktionen. Weiße Kreise sind nicht blockierende Aktionen.

Die Bombe selbst sollte ein völlig neues Spielobjekt sein und drei oder mehr Aktionen in ihrer eigenen Aktionsliste haben. Die erste Aktion ist eine blockierende Pause-Aktion.  Danach sollte eine Aktion zum Abspielen einer Animation für eine Explosion erfolgen. Das Bomben-Sprite selbst muss zusammen mit der Kollisionsbox entfernt werden. Zum Schluss sollte ein Explosionseffekt abgespielt werden.

Insgesamt sollten etwa sechs bis zehn verschiedene Arten von Aktionen vorhanden sein, die alle zusammen verwendet werden, um das erforderliche Verhalten zu konstruieren. Das Beste an diesen Aktionen ist, dass sie im Verhalten jedes Feindtyps wiederverwendet werden können, nicht nur in dem hier gezeigten.


Mehr von Aktionen

Lanes-Aktion

Jede Aktionsliste in ihrem aktuellen Formular verfügt über eine einzige lane, in der Aktionen vorhanden sein können. Eine lane ist eine Folge von zu aktualisierenden Aktionen. Eine lane kann entweder gesperrt oder nicht gesperrt sein.

Die perfekte Implementierung von Bahnen verwendet Bitmasken. (Informationen zu Bitmask-Details finden Sie unter Eine kurze Bitmask-Anleitung für Programmierer und auf der Wikipedia-Seite.) Mit einer 32-Bit-Ganzzahl können 32 verschiedene lanes erstellt werden.

Eine Aktion sollte eine ganze Zahl haben, um alle verschiedenen Spuren darzustellen, auf denen sie sich befindet. Dadurch können 32 verschiedene Fahrspuren verschiedene Kategorien von Aktionen darstellen.  Jede Spur kann während der Aktualisierungsroutine der Liste selbst entweder gesperrt oder nicht gesperrt werden.

Hier ist ein schnelles Beispiel für die Update-Methode einer Aktionsliste mit Bitmasken-Lanes:

Dies bietet ein erhöhtes Maß an Flexibilität, da nun eine Aktionsliste 32 verschiedene Arten von Aktionen ausführen kann, wobei zuvor 32 verschiedene Aktionslisten erforderlich wären, um dasselbe zu erreichen.

Delay-Aktion

Eine Aktion, die nichts anderes tut, als alle Aktionen um einen bestimmten Zeitraum zu verzögern, ist sehr nützlich. Die Idee ist, alle nachfolgenden Aktionen zu verzögern, bis ein Timer abgelaufen ist.

Die Implementierung der Verzögerungsaktion ist sehr einfach:

Synchronisierung-Aktion 

Eine nützliche Aktion ist eine, die blockiert, bis sie die erste Aktion in der Liste ist. Dies ist nützlich, wenn einige andere nicht blockierende Aktionen ausgeführt werden, Sie jedoch nicht sicher sind, in welcher Reihenfolge sie abgeschlossen werden sollen.  Durch die Synchronisierung-Aktion wird sichergestellt, dass keine vorherigen nicht blockierenden Aktionen ausgeführt werden, bevor Sie fortfahren.

Die Implementierung der synch-Aktion ist so einfach wie man sich vorstellen kann:


Erweiterte Funktionen

Die bisher beschriebene Aktionsliste ist ein ziemlich mächtiges Werkzeug. Es gibt jedoch ein paar Ergänzungen, die gemacht werden können, um die Aktionsliste wirklich zum Strahlen zu bringen.  Diese sind ein wenig fortgeschritten, und ich empfehle nicht, sie zu implementieren, es sei denn, Sie können das ohne großen Aufwand tun.

Messaging

Die Möglichkeit, eine Nachricht direkt an eine Aktion zu senden oder eine Aktion zum Senden von Nachrichten an andere Aktionen und Spielobjekte zuzulassen, ist äußerst nützlich.  Dadurch können Aktionen außerordentlich flexibel sein. Oft kann eine Aktionsliste dieser Qualität als "arme Mannskriptsprache" wirken.

Einige sehr nützliche Nachrichten zum Posten einer Aktion können Folgendes umfassen: gestartet; endete; pausierte; wieder aufgenommen abgeschlossen; abgebrochen; verstopft.  Die blockierte ist sehr interessant - wenn eine neue Aktion in eine Liste aufgenommen wird, kann sie andere Aktionen blockieren. Diese anderen Aktionen möchten darüber informiert werden und möglicherweise andere Abonnenten über das Ereignis informieren.

Die Implementierungsdetails von Messaging sind sprachspezifisch und eher nicht trivial. Daher werden die Details der Implementierung hier nicht besprochen, da Messaging nicht im Mittelpunkt dieses Artikels steht.

Hierarchische Aktionen

Es gibt verschiedene Möglichkeiten, Hierarchien von Aktionen darzustellen. Eine Möglichkeit ist, zuzulassen, dass eine Aktionsliste selbst eine Aktion in einer anderen Aktionsliste ist.  Das ermöglicht die Erstellung von Aktionslisten, um große Gruppen von Aktionen unter einer einzigen Kennung zusammenzufassen. Dies erhöht die Benutzerfreundlichkeit und macht es einfacher, komplexere Aktionslisten zu entwickeln und zu debuggen.

Eine andere Methode besteht darin, Aktionen zu haben, deren einziger Zweck darin besteht, andere Aktionen unmittelbar vor sich selbst in der Eigentümeraktionsliste zu erzeugen. Ich selbst ziehe diese Methode der vorgenannten vor, obwohl sie etwas schwieriger zu implementieren ist.


Schlussfolgerung

Das Konzept einer Aktionsliste und ihre Implementierung wurden ausführlich erörtert, um eine Alternative zu starren Ad-hoc-Zustandsmaschinen zu bieten.  Die Aktionsliste bietet eine einfache und flexible Möglichkeit, schnell ein breites Spektrum dynamischer Verhaltensweisen zu entwickeln. Die Aktionsliste ist eine ideale Datenstruktur für die Spielprogrammierung im Allgemeinen.

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.