Systèmes de replays dans les jeux vidéo
Concepts de base, méthodes et problématiques
TENORIO DE ALBUQUERQUE Thales Alex - Mémoire Master 1ere année
Master « jeux et médias interactifs numériques » cohabilité par le Conservatoire national des arts et métiers, l’Université de Poitiers et l’Université de La Rochelle
Remerciements
Je remercie premièrement à mon petit copain Felipe Moura qui m’a aidé dans tout le parcours jusqu’au moment, pour être patient avec tous mes <<je ne peux pas maintenant parce que…>> et pour m’avoir donné plusieurs moments de bonheur <3.
Je remercie aussi à ma famille qui me motive chaque jour et que croient en moi (love you).
Je remercie à Athenais Jan pour être une bonne compagnie et aussi de m’avoir donné les moyens pour arriver jusqu’à ici :)
Sommaire
2.1. Enregistrer Chaque État (ECE)
2.2. Premier État et Ressimulation (PER)
2.2.2 Pseudo Random Number Generators (PRNG).
2.2.4 Les actions et décisions des IA’s
3. Interactions avec le replay
3.4 Explorer le scénario et bouger la caméra
4. Reproductibilité et Debugging
5. Optimisations et compressions
Ce mémoire présentera une vision résumée et claire des principaux concepts et problématiques pour tenir en compte lors du développement d'un système de replay pour un jeu vidéo. L’objectif du mémoire n’est pas d’être exhaustif et si d’introduire le sujet et d’être une référence à d’autres références. Dans le deuxième chapitre, nous allons parler des quelques concepts bases pour le développement d’un système de replay, deux moyens simple pour le faire et les problématiques de chacun. Ensuite, le troisième montrera des possibles fonctionnalités que nous pouvons avoir dans un système de replay et l’approche pour implémenter chacune. Après, dans le quatrième, nous expliquerons un peu de l’importance d’un système de replay pour le développement d’un jeu vidéo. Le cinquième donnera une petite introduction à des possibles optimisations pour l'enregistrement d’un replay. Enfin, la conclusion du travail de recherche. Ce mémoire est basé sur des recherches sur l’internet, principalement des game dev blogs comme Gamasutra, et aussi sur mon expérience personnelle.
Pour pouvoir développer un système de replay il faut tenir en compte deux moyens de le faire : enregistrer l’état de toutes les entités à chaque cadre (utilise beaucoup de mémoire), ou enregistrer le tout premier état et toutes les actions qui modifient cet état et les états suivants (système déterministe) [1]. Après, nous verrons comment mélanger ces deux manières pour arriver à des fonctionnalités plus complexes.
Avant parler des chacun de ces deux approches, c’est important de définir ce
que c’est un état et ce que c’est une action. Dans l’image 1, nous pouvons voir
que l’état du jeu (game state) c’est l’ensemble de l’état des toutes les
entités du jeu, par exemple la position, la rotation, l'échelle et la vitesse
de l’entité contrôlée par les joueurs, les données connues par les
intelligences artificielles (IA’s) et leurs état. Les entrées (inputs)
sont les données reçues des joueurs ou d’autres sources externes. Le temps de
jeu et le temps depuis le dernier cadre (frame) peuvent être considérés
comme des inputs, mais cela dépendra de comment la personne développe le jeu,
nous parlerons de cela plus tard dans l’article.
Image 1: Les entrées, l’état du jeu et les sorties (image adaptée de [2])
Maintenant que nous avons parlé de ce que c’est un game state et un input, nous pouvons avancer aux façons de faire un replay.
Imaginons une athlète qui court dans une épreuve d'athlétisme de 400 mètres haies et nous voulons faire un replay de sa performance. Pour y arriver, nous avons juste besoin de, à chaque instant prendre des notes de la distance de l’athlète par rapport au début, la pose qu’elle faisait, la hauteur par rapport au sol, la position et la pose des obstacles. Après, pour reproduire la même situation, il va falloir faire une reprise de tout cela en ordre (imaginons qu’on a des cordes pour suspendre l’athlète dans l’air). Si cela était dans un jeu vidéo, chaque à frame nous enregistrions toutes ces informations sur mémoire.
Le problème de cette méthode est que selon le type de jeu vidéo, la quantité de mémoire nécessaire va être trop grande. Disons que le match d’un jeu de course de voitures aurait une durée de 300 seconds à 60 frames par secondes, cela veut dire, 18000 frames au total. Disons aussi que pour enregistrer l’état d’une voiture nous avons besoin de 1KB. Disons encore que pour le circuit nous avons besoin de 4KB. Cela fait un total de 10KB par frame ce que veut dire que pour tout le match, nous allons avoir besoin d’environ 200MB, juste pour un replay de 5 minutes [1]. Il faut tenir en compte qu'il est possible de faire des compressions, mais cela dépendra du type de jeu vidéo et ne sera pas facilement portable à un autre.
Pros :
Contres :
Pour expliquer cela nous allons prendre le même exemple de l’athlète ci-dessous. Au lieu de prendre note de chaque attribut, nous allons enregistrer le premier état du jeu et toutes les actions responsables pour le changer. En d’autres termes, le départ, les sautes et les moments où l’athlète augmente ou diminue sa vitesse. Comme cela nous pourrons reproduire la même situation (vu que toutes les actions et l’état initial seront les mêmes).
Comme est dit en [3], pour mieux comprendre cela, on va définir les états comme s [ j ], les fonctions comme f [ j ] les inputs des fonctions comme x [ j ], où le j est le frame actuel. Pour avancer d’un état à l’autre, nous utilisons s [ j + 1 ] = f [ j ] ( s [ j ] , x [ j ] ). Dans le cas de l’athlète, l’état initial (s0) c’est le départ, les fonctions sont s'élever, augmenter vitesse, diminuer vitesse, sauter et atterrir, chacune avec ses respectifs paramètres. À partir du premier état (s0), le départ de l’athlète, nous prenons l’action utilisée par l’athlète dans le moment j = 0, cela veut dire, f0 et x0. Si nous appliquons f0 à s0, nous arrivons à s1, l’état où l’athlète est déjà avec une vitesse et n’est plus au début. Dans s60, par exemple, il y a un obstacle proche, et la f60 c’est un saute réalisé par l’athlète, et à partir de là nous l’athlète commence à sortir du sol dans les états suivants (s61, s62…).
Dans le monde réel il est difficile de reproduire une même situation de la même façon. Par contre, les jeux vidéo sont des logiciels, et les logiciels sont des systèmes déterministes, cela veut dire que avec les mêmes inputs on aura les mêmes outputs. Par contre, il est possible qu’un logiciel acte comme non-déterministe, par exemple, s’il utilise des Pseudo Random Number Generators (PRNG) parce que généralement ce n’est pas un input et si quelque chose interne que nous ne contrôlons pas forcément [3].
Cette méthode demande une attention spéciale au déterminisme du jeu. Il faut identifier toutes les partis du code qui ne sont pas déterministes et vérifier si elles vont interférer dans la ressimulation. Par exemple, il est possible que même l’utilisation d’un float change la séquence des événements, nous expliquerons cela dans la prochaine section. Il y a aussi les PRNG et les moteurs de physique. Dans Starcraft - Brood War, par exemple, un replay d’un match contre une IA, qui a été enregistré sur la version sans expansion, ne marcherais pas de la même façon, parce que dans Brood War, l’IA avait accès à plus d’unités différentes [4].
Les floats peuvent varier d’un ordinateur à l’autre, et aussi dans des systèmes opérationnels différents. Cela arrive à parce que, parfois, ils ont une représentation interne différente par rapport à la plateform. À cause de cela, il est possible qu’un replay ne soit pas ressimuler de la même manière dans une machine différente, par exemple, Windows et Mac OS [5]. Pour éviter les problèmes avec les floats nous pouvons les remplacer par des integers (point fixé) pour représenter l’état du jeu (et aussi les inputs) [2].
Un PRNG est basé sur un seed pour générer des chiffres aléatoires, donc si on utilise le même seed nous allons avoir la même séquence. Pour un système simple de replay, cela veut dire des replay que ne font qu’avancer, c’est suffi d’enregistrer le seed et d’utiliser le même, mais nous allons voir dans les prochaines chapitres les manières de le faire plus élaboré. Il faut tenir en compte aussi que nous ne devons pas utiliser le même PRNG utilisé dans la partie non-déterministe du code (le rendering, le son, le moteur physique) [1].
Dans l’image 1 nous pouvons remarquer que l’entrée << temps >> est avec une étoile à côté, pour indiquer qu’il n’est pas un input obligatoire. Le besoin du temps, ou de la variation du temps par rapport au dernier frame, dépendra du code. Si les frames n’ont pas un temps fixé, il vaudra mieux l’utiliser comme input parce que dans la reproduction du replay, il est possible que l’ordinateur soit plus chargé et lent que quand les inputs ont été enregistrés, et, si c’est le cas, nous n’aurons pas le résultat attendue. Par contre, si le temps est fixé pour chaque frame, nous n’avons pas besoin de l’enregistrer [1].
Comme nous avons déjà dit ci-dessus, les logiciels et les algorithmes sont déterministes, par conséquent, si nous avons les mêmes inputs, les états vont être les mêmes et les IA’s vont prendre les mêmes décisions et vont réaliser les mêmes actions. Donc les décisions des IA’s sont considérés comme un état du jeu (voir l’image 1).
Maintenant que nous avons montré les concepts de base pour développer un système de replay simple, nous allons expliquer comment utiliser ces concepts pour ajouter des fonctionnalités plus complexes.
Pros :
Contres :
Plusieurs jeux vidéo ont un système de replay où nous pouvons reculer, changer la vitesse de reproduction et aussi choisir le point de reproduction dans la ligne de temps. Mélanger les concepts décrits au chapitre 2, nous permettra de développer ces fonctionnalités. Les prochaines sections vont expliquer avec plus de détails l’approche pour chacune de ces interactions, basée sur ce qui est dit en [3].
Le Random Seek est une fonctionnalité que nous permet de choisir un point dans la ligne de temps d'exécution du replay et le reproduire à partir de ce point. Si nous utilisons la méthode ECE, nous n’avons pas beaucoup de travail à faire. Disons que nous avons choisi le frame j = 139, il faut justs prendre l’état s[139] et le restaurer. Par contre, si nous avons choisi la méthode PER cela sera un peu plus compliqué.
Avec la méthode PER, nous avons que le tout premier état du jeu enregistré, le s[0], et pour arriver au s[139], il faudra calculer les états s[0], s[1]...s[138]. Cela peut prendre un peu de temps mais nous pouvons l’optimiser avec quelques états intermédiaires. Imaginons que nous avons un paramètre Q qui va indiquer la fréquence que nous allons enregistrer un état, cela veut dire, si j % Q == 0, nous le gardons. Si par exemple Q = 100, nous enregistrerons les états s[0], s[100], s[200], etc. Maintenant, pour avoir le s[138] nous allons prendre le s[100] et calculer les états de s[100] à s[138] et appliquer les fonctions f[138] et les inputs x[138] pour trouver le s[139]. Plus Q est petit, plus vite nous aurons le résultat, par contre, nous utiliserons un peu plus de mémoire.
Pour lancer le replay à l’inverse, nous pouvons utiliser la même approche que le random seek. Disons que Q = 100 et nous voulons jouer un replay à l’inverse du frame j = 150 au frame j = 90. Pour cela, il faut prendre le s[100] et calculer le s[150], après nous prenons le s[100] pour calculer le s[149], etc. Ainsi, nous aurons le replay à l’inverse mais cela peut prendre un peu de temps.
Pour optimiser la reproduction,
nous allons utiliser une mémoire cache pour enregistrer tous les états que nous
avons calculé pour arriver de s[100] à s[150], en d’autres
termes, enregistrer s[100], s[101], … , s[149]. De cette façon, quand
nous voulons afficher le s[149], il sera déjà dans la cache parce que
nous avons déjà le calculer pour trouver le s[150]. Cela sera pareil
pour les frames j = 90 à j = 99. Encore, plus Q est petit,
plus vite sera le calcul et aussi plus petite sera la mémoire cache.
Pouvoir changer la vitesse de reproduction d’un replay est une fonctionnalité très utile, soit pour regarder plus attentivement les événements qui arrivent, soit pour ne pas perdre trop de temps pour trouver quelque chose d’intéressante. Pour comprendre la méthode de comment faire cela, il est important de préciser que l’update de l’image du jeu (rendering) ne doit pas être le même que ce de la logique du jeu. Ainsi, si nous voulons regarder un replay avec une vitesse de 2x, nous allons exécuter deux fois l’update de la logique du jeu à chaque update de render. Si nous voulons l’inverse, plus lent, par exemple avec une vitesse de 1/2x, nous allons exécuter un update de la logique à chaque deux update de render. Dans le cas d’une système ECE, nous ignorons un de chaque deux états pour aller plus vite et nous utilisons le même état deux fois pour aller plus lentement.
Dans quelques jeux vidéo, comme par exemple les Real Time Strategy (RTS), il est possible de regarder le replay comme si nous étions des spectateurs. Nous pouvons bouger la caméra et sélectionner des entités du jeu, mais sans rien changer (mode lecture). Par contre, il faut faire attention si le jeu utilise la caméra ou les clicks comme input, pour ne pas interférer dans le gameplay qui est déjà arrivé. Pareil pour tous les outputs (les sons, les images) qui font parti de l’ensemble des inputs, si c’est le cas.
Chaque jeu aura des difficultés spécifiques pour s’adapter à un système de replay, mais les concepts ci-dessus sont très importants pour commencer. Dans le prochain chapitre, nous parlerons un peu de l’importance d’avoir un système de replay.
Dans le monde du développement des jeux vidéo il y a toujours des bugs difficile ou presque impossibles de reproduire. Parfois, la raison c’est le non-déterminisme, ou sinon, c’est juste que le bug a été trouvé après une heure de gameplay. Avec un système de replay nous serons toujours capables de reproduire exactement tous qui est arrivé quand le bug est apparue. Par contre il faut faire attention à ne pas avoir de bugs dans le système replay.
Même si nous choisissons utiliser le système PER, il est très important d’avoir une manière d’enregistrer l’état du jeu et de le restaurer après. Disons que tous les objets vont avoir une fonction save_state, pour enregistrer l’état de l’objet, et une autre load_state, pour récupérer l’état de l’objet. Après cela, nous ajoutons une fonction assert_state, qui va vérifier si un état est égale à un autre. Comme cela, chaque objet saura comment s’enregistrer, se récupérer et vérifier il même s’il est correct.
Une fois que le système de load/save state est fait, nous avons déjà une façon de reproduire un bug (si nous utilisons le ECE) et aussi, nous pouvons commencer à développer le système de replay PER avec sécurité. Pour cela nous allons, à chaque frame, vérifier si les inputs enregistrés pour le frame actuel appliqués sur l’état actuel du jeu, donnent comme résultat l’état attendue pour. Disons que nous avons tous les états du jeu enregistrés et nous voulons reproduire le replay, donc nous avons les assert state de as[0] à as[t] avec t = nombre total de frames. Á chaque frame, dans le mode replay, nous allons appliquer les inputs correspondants au frame et à la fin, faire la comparaison avec le full state déjà enregistré. Par exemple, pour le frame j = 50, nous allons prendre le s[49] pour calculer le s[50] et après, vérifier si s[50] est égale à as[50]. Toutes les différences trouvées devront être sauvegardés pour pouvoir identifier où le replay commence à différer du vrai gameplay.
Avec un système comme cela, il sera beaucoup plus facile de résoudre des bugs et aussi, il sera plus simple de trouver des partis non-déterministes du code. De plus, cela va faciliter le travail de créer un jeu multijoueur [2]. Dans le prochain chapitre nous allons parler de quelques optimisations que nous pouvons faire pour réduire la quantité de ressources de mémoire utilisés par un système de replay.
Comme nous avons déjà dit dans cet article, la façon que nous allons faire un système de replay dépendra du jeu, de la plateforme cible, quantité de ressources par rapport à cette plateforme et aussi, des fonctionnalités désirées. Une fois que nous détectons tout cela, nous verrons la manière la plus favorable. Il est important de faire des compressions si, par exemple, nous voulons faire un streamming d’un match ou si nous n’avons pas beaucoup de ressources de stockage.
S’il est décidé de faire un système ECE, d’abord, il faut détecter tous les objets du jeu et toutes leurs propriétés qu’ont besoin d’être enregistrés. Ensuite, pour utiliser moins de place, nous pouvons, au lieu d’enregistrer toutes les données à chaque frame, nous enregistrons juste la variation depuis le dernier frame, cela veut dire, si un objet n’a pas changé depuis le dernier frame, nous ne l’enregistrons pas. Par contre, une implémentation comme cela n’est pas très idéale si nous voulons faire du random seek, parce que il va falloir calculer tous les états à partir du dernier état complet que nous avons enregistré et appliquer les variations, comme dans le PER. Pour un RTS, c’est pas très astucieux d’utiliser la méthode ECE, parce que il y a une grande quantité d’unités et normalement les matchs ont une durée entre 20 et 40 minutes à 60 FPS. Braid a été fait avec cette méthode là et un peu de compression [6].
Pour la méthode PER, tout que nous avons besoins d’enregistrer à chaque frame c’est l’état des contrôleurs d’input et le delta time, normalement. Il faut pas oublier d’enregistrer le premier état du jeu et le seed pour le PRNG et aussi, les états intermédiaires si c’est le cas. Prenons un match de League of Legends (LoL), avec 10 personnes. Nous allons simplifier les inputs pour expliquer cela et nous allons assumer que chaque personne a comme input les touches A, Z, E et R, clique droite et clique gauche. Chacun de ces inputs peut être stocké comme un boolean, appuyé ou pas appuyé. Si nous faisons les calcules, cela donnera 6 booleans par personne, donc 60 booleans et, si la taille d’un boolean est de 1 byte, nous aurons 60 bytes per frame.
Disons que le framerate logique de LoL est de 60FPS et que les matchs ont une durée de 30 minutes environ, cela donnerait 108000 frames * 60 bytes, donc 6MB environ. C’est pas trop pour un jeu comme LoL, mais nous allons montrer quand même une façon de le comprimer. Un boolean peut être représenté par un bit, donc si nous avons 60 booleans par frame, nous pouvons réduire cela à 60 bits par frame, 7 bytes environ, donc 0.7 MB. Il faut pas oublier le temps, normalement représenté avec un float mais qui peut être optimisé à un byte, avec un range de 0 à 255.
Pour créer un système de replay pour un jeu vidéo, il faut tenir en compte deux manières basiques pour le faire : soit nous enregistrons l’état de toutes les entités à chaque cadre, soit nous enregistrons le premier état complet (de tous les objets) et aussi les entrées des joueurs, le seed du PNRG et de quoi que ce soit considérés comme entrée. Il est important de savoir que même si nous ne voulons pas faire une fonctionnalité de replay dans notre jeu, un système comme cela peut nous aider beaucoup à trouver des bugs plus facilement, soit pour pouvoir le reproduire, dans le cas des deux méthodes ECE et PER, soit pour pouvoir trouver le point non-déterministe du code, dans le cas de la méthode PER. Il faut aussi tenir en compte que chaque jeu aura son niveau de difficulté pour implémenter le replay. L’objectif initial c’était de après avoir fait la recherche, écrire un tutoriel de comment faire, petit à petit, un système de replay sur Unity, mais j’ai décidé de ne pas le faire parce que c’était plus important d’avoir une recherche plus approfondie en termes théoriques pour un moment futur. Avoir recherché ce sujet m’a fait comprendre l’importance d’un système de replay comme outil de détection et reproduction des bugs et je vais utiliser cela chaque fois que j’ai l’opportunité.
[1] http://www.gamasutra.com/view/feature/130442/developing_your_own_replay_system.php
[2] http://www.gamasutra.com/view/feature/3057/instant_replay_building_a_game_.php?print=1
[3]
http://gamedev.stackexchange.com/questions/6080/how-to-design-a-replay-system#answer-8372
[5] http://gamedev.stackexchange.com/questions/6080/how-to-design-a-replay-system#answer-8315
[6]