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.

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 stores all variables in the scripting API in the Variant class. Variants can store Variant-compatible data structures such as Array and Dictionary as well as Objects.

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

For those unfamiliar with C++, a Vector is the name of the array object in traditional C++ libraries. It is a "templated" type, meaning that its records can only contain a particular type (denoted by angled brackets). So, for example, a PackedStringArray would be something like a 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.

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.

The primary issue with using integers comes up when one wants to print an enum value. As integers, attempting to print MY_ENUM will print 5 or what-have-you, rather than something like "MyEnum". To print an integer enum, one would have to write a Dictionary that maps the corresponding string value for each enum.

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. AnimatedSprite2D 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. the rate at which it moves across each section of the texture (FPS).

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

Godot's RenderingServer then draws the regions in sequence at the prescribed rate. The good news is that this involves no extra logic on the part of the engine. The bad news is that users have very little control.

Also note that AnimatedTexture is a Resource unlike the other Node objects discussed here. One might create a Sprite2D node that uses AnimatedTexture as its texture. Or (something the others can't do) one could add AnimatedTextures as tiles in a TileSet and integrate it with a TileMap for many auto-animating backgrounds that all render in a single batched draw call.

The AnimatedSprite2D node, in combination with the SpriteFrames resource, allows one to create a variety of animation sequences through spritesheets, flip between animations, and control their speed, regional offset, and orientation. This makes them well-suited to controlling 2D frame-based animations.

If one needs trigger other effects in relation to animation changes (for example, create particle effects, call functions, or manipulate other peripheral elements besides the frame-based animation), then will need to use an AnimationPlayer node in conjunction with the AnimatedSprite2D.

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

  1. Cut-out animations: editing sprites' transforms at runtime.

  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.