Qu'est-ce qui fait le succès d'un jeu ? Dossier spécial - Buffy, la chasseuse de performances

Par Mathieu Ropert

Que l'on développe un jeu de rôle ou un jeu de stratégie, il arrive généralement un moment où les concepteurs souhaitent attribuer toute une série de bonus et de malus aux statistiques de chaque élément du jeu. Les acteurs du jeu commencent modestement, mais on finit par vouloir que les statistiques de nos personnages, unités, nations et monstres puissent être influencées par une combinaison d'équipements, d'avantages, d'effets de zone, de niveaux de difficulté et bien d'autres éléments encore. Et si l’on n’y prend pas garde, notre jeu risque de se transformer en « simulateur de recalcul de bonus 2000 ».

Pour ceux qui n’ont jamais conçu ni implémenté de système de statistiques, cela peut ne pas sembler très compliqué à première vue. Après tout, ne s’agit-il pas simplement d’une structure contenant une série de valeurs ? Cela pourrait être le cas, mais cela dépend beaucoup de ce que votre système est capable de gérer ou non.


Imaginons que nous souhaitions que nos personnages disposent d’un ensemble de statistiques pouvant être influencées par diverses sources, comme nous l’avons mentionné dans notre introduction. Posons-nous quelques questions sur l’étendue de notre système.

Mettre en cache ou ne pas mettre en cache ?

Commençons par régler la question la plus fondamentale : « Avons-nous besoin de stocker la somme totale d’une statistique donnée avec tous les bonus appliqués ? ». Après tout, nous pourrions simplement la recalculer à la volée à chaque fois. Cela nous aide à définir le domaine du problème comme étant fondamentalement une question de mise en cache. On dit souvent que l’invalidation du cache est l’un des deux problèmes difficiles du génie logiciel ; pouvons-nous donc nous en passer ?

Cela peut sembler une évidence, mais cela dépend en réalité beaucoup du jeu, et éventuellement de la statistique elle-même. Cela nous oblige à nous demander (et à interroger les concepteurs) : à quelle fréquence cette valeur change-t-elle par rapport à la fréquence à laquelle elle est utilisée ? La question est d’autant plus délicate que la réponse peut évoluer au fur et à mesure que la conception du jeu évolue. Peut-être que le concepteur a de grands projets pour une statistique donnée, mais qu’il s’avère que « le bonus de vitesse des torpilles pour les sous-marins en eaux profondes » n’est pas une valeur souvent utilisée dans le jeu, ou peut-être qu’une statistique, au départ très spécifique, est devenue omniprésente au fil des années.

Dans le même ordre d’idées, quel est le coût de calcul de la valeur elle-même ? S’agit-il simplement d’interroger quelques valeurs et de les additionner ? Faut-il parcourir une collection d’objets provenant de dizaines, voire de milliers de contributeurs potentiels ? Et enfin, faut-il interroger de manière récursive les valeurs d’un autre objet de jeu susceptible d’utiliser le même système ?

En partant du principe qu’il est nécessaire de mettre en cache au moins une certaine catégorie de statistiques, passons à la question suivante.

Suivi des sources

Une autre question très importante est la suivante : « devons-nous garder une trace des contributeurs à une statistique donnée ? ». Dans le cas le plus simple, ce n’est pas nécessaire. Nous pourrions simplement disposer d’une valeur, y ajouter lorsque le bonus est activé et en soustraire lorsqu’il est désactivé (par exemple lorsqu’un personnage équipe ou déséquipe un objet).

Je dis « très importante » car elle peut facilement être négligée aux premiers stades du développement. À première vue, cela ne semble pas nécessaire. L’architecture nous fournit des callbacks OnEnable() et OnDisable() clairs que nous pouvons utiliser pour nous assurer que la valeur est à jour. Les concepteurs ne prévoient pas la nécessité de suivre la provenance d’un buff. Ils ont même réfléchi aux règles de cumul et ont conclu qu’il était possible de cumuler plusieurs sources ; nous n’aurions donc pas besoin de veiller à ce que seul l’effet de sort le plus élevé s’applique en cas de cumuls.

Mais voilà que les premiers retours de la bêta arrivent, et le commentaire le plus fréquent est que l’interface utilisateur n’affiche pas la répartition et qu’il est impossible de comprendre pourquoi une statistique donnée aboutit à une valeur donnée. Ou peut-être que l’équipe d’assurance qualité se plaint qu’il est difficile de tester si le système de buffs fonctionne réellement et demande au moins une infobulle de débogage expliquant comment la valeur a été calculée.

Alors… cela signifie-t-il que nous devrions toujours conserver la trace des décompositions dans notre système de mise en cache des statistiques, car nous aurons toujours besoin de les afficher sous une forme ou une autre ? D’après mon expérience, je dirais que oui, dans la plupart des cas, même si j’ai envisagé de « tricher » une ou deux fois. Compte tenu du coût que peut représenter l’ensemble du système, on pourrait envisager que le chemin de code de l’interface utilisateur dédié aux décompositions contourne le système de mise en cache et refasse le calcul à la volée, puisque nous n’affichons généralement qu’une poignée de décompositions par image. La valeur affichée peut finir par être légèrement décalée par rapport à la valeur mise en cache qui est réellement utilisée par les mises à jour de tick, ce qui peut semer la confusion tant chez les joueurs que chez les testeurs. Si vous en avez les moyens, ne pas suivre les sources des buffs dans le cache vous permettra d’économiser de précieux cycles CPU (et de la mémoire).

La seule chose que je déconseille formellement, c’est de forcer un recalcul du cache à la volée (avec les décompositions) lorsque l’interface utilisateur en a besoin. J’ai corrigé plusieurs bugs de multijoueur liés à ce décalage au cours de ma carrière à cause de cela. Et même pour les jeux exclusivement solo, cela permet à l’interface utilisateur de modifier l’état du jeu à la volée, ce à quoi je suis farouchement opposé, comme vous le savez si vous avez suivi mes articles précédents.

Pilot

Cela étant dit, parlons un peu de la genèse de cet article. J’ai récemment eu l’occasion d’intervenir en tant que consultant auprès de Galactic Starfish sur leur prochain titre, Strategeist. L’une des choses que j’ai remarquées, c’est que, comme dans tous les jeux de grande stratégie que je connais, leur système de modificateurs posait un problème de performances.

Ils m’ont aimablement autorisé à utiliser leur code source comme référence « en conditions réelles » afin de tester différentes implémentations dans le cadre de cet article. Je ne considérerais pas les chiffres actuels comme une indication de ce à quoi pourrait ressembler la version finale ; ils ne servent qu’à illustrer l’impact des différents choix d’implémentation.

Commençons donc par notre implémentation de référence :



Assez simple jusqu’ici. Dans le cas de Strategeist, le jeu compte actuellement 480 statistiques uniques. Les jeux de grande stratégie en comptent généralement plusieurs milliers. Celles-ci devraient probablement être réparties en catégories (en fonction des classes d’objets de jeu finales auxquelles elles s’appliquent), mais ce chiffre reste sans doute représentatif.

Comme je l’ai mentionné précédemment, cette implémentation était assez coûteuse en ressources. Sur mon i7-10700, j’ai mesuré le temps de recalcul du cache pour chaque pays du jeu (l’acteur contrôlé par le joueur) à environ 163,7 µs par exécution. Bien sûr, cette opération est effectuée pour chaque pays du jeu, et si vous connaissez bien les jeux de stratégie sur carte, vous savez déjà qu’il y en a des centaines dans le jeu.

Même s’il y a sans doute des aspects à améliorer dans les calculs eux-mêmes, je souhaite, dans la suite de cet article, me concentrer sur les gains que l’on pourrait obtenir simplement en modifiant le stockage sous-jacent.

Alors, tu es un gentil démon ? Tu viens nous apporter des allocations ?

Alors que j’avais d’abord utilisé Unreal Insights comme profileur d’instrumentation pour voir la mise à jour du modificateur ressortir dans le profil de tick, le passage à un profilage par échantillonnage (même aussi basique que celui intégré à Visual Studio) a suffi à confirmer mes soupçons : l’utilisation de ces conteneurs déclenchait de nombreuses allocations, au point que la majeure partie de la mise à jour était consacrée aux opérations new et delete. Le TMalloc d’Unreal est meilleur que le malloc par défaut fourni par la CRT de Windows, mais cela restait un problème majeur.

En ce qui concerne les conteneurs associatifs, std::unordered_map n’est pas terrible. Il est plus performant sur MSVC que sur Clang/GCC grâce à la manière dont il évite le modulo, mais il reste tout de même médiocre. D’autant plus que le problème ici ne réside pas dans le temps de recherche, mais dans les insertions et suppressions qui déclenchent une multitude d’opérations new et delete. Cela s’explique par le fait que std::unordered_map est essentiellement implémenté comme un std::vector de std::list, chaque entrée étant un std::pair alloué dans le tas.

En examinant les schémas d’utilisation à travers le code, j’ai remarqué que nous n’utilisons pratiquement jamais le std::unordered_map interne de manière significative. Le besoin d’une recherche en O(1) d’une source BuffSource donnée dans une entrée donnée est rare, se limitant principalement à l’interface utilisateur. La plupart des entrées ne contiennent qu’une poignée de sources, le cas maximal pouvant atteindre une douzaine ou deux.

Il s’avère que les processeurs modernes sont en réalité assez performants pour effectuer une recherche linéaire par force brute dans de petits tableaux. Nous pourrions remplacer le std::unordered_map interne par un std::vector et utiliser std::find_if pour trouver la paire recherchée. Si nous en avions vraiment besoin, nous pourrions même utiliser deux vecteurs (un pour les clés, un pour les valeurs), ce qui permettrait de transformer notre std::find pour une clé donnée en une poignée de comparaisons SIMD de type uint64_t.

Le simple fait de convertir nos sources en un std::vector<std::pair<BuffSource, double>> donne déjà des résultats assez impressionnants : 91,8 µs. Cela réduit également l’empreinte mémoire (vector est plus économe en mémoire qu’un unordered_map pour une taille ou une capacité identique).

Essayer les types Unreal

Puisque nous utilisons Unreal Engine 5, autant essayer leur propre alternative à vector. Après tout, il y a toujours des gens dans mes commentaires qui me disent que la STL est mauvaise et que tout développeur de jeux devrait la réécrire, même sur un projet solo. Je sais que je suis un peu impertinent, mais c’est un sujet récurrent auquel je suis confronté depuis des années. À mon sens, le strict minimum qu’Unreal devrait faire pour me convaincre serait de fonctionner comme un remplacement direct de std::vector (à l’instar d’EASTL), mais malheureusement ce n’est pas le cas. Les itérateurs ne sont pas copiables pour une raison quelconque (ce qui les rend inutilisables avec la plupart des éléments de <algorithm>), et aucun des noms de méthodes ne correspond à ceux de la STL, à l’exception de begin() et end() (pour autant qu’ils existent).

Quoi qu’il en soit, prenons notre mal en patience et essayons une nouvelle fois de remplacer nos origins par TArray<std::pair<BuffSource, double>>.

Le résultat donne 86,6 µs en moyenne. C’est 5 µs de mieux. Ce n’est pas mal, mais je ne suis pas sûr que cela vaille la peine de s’embêter, d’autant plus que l’amélioration principale des performances peut être obtenue sans cela.

En effet, la principale raison pour laquelle cette méthode est plus rapide est que le TArray d’Unreal alloue au moins 4 éléments lorsqu’il passe d’une capacité de 0 (à moins que vous ne définissiez un indicateur lui demandant d’être aussi « économe » que la STL). Cela évite l’écueil courant avec std::vector, qui réalloue de la mémoire en passant d’une capacité de 0 à 1, puis de 1 à 2, puis de 2 à 3, et (si on n’a pas de chance) de 3 à 4, en raison du fonctionnement mathématique du facteur de croissance géométrique. Je suis d’accord avec les développeurs d’Unreal : dans la plupart des cas, c’est probablement une meilleure stratégie. En particulier, j’apprécierais beaucoup que la STL dispose d’une heuristique de base pour éviter les réallocations 0 → 1 → 2 → 3 → 4 lorsque la taille des éléments est inférieure à une certaine valeur. Dans le pire des cas, cela peut être ajouté de notre côté à l’aide d’une simple vérification : if (v.capacity() == 0) v.reserve(4);.

Quoi qu’il en soit, il existe une solution encore meilleure qu’une seule allocation pour les petites tailles. C’est l’absence d’allocation. On parle généralement de « petit vecteur » (car il utilise l’optimisation des petits tampons, comme std::string). Ils ne font pas partie de la STL (malheureusement), mais on les trouve dans des bibliothèques courantes comme Abseil et Boost. Ou, puisque nous utilisons Unreal, nous pouvons utiliser leur TInlineAllocator avec notre TArray :



Cela nous amène à 69 µs par mise à jour en évitant complètement les allocations pour les origines de la plupart des entrées, à moins qu’elles ne soient associées à un grand nombre de buffs, auquel cas la formule d’allocation géométrique entre en jeu, garantissant que nous ne (ré)allouons qu’une ou deux fois à mesure que le tableau s’agrandit. Nous sommes déjà deux fois plus rapides que notre référence !

Des tableaux, des tableaux partout !

Vous vous dites peut-être : « Eh bien, si le conteneur interne est plus rapide sous forme de tableau, ne devrions-nous pas faire de même pour le conteneur externe ? ». Félicitations, j’ai pensé exactement la même chose. Car c’est ce qui a été fait dans des jeux comme Europa Universalis IV et Hearts of Iron IV. Sauf qu’il y a un hic.



… et notre recalcul moyen des statistiques passe à 1 142,8 µs. Une milliseconde entière par acteur. Avec plusieurs centaines d’acteurs, on se retrouve face à un tick pouvant prendre jusqu’à une seconde entière. C’est un désastre ! Qu’est-ce qui a mal tourné ?

Le problème vient du fait que les calculs utilisent des variables Stats temporaires avant d’ajouter les résultats aux statistiques principales du pays. À chaque fois, elles allouent environ une centaine de kilo-octets. Même si elles ne contiennent que quelques valeurs, chacune provenant d’une seule source. Bien que cela indique probablement un recours excessif à des variables temporaires qui mériteraient une refonte de l’architecture, cela illustre bien un point. Peut-être que toutes les statistiques n’ont pas besoin d’utiliser un espace de stockage important (mais en grande partie vide). Certains systèmes et objets de jeu comportant peu d’entrées réelles tireraient probablement tout de même profit du stockage clairsemé offert par unordered_map.

Et si nous laissions l’utilisateur choisir la stratégie de stockage ? Après tout, c’est sans doute lui qui sait le mieux quelle solution est la plus adaptée à une partie spécifique du code.



De cette manière, le comportement par défaut consiste à utiliser le stockage en carte clairsemée, optimisé pour les objets ne comportant que quelques statistiques actives, tandis que les objets plus volumineux (comme les pays) peuvent passer à la version tableau. Notez que nous sommes passés de array<Stats, 480> à vector<Stats> afin de garantir que la taille d’un objet Stats vide reste minimale. Nous effectuerons une seule allocation pour les objets que nous faisons passer à la variante vector, un coût tout à fait acceptable qui n’est payé qu’une seule fois lors de l’initialisation ou de la construction.

Les résultats montrent en effet un bond considérable des performances : 45,1 µs. Nous sommes désormais près de 4 fois plus rapides. Non seulement les recherches et les insertions sont bien plus rapides, mais comme nous utilisons désormais un vector comme base, nous pouvons nous assurer de ne libérer aucune mémoire lors de l’effacement. Le tableau origins sous chaque Entry n’aura jamais besoin d’allocation pour la plupart des pays après un tick, car nous conserverons la capacité inchangée. C’est l’un des grands avantages des tableaux denses, car ils peuvent facilement préserver les allocations des conteneurs internes (ce n’est pas impossible à faire avec des cartes, mais il faudrait un allocateur personnalisé qui réutilise les entrées libérées et maintienne leur tableau « origins » alloué).

De meilleures cartes ?

Nous avons dit qu’ unordered_map n’était pas très performant, alors pourquoi ne pas essayer autre chose ? Pour rester dans le thème d’Unreal Engine, j’ai envisagé d’utiliser TMap, mais j’ai malheureusement trouvé son API vraiment exécrable, surtout lorsque j’ai essayé de remplacer unordered_map pour un test rapide. À la place, j’ai décidé d’utiliser ska::bytell_hash_map, créé par l’auteur de la conférence C++Now sur les tables de hachage mentionnée précédemment. Si vous souhaitez découvrir d’autres options, j’ai trouvé que cet article offrait un bon aperçu.

Comme il s’agit d’un remplacement direct de std::unordered_map (en grande partie, n’oubliez pas que les insertions invalident les itérateurs &#128521, c’est facile à tester :

Cela nous donne notre meilleur temps de toute l'expérience : 42,4 µs. La faible ampleur de l'amélioration s'explique principalement par le fait que notre conteneur Stats de pays utilise la variante « array » ; cela n'améliore donc que les variables temporaires et les éléments associés utilisés dans le code de recalcul.

Si nous désactivons le stockage en tableau pour les pays et utilisons la bytell_hash_map dans tous les cas, nous obtenons tout de même un temps honorable de 53,43 µs. Cela nous donne également un aperçu des améliorations potentielles que nous pourrions obtenir en optimisant l’utilisation de Stats dans nos calculs, au-delà de celles stockées au sein du conteneur « country ».

Encore une fois, tous ces chiffres sont fournis pour illustrer la différence que peut faire le choix du conteneur sans modifier quoi que ce soit d’autre dans notre système de statistiques/buff. Le rapport relatif est probablement un peu faussé, car les calculs de référence pourraient être améliorés.

Chiffres finaux

Au cours de cette petite expérience, j’ai testé de nombreuses combinaisons. Je vais indiquer ici l’utilisation du processeur et de la mémoire (taille des statistiques par pays, y compris les sous-allocations) à titre de référence :

- V1 (référence) (unordered_map + unordered_map) : 163,7 µs / 17 918 octets
- V2 (unordered_map + vector) : 91,8 µs / 11 629 octets
- V3 (unordered_map + TArray) : 86,6 µs / 18 645 octets
- V4 (unordered_map + TArray Inline) : 69 µs / 18 291 octets
- V5 (vector + TArray Inline) : 1 142,8 µs / 994 224 octets
- V6 (variant<unordered_map,vector> + TArray Inline) : 45,1 µs / 45 096 octets
- V7 (variant<bytell_hash_map,vector> + TArray Inline) : 42,4 µs / 45 096 octets
- V8 (bytell_hash_map + TArray Inline) : 53,4 µs / 25 086 octets
- V9 (`bytell_hash_map` + `TArray`) : 71,4 µs / 19 558 octets
- V10 (`variant<bytell_hash_map,vector>` + `TArray`) : 44,8 µs / 25 314 octets

Soit dit en passant, je n’ai pas encore évoqué le multithreading, et ce pour une bonne raison. Bien que la mise à jour du cache des statistiques puisse tout à fait être confiée à un parallel_for pour chaque acteur, je souhaitais me concentrer sur les performances monocœur dans le cadre de cet article. D’autant plus que ceux d’entre vous qui utilisent encore l’implémentation par défaut de malloc() fournie par MSVC ressentiront toute la difficulté de tenter de paralléliser une opération principalement limitée par les allocations. Comme je l’ai mentionné lors de ma présentation l’année dernière, l’allocateur par défaut utilise des mutex qui feront exploser tous vos chiffres. Si votre application ne dispose pas déjà d’un allocateur de mémoire polyvalent personnalisé comme c’est le cas pour Unreal, pensez à passer à mimalloc.

Sur ce, à la prochaine !

Licensed under CC BY-NC-SA 4.0

Source : What makes a game tick? Special Issue - Buffy the Performance Slayer

Et vous ?

Quel est votre avis sur le sujet ?

Voir aussi :

Meta lance Pocket, une application basée sur l'IA qui génère des jeux jouables à partir de consignes textuelles, signe que Meta mise sur un avenir où il sera possible de développer des jeux sans savoir coder

Roblox vous permettra de créer des jeux intégrant l'IA directement sur mobile, risquant de surcharger une plateforme déjà saturée de contenus douteux, désormais envahie par des jeux générés par l'AI slop

Google annonce « Playground », une plateforme de jeux expérimentale qui permet de créer, de jouer et de partager des jeux entièrement personnalisés sur navigateur à l'aide d'instructions génératives d'IA