La génération procédurale ou comment le jeu vidéo devient infini

Cela fait maintenant quatre ans que Kurt J. Mac explore le jeu Minecraft en marchant dans la même direction. Depuis mars 2011, ce youtuber a commencé une web série intitulée Far land or bust avec un objectif presque impossible à réaliser : atteindre le bord du monde en partant du centre de la carte. Cinq cent épisodes plus tard, notre randonneur a donc parcouru 2 266 779 blocs qui constituent l’univers de ce jeu soit 2 266 kilomètres si l’on se réfère aux unités de mesure officielles.

À son rythme, Kurt va encore devoir marcher plus de 22 ans pour arriver au pied des Far Lands, les gigantesques falaises chaotiques, dignes d’un roman de Lovecraft, qui marquent la limite du terrain. En effet, si le monde de Minecraft n’est pas infini, sa surface atteint tout de même 3,6 milliards de kilomètres carrés. Dans la version bêta 1.7 utilisée par notre youtuber, la carte ne mesure que 24 000 kilomètres² ce qui donne un trajet total de 12 000 kilomètres en partant du centre.

[large-image]

[/large-image]

Minecraft vs GTA

Mais comment Notch, le créateur de Minecraft, a-t-il pu créer un monde aussi gigantesque, alors qu’il a développé le jeu tout seul ? Facile, il a confié tout le travail à un algorithme.

En effet, tout ce que le joueur voit dans le jeu, depuis le positionnement des arbres, des montagnes et des cavernes, jusqu’à l’apparition des monstres et des ressources qu’il faut miner, s’appuie en fait sur un processus appelé génération procédurale. Au fur et à mesure que le joueur avance sur le terrain, l’environnement qui l’entoure est automatiquement généré à partir de formules mathématiques, de suites de nombres aléatoires et de règles définies par le développeur qui donnent au monde une certaine cohérence.

Pour mieux comprendre cette technique on l’oppose souvent aux environnements de jeux créés « à la main » dans les séries comme GTA, Far Cry ou Assassin’s Creed. Dans ces open world, le terrain est divisé en cases plus ou moins grandes contenant un morceau de terrain et des éléments de décor qui ont été modélisés en trois dimensions puis texturés par des artistes. Une fois le jeu lancé, le joueur évolue alors de case en case, appelées en jargon technique des chunks. Dans GTA, les chunks sont très complexes et détaillées mais se trouvent en nombre limité. Dans Minecraft, elles sont simplement créées à la volée par votre ordinateur ce qui permet d’en produire un nombre quasiment infini tout en économisant du temps de développement.

GTA V

La taille qui compte ?

Le principal avantage de la génération procédurale est de générer des univers virtuels qui, sans être infinis, ont une taille et une diversité propices à l’exploration. Elite Dangerous, une simulation spatiale sortie en 2014 après une campagne de crowdfounding, propose aux joueurs une galaxie à l’échelle 1:1 avec 200 milliards de planètes et d’étoiles. No Man’s Sky, une autres simulation spatiale qui doit sortir en 2016 axe sa communication sur le gigantisme de son monde avec 18 quintillions (18 446 744 073 709 551 616) de corps célestes sur lesquels l’on pourra se poser et que l’on pourra explorer pour découvrir la faune et la flore extraterrestres.

Bref, si l’on s’en tient à ces exemples, on pourrait croire à une nouvelle génération de jeu qui semble profiter de la génération procédurale. Pourtant, l’utilisation de cette technique est loin d’être nouvelle puisqu’elle remonte au début des années 1980 et au boom des rogue-like sur ordinateur.

Elite Dangerous

Dans ces jeux d’aventure et d’action les joueurs explorent un donjon rempli de monstres et de trésors dont la difficulté s’accroît fortement au fur et mesure de la progression. Très punitifs, les rogues like ne permettent pas la sauvegarde. Quand un joueur meurt, il perd son personnage et recommence tout depuis le début. Pour éviter l’ennui et renouveler la difficulté, chaque respawn (réapparition) est sanctionné par un nouveau donjon dont les salles et les couloirs en deux dimensions sont générés de manière procédurale.

Utilisée dès le premier jeu du genre, Rogue, sorti en 1980, cette technique va surtout être connue au yeux des gamers avec Diablo en 1996. Pour la première fois, les niveaux ne sont plus en deux dimensions mais bien en 3D isométrique tandis que les statistiques qui caractérisaient les items du jeux (puissance des armes, niveau de protection des armures, potion…) sont elles aussi générées de manière procédurale.
À présent, les jeux de plateformes et d’exploration comme Spelunky et Terraria ou bien encore les puzzles comme Candy Crush utilisent eux aussi la génération procédurale pour créer des niveaux différents à chaque fois.

Dungen

Merci qui ? Merci Fibonacci

Qu’ils soient en fil de fer, en cube ou ultra réalistes, les univers générés de manière procédurale ouvert sont avant tout gérés par des formules mathématiques et plus particulièrement par des suites de nombres aléatoires. En effet, le défi auquel doivent faire face les créateurs d’open world est la fabrication d’un univers suffisamment varié pour qu’il fasse vrai. Il suffit d’observer la nature pour s’apercevoir qu’elle déteste les lignes droites et les structures identiques.

La génération de paysages ou de systèmes solaires « naturels » demande donc quelques formules permettant de simuler une certaine forme de chaos et de variété. En leur temps, les concepteurs d’Elite utilisèrent la suite de Fibonacci afin de créer des galaxies différentes les unes des autres. Créée par Leonardo Fibonacci  en 1202, cette suite de nombres entiers devait simuler la croissance d’une population de lapins dans un endroit isolé. Fibonacci proposa d’additionner les deux premiers termes de la suite, à savoir le 0 et 1, puis d’additionner la somme obtenue avec le terme précédant. Visuellement, cela donne :

0+1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
etc.

Rapidement, la suite devient une succession de nombres que l’on pourrait décrire comme aléatoires mais qui obéissent en fait à une formule mathématique simple. Pour obtenir une séquence différente, il suffit de commencer la suite avec deux autres chiffres comme le 2 et 7 par exemple. Cette simple variation permet de donner des résultats très différents que l’on appelle dans le jargon une « seed » (graine en français). Il suffit alors de rattacher chaque nombre à une caractéristique spécifique (distance entre les systèmes, taille et composition de votre planète… ) pour générer un nouvel univers. Avant de mettre le jeu en vente, Bell et Braben, les créateurs d’Elite,  passèrent plusieurs mois à jouer aux dieux en générant plusieurs seeds jusqu’à trouver la configuration la plus équilibrée.

Les mathématiques derrière la montagne

La génération de nombres aléatoires constitue la clé principale de la fabrication de mondes procéduraux. Mais entre Elite et Minecraft ou No Man’s sky, de nombreux progrès ont été réalisés pour rendre les paysage plus réaliste. Ainsi en 1980, Loren Carpenter, un chercheur et développeur en informatique spécialisé en graphique numérique a créé la première génération procédurale de terrains montagneux. Si son nom ne vous dit rien, le monsieur est pourtant une pointure du milieu de l’animation qui a travaillé pour LucasFilm puis fondé Pixar et dirigé son département technique. En 1980, alors qu’il travaille pour l’avionneur Boeing, on lui demande de réaliser une démo informatique permettant de visualiser une montagne virtuelle et réaliste.

Il va alors s’inspirer des formules mathématique de Benoit Mandelbrot, un mathématicien à l’origine de la découverte des fractales, ces objets dont la structure morcelée se répète à l’infini. En utilisant le même principe de répétition, Carpenter va modéliser un paysage à partir de gros triangles. Chaque triangle est découpé en d’autres triangles qui sont découpés eux aussi en une multitude de triangles. Le processus est répété une dizaine de fois, au point de former des formes géométriques complexes semblables à des montagnes escarpées. Grâce à cette technique, il produit un petit film de deux minutes intitulé vol libre qu’il présentera à la conférence  SIGGRAPH ce qui lui vaudra une standing ovation et son poste chez LucasFilm. Il utilisera plus tard la même technique pour modéliser le vaste paysage d’une planète dans Star Trek II , la colère de Khan en 1982.

Faites du bruit !

Toujours à la même période, l’informaticien et spécialiste de l’animation Ken Perlin travaille quant à lui sur le film Tron. Lui aussi est limité par la puissance et la mémoire des machines qui ne lui permettent pas de créer des textures complexes pour les séquences se passant dans l’ordinateur. En 1985, il va donc créer un algorithme, basé lui aussi sur les nombre aléatoires, permettant de créer du bruit graphique. En superposant plusieurs couches de bruit de Perlin, on obtient une texture aux motifs variés et colorés permettant simuler de manière réaliste la terre, l’herbe, de la fumée ou des nuages. Le bruit peut aussi être décliné en trois dimensions afin de générer des terrains montagneux et même des cavernes. C’est en partie cette méthode qui a été utilisée par Notch dans Minecraft pour créer ses paysages variés plein de vallées, de falaises et de grottes.

Pour créer ces environnements, sans manger l’intégralité la mémoire de votre ordinateur, le code les génère à la volée, c’est-à-dire au moment où il faut l’afficher sur le moniteur. Quand une partie de Minecraft se lance, le moteur génère un chunk de 16 blocs sur 16 avec une profondeur de 128 blocs seulement. Au fur et à mesure que le personnage progresse, de nouveaux chunks sont générés. Les joueurs utilisant un code permettant de voler et se déplacer rapidement, peuvent assister à cette génération qui donne l’impression que le paysage émerge comme par magie. Une fois qu’ils sont générés, les endroits visités et modifiés par le joueur sont gardés en mémoire. À moins de jouer comme Kurt J. Mac, dont la sauvegarde de terrain dépasse les 18 gigaoctets, le jeu est donc plutôt sobre en ressources.

Le chaos ordonné

Générer du terrain c’est bien, le rendre cohérent, c’est encore autre chose. En effet, quand on parle de génération procédurale, on évoque souvent le terme de génération aléatoire, en référence aux nombres aléatoires qui sont utilisés dans le processus. Or, si la nature déteste les lignes droites, elle déteste tout autant le chaos total. Les montagnes, les cavernes ou les rivières sont le fruit de processus naturels que les développeurs peuvent tout à fait intégrer dans leur code grâce à un ensemble de règles. Pour comprendre comment fonctionne le système, on peut utiliser l’analogie de la recette de cuisine.

Chaque ingrédient représente un élément particulier de votre univers comme la taille d’une planète, la composition chimique de son atmosphère, etc. Une fois que les ingrédients sont définis il suffit d’utiliser une série de règles logiques pour les faire interagir entre eux de manière cohérente. Pour No Man’s Sky, Sean Murray explique que toutes les planètes de son jeu ne sont pas propices à la vie. Pour cela, elles doivent être générées à la bonne distance du soleil et contenir de l’eau à l’état liquide. La faune et la flore répondent aussi à des règles logiques liées à la théorie de l’évolution. Les animaux sont bipèdes ou quadrupèdes, ils vivent et développent des caractéristiques en fonction de la température de l’air. Une planète froide engendrera des animaux à fourrure par exemple.

À ce niveau, le rôle du développeur devient alors celui d’un chef d’orchestre qui doit faire fonctionner ses algorithmes ensemble et sans fausse note.

[large-image]

[/large-image]