Un milliard de milliard de planètes différentes à explorer : c’est la promesse de No Man’s Sky, l’un des jeux vidéo les plus attendus de l’année, qui sort le 10 août (sur PlayStation 4) et le 12 août (sur PC). Un monde presque infini, dans lequel chaque joueur pourra se perdre à loisir, et dont chaque planète n’a bien sûr pas été conçue par l’équipe de développement du jeu. Cet univers n’a été rendu possible que par un procédé appelé la « génération procédurale » : une technique utilisée pour créer, de façon automatisée et en partie aléatoire, du contenu (décors, objets, évènements…) en suivant des règles établies à l’avance.

No Man's Sky gameplay E3 2014
Durée : 03:07

Le principe n’est pas nouveau – on le retrouve aussi dans des jeux très connus comme Minecraft, ou, dès 1984, dans Elite (Acornsoft), l’une des inspirations de No Man’s Sky. Sa principale application est la génération des niveaux que le joueur parcourra. Plutôt que d’employer un humain – le level designer – qui construit « à la main » ces différents lieux, un algorithme, une série d’instructions informatiques, va générer le décor, les textures qui recouvrent les murs, les objets qui s’y trouvent et même les objectifs à accomplir par le joueur. Vous pouvez voir ici un exemple très visuel d’algorithme créateur de niveau, par Adonaac et Phi Dinh.

Le level designer n’est néanmoins pas totalement écarté, et la création n’est pas laissée entièrement au hasard. Ainsi le level designer peut créer des salles, qui seront ensuite assemblées semi-aléatoirement en suivant des règles strictes : s’assurer que le niveau n’est pas une impasse, par exemple, ou qu’un monstre généré n’est pas trop puissant pour le joueur à ce moment-là du jeu. C’est la méthode choisie par les développeurs français du jeu Darkstone (Delphine Software, 1999) réédité l’an dernier sur mobile.

Dans la construction des objets, la génération procédurale est aussi très importante. Un arbre par exemple contient de nombreuses feuilles. Il serait bien trop lent – et décourageant – de les placer une par une. La génération procédurale construira un arbre en disposant ces feuilles en répétant un schéma, à la manière des fractales de Benoît Mandelbrot dans le domaine des mathématiques, mais avec quelques variations pour créer une impression de désordre naturel.

Pour les textures, ces images que les concepteurs appliquent aux surfaces des décors, des algorithmes spécifiques sont utilisés pour en produire de différents types. L’un des plus connus est le bruit de Perlin, inventé par le professeur en informatique Ken Perlin en 1983, qui cherchait à obtenir des textures générées automatiquement mais qui imitent les irrégularités présentes dans la nature, afin qu’elles n’aient pas un rendu trop « artificiel ». Un procédé très utilisé pour générer des terrains ou des éléments naturels comme les flammes d’un feu.

Quels sont les avantages de la génération procédurale ?

• La rentabilité

Les développeurs se heurtent dans la création de niveaux à un problème simple : plus le rythme du jeu est rapide, moins la création de niveau est rentable, car les joueurs les traverseront bien plus vite. Alors qu’il faut de nombreuses heures aux level designers pour créer les architectures des lieux et les différentes interactions qui les peupleront, un joueur peut très bien les traverser en quelques minutes.

Avec la génération procédurale, un programmeur peut créer un algorithme qui générera une infinité de lieux. Une solution très intéressante pour les studios indépendants aux budgets très contraints ou pour créer des environnements vraiment immenses. Ainsi, la carte de l’univers de Skyrim (Bethesda Game Studios, 2011), intégralement créée manuellement, fait entre 35 et 40 km², selon les estimations. Celle de Daggerfall (Bethesda Softworks, 1996), générée en partie aléatoirement fait 161 600 km² ! Une immensité qui serait bien trop longue et coûteuse à créer par une équipe de level designers.

Travelling from Daggerfall to the High Rock Sea Coast (w/ speed cheat)
Durée : 06:26

• La diversité

Les niveaux créés sont à chaque fois différents, car l’algorithme utilise une part de hasard pour fabriquer les décors. Cela peut inciter les joueurs à refaire le jeu, pour découvrir de nouvelles configurations, ou des éléments non intégrés par l’algorithme la première fois. Diablo (Blizzard North, 1996) génère ainsi 16 niveaux que le joueur doit traverser pour finir le jeu. L’algorithme pioche dans une liste de quêtes à accomplir pour varier les niveaux. Le joueur est assuré de ne pas avoir toutes les quêtes en une seule partie, l’invitant à recommencer le jeu. De même, pour les objets qu’il trouve sur les cadavres des ennemis, un ensemble de pourcentages régit les algorithmes de génération, et certains objets ont une chance très faible d’apparaître. À la façon d’un bandit manchot, le joueur est titillé pour l’inciter à retenter sa chance encore et encore afin de dénicher de nouveaux objets ou les plus rares, plus puissants.

• L’économie d’espace de stockage

L’avantage d’un algorithme, c’est qu’il prend très peu de place. Pour les niveaux, cette technique était très utilisée dans les premiers temps du jeu vidéo, lorsque l’espace de stockage disponible était extrêmement limité, à la place de fichiers décrivant des lieux en 3D. Les textures photoréalistes plaquées sur les murs sont encore plus gourmandes en taille. La quête du « toujours plus » et la capacité grandissante des supports font que la taille des jeux augmente ainsi de façon exponentielle : si Diablo en 1997 « pesait » 60 méga-octets (Mo), Diablo II en comptait déjà 650, et Diablo III a quant à lui dépassé les 12 Go. Mais certains développeurs cherchent à rester concis et trouvent dans la génération procédurale des textures un moyen de réduire drastiquement la taille de leurs jeux. La démo .kkrieger (.theprodukkt, 2004) réalisait ainsi l’exploit de tenir sur seulement 96 Ko en offrant 7 minutes de jeu.

.kkrieger / The FPS Game in 96KB (Full Gameplay)
Durée : 07:16

Quels sont ses désavantages ?

• La répétitivité

Même s’il y a une part d’aléatoire, un algorithme finit toujours par se répéter. Pas de façon exacte, mais assez pour que le joueur le remarque. Ainsi une forte impression de déjà-vu prend le joueur lorsqu’il traverse les lieux de Daggerfall. Le contenu est réutilisé par l’algorithme et est placé plusieurs fois dans différents endroits du monde. Une répétition qui peut nuire à l’expérience du joueur : si la génération procédurale peut créer des plaines ou des forêts gigantesques, il n’est pas sûr qu’elles captivent l’intérêt du joueur juste par leur taille. De même pour les quêtes que le joueur doit mener, si celles-ci sont écrites sur des modèles « trouver l’objet X dans le donjon Y », « trouver et tuer la créature Z » ou « transporter l’objet X au personnage P » et sont répétées ad nauseam.

• Le manque de richesse

Un algorithme n’aura jamais l’imagination d’un être humain. Toute la sophistication possible ne permettra pas d’atteindre la création artistique qui est à l’œuvre dans la création d’un niveau. Dans certains jeux, un level designer repasse après l’algorithme pour finaliser les décors. Une division peut-être effectuée entre certains aspects laissés à la génération procédurale et d’autres conçus par des humains. Age of Empire (Ensemble Studios, 1997) proposait par exemple de créer des cartes de façon procédurale seulement pour les parties multijoueurs.

Aussi un algorithme ne ressentira pas le résultat qu’il crée. Le level designer cherche à créer une ambiance, une impression, voir comment les joueurs y réagissent. Il peut accentuer certains points pour que le décor transmette bien l’émotion qu’il veut donner : tristesse, joie… Ce manque de sentiment de la part de l’algorithme prive « d’âme » les contenus créés, et parfois l’absurdité n’est pas loin. Certains noms d’objets ou de monstres générés dans Diablo II par exemple sonnent très étrangement, surtout avec la traduction française, le site spécialisé JudgeHype en a même donné une liste. Il est sûr qu’affronter « le bourreau : le danseur suintant » ou « le démembreur : la mise à mort de la tempête » risque plus de faire rire les joueurs qu’autre chose… ce que peut difficilement évaluer l’algorithme.