Au cœur de Warcraft Rumble : le calcul de l’expérience pour les figurines
Salut à tous !
Je m’appelle Andy Lim et je suis ingénieur en chef pour les fonctionnalités serveur de Warcraft Rumble. L’équipe serveur est responsable de tout ce qui concerne les serveurs, notamment la mise en réseau, le cloud computing et le stockage, mais nous travaillons aussi sur des fonctionnalités du jeu, telles que la progression de la campagne et les quêtes. J’aimerais vous inviter dans les coulisses du jeu et vous en dire un peu plus sur le stockage et l’utilisation de l’expérience pour calculer les niveaux de chaque figurine.
Permettez-moi de vous présenter Cassandra
Avertissement : détails techniques en approche ! Ça risque de devenir un peu compliqué, mais restez avec nous.
Pour commencer, parlons un peu de Cassandra, la solution de stockage que nous utilisons pour assurer le suivi de tous les changements fréquents et simultanés des données de nos joueurs et joueuses. Cassandra est une base de données décentralisée et très évolutive, populaire et disponible en open source, qui offre un juste équilibre entre intégrité et disponibilité des données. En ce qui concerne les données elles-mêmes, Cassandra peut en gérer de vastes ensembles sans forcer l’utilisation d’un schéma spécifique. Nous avons créé des outils qui permettent aux ingénieurs de définir nos bases de données et le schéma de tableau adapté à chaque fonctionnalité, ce qui nous donne la flexibilité que nous voulons en termes de structure et d’organisation. Nous pouvons facilement écrire et valider notre schéma et nos interrogations.
Qu’est-ce qu’un schéma ? Un schéma de base de données définit la façon dont les données sont organisées dans une base de données relationnelle, comme ce qu’on trouve dans les tableaux.
Stockage de l’expérience en tant que registre
Avec Cassandra, l’écriture des données est très rapide, mais la lecture prend du temps. La mise à jour sur place des données est souvent une opération de lecture puis d’écriture, ce qui manquerait donc de rapidité. Pour contourner ce problème, nous avons fait en sorte que les données des joueurs et joueuses soient stockées sous forme de registre. Dans un registre, on écrit chaque ligne en tant que modification et lorsqu’on passe à la lecture, on lit toutes les entrées puis on s’en sert pour faire des calculs.
Si vous voulez un exemple de registre, pensez à une carte bancaire. Chaque transaction est écrite sous forme d’une entrée de valeur positive ou négative. À chaque fois que vous utilisez votre carte pour un paiement, c’est une transaction de valeur négative ; à chaque fois que de l’argent est versé sur votre compte, c’est une transaction de valeur positive. Comment calculez-vous votre solde ? Vous devez prendre en compte la totalité du registre et ajouter/soustraire chaque valeur.
Une donnée sur place, c’est un peu comme un élément individuel qu’on peut stocker. Lorsque vous voulez en changer la valeur, vous devez le lire, faire le changement, puis écrire la nouvelle valeur. Par conséquent, s’il s’agit du score d’un match de foot, chaque fois qu’une équipe marque un but, vous devez faire une lecture pour vérifier le dernier total, y ajouter le nouveau but, puis écrire le résultat dans le score.
Prenons un exemple concret dans Arclight : le registre d’expérience de chaque figurine. Après chaque mission, une rangée est ajoutée au registre pour chaque figurine, indiquant la quantité d’expérience obtenue par celle-ci. Après cinq missions, on aura des entrées de ce type :
Tableau 1
|
Joueur/joueuse |
Figurine |
Valeur |
Date et heure |
|---|---|---|---|
|
Andy |
Brute gnolle |
3 |
Lundi 14 h |
|
Andy |
Chevaucheur de griffon |
3 |
Lundi 14 h 05 |
|
Andy |
Brute gnolle |
3 |
Lundi 14 h 10 |
|
Andy |
Pilote IMUN |
3 |
Lundi 14 h 15 |
|
Andy |
Brute gnolle |
3 |
Lundi 14 h 20 |
Pour obtenir le total d’expérience de chaque figurine, il suffit de récupérer toutes ces entrées de registre, de les regrouper par figurine et d’ajouter leurs valeurs d’expérience. Voici à quoi ressemblerait le résultat :
Tableau 2
|
Joueur/joueuse |
Figurine |
Total |
|---|---|---|
|
Andy |
Brute gnolle |
9 |
|
Andy |
Chevaucheur de griffon |
3 |
|
Andy |
Pilote IMUN |
3 |
Processus de cumul des données
Vous savez maintenant comment nous stockons l’expérience. À présent, voyons comment nous pouvons affiner les calculs qui doivent être effectués pour chaque figurine. Le stockage de rangées individuelles pour chaque obtention d’expérience d’une figurine donnerait lieu à un processus de lecture trop intense. Il y aurait énormément de rangées et ce tableau s’allongerait indéfiniment… et ÉTERNELLEMENT. Disons que pour vous, une journée typique dans Rumble inclut une combinaison de 15 quêtes ou combats JcJ, avec 20 déferlantes par semaine pour obtenir de l’or et un raid de donjon hebdomadaire pour améliorer votre armée. Cela correspondrait à 100 entrées par semaine. Après environ 3 mois de jeu, on aurait quelque chose comme 1 260 entrées de registre. Pour calculer vos totaux, il faudrait qu’on les récupère dans Cassandra avec son système de lectures lentes. Aïe.
Nous avons mis au point une solution à ce problème : les cumuls. Un cumul, c’est un calcul de valeurs jusqu’à un certain moment. Dans notre cas, on les ajoute toutes et on les représente sous la forme d’une rangée unique. On stocke ensuite cette rangée dans un deuxième tableau. Vous comprenez à présent à quoi sert l’horodatage. En ce qui concerne l’expérience, les attributs sont le joueur ou la joueuse ainsi que la figurine, et le calcul est une somme. Si nous faisons un cumul de toutes les entrées de registre jusqu’au mardi à minuit en stockant les résultats dans un deuxième tableau de Cassandra, on obtiendra des entrées de ce type :
Tableau 3
|
Joueur/joueuse |
Figurine |
Total |
Date de fin |
|---|---|---|---|
|
Andy |
Brute gnolle |
9 |
Mardi minuit |
|
Andy |
Chevaucheur de griffon |
3 |
Mardi minuit |
|
Andy |
Pilote IMUN |
3 |
Mardi minuit |
Si vous continuez à jouer le mercredi, davantage d’entrées d’expérience sont générées. Le tableau d’expérience d’origine se serait allongé.
Tableau 4
|
Joueur/joueuse |
Figurine |
Valeur |
Date et heure |
|---|---|---|---|
|
Andy |
Brute gnolle |
3 |
Lundi 14 h |
|
Andy |
Chevaucheur de griffon |
3 |
Lundi 14 h 05 |
|
Andy |
Brute gnolle |
3 |
Lundi 14 h 10 |
|
Andy |
Pilote IMUN |
3 |
Lundi 14 h 15 |
|
Andy |
Brute gnolle |
3 |
Lundi 14 h 20 |
|
Andy |
Pilote IMUN |
3 |
Mercredi 12 h |
|
Andy |
Chaîne d’éclairs |
3 |
Mercredi 12 h 05 |
|
Andy |
Chevaucheur de griffon |
3 |
Mercredi 12 h 10 |
Maintenant, nous voulons faire un récapitulatif complet et recalculer les niveaux actuels des figurines après cette session de jeu. On doit interroger les deux tableaux (le tableau des cumuls pour l’entrée unique et le registre pour les entrées ultérieures) et ajouter les valeurs pour obtenir un tableau final d’expérience totale. Ainsi, on lit le tableau 3 puis on interroge le tableau 4 uniquement pour les données postérieures à chaque rangée du tableau 3. Voici la liste des étapes à suivre :
- Lecture d’une rangée du tableau 3
|
Chevaucheur de griffon |
3 |
Mardi minuit |
- Lecture des rangées du tableau 4 pour le Chevaucheur de griffon après mardi à minuit
|
Chevaucheur de griffon |
3 |
Mercredi 12 h 10 |
- Calcul de la somme des deux ensembles de données pour générer un total de :
|
Chevaucheur de griffon |
6 |
Comme vous pouvez le voir, cette approche permet de court-circuiter pas mal de lectures du tableau 4.
Vous pensez peut-être qu’on devrait simplement stocker les nouveaux calculs de données après le stockage d’une nouvelle entrée du registre. Sur le papier, ça pourrait marcher, mais cela provoquerait des incohérences dans les données et une dégradation des performances. Par exemple, une dégradation possible des performances serait due à la charge que représenterait pour le système la nécessité de recalculer et stocker les données, souvent à cause du processus de lecture puis d’écriture que cela implique. Nous devons équilibrer les besoins en calculs avec l’impératif d’exécution du jeu avec des performances acceptables pour tous les joueurs et joueuses.
Quant aux incohérences dans les données, prenons par exemple les calculs de fin de jeu. La plateforme et l’infrastructure de nos serveurs prennent en charge les retards d’arrivée des messages. Imaginons qu’un problème temporaire s’est produit entre deux centres de données (A et B) et que le message de gain d’expérience d’une figurine a été envoyé par A mais n’est pas encore arrivé sur B. Considérons le scénario suivant : vous faites une partie juste avant minuit. Vous jouez et vous gagnez le mercredi à 23 h 59. Le processeur de cumul a été configuré pour être exécuté quotidiennement pour toutes les données de la journée en cours. Il serait donc lancé à minuit et calculerait vos valeurs totales d’expérience jusqu’à jeudi à 0 h. Ces données seraient stockées dans le second tableau et les nouvelles lectures d’expérience consulteraient la dernière valeur stockée en ajoutant toutes les données reçues après jeudi à 0 h. Dans le cas d’un retard de message, celui-ci serait reçu mais indiquerait que la partie s’est terminée mercredi à 23 h 59. L’entrée correspondante serait donc écrite avec cet horodatage. Cette entrée se serait donc pas incluse dans le tableau de cumul et une interrogation des données ultérieures ne la renverrait pas non plus. Ces données incomplètes seraient problématiques. Qu’en est-il des messages arrivés avec quelques jours de retard ? Eh bien, nous avons mis en place un système de surveillance et d’alerte qui garantit presque toujours le traitement de ces nouvelles informations dans les temps avant le prochain cumul.
Calcul des niveaux des figurines
Si vous vous penchez à nouveau sur le tableau d’expérience totale, vous remarquerez qu’il n’inclut aucun calcul de niveau. On y trouve uniquement le total de l’expérience accumulée dans le jeu. Séparément, il y a un tableau statique défini par les concepteurs du jeu qui ressemble à celui-ci. Pour commencer, une figurine est au niveau 1 ; lorsqu’elle obtient 1 point d’expérience, elle passe au niveau 2, puis il lui faut 3 points pour atteindre le niveau 3.
|
Niveau |
Points pour passer au niveau suivant |
|---|---|
|
1 |
1 |
|
2 |
3 |
|
3 |
6 |
|
4 |
10 |
|
5 |
20 |
|
… |
… |
|
10 |
250 |
La combinaison des deux tableaux nous permet de calculer le niveau actuel d’une figurine au moment de l’exécution du jeu en calculant un total cumulé, ce qui nous donne l’ensemble de données suivant :
|
Figurine |
Niveau |
Exp. |
Points pour passer au niveau suivant |
|---|---|---|---|
|
Brute gnolle |
3 |
5 |
1 |
|
Chevaucheur de griffon |
3 |
2 |
4 |
|
Pilote IMUN |
3 |
2 |
4 |
|
Chaîne d’éclairs |
2 |
2 |
1 |
Cela donne plus de flexibilité aux concepteurs du jeu en leur permettant de changer la quantité d’expérience nécessaire pour passer au niveau supérieur. S’ils pensent qu’il est trop difficile d’améliorer les figurines de faibles niveaux, ils peuvent diminuer les quantités d’expérience requises. Il en résulterait une petite amélioration du niveau actuel de toutes les figurines et moins d’expérience à obtenir pour les faire passer au niveau supérieur, sans apporter aucune modification aux données des joueurs et joueuses enregistrées dans la base de données. L’inverse est un peu plus douloureux. Si les concepteurs du jeu décident que les passages aux niveaux supérieurs sont trop rapides et augmentent les valeurs, nous n’offrirons pas d’expérience en compensation pour rétablir les niveaux qu’avaient atteint les figurines avant la modification. Cela dit, nous pouvons donner aux concepteurs la possibilité d’octroyer de l’expérience aux figurines pour atténuer le choc.
Autres approches considérées
Avant d’adopter notre solution actuelle, nous avons examiné diverses approches pour le stockage des gains d’expérience et le calcul du niveau résultant des figurines. Certaines impliqueraient plus de temps de pause pour nous permettre de modifier l’expérience des joueurs, tandis que d’autres offriraient une bonne expérience de jeu sans négliger la progression des joueurs.
« Toujours stocker le niveau, l’expérience et les points pour passer au niveau supérieur des figurines »
Et si on utilisait juste un modèle SQL standard et des mises à jour transactionnelles ? Les mises à jour transactionnelles permettent de mettre à jour un ensemble de données dans sa totalité, selon un principe de tout ou rien. Si l’écriture d’une partie échoue, toutes les données retournent à leur valeur d’origine. Elles permettent donc de bénéficier des propriétés « ACID » : atomicité, cohérence, isolation et durabilité.
Avec cette approche, le suivi de l’expérience et du niveau total de chaque figurine se réduirait à une seule ligne, ce qui allégerait énormément les lectures.
Lorsqu’une figurine gagne de l’expérience, la mise à jour lui donne 2 points d’expérience avec 8 points avant de passer au niveau suivant et le niveau 3. Ce type de modification force le système à lire les données, à les recalculer, puis à les écrire dans la base de données. Ce modèle ne permet pas d’exploiter les atouts offerts par Cassandra. Ce n’est pas le seul défaut de cette approche, car pour changer le nombre de points nécessaires pour passer au niveau supérieur, il faudrait mettre le jeu hors ligne pour modifier les données de toutes les figurines pour tous les joueurs et joueuses.
« Stockage en tant que pourcentage »
Nous avons aussi réfléchi à la possibilité de stocker un pourcentage avant le passage au niveau supérieur, comme dans cet exemple :
|
Figurine |
Niveau |
Niveau supérieur |
|---|---|---|
|
Brute gnolle |
3 |
20 % |
|
Chevaucheur de griffon |
2 |
20 % |
|
Pilote IMUN |
2 |
20 % |
Ensuite, après une partie, nous ferions quelques calculs rapides. Par exemple, la brute gnolle obtient +3 exp, le pourcentage est +3 / 10, ce qui signifie que nous devons donner 30 % d’un niveau à la brute gnolle, avec le résultat suivant :
|
Figurine |
Niveau |
Niveau supérieur |
|---|---|---|
|
Brute gnolle |
3 |
50 % |
|
Chevaucheur de griffon |
2 |
20 % |
|
Pilote IMUN |
2 |
20 % |
Cette approche nous donnerait de la flexibilité pour modifier la courbe de niveaux des figurines sans que cela ne change leur niveau actuel. Cela faciliterait aussi les visualisations dans l’interface utilisateur en nous permettant de remplir simplement 30 % de la barre de progression, sans calcul supplémentaire. Avec ce type de modèle, on se retrouverait toutefois avec des pourcentages minuscules aux niveaux plus élevés. Lorsqu’une figurine obtient 10 xp par partie et doit en avoir 100 000 pour passer au niveau supérieur, cela correspondrait à 0,01 %. Les unités centrales (UC) peuvent gérer les nombres flottants, mais la précision et l’exactitude peuvent être source de bugs si nous ne prenons pas en compte la nature des calculs en nombres à virgule flottante.
En attendant la suite…
Il y avait de nombreuses options à considérer parmi ce que permet la technologie des base de données, ainsi que les outils à fournir et enfin comment tout stocker et calculer. Comme pour tout projet encore en développement, nous pourrions tout changer plus tard si nous trouvons quelque chose de mieux, mais cela semble être un bon point de départ pour ce jeu.
Merci de nous avoir rejoint pour ces notes d’ingénierie informatique !
~ Andy Lim
Soit dit en passant, veuillez noter que c’est officiel, je ne suis pas le « bandit des yeux remuants ». Quand j’ai rejoint l’équipe, pendant ma première journée, le bandit s’en est pris à mes écrans d’ordinateur tout neufs. Ils m’observent tout le temps… tout… le… temps.