Préférences de données

Vous êtes-vous déjà demandé s'il fallait aborder le problème X avec la structure de données Y ou Z ? Cet article couvre une variété de sujets liés à ces dilemmes.

Note

Cet article fait référence à des opérations "[something]-time". Cette terminologie provient de l'analyse d'algorithme Big O Notation.

Pour résumer, elle décrit le pire des scénarios de durée d'exécution. En termes simples :

"Quand la taille d'un domaine problématique augmente, la durée d'exécution de l'algorithme..."

• Temps-constant, O(1) : "....n'augmente pas."

• Temps-logarithmique, O(log n) : "....augmente lentement."

• Temps-linéaire, O(n) : "....augmente au même rythme."

• Etc.

Imaginez si l'on devait traiter 3 millions de points de données dans une seule trame. Il serait impossible d'utiliser un algorithme de temps linéaire puisque la taille même des données augmenterait le temps d'exécution bien au-delà du temps alloué. En comparaison, l'utilisation d'un algorithme à temps constant pourrait traiter l'opération sans problème.

Dans l'ensemble, les développeurs veulent éviter autant que possible de s'engager dans des opérations en temps linéaire. Mais, si l'on garde l'échelle d'une opération temps-linéaire petit, et si l'on n'a pas besoin d'effectuer l'opération souvent, alors elle peut être acceptable. L'équilibre entre ces exigences et le choix de l'algorithme et de la structure de données appropriés pour le travail fait partie de ce qui rend les compétences des programmeurs précieuses.

Array vs. Dictionary vs. Object

Godot stocke toutes les variables dans l'API de script dans la classe Variant. Les Variants peuvent stocker des structures de données Variant-compatible telles que Array et Dictionary ainsi que Object.

Godot implémente le tableau Array en tant que Vector<Variant>. Le moteur stocke le contenu des tableaux dans une section contiguë de la mémoire, c'est-à-dire qu'ils sont alignés les uns à côté des autres.

Note

Pour ceux qui ne connaissent pas le C++, un vecteur est le nom de l'objet array dans les bibliothèques C++ traditionnelles. Il s'agit d'un type " modele ", ce qui signifie que ses données ne peuvent contenir qu'un type particulier (indiqué par des crochets coudés). Ainsi, par exemple, un PoolStringArray serait quelque chose comme un Vector<String>.

Les mémoires contiguës impliquent les performances d'opération suivantes :

• Itéré: Trés rapide. Idéal pour les boucles.

  • Op : Tout ce qu'il fait est d'incrémenter un compteur pour passer à la donnée suivante.

• Insérer, Effacer, Déplacer: En fonction de la position. Généralement lent.

  • Op : Ajouter/supprimer/déplacer du contenu implique de déplacer les enregistrements adjacents (pour faire de la place/remplir de l'espace).

  • Ajout/suppression rapide à la fin.

  • Ajout/suppression lente à une position arbitraire.

  • Ajout/suppression le plus lent au début.

  • Si vous faites beaucoup d'insertions/déplacements au début, alors....

    1. inverser le tableau.

    2. faire une boucle qui exécute les changements du tableau à la fin.

    3. ré-inversez le tableau.

    Cela fait seulement 2 copies du tableau (temps-constant, mais lent) par rapport à une copie d'environ la moitié du tableau, en moyenne, N fois (temps-linéaire).

• Get, Set : Le plus rapide par position. Par exemple, vous pouvez demander le 0e, 2e, 10e enregistrement, etc., mais vous ne pouvez pas spécifier quel enregistrement vous voulez.

  • Op : 1 opération d'addition à partir de la position de départ du tableau jusqu'à l'indice désiré.

• Trouver: Le plus lent. Indique l'index/position d'une valeur.

  • Op : Doit itérer à travers le tableau et comparer les valeurs jusqu'à ce que soit trouvé une correspondance.

    • La performance dépend également de la nécessité ou non d'une recherche exhaustive.

  • Si elles sont conservées ordonnées, les opérations de recherche personnalisées peuvent les amener à un temps-logarithmique (relativement rapide). Les utilisateurs profanes ne seront pas à l'aise avec cela. Cela est fait en triant à nouveau le tableau après chaque édition et en écrivant un algorithme de recherche ordonné.

Godot implémente le Dictionary(dictionnaire) sous la forme d'un OrderedHashMap<Variant, Variant>. Le moteur stocke un petit tableau (initialisé à 2^3 ou 8 enregistrements) de paires clé-valeur. Lorsqu'on tente d'accéder à une valeur, ils lui fournissent une clé. Il hashes ensuite la clé, c'est-à-dire la convertit en un nombre. Le "hash" est utilisé pour calculer l'index dans le tableau. En tant que tableau, l'OHM a ensuite une recherche rapide dans le "tableau" des clés mises en correspondance avec les valeurs. Lorsque le HashMap devient trop plein, il passe à la puissance 2 suivante (donc, 16 enregistrements, puis 32, etc.) et reconstruit la structure.

Les hashes ont pour but de réduire les risques de collision de clés. Si une collision se produit, la table doit recalculer un autre indice pour la valeur qui prend en compte la position précédente. Dans l'ensemble, cela se traduit par un accès en temps constant à toutes les données, au détriment de la mémoire et d'une certaine efficacité opérationnelle mineure.

1. Hach chaque clé un nombre arbitraire de fois.

   • Les opérations de hach sont à temps constant, donc même si un algorithme doit en faire plus d'un, tant que le nombre de calculs de hachage ne devient pas trop dépendant de la densité de la table, les choses vont rester rapides. Ce qui mène à...

2. Maintenir une taille toujours plus grande pour la table.

   • Les HashMaps maintiennent des espaces de mémoire inutilisés intercalés dans le tableau dans le but de réduire les collisions de hash et de maintenir la vitesse d'accès. C'est pourquoi sa taille augmente constamment de façon quadratique par puissances de 2.

Comme on peut le constater, les Dictionaries se spécialisent dans des tâches où les tableaux ne le sont pas. Voici un aperçu de leurs détails opérationnels :

• Itéré : Rapide.

  • Op : Itérer sur le vecteur interne des hashes de la carte. Retourner chaque clé. Ensuite, l'utilisateur utilise la clé pour sauter à la valeur désirée et la retourner.

• Insérer, Effacer, Déplacer : Trés rapide.

  • Op : Hash la clé donnée. Effectue 1 opération d'addition pour rechercher la valeur appropriée (début de tableau + décalage). Déplacer est deux d'entre eux (un insert, un effacer). La carte doit être entretenue pour préserver ses capacités :

    • Mettre à jour la Liste ordonnée des données.

    • déterminer si la densité des tables nécessite une augmentation de la capacité des tables.

  • Le Dictionary se souvient dans quel ordre les utilisateurs ont inséré ses clés. Cela lui permet d'exécuter des itérations fiables.

• Get, Set: Très rapide. Identique à une recherche par clé.

  • Op : Identique à insérer/effacer/déplacer.

• Trouver: Très lent. Identifie la clé d'une valeur.

  • Op : Doit itérer à travers les données et comparer la valeur jusqu'à ce qu'une correspondance soit trouvée.

  • Notez que Godot ne fournit pas cette fonctionnalité en standard (parce qu'ils ne sont pas destinés à cette tâche).

Godot implémente les Objects comme des conteneurs stupides, mais dynamiques, de données. Les Objects interrogent les sources de données lorsqu'ils posent des questions. Par exemple, pour répondre à la question, "avez-vous une propriété appelée,'position'?", il peut demander son script ou le ClassDB. On peut trouver plus d'informations sur ce que sont les objets et comment ils fonctionnent dans l'article Application des principes orientés objet dans Godot.

Le détail important ici est la complexité de la tâche de l'Objet. Chaque fois qu'il effectue une de ces requêtes multi-sources, il exécute plusieurs boucles d'itération et recherches HashMap. De plus, les requêtes sont des opérations linéaires dans le temps qui dépendent de la taille de la hiérarchie d'héritage de l'objet. Si la classe que l'objet interroge (sa classe courante) ne trouve rien, la requête passe à la classe de base suivante, jusqu'à la classe originale de l'objet. Bien qu'il s'agisse d'opérations rapides isolément, le fait qu'il doive effectuer autant de vérifications est ce qui les rend plus lentes que les deux alternatives pour la recherche de données.

Note

Lorsque les développeurs mentionnent la lenteur de l'API de script, c'est à cette chaîne de requêtes qu'ils se réfèrent. Comparé au code C+++ compilé où l'application sait exactement où aller pour trouver quoi que ce soit, il est inévitable que les opérations de l'API de script prennent beaucoup plus de temps. Ils doivent localiser la source de toute donnée pertinente avant de pouvoir tenter d'y accéder.

La raison pour laquelle GDScript est lent est que chaque opération qu'il effectue passe par ce système.

C# peut traiter certains contenus à des vitesses plus élevées via un bytecode plus optimisé. Mais, si le script C# appelle dans le contenu d'une classe de moteur ou si le script essaie d'accéder à quelque chose d'externe à celui-ci, il passera par ce pipeline.

NativeScript C++ va encore plus loin et garde tout en interne par défaut. Les appels vers des structures externes passeront par l'API de script. Dans NativeScript C++, l'enregistrement des méthodes pour les exposer à l'API de script est une tâche manuelle. C'est à ce stade que les classes externes non C++ utiliseront l'API pour les localiser.

Donc, en supposant que l'une d'elles hérite de Reference pour créer une structure de données, comme un Array ou un Dictionary, pourquoi choisir un Object plutôt que les deux autres options ?

1. Contrôle : Avec les objets vient la possibilité de créer des structures plus sophistiquées. On peut superposer des abstractions sur les données pour s'assurer que l'API externe ne change pas en réponse aux changements de structure de données internes. De plus, les objets peuvent avoir des signaux, ce qui permet un comportement réactif.

2. Clarté : Les objets sont une source de données fiable lorsqu'il s'agit des données que les scripts et les classes de moteurs définissent pour eux. Les propriétés peuvent ne pas contenir les valeurs auxquelles on s'attend, mais on n'a pas besoin de s'inquiéter de savoir si la propriété existe en premier lieu.

3. Commodité : Si l'on a déjà une structure de données similaire à l'esprit, alors l'extension à partir d'une classe existante rend la tâche de construction de la structure de données beaucoup plus facile. En comparaison, les tableaux et dictionnaires ne remplissent pas tous les cas d'utilisation que l'on peut avoir.

Les Objects permettent également aux utilisateurs de créer des structures de données encore plus spécialisées. Avec lui, on peut concevoir sa propre liste, arbre de recherche binaire, tas, arbre de Splay, graphique, ensemble disjoint, et une foule d'autres options.

"Pourquoi ne pas utiliser Node pour les arborescences ?" pourrait-on se demander. Eh bien, la classe Node contient des choses qui ne seront pas pertinentes à la structure de données personnalisée de chacun. Ainsi, il peut être utile de construire son propre type de nœud lors de la création de structures arborescentes.

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()

A partir de là, on peut alors créer ses propres structures avec des caractéristiques spécifiques, limitées seulement par son imagination.

Énumérations : int vs string

La plupart des langages offrent une option de type énumération. GDScript n'est pas différent, mais contrairement à la plupart des autres langages, il permet d'utiliser des entiers ou des chaînes de caractères pour les valeurs d’énumération. La question se pose alors, "lequel utiliser ?"

Pour faire court : "choisissez ce qui vous semble le plus confortable". C'est une fonctionnalité spécifique à GDScript et non au scripting de Godot en général, la lisibilité des langages est priorisée par rapport aux performances.

Sur le plan technique, les comparaisons d'entiers (temps-constant) seront plus rapides que les comparaisons de chaînes de caractère (temps-linéaire). Si l'on veut respecter les conventions d'autres langages, alors on doit utiliser des entiers.

Le principal soucis lorsqu'on utilise des entiers se produit lorsque l'on souhaite print la valeur d'énumération. En tant qu'entier, vouloir afficher MY_ENUM va en fait afficher 5 ou ce-qui-a-été-défini, plutôt qu'afficher quelque chose du style "MyEnum". Pour afficher un entier d'énumération, vous devrez écrire un dictionnaire qui recense les chaînes de caractère qui correspondent à chaque entier.

Si l'usage principal de l'énumération est d'afficher des valeurs et que vous voulez les regrouper selon un concept les liants, alors il fait sens d'utiliser des chaînes de caractère pour faire cette énumération. De cette façon il n'est pas nécessaire d'utiliser une structure de donnée annexe.

AnimatedTexture vs. AnimatedSprite vs. AnimationPlayer vs. AnimationTree

Dans quelles circonstances faut-il utiliser chacune des classes d'animation de Godot ? La réponse peut ne pas être immédiatement claire pour les nouveaux utilisateurs de Godot.

AnimatedTexture est une texture que le moteur dessine comme une boucle animée plutôt que comme une image statique. Les utilisateurs peuvent manipuler...

1. la vitesse à laquelle il se déplace dans chaque section de la texture (fps).

2. le nombre de régions contenues dans la texture (images).

VisualServer de Godot dessine ensuite les régions en séquence au rythme prescrit. La bonne nouvelle, c'est que cela n'implique aucune logique supplémentaire de la part du moteur. La mauvaise nouvelle, c'est que les utilisateurs ont très peu de contrôle.

Notez également que AnimatedTexture est un objet Resource contrairement à d'autre objets Node discutés ici. On peut créer un nœud Sprite qui utilise AnimatedTexture comme texture. Ou (ce que les autres ne peuvent pas faire) on pourrait ajouter des AnimatedTextures comme tuiles dans un TileSet et l'intégrer avec un TileMap pour de nombreux fonds auto-animés qui sont tous rendus dans un seul draw call.

Le nœud AnimatedSprite, en combinaison avec la ressource SpriteFrames, permet de créer une variété de séquences d’animation à travers de spritesheets, naviguer entre les animations, et de contrôler leur vitesse, décalage de frame, et orientation. Ils sont donc bien adaptés pour contrôler les animations 2D.

Si l'on a besoin de déclencher d'autres effets en relation avec les changements d'animation (par exemple, créer des effets de particules, appeler des fonctions ou manipuler d'autres éléments périphériques en plus de l'animation à base d'images), il faudra alors utiliser un nœud AnimationPlayer conjointement avec l'AnimatedSprite.

AnimationPlayers est également l'outil qu'on devra utiliser afin de créer des systèmes d'animations plus complexes, tels que...

1. Découper les animations : éditer les transformations des sprites au moment de l'exécution.

2. Animations 2D Mesh : Définir une région pour la texture du sprite et y accrocher un squelette. Ensuite, on anime les os qui s'étirent et plient la texture proportionnellement aux relations des os entre eux.

3. Un condensé de ce qui est présent au-dessus.

Bien qu'un AnimationPlayer soit nécessaire pour concevoir chacune des séquences d'animation d'un jeu, il peut également être utile de combiner des animations pour les mélanger, c'est-à-dire permettre des transitions fluides entre ces animations. Il peut aussi y avoir une structure hiérarchique entre les animations qu'on planifie pour leur objet. Ce sont les cas où le AnimationTree brille. Vous trouverez un guide détaillé sur l'utilisation de l'AnimationTree ici.