Work in progress

The content of this page was not yet updated for Godot 4.2 and may be outdated. If you know how to improve this page or you can confirm that it's up to date, feel free to open a pull request.

Daten-Präferenzen

Haben Sie sich jemals gefragt, ob man Problem X mit Datenstruktur Y oder Z angehen sollte? Dieser Artikel behandelt eine Reihe von Themen, die mit diesen Dilemmas zusammenhängen.

Bemerkung

Dieser Artikel enthält Verweise auf "[irgendetwas]-Lauzeit" -Operationen. Diese Terminologie stammt aus der Algorithmusanalyse ' O-Notation.

Knapp zusammengefasst, beschreibt es das Worst-Case-Szenario der Laufzeit. In einfachen Worten:

"Mit zunehmender Größe eines Problems bedeutet dies für die Laufzeit des Algorithmus:"

  • Bei konstanter Laufzeit, O(1): "Sie erhöht sich nicht."

  • Bei logarithmischer Laufzeit, O(log n): "Sie nimmt langsam zu."

  • Bei linearer Laufzeit, O(n): "Sie erhöht sich mit derselben Rate."

  • Etc.

Stellen Sie sich vor, Sie müssten 3 Millionen Datenpunkte in einem einzigen Frame verarbeiten. Es wäre unmöglich, das Feature mit einem Algorithmus mit linearer Laufzeit zu erstellen, da die schiere Größe der Daten die Laufzeit weit über die zugewiesene Zeit hinaus erhöhen würde. Im Vergleich dazu könnte die Verwendung eines Algorithmus mit konstanter Laufzeit die Operation ohne Probleme handhaben.

Im Großen und Ganzen möchten Entwickler möglichst keine Operationen mit linearer Laufzeit durchführen. Wenn man jedoch den Maßstab einer Operation mit linearer Laufzeit klein hält und die Operation nicht oft ausführen muss, kann dies akzeptabel sein. Das Abwägen dieser Anforderungen und die Auswahl des richtigen Algorithmus / der richtigen Datenstruktur für die anstehende Aufgabe ist Teil dessen, was die Fähigkeiten von Programmierern wertvoll macht.

Array vs. Dictionary vs. Object

Godot speichert alle Variablen in der Skripting-API in der Klasse Variant. Variants können Variant-kompatible Datenstrukturen wie Array und Dictionary, sowie Object speichern.

Godot implementiert ein Array als Vector <Variant>. Die Engine speichert die Array-Inhalte in einem zusammenhängenden Speicherabschnitt, d.h. sie befinden sich in einer Reihe nebeneinander.

Bemerkung

Für diejenigen, die mit C++ nicht vertraut sind, ist ein Vector der Name des Array-Objekts in den traditionellen C++-Bibliotheken. Er ist ein "templatisierter" Typ, d.h. seine Datensätze können nur einen bestimmten Typ enthalten (durch spitze Klammern gekennzeichnet). So wäre zum Beispiel ein PackedStringArray so etwas wie ein Vector<String>.

Zusammenhängende Speicherbereiche beinhalten die folgende Ausführungsperformance:

  • Iterieren: Am schnellsten. Ideal für Schleifen.

    • Verfahren: Erhöht lediglich einen Zähler, um zum nächsten Eintrag zu gelangen.

  • Einfügen, Entfernen, Verschieben: Positionsabhängig. Im Allgemeinen langsam.

    • Verfahren: Beim Einfügen/ Entfernen/Verschieben von Inhalten müssen die angrenzenden Datensätze verschoben werden (um Platz zu schaffen / freigewordenen Platz zu füllen).

    • Schnelles Hinzufügen/Entfernen vom Ende.

    • Langsames Hinzufügen/Entfernen von einer beliebigen Position.

    • Sehr langsames Hinzufügen/Entfernen von vorne.

    • Wenn Sie viele Einfügungen/Entfernungen von vorne ausführen, dann ...

      1. invertieren Sie das Array.

      2. Führen Sie eine Schleife aus, die Ihre Array-Änderungen am Ende ausführt.

      3. Invertieren Sie das Array erneut.

      Dies erstellt nur 2 Kopien des Arrays (immer noch konstante Laufzeit, aber langsam), was besser ist als etwa die Hälfte des Arrays im Mittel N-mal zu kopieren (lineare Laufzeit).

  • Get, Set: Am schnellsten nach Position. Sie können z. B. den nullten, zweiten, zehnten Datensatz usw. anfordern, aber nicht angeben, welchen Eintrag Sie wünschen.

    • Verfahren: 1 Additionsoperation um von der Startposition des Arrays zum gewünschten Index zu gelangen.

  • Suchen: Am langsamsten. Identifiziert den Index/die Position eines Wertes.

    • Verfahren: Muss das Array durchlaufen und Werte vergleichen, bis eine Übereinstimmung gefunden wird.

      • Die Performance hängt auch davon ab, ob eine vollständige Suche erforderlich ist.

    • Bei sortierten Datentypen können Suchvorgänge eine logarithmische Laufzeit erreichen (relativ schnell). Laien werden sich damit jedoch nicht wohl fühlen. Wird umgesetzt indem das Array nach jeder Bearbeitung neu sortiert und ein spezieller Suchalgorithmus für sortierte Datentypen geschrieben wird.

Godot implementiert Dictionary als OrderedHashMap<Variant, Variant>. Die Engine speichert ein kleines Array (initialisiert mit 2^3, also 8 Datensätzen) von Key-Value-Paaren. Wenn man versucht, auf einen Value zuzugreifen, verwendet man einen Key. Das Dictionary hasht dann den Key, d. h. wandelt ihn in eine Zahl um. Der "Hash" wird verwendet, um den Index im Array zu berechnen. Als Array hat das OHM dann einen schnellen Zugriff auf die "Tabelle" der Keys, die den Values zugeordnet sind. Wenn die HashMap zu voll wird, vergrößert sie sich auf die nächste Zweierpotenz (also 16 Datensätze, dann 32 usw.) und baut die Struktur neu auf.

Hashes sollen die Wahrscheinlichkeit einer Key-Kollision verringern. In diesem Fall muss die Tabelle einen anderen Index für den Value neu berechnen, der die vorherige Position berücksichtigt. Insgesamt führt dies zu einem zeitlich konstanten Zugriff auf alle Datensätze auf Kosten des Speichers und eines kleinen Teils der operativen Effizienz.

  1. Jeden Key beliebig oft hashen.

    • Hash-Operationen sind zeitlich konstant, d.h. selbst wenn ein Algorithmus mehr als eine Hash-Berechnung durchführen muss, bleibt alles schnell, solange die Anzahl der Hash-Berechnungen nicht zu stark von der Dichte der Tabelle abhängt. Das führt zu...

  2. Organisation einer ständig wachsenden Tabelle.

    • HashMaps behalten absichtlich nicht genutzten Speicherlücken in der Tabelle bei, um Hash-Kollisionen zu reduzieren und die Zugriffsgeschwindigkeit niedrig zu halten. Deshalb vergrößert sie sich ständig quadratisch in Zweierpotenzen.

Wie man vielleicht erkennen kann, sind Dictionaries auf Aufgaben spezialisiert, für die sich Arrays nicht gut eignen. Nachfolgend sehen Sie eine Übersicht über ihre Details ihrer Vorgehensweisen:

  • Iterieren: Schnell.

    • Verfahren: Iteriert über den internen Hash-Vektor der Map. Gibt jeden Key zurück. Anschließend nutzen Anwender den Key, springen mit ihm zum gewünschten Value und geben ihn zurück.

  • Einfügen, Entfernen, Verschieben: Am schnellsten.

    • Verfahren: Hasht den übergebenen Key. Führt eine Additionsoperation aus, um den entsprechenden Value zu ermitteln (Array-Start + Offset). Verschieben besteht aus zwei Operationen (einmal einfügen, einmal entfernen). Die Map muss einige Wartungsarbeiten durchführen, um ihre Funktionalität aufrechtzuerhalten:

      • Aktualisieren der sortierten Liste von Einträgen.

      • Bestimmen, ob die Tabellendichte eine Erweiterung der Tabellengröße erfordert.

    • Das Dictionary merkt sich, in welcher Reihenfolge Benutzer ihre Keys eingegeben haben. Dies ermöglicht es, zuverlässige Iterationen auszuführen.

  • Get, Set: Am schnellsten. Dieselbe wie eine Suche nach Key.

    • Op: Dieselbe wie einfügen/entfernen/verschieben.

  • Suchen: Am langsamsten. Identifiziert den Key eines Values.

    • Verfahren: Muss Datensätze durchlaufen und den Value vergleichen, bis eine Übereinstimmung gefunden wird.

    • Beachten Sie, dass Godot dieses Feature nicht standardmäßig bereitstellt (da sie nicht für diese Aufgabe vorgesehen sind).

Godot implementiert Objekte als dumme, aber dynamische Container mit Dateninhalten. Objekte fragen Datenquellen ab, wenn ihnen Fragen gestellt werden. Um beispielsweise die Frage "Hast Du eine Eigenschaft namens 'position'?" zu beantworten, frage es möglicherweise sein Skript oder die ClassDB. Weitere Informationen darüber, was Objekte sind und wie sie funktionieren, finden Sie im Artikel Anwendung objektorientierter Prinzipien in Godot.

Das wichtige Detail hierbei ist die Komplexität der Aufgabe des Objekts. Jedes Mal, wenn es eine dieser Anfragen an mehrere Quellen ausführt, werden mehrere Iterationsschleifen und HashMap-Lookups durchlaufen. Darüber hinaus handelt es sich bei den Anfragen um Operationen mit linearer Laufzeit, die von der Größe der Vererbungshierarchie des Objekts abhängen. Wenn die Klasse, die das Objekt abfragt (seine aktuelle Klasse), nichts findet, wird die Anforderung zur nächsten Basisklasse verschoben, bis hin zur ursprünglichen Object-Klasse. Dies sind zwar für sich genommen schnelle Operationen, aber die Tatsache, dass es so viele Überprüfungen durchführen muss, macht sie langsamer als die beiden Alternativen zum Nachschlagen von Daten.

Bemerkung

Wenn Entwickler erwähnen, wie langsam die Skript-API ist, beziehen sie sich auf diese Kette von Abfragen. Im Vergleich zu kompiliertem C++ - Code, bei dem die Anwendung genau weiß, wo sie etwas finden muss, ist es unvermeidlich, dass Skript-API-Vorgänge viel länger dauern. Sie müssen die Quelle aller relevanten Daten lokalisieren, bevor sie versuchen können, darauf zuzugreifen.

Der Grund warum GDScript langsam ist, liegt darin, dass jede von ihm ausgeführte Operation dieses System durchläuft.

C# kann einige Inhalte mit höherer Geschwindigkeit über einen optimierten Bytecode verarbeiten. Wenn das C#-Skript jedoch den Inhalt einer Engine-Klasse aufruft oder wenn das Skript versucht, auf etwas außerhalb zuzugreifen, durchläuft es diese Pipeline.

NativeScript C++ geht noch weiter und hält standardmäßig alles intern. Aufrufe externer Strukturen werden über die Skript-API durchgeführt. In NativeScript C++ ist das Registrieren von Methoden, um sie für die Skript-API verfügbar zu machen, eine manuelle Aufgabe. Zu diesem Zeitpunkt verwenden externe Nicht-C++ - Klassen die API, um sie zu lokalisieren.

Angenommen, man leitet von Reference ab, um eine Datenstruktur wie ein Array oder ein Dictionary zu erstellen, warum sollte man dann ein Objekt gegenüber den beiden anderen Optionen auswählen?

  1. Kontrolle: Mit Objekten ist die Möglichkeit verbunden, komplexere Strukturen zu erstellen. Man kann Abstraktionen über die Daten legen, um sicherzustellen, dass sich die externe API nicht als Reaktion auf interne Datenstrukturänderungen ändert. Darüber hinaus können Objekte Signale haben, die reaktives Verhalten ermöglichen.

  2. Klarheit: Objekte sind eine zuverlässige Datenquelle, wenn es um die Daten geht, die Skripte und Engine-Klassen für sie definieren. Propertys enthalten möglicherweise nicht die erwarteten Werte, aber Sie müssen sich keine Gedanken darüber machen, ob die Property überhaupt vorhanden ist.

  3. Bequemlichkeit: Wenn jemand bereits eine ähnliche Datenstruktur im Sinn hat, erleichtert das Erweitern einer vorhandenen Klasse das Erstellen der Datenstruktur erheblich. Im Vergleich dazu erfüllen Arrays und Dictionarys nicht alle Anwendungsfälle.

Objekte ermöglichen es Nutzern, spezialisierte Datenstrukturen zu erstellen. Damit können eigene Listen, Binäre Suchbäume, Heaps, Splay Trees, Graphen, Disjoint Sets und vieles mehr erstellt werden.

Man könnte fragen: "Warum nimmt man keine Nodes für Baumstrukturen?" - Nun, die Node-Klasse enthält Dinge, die für spezialisierte Datenstrukturen unnötig sind, und als solches könnte es nützlich sein, einen eigenen Node-Typ für Baumstrukturen zu definieren.

extends Object
class_name TreeNode

var _parent: TreeNode = null
var _children: = [] setget

func _notification(p_what):
    match p_what:
        NOTIFICATION_PREDELETE:
            # Destructor.
            for a_child in _children:
                a_child.free()

Daher kann nun jede erdenkliche Art von spezialisierten Strukturen erstellt werden.

Enumerationen: int vs. string

Die meisten Programmiersprachen bieten einen Enumerationstypen an. So auch GDScript, aber anders als die meisten anderen Sprachen erlaubt es, Integer-Zahlen oder Strings als Enum-Werte zu nutzen (letzteres nur, wenn das export Schlüsselwort in GDScript verwendet wird). Doch dann stellt sich die Frage: "Welches sollte man nehmen?"

Die kurze Antwort wäre "was auch immer Ihnen mehr liegt". Das ist ein spezielles Merkmal, das nur GDScript hat, und nicht Godot-Skripte im Allgemeinen; GDScript gewichtet Nutzbarkeit höher als Geschwindigkeit.

Auf technischer Ebene sind Integer-Vergleiche (konstante Laufzeit) schneller als Stringvergleiche (lineare Laufzeit). Wenn man jedoch die Konventionen anderer Programmiersprachen einhalten will, sollte man Integer verwenden.

Das Hauptproblem mit Integer-Werten ist die Ausgabe eines Enum-Werts. Mit Integer-Werten würde beim Ausgeben von MY_ENUM der Wert 5 oder so etwas ausgegeben werden, anstatt "MyEnum". Um einen Integer-Enum auszugeben, müsste man ein Dictionary schreiben, das jedem Enum-Wert den entsprechenden String-Wert zuordnet.

Wenn der Hauptzweck der Verwendung eines Enums die Ausgabe von Werten ist und man sie als verwandte Konzepte gruppieren möchte, dann ist es sinnvoll, sie als Strings zu verwenden. Auf diese Weise wird eine separate Datenstruktur für die Ausgabe überflüssig.

AnimatedTexture vs. AnimatedSprite2D vs. AnimationPlayer vs. AnimationTree

Unter welchen Umständen sollte man welche der Animationsklassen von Godot verwenden? Die Antwort ist für neue Godot-Benutzer möglicherweise nicht sofort klar.

AnimatedTexture ist eine Textur, die von der Engine als animierte Schleife und nicht als statisches Bild gezeichnet wird. Benutzer können Folgendes verändern:

  1. Die Rate, mit der sie sich über jeden Abschnitt der Textur bewegt (FPS).

  2. Die Anzahl der in der Textur enthaltenen Regionen (Frames).

Godots RenderingServer zeichnet dann die Regionen nacheinander mit der vorgeschriebenen Geschwindigkeit. Die gute Nachricht ist, dass dies keine zusätzliche Logik von Seiten der Engine erfordert. Die schlechte Nachricht ist, dass der Benutzer sehr wenig Kontrolle hat.

Beachten Sie auch, dass AnimatedTexture eine Resource ist, im Gegensatz zu den anderen hier besprochenen Node-Objekten. Man könnte einen Sprite2D-Node erstellen, der AnimatedTexture als seine Textur verwendet. Oder man könnte (was die anderen nicht können) AnimatedTextures als Tiles in einem TileSet hinzufügen und es mit einer TileMap für viele autoanimierende Hintergründe integrieren, die alle in einem einzigen, gebündelten Zeichnen-Aufruf gerendert werden.

Der AnimatedSprite2D-Node in Kombination mit der Ressource SpriteFrames ermöglicht es, eine Vielzahl von Animationssequenzen durch Spritesheets zu erstellen, zwischen Animationen zu wechseln und deren Geschwindigkeit, regionalen Versatz und Ausrichtung zu steuern. Dadurch sind sie gut geeignet, um 2D-framebasierte Animationen zu steuern.

Wenn sie andere Effekte in Bezug auf Animationsänderungen auslösen müssen (z.B. Partikeleffekte erstellen, Funktionen aufrufen oder andere Peripherieelemente neben der framebasierten Animation bearbeiten), müssen Sie einen AnimationPlayer-Node in Verbindung mit dem AnimatedSprite verwenden.

AnimationPlayers sind auch das Tool, das man verwenden muss, wenn man komplexere 2D-Animationssysteme entwerfen möchte, wie z. B....

  1. Cut Out-Animationen: Bearbeitung der Transformationen von Sprites zur Laufzeit.

  2. 2D Mesh-Animationen: Man definiert einen Bereich für die Textur des Sprites und riggt ein Skelett dazu. Dann animiert man die Knochen, welche die Textur im Verhältnis zum Verhältnis der Knochen zueinander dehnen und verbiegen.

  3. Eine Mischung der beiden.

Während man einen AnimationPlayer benötigt, um die einzelnen Animationssequenzen für ein Spiel zu entwerfen, kann es auch sinnvoll sein, Animationen für Blending zu kombinieren, d. h. fließende Übergänge zwischen diesen Animationen zu ermöglichen. Es kann auch eine hierarchische Struktur zwischen den Animationen geben, die man für sein Objekt ausplant. Das sind die Fälle, in denen der AnimationTree glänzt. Eine ausführliche Anleitung zur Verwendung des AnimationTree findet man hier.