Balthazar-Hippolyte a toutes les raisons d’être heureux. Il vient de recevoir BabelWorks, ce titre dont il espérait la sortie depuis des mois. L’idée de ce jeu – parfaitement imaginaire – est inspirée par La Bibliothèque de Babel, l’une des plus célèbres nouvelles de Jorge Luis Borges (1899-1986), nouvelliste et poète argentin dont les préoccupations n’étaient pas très éloignées du sujet de cette histoire. La bibliothèque qui donne son nom au texte est constituée de tous les livres de 410 pages possibles, c’est-à-dire tous ceux qu’on peut écrire en utilisant les lettres de l’alphabet latin, l’espace, la virgule et le point à raison de 3 200 signes par page.

Comme elle contient toutes les œuvres pouvant exister, on y trouve « le catalogue fidèle de la Bibliothèque, des milliers (…) de catalogues mensongers, la démonstration de la fausseté de ces catalogues, la démonstration de la fausseté du catalogue véritable, (…) l’histoire exacte de ta mort ». De la même façon, un jeu combinant aléatoirement tous les éléments (visuels, sonores, narratifs…) possibles serait le jeu ultime, puisque pouvant générer n’importe quel univers. Bien sûr, quasiment tous les livres de la bibliothèque sont remplis de phrases aussi pertinentes que « mvyxv afbqdmetivcndmah » et la plupart des univers produits par un jeu fonctionnant sur le même principe n’auraient aucun sens. Telle est la grande beauté et la grande faiblesse de la combinatoire.

generation-procedurale-ulyces-02

La galaxie spirale barrée NGC 1300
Crédits : NASA

BabelWorks n’est pas un jeu de plus. C’est le jeu, celui qui se vendra à des millions d’exemplaires et dont la simple évocation suffit à terrifier les éditeurs concurrents. Sitôt la porte de son appartement refermée, Balthazar lance l’installation. Quelques minutes plus tard, le temps de copier le petit giga-octet de données que représente le jeu, le menu principal apparaît sur l’écran. Après quelques secondes d’hésitation, Balthazar décide que sa première partie se déroulera dans un univers médiéval-fantastique, sur une île dont le centre seul aura été colonisé, les régions extérieures restant mystérieuses et inviolées.

Le climat y sera chaud et humide, les terres émergées couvertes d’une épaisse jungle, et la capitale du royaume déchirée par des luttes entre prétendants au trône. Quelques minutes plus tard, BabelWorks a fini de générer le monde de jeu et le personnage de Balthazar s’apprête à fouler le sol d’une terre qu’aucun autre joueur n’a vue avant lui. Ce week-end, se dit notre joueur béat, j’essaierai un univers cyberpunk, pour changer.

Génération procédurale

Science-fiction ? Pas du tout. Si BabelWorks n’existe pas encore, aucune limite technique n’empêche, à l’heure actuelle, sa réalisation. Encore mieux : sous une forme ou sous une autre, de nombreux jeux ont recours à ce que l’on qualifie de génération procédurale, et cela depuis des années. Avant d’examiner tout cela plus en détail, prenons le temps d’une définition. On appelle génération procédurale toute technique permettant l’automatisation d’un processus de création, l’algorithme y remplaçant le cerveau humain.

Si on prend le terme dans son acception la plus large, la génération procédurale concerne quasiment n’importe quel jeu : l’éclairage dynamique utilisé par les moteurs graphiques récents, calculé en temps réel à partir de la position et des caractéristiques de sources lumineuses, en fait partie. Les moteurs physiques, qui tendent à se généraliser, sont un autre triomphe de la génération dynamique. Pendant des années, les ennemis fauchés par les rafales rageuses de M16 s’effondraient toujours de la même façon : le jeu se contentait de choisir une animation de mort aléatoirement parmi la poignée créée par les graphistes. Désormais, l’usage de ragdolls (« poupées de chiffon ») garantit que chaque ennemi abattu tombera de façon inédite, en fonction de la localisation de l’impact ayant mis un terme à son existence, de la répartition de sa masse et des obstacles se trouvant éventuellement sur la trajectoire de sa chute.

generation-procedurale-ulyces-04

La galaxies des Antennes
Crédits : NASA

On pourrait pousser encore plus loin et considérer que l’essence même d’un jeu, l’interactivité, suppose la création dynamique de situations à partir de quelques paramètres. Tout véritable jeu vidéo serait alors une vaste machine à générer, de façon procédurale, des situations inédites. Contentons-nous pour le moment de nous intéresser au cas de la génération procédurale de contenu, que nous définirons (car les définitions sont nombreuses et parfois contradictoires) comme la capacité d’un programme à générer dynamiquement des éléments artistiques et scénaristiques.

Les années 1980 et la première moitié des années 1990 ont représenté l’âge d’or de la génération procédurale, tout simplement parce que le matériel de l’époque était terriblement limité. Lorsque l’espace mémoire se compte en kilo-octets, y stocker la géographie d’un pays entier relève de l’utopie. Les programmeurs ont donc eu recours à la génération procédurale pour économiser de la mémoire. Un bon exemple est The Sentinel (Firebird, 1986) qui ne contenait, en guise de niveaux, qu’autant de graines, le programme appliquant un algorithme de façon récursive pour générer les caractéristiques de chaque carte. Résultat : dix mille niveaux différents n’occupaient que 64 kilo-octets. Elite (Acornsoft, 1984) poussa la même idée encore plus loin. L’univers de jeu devait à l’origine comporter 2 puissance 48 (soit un nombre à quinze chiffres, tout de même) galaxies, chacune d’entre elles contenant 256 systèmes stellaires.

Anecdote amusante, ce n’est pas une limitation technique qui contraignit les développeurs à se contenter de huit galaxies dans la version finale mais leur éditeur, qui craignait qu’un univers aussi gargantuesque ne terrifie les joueurs. Alors qu’acheter un giga-octet de RAM est devenu aussi banal que faire le plein de tomates au marché et que sort chaque mois ou presque un nouveau format de DVD doublant la capacité de la génération précédente, avons-nous encore besoin de recourir à cet équivalent numérique de la mnémotechnie ? Étonnamment, oui. Sans l’usage, même modéré, de la combinatoire et d’éléments générés de façon procédurale, même les supports actuels ne feraient pas le poids face à la masse de données des jeux vidéo modernes. Si la génération purement procédurale est passée de mode, c’est pour une autre raison, une raison qu’avait déjà perçue Acornsoft lorsqu’il incitait les concepteurs d’Elite à revoir leurs ambitions à la baisse.

L’immensité et le vide

Le gros défaut de la génération purement procédurale est sa tendance à aboutir à des niveaux sans grande imagination. Si un algorithme peut, facilement et avec une consommation de mémoire minimale, créer un univers gigantesque, il peine à rivaliser avec la créativité humaine lorsqu’il s’agit de le peupler. Comment ne pas citer en exemple la série des Elder Scrolls ? Daggerfall (Bethesda Softworks, 1996), le deuxième épisode de la série, offrait aux joueurs un bac à sable de plus de 150 000 kilomètres carrés.

Cette immensité, couplée à la totale liberté donnée au joueur, en fit rapidement un titre culte, certains allant jusqu’à le qualifier de « premier véritable jeu de rôles sur ordinateur ». Sans doute. Mais, malgré la progression de la capacité mémoire depuis Elite, il aurait été impossible de stocker dans les 650 méga-octets d’un unique CD-Rom un univers aussi colossal. Chaque zone du jeu était donc générée de façon procédurale, une fois encore à partir d’une graine unique.

Le problème est que l’unicité, justement, s’arrêtait là. Et passés les premiers jours, on réalisait à quel point l’univers était vide, à quel point tous les donjons et toutes les villes se ressemblaient. Daggerfall avait pour lui l’immensité, mais, malheureusement, pas grand-chose d’autre. Arrive le volet suivant des Elder Scrolls, Morrowind (Bethesda, 2002). Seulement 26 kilomètres carrés, mais chacun d’entre eux patiemment conçu par un artiste humain. Fini les personnages non jouables génériques : tous ont cette fois une histoire, un rôle, une âme. Sur l’île de Vvardenfell, le paysage varie de façon fluide d’une rive à l’autre. Le passage de Daggerfall à Morrowind n’est pas qu’une anecdote : de moins en moins générés, de plus en plus écrits, les jeux sont, avec l’entrée dans le XXIe siècle, devenus des superproductions bâties à coups de millions de dollars par des armées d’artistes et d’auteurs.

Paradoxe de l’évolution technique : à mesure que les jeux sont devenus moins symbolistes et plus figuratifs, les joueurs n’ont plus accepté la vacuité des univers générés automatiquement.

Et le procédural dans tout cela ? Personne n’accepterait aujourd’hui d’arpenter des plaines infinies et des donjons ennuyeux créés de façon purement procédurale à la manière des années 1990. Les espaces immenses d’un GTA ou d’un Just Cause ont donc été façonnés brique par brique par des équipes de level designers. Mais, chassée par la porte, la génération procédurale fit son grand retour par la fenêtre. Tout d’abord sous forme de middleware, ces petits programmes utilisés en interne par les développeurs. Ainsi, les îles de Just Cause 2, avant d’être finalisées et peuplées manuellement, ont été créées à l’aide d’un générateur automatique de terrain utilisant des fractales. Speedtree, logiciel très populaire, génère en quelques minutes des milliers d’arbres différents, de quoi former de jolies forêts bien touffues sans se contenter de planter côte à côte des centaines d’arbres tous similaires.

Car c’est un paradoxe de l’évolution technique : à mesure que les jeux sont devenus moins symbolistes et plus figuratifs, les joueurs n’ont plus accepté la vacuité des univers générés automatiquement. Dans le même temps, ils ont continuellement exigé plus de diversité au sein de ces univers, diversité qui ne peut être obtenue qu’en ayant recours, d’une façon ou d’une autre, à la génération procédurale. Un petit exemple suffira à clarifier tout cela. Personne n’est choqué par le fait que les soldats d’un Wolfenstein 3D (ID Software, 1992) se ressemblent tous : les graphismes sommaires suffisent à nous convaincre que nous nous trouvons dans un univers virtuel où les ennemis ne sont que des cibles. Imaginons maintenant un GTA 4 peuplé de passants ayant tous le même visage et portant les mêmes vêtements. Personne n’y croirait une seule seconde.

En effet, dans le monde réel, les objets sont imparfaits et chacun d’entre eux comporte de petites variations. À mesure que les graphismes s’approchent du photo-réalisme, il est nécessaire, pour maintenir la suspension d’incrédulité, de garantir toujours plus de diversité dans ce qui apparaît à l’écran. Et la génération procédurale, une fois de plus, arrive à la rescousse. Left 4 Dead 2 (Valve, 2009), pour n’en citer qu’un parmi la pléthore de titres ayant recours à ce genre de techniques, combine visages, cheveux, vêtements et textures en temps réel pour ajouter de la variété à la masse de zombies. Mais il ne s’agit là que d’une sorte de Lego numérique, une astuce utilisant la tendance de la combinatoire à la démultiplication pour créer artificiellement de la variété en assemblant des morceaux épars.

D’autres techniques plus complexes sont utilisées, comme la déformation en temps réel d’un modèle 3D (méthode utilisée pour créer un nombre quasi-infini de visages différents dans Oblivion ou Dragon Age) voire la création procédurale de textures complètes, par exemple en utilisant la méthode dite du bruit de Perlin pour créer des effets de fumée variés. Car il est possible de générer des graphismes et des sons de façon totalement automatisée, ce qu’ont par exemple tenté de faire les auteurs de .kkrieger (.theprodukkt, 2004), un First Person Shooter gratuit dont le moindre élément est généré dynamiquement, et qui ne pèse que… 97 280 octets. Si .kkrieger reste un cas extrême, une démo technologique, de nombreux jeux continuent à utiliser la génération procédurale pour des raisons qui dépassent de loin les questions cosmétiques. Certains d’entre eux font même partie des titres connus de tout joueur qui se respecte.

Le diable dans les dés

Diablo, le titre de Blizzard (1997) et sa suite Diablo 2 (2000) restent célèbres, aujourd’hui encore, pour leurs niveaux générés aléatoirement. De plus, ils furent parmi les premiers jeux grand public à recourir à la combinatoire pour créer objets et monstres aux propriétés variées. Certes, les cartes de Diablo, aussi aléatoires soient-elles, n’offrent pas de grande surprise au joueur : si la disposition des pièces et des couloirs est déterminée au hasard, l’enchaînement des niveaux et leur apparence ne varient pas. De plus, les développeurs de Blizzard n’ont fait qu’emprunter un mécanisme utilisé depuis plus d’une décennie par les rogue-likes, ces jeux en mode texte dans lesquels un héros explore un donjon généré dynamiquement à chaque début de partie.

Mais le précédent créé par les Diablo, qui ont fait de la génération aléatoire un argument commercial et se sont vendus à des millions d’exemplaires, a marqué les esprits des éditeurs. Après le flux et le reflux de la vague de clones, phénomène habituel lorsqu’un nouveau concept de jeu dégage un gros paquet de bénéfices, la mode de la combinatoire a fini par dépasser le petit monde du hack & slash. Citons par exemple Borderlands (Gearbox, 2009), dont les armes sont créées de façon dynamique par un système de combinaisons à côté duquel celui de Diablo fait pâle figure : plus de 17 millions d’objets sont théoriquement possibles.

generation-procedurale-ulyces-03

Cœur de la Voie lactée
Crédits : Nasa

Mais la création dynamique ne se limite pas à l’assemblage de niveaux, d’objets et d’armes. Utilisée subtilement, elle permet d’allonger la durée de vie de jeux plus classiques, dont les niveaux et le contenu ont été créés de façon traditionnelle. Évoquons par exemple Left 4 Dead (Valve, 2008) qui propose une approche originale. Son director (en français « réalisateur ») garantit aux joueurs une expérience différente lors de chaque partie, et ce malgré des cartes fixes. En coulisse, le director examine le comportement des joueurs, analyse leurs performances et altère le placement des ennemis et des objets afin de s’adapter à leur style de jeu. Que le groupe s’attarde un peu trop, et le director balance une horde ou deux à ses trousses pour inciter ses membres à lever le camp et maintenir le rythme de la partie. Left 4 Dead 2 va plus loin en permettant au director de modifier l’emplacement de certains éléments d’architecture pour contraindre les joueurs à remettre en question ce qu’ils croyaient savoir.

Quand on est poursuivi par un tank (un ennemi massif), trouver une porte condamnée là où on s’attendait à une sortie suffit à changer beaucoup de choses. Plus modestement, de nombreux FPS, depuis la fin des années 1990, altèrent légèrement le placement des ennemis à chaque partie, ce qui peut avoir des conséquences importantes, en particulier dans les jeux tactiques (SWAT 4, Raven Shield) où planification et connaissance du terrain sont les clés de la réussite.

Tout cela ne constitue qu’une vision terriblement pauvre de ce que la génération procédurale peut nous offrir. La combinatoire permet certes la création d’un monde vaste et l’ajout de variété mais ne nous donnera jamais un univers vivant. Modifier certains paramètres au fil de la partie reste somme toute un moyen de prolonger artificiellement la durée de vie d’un jeu. Or, il existe une autre façon de penser la génération procédurale, bien plus ambitieuse. Imaginons que nous voulions créer un programme qui génère une grotte de façon aléatoire. Comment devrions-nous nous y prendre ? La solution la plus évidente consiste à établir une liste plus ou moins exhaustive de ce que l’on peut trouver dans une grotte (corridors étroits, lacs souterrains, vastes dômes de pierre, stalactites…) et à combiner ces éléments avec des variations de formes, de taille, d’apparence. Nous obtiendrions ainsi, sans trop de travail, un programme capable de créer des milliards de cavernes uniques.

Mais il est également possible de prendre le problème dans l’autre sens. Qu’est-ce qu’une grotte ? Un bloc de roche lentement creusé par l’érosion. Un programme modélisant, même de façon très approximative, l’usure de la roche par l’eau serait donc à même de créer des grottes à partir de quelques paramètres : dureté de la pierre, vitesse de l’eau, salinité. Un simple petit algorithme bricolé en feuilletant un bouquin de géologie pourrait potentiellement créer toutes les grottes possibles et imaginables, avec une variété digne de celle du monde réel et sans exiger l’entrée fastidieuse et forcément limitative d’une liste d’éléments possibles. Nous ne sommes plus là dans la combinatoire mais dans l’émergence, et le monde de jeu devient l’aboutissement d’un processus autonome.

Univers vivants

La puissance considérable des processeurs modernes a donné des ailes aux développeurs. Plus que la génération de contenu, c’est l’Intelligence Artificielle que les développeurs ont commencé à utiliser pour créer par émergence des situations de jeu inédites et des univers vivants. Certes, toute intelligence artificielle provoque, par définition, l’apparition de comportements en réaction à un environnement, mais certains exemples récents dépassent de loin les tactiques de groupe des marines de Half-Life, aussi admirables soient-elles.

Prenons S.T.A.L.K.E.R. (GSC Game World, 2007) et son système A-Life, grâce auquel chacun des habitants de la Zone est gratifié d’un certain nombre de motivations et de désirs qui lui sont propres. Ces derniers vont, selon l’intelligence de la créature concernée, du plus primitif (faim, sommeil) au plus complexe (accomplissement de tâches à long terme). Une fois ces êtres placés dans le vaste zoo radioactif que constitue la Zone, se forment naturellement des associations, des groupes, des conflits. On assiste alors à des scènes d’un réalisme troublant : les blind dogs chassent en meute, de petits groupes de Stalkers les traquent avant d’être surpris par un gang de bandits partis piller un camp. Le tout est devenu bien plus que la somme de ses parties. Ce fameux tout commence d’ailleurs à ressembler à un monde doué de sa propre vie, se reconfigurant en permanence sous l’effet des forces qui le composent, sans avoir besoin des deus ex machina d’aucun scénariste.

La génération procédurale, capable de créer de grands touts à partir de petits riens, apporte une réponse.

Est-il possible de créer par émergence non seulement des comportements, mais un univers entier ? Oui, et Dwarf Fortress (Tarn Adams, 2006) nous l’a prouvé mieux qu’aucun autre. Si on démarre une nouvelle partie, un monde sera généré devant nos yeux ébahis : des strates géologiques se constituent, l’eau creuse la roche et la terre pour former rivières et nappes phréatiques, des animaux apparaissent et vaquent à leurs occupations, des villes sortent de terre, gratifiées d’une histoire par un petit coup de combinatoire. Les nains que dirige le joueur et leur fameuse forteresse ne sont qu’un prétexte pour jouer dans le plus incroyable bac à sable de l’histoire du jeu vidéo, pour jouir du plaisir d’avoir sous les doigts un monde d’une cohérence infinie, non pas peuplé d’entités en carton-pâte interagissant les unes avec les autres selon les quelques modalités prévues par les développeurs, mais bien prises dans la toile d’un univers où chaque élément, aussi infime soit-il, dépend de tous les autres et où la moindre action entraîne en cascade une foule de réactions, généralement assez funestes pour les nains. Dwarf Fortress constitue sans aucun doute un précédent, le premier monde dynamique aussi abouti.

La course à l’armement technologique n’a pas eu que de bons côtés : développer un jeu est devenu extrêmement coûteux et fastidieux. Résultat, les titres sont de plus en plus courts et nous avons vu apparaître une nouvelle génération de jeux linéaires à l’extrême qui tenaient parfois plus du film interactif que du jeu à proprement parler. Face à cette déferlante de titres hautement scriptés et à l’augmentation incessante des coûts, la génération procédurale, capable de créer de grands touts à partir de petits riens, apporte une réponse. Car, au moment précis où le peloton des FPS prenait des allures de promenade sur rail, apparaissaient les rues de GTA 4 et les campagnes dévastées de S.T.A.L.K.E.R. Pour la première fois, nous avions devant les yeux des univers vivants. Pour la première fois également, nous avions, au sens strict, des anecdotes à raconter sur nos sessions de jeu : au sein de ces mondes, nous étions témoins d’événements imprévus, de situations que même les développeurs n’avaient pas imaginées.

Puis vint Dwarf Fortress, qui acheva de nous convaincre qu’un jeu offrant un monde entièrement dynamique, où jamais une partie ne ressemble à une autre, n’était plus une utopie. Or, les programmeurs aiment l’élégance et les défis, et quoi de plus élégant et audacieux que la génération procédurale ? Quant aux éditeurs, Spore (Maxis, 2008), même s’il n’est qu’une suite de tableaux sans grand intérêt où la création procédurale se voit réduite au rôle de gimmick, nous prouve qu’ils considèrent comme financièrement viable l’idée d’un jeu-monde.

Un jour pas si lointain, sortira un titre grand public qui mettra la génération procédurale au cœur de son gameplay. Ce sera peut-être un BabelWorks, peut-être un jeu d’exploration spatiale dans lequel un algorithme inspiré de l’évolution darwinienne générera à la surface de chaque planète un écosystème dynamique et adapté aux conditions locales, sans doute autre chose. Car une fois mis en équations, l’Univers entier peut tenir sur un DVD. Reconnaissons que cela donne le vertige.


Adapté de l’article « Génération procédurale, un coup de dés jamais n’abolira le gameplay », publié dans le magazine Canard PC numéro 212.

Couverture : Andromède, par Adam Evans.