Dateneinstellungen

Haben Sie sich jemals gefragt, ob Problem X mit der Datenstruktur Y oder Z zusammenarbeitet? Dieser Artikel behandelt eine Vielzahl von Themen im Zusammenhang mit dieser Frage.

Bemerkung

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

Kurz gesagt, es beschreibt das Worst-Case-Szenario der Laufzeitlänge. Laienhaft ausgedrückt:

"Mit zunehmender Größe eines Problems, nimmt die Laufzeit des Algorithmus..."

• Konstante Zeit, O(1): "...erhöht sich nicht.."

• Logarithmische Zeit, O(log n): "...nimmt langsam zu."

• Lineare Zeit, O(n):"... erhöht sich mit der gleichen Geschwindigkeit."

• 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 linearen Zeitalgorithmus 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 Zeit die Operation ohne Probleme handhaben.

Im Großen und Ganzen möchten Entwickler möglichst keine linearen Operationen durchführen. Wenn man jedoch den Maßstab einer linearen Zeitoperation 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 den Job ist Teil dessen, was die Fähigkeiten von Programmierern wertvoll macht.

Array, Dictionary und Object

Godot stores all variables in the scripting API in the Variant class. class. Variants can store Variant-compatible data structures such as Array and Dictionary as well as Object s.

Godot implementiert ein Array als Vector <Variant>. Die Engine speichert den Array-Inhalt 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 Vektor der Name des Array-Objekts in herkömmlichen C++ Bibliotheken. Es handelt sich um einen Typ mit Vorlagen, was bedeutet, dass seine Datensätze nur einen bestimmten Typ enthalten können (gekennzeichnet durch spitze Klammern). So wäre beispielsweise ein PoolStringArray so etwas wie ein Vector <String>.

Zusammenhängende Speicherbereiche beinhalten die folgende Operationsleistung:

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

  • Op: Erhöht nur einen Zähler, um zum nächsten Datensatz zu gelangen.

• Einfügen, Löschen, Verschieben: Positionsabhängig. Im Allgemeinen langsam.

  • Op: Beim Hinzufügen/ Entfernen/Verschieben von Inhalten werden die angrenzenden Datensätze verschoben (um Platz zu schaffen/Platz zu füllen).

  • Schnelles Hinzufügen/Entfernen vom Ende.

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

  • Langsamstes 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 die Array-Änderungen am Ende ausführt.

    3. Invertieren Sie das Array erneut.

    Dies erstellt nur 2 Kopien des Arrays (noch konstante Zeit, aber langsam) im Vergleich zum Kopieren von ungefähr der Hälfte des Arrays, durchschnittlich N-mal (lineare Zeit).

• Get, Set: Fastest by position. E.g. can request 0th, 2nd, 10th record, etc. but cannot specify which record you want.

  • Op: 1 Additionsoperation von der Startposition des Arrays bis zum gewünschten Index.

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

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

    • Die Leistung hängt auch davon ab, ob eine umfassende Suche erforderlich ist.

  • Wenn die Reihenfolge beibehalten wird, können benutzerdefinierte Suchvorgänge die logarithmische Zeit erreichen (relativ schnell). Laien werden sich damit jedoch nicht wohl fühlen. Dies geschieht, indem das Array nach jeder Bearbeitung neu sortiert und ein geordneter Suchalgorithmus geschrieben wird.

Godot implementiert Dictionary als OrderedHashMap<Variant, Variant>. Die Engine speichert ein kleines Array (initialisiert mit 2^3 oder 8 Datensätzen) von Schlüssel-Wert-Paaren. Wenn man versucht, auf einen Wert zuzugreifen, gibt man ihm einen Schlüssel. Es hasht dann den Schlüssel, 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 eine schnelle Suche in der "Tabelle" der Schlüssel, die Werten zugeordnet sind. Wenn die HashMap zu voll wird, erhöht sie sich auf die nächste Potenz von 2 (also 16 Datensätze, dann 32 usw.) und baut die Struktur neu auf.

Hashes sollen die Wahrscheinlichkeit einer Schlüsselkollision verringern. In diesem Fall muss die Tabelle einen anderen Index für den Wert 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 einer geringen operativen Effizienz.

1. Jeden Schlüssel beliebig oft puffern.

   • 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. Beibehaltung einer ständig wachsenden Tabellengröße.

   • HashMaps behalten absichtlich nicht genutzten Speicherlücken in der Tabelle bei, um Hash-Kollisionen zu reduzieren und die Zugriffsgeschwindigkeit aufrechtzuerhalten. Deshalb vergrößert es sich quadratisch ständig um Potenzen von 2.

Wie man vielleicht erkennen kann, sind Dictionaries auf Aufgaben spezialisiert, die Arrays nicht ausführen. Nachfolgend sehen Sie eine Übersicht über ihre Operationsdetails:

• Iterieren: Schnell.

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

• Einfügen, Löschen, Verschieben: Am schnellsten.

  • Op: Hasht den gegebenen Schlüssel. Führt eine Additionsoperation aus, um den entsprechenden Wert zu ermitteln (Array-Start + Offset). Verschieben sind zwei Operationen (eine einfügen, eine löschen). Die Map muss einige Wartungsarbeiten durchführen, um ihre Funktionen zu erhalten:

    • Aktualisiert die geordnete Liste der Datensätze.

    • Bestimmt, ob die Tabellendichte eine Erweiterung der Tabellenkapazität erfordert.

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

• Get, Set: Am schnellsten. Dasselbe wie eine Suche nach Schlüssel.

  • Op: Wie einfügen/löschen/bewegen.

• Finden: Am langsamsten. Identifiziert den Schlüssel eines Wertes.

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

  • Beachten Sie, dass Godot diese Funktion nicht sofort 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 Fragen gestellt werden. Um beispielsweise die Frage "Haben Sie eine Eigenschaft namens 'position'?" zu beantworten, wird möglicherweise das script oder ClassDB gefragt. 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 Objektaufgabe. Jedes Mal, wenn eine dieser Multi-Source-Abfragen ausgeführt wird, werden mehrere Iterationsschleifen und HashMap-Lookups durchlaufen. Darüber hinaus handelt es sich bei den Abfragen um Operationen mit linearer Zeit, die von der Größe der Vererbungshierarchie des Objekts abhängen. Wenn die Klasse, die das Objekt abfragt (die aktuelle Klasse), nichts findet, wird die Anforderung bis zur ursprünglichen Objektklasse auf die nächste Basisklasse verschoben. Für sich genommen sind das zwar alles schnelle Vorgänge, aber die Tatsache, dass so viele Überprüfungen durchgeführt werden müssen, macht sie langsamer als beide 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 Referenz 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. Eigenschaften enthalten möglicherweise nicht die erwarteten Werte, aber Sie müssen sich keine Gedanken darüber machen, ob die Eigenschaft ü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 Dictionaries nicht alle Anwendungsfälle.

Objekte ermöglichen 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 Node 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 Knotentyp für Baumstrukturen zu definieren.

GDScriptC#

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.

Aufzählungen: int im Vergleich zu string

Die meisten Programmiersprachen bieten einen Enumerationstypen an. So auch GDScript, aber er erlaubt es, im Gegensatz zu den meisten anderen Sprachen, Ganzwertzahlen oder Zeichenketten als Enumerationswerte zu nutzen (letztes nur wenn das ` export` Schlüsselwort in GDScript verwendet wird). Es bleibt die Frage: "Was soll ich nun nehmen?"

Die kurze Antwort wäre "was auch immer Ihnen mehr liegt". Das ist ein spezielles Merkmal das nur GDScript hat, und nicht allgemein Godot Skripte - die GDScript Sprache bevorzugt Nutzbarkeit über Geschwindigkeit.

Im Detail erklärt - Ganzzahlenwert-Vergleiche (Konstanter Zeitverbrauch) passieren schneller als Zeichenkettenvergleiche (Lineare Zeitverbrauch). Möchte man sich an den Konventionen anderer Programmiersprachen orienteren sollte man Ganzzahlenwerte nutzen.

Das Hauptproblem mit Ganzzahlenwerte ist die Ausgabe des Enumerationswertes. Mit Ganzzahlenwerte würde beim Ausgeben von MY_ENUM ` 5` oder so ausgegeben werden, anstatt "MyEnum". Um einen Text auszugeben müsste man den Ganzzahlenwert mit einem Dictionary mappen.

Wenn der Hauptgrund, eine enum-Aufzählung zu verwenden, darin besteht, Werte auszugeben, und diese als verwandte Konzepte gruppiert werden sollen, macht es Sinn, Strings statt Integer zu verwenden. Dadurch muss keine separate Datenstruktur zum Ausgeben der symbolischen Namen bereitgestellt werden.

AnimatedTexture, AnimatedSprite, AnimationPlayer und AnimationTree

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

AnimatedTexture ist eine Textur, die die Engine als animierte Schleife und nicht als statisches Bild zeichnet. Benutzer können verändern...

1. die Geschwindigkeit, mit der es sich über jeden Abschnitt der Textur bewegt (fps).

2. die Anzahl der in der Textur enthaltenen Bereiche (Frames).

Godot's VisualServer zeichnet dann die Regionen nacheinander mit der vorgegebenen 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 ein Resource ist, im Gegensatz zu den anderen hier besprochenen Node-Objekten. Man könnte einen Sprite-Node erstellen, der AnimatedTexture als seine Textur verwendet. Oder man könnte (was die anderen nicht können) AnimatedTextures als Kacheln in einem TileSet hinzufügen und es mit einer TileMap für viele autoanimierende Hintergründe integrieren, die alle in einem einzigen gebündelten Renderaufruf gerendert werden.

Das AnimatedSprite-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. Dies macht sie gut geeignet, um 2D-Frame-basierte 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 frame-basierten Animation bearbeiten), müssen Sie ein Node AnimationPlayer in Verbindung mit dem AnimatedSprite verwenden.

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

1. Ausschnitt-Animationen: Bearbeiten 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 zu den Beziehungen der Knochen zueinander dehnen und verbiegen.

3. Eine Mischung aus dem oberen.

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.