En poursuivant votre navigation, vous acceptez l’utilisation de cookies qui permettront notamment de vous offrir contenus, services, et publicités liés à vos centres d'intérêt.

En savoir plus
La science derrière les univers infinis

Depuis la sortie de Minecraft, les jeux vidéo dont les univers virtuels gigantesques peuvent être explorés pendant des années sans jamais en voir le bout ont le vent en poupe. Mais quels peuvent bien être leurs secrets de fabrication ?

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.

 



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

Daggerfall, le « plat pays »
du jeu vidéo

Idéale pour les jeux avec des niveaux en deux dimensions, la génération procédurale a cependant rarement été utilisée pour simuler des mondes ouverts en 3D. L’un des premiers à marquer le coup reste le premier épisode d’Élite sorti en 1984. Si ses graphismes en fil de fer font mal aux yeux, le jeu était considéré à l’époque comme une véritable prouesse . Les joueurs pouvaient explorer 8 galaxies contenant chacune 256 systèmes solaires soit 2500 mondes représentés en 3 dimensions. À l’époque, la mémoire des machines étaient extrêmement limitée et le jeu tenait sur une disquette de 20 ko.

En 1996 c’est le jeu Daggerfall, de la série des Elder’s Scrolls, qui propose aux joueurs un continent entier, généré de façon procédurale. Nous sommes 10 ans après Élite et les graphismes ont fait un bond en avant. Le joueurs sont invités à parcourir un territoire de 45 000 kilomètres² contenant 15 000 villes ou donjons et plus de 750 000 personnages avec qui interagir. C’est la première fois qu’un jeu offre au public un large univers en trois dimensions aussi détaillé.

Malgré son succès, Daggerfall marque pourtant une limite dans l’utilisation de la génération procédurale. Même gigantesque, le monde s’avère souvent répétitif et presque sans aucun relief. Les quêtes secondaires, elles aussi générées de façon procédurale, finissent par se ressembler puisqu’elles sont en fait un assemblage de 300 éléments prédéfinis à l’avance.

Minecraft va bien évidement changer la donne à sa sortie en 2009. Pour la première fois depuis Daggerfall, un jeu vidéo propose un univers ouvert gigantesque, presque impossible à explorer intégralement et surtout extrêmement varié dans ses environnements avec des montagnes, des cavernes gigantesques et des biomes différents allant de la jungle à l’océan en passant par le désert.

Et pour comprendre cette évolution, il faut passer du côté des développeurs.

dagger

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.

Bruit graphique : De manière générale, le bruit graphique est un ensemble d’éléments visuels qui n’est pas porteur de sens et qui pollue en quelque sorte l’image dans laquelle il est situé. L’exemple le plus connu de bruit est celui de la « neige » qui s’affichait sur les anciennes télévisions qui étaient en état de marche mais ne recevaient aucun signal.

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.


No-Mans-Sky

L’avenir du jeu vidéo
(ou pas) ?

Avec les outils de génération procédurale actuels il est donc possible de simuler une galaxie entière depuis ses clusters d’étoiles, à une simple étendue d’herbe sur une planète paumée. D’un simple clic on peut saisir les distances astronomiques qui séparent les systèmes solaires les uns des autres et explorer le cosmos. Mais est-ce que cela suffit pour faire un bon jeu ? La question se pose particulièrement pour No Man’s Sky qui fonde son gameplay sur l’exploration, le minage de ressources et l’amélioration de son matériel, un peu à la manière de Minecraft.

Mais quand on analyse le succès de ce dernier, on comprend que c’est le mode multijoueur et la possibilité de construire des bâtiments avec ses amis qui ont fait le sel du jeu — pas forcément l’exploration. Cela ne sert à rien de le cacher : même si les paysages de Minecraft sont plus variés que les décors de Daggerfall, ils finissent toujours par devenir répétitifs et monotones. Et à moins de considérer la découverte et la contemplation comme un style de jeu à part entière, No Man’s Sky prend lui aussi le risque d’ennuyer fermement les joueurs.

Pour éviter cet écueil et inscrire son Dual Universe dans la durée comme Minecraft, le physicien et ingénieur Jean-Christophe Baillie a développé une toute autre approche pour son jeu. S’il offre bien une galaxie complète et des planètes générées de manière procédurale, les joueurs devront avant tout survivre et construire une civilisation entière avant d’aller explorer les confins de l’univers. « On est en train de créer une seule et même réalité partagée par des milliers de joueurs qui joueront dans le même monde, nous explique-t-il. Avant d’aller voir le bout de la galaxie, les joueurs devront commercer, échanger, s’organiser. Si vous voulez des pièces détachées pour votre vaisseau, des minerais pour votre usine ou pour construire votre base spatiale, il y a de grandes chances que vous ne puissiez pas tout faire en autarcie. »

Si le terrain de jeu est infini, les développeurs laissent finalement l’univers aux mains des joueurs qui devront gérer la récolte de ressources, l’économie, la politique, l’architecture et la construction des villes et des vaisseaux. Une manière plutôt intelligente de réintroduire de l’humain, dans un jeu entièrement généré par une machine.

Et entrevoir l’avenir du jeu vidéo ?


03_explorer

Commentaires

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

  • Voir la discussion complète
  • Très bon article, qui donne juste assez de détails techniques pour que ce soit intéressant, mais pas assez pour que ça devienne incompréhensible. Toutefois, je n'ai pas pu m’empêcher de tiquer à chaque fois que j'ai lu "shunk", le terme étant "chunk". Autre petit détail sans grande importance, la génération des chunks Minecraft se fait maintenant sur 256 niveaux.

    • C'est corrigé, merci :smile:

  • Petite erreur dans la suite de Fibonacci : la 5e opération est 3+5=8 et la 6e sera 5+8=13.

    Sinon, article très intéressant, merci !

  • Bah après entre un univers immense, même si il est cohérent, qui reste générique et un univers à la GTA V où on reconnaît des clins d’œil des levels designers, des easters eggs ou des ref dans le moindre positionnement de cailloux, perso j'ai choisis.

    Un algo ne remplacera jamais la création artistique et l'originalité.

    • Pas si sûr, il existe aussi des modèles hybrides où la génération procédurale fait le "gros" du travail, puis un level designer passe par dessus pour améliorer certaines zones où les rendre utilisable d'un point de vue narratif.

      Le jeu ne stockant que la différence entre les deux.

  • Ce qui n'a pas encore été fait (je crois), c'est de combiner ces méthodes. Cela permet en théorie d'accroître grandement la taille d'une carte de jeu tout en conservant un niveau de détail et de choix de la part des concepteurs.

    Ce serait - en théorie toujours - assez facile : les développeurs et designers créent à la main des dizaines de lieux mémorables :
    - une grotte avec une cascade sous-terraine et un réseau de rivières
    - une ancienne pyramide oubliée
    - un village de pêcheurs
    - une oasis luxuriante
    - etc.

    Puis, il suffit d'utiliser la génération procédurale décrite dans cet article pour lier ces différents lieux. On s'épargne ainsi la peine de "dessiner à la main" des environnements au final peu intéressants, tels que des routes marchandes ou des kilomètres de dunes.

    On prend donc un terrain procédural, généré "à la demande" par le PC du joueur, et on inclut en plus un algorithme pour dynamiquement injecter des "lieux-clés" dessinés à la main dans ce terrain.

    Tada !

    Non ? :smiley:

  • 24.000 km² = 155km de long, 155km de large. Soit 77km depuis le centre pour atteindre un bord.

  • Merci pour ce bien bel article !

    Vivement la génération procédurale appliquée à des jeux comme GTA. Le concept de No Man’s Sky a l'air très sympa.

  • Un blog d'un développeur de jeu qui relate les différentes étapes et expérimentations du contenu généré par algo :

    http://www.introversion.co.uk/subversion/

    Génération de villes, de l'intérieur d'immeuble, génération procédurale de la musique d'ambiance selon l'état du jeu, j'avais trouvé ça intéressant.

  • Très bon article, merci. Il m'a donné envie de tester No Man's Sky et Dual Universe.

  • Un bien bel article, très intéressant. Je joue à élite et je me demandais justement quelle était leurs techniques procédurales quand ils avaient généré la Galaxie.

  • Passionnant.

  • Disons que la partie sur les suites de Fibonacci n'est pas très intéressante. Tous les langages informatiques proposent un générateur de nombre pseudo-aléatoire et une possibilité de l'initialiser à une valeur donnée. Tous les nombres générés à partir d'un init particulier seront toujours les mêmes, le décor d'une zone sera donc toujours identique à un init près. Si on veut utiliser un décor montagneux de type fractal il suffit de mémoriser l'init de la zone pour recréer toujours la même montagne, quelque soit sa taille virtuelle.

  • Voir la discussion complète

En cours (15 min) : La génération procédurale ou comment le jeu vidéo devient infini