La génération procédurale dans le jeu vidéo

Je recycle ici un tra­vail étu­diant datant d’il y a trois ou quatre ans. Le texte a été un peu dés­uni­ver­si­ta­ri­sé, à part ça il est tel quel. Le for­mat était volon­tai­re­ment court et limi­té au jeu vidéo.

Les jeux vidéos grand public actuels ont sou­vent une grande valeur ajou­tée en terme de conte­nu : gra­phismes réa­listes, envi­ron­ne­ments vastes et variés, acteurs pro­fes­sion­nels, etc. Même avec un gros bud­get, cette richesse repré­sente un défi de pro­duc­tion. Par exemple, la ville immense et détaillée de GTA4 a été entiè­re­ment créée « à la main » : chaque immeuble a été des­si­né et pla­cé avec soin par des artistes. Il existe une autre approche, qui consiste à par­tir d’éléments de base (ici, un ensemble de bâti­ments) et à les dis­po­ser semi-aléatoirement, avec cer­taines contraintes (lais­ser des vides pour que des rues se forment, ras­sem­bler les immeubles simi­laires pour que chaque quar­tier ait une iden­ti­té, etc.). Cette approche dite pro­cé­du­rale est très géné­rique : avec elle, on peut géné­rer des tex­tures, des ter­rains, des niveaux de jeu, des scé­na­rios, etc.

Un peu de technique

Il y a glo­ba­le­ment deux familles de tech­niques : celles des gram­maires de formes et celles uti­li­sant des fonc­tion de bruit.

[Note 2014 : J’avoue ne plus savoir d’où je sors cette dis­tinc­tion. Il existe des dicho­to­mies plus géné­rales, notam­ment entre algo­rithmes onto­gé­né­tiques et téléo­giques, c’est-à-dire en gros entre les modèles réa­listes seule­ment en appa­rence et ceux qui le sont vrai­ment. Voir cette liste et cet article.]

Les gram­maires de formes sont héri­tées des gram­maires for­melles, qui per­mettent de décrire avec un jeu de règles l’ensemble des phrases cor­rectes d’un lan­gage don­né. On pro­cède en géné­rant toutes les phrases pos­sibles à par­tir d’un alpha­bet et de règles de tran­si­tion. Par, exemple, à par­tir de l’alphabet {a, b} et de la règlea => b, on peut géné­rer le lan­gage {a, ab, abb, abbb…}. Cette idée fut d’abord uti­li­sée pour modé­li­ser des phé­no­mènes de crois­sance natu­relle (feuilles, colo­nies de bac­té­rie), puis éten­due à l’architecture. En pre­nant des formes géo­mé­triques simples comme alpha­bet de base, on peut créer des façades, des bâti­ments, voire des villes entières.

Système L
Système L

Passons aux fonc­tions de bruit. On com­mence par pla­cer des points dont les valeurs sont géné­rées de façon pseudo-aléatoire, puis à effec­tuer une inter­po­la­tion entre eux afin d’obtenir une courbe. Faire la somme de plu­sieurs de ces courbes per­met d’en obte­nir une d’aspect plus frac­tal, com­pli­qué et natu­rel. On peut faire la même chose en deux dimen­sions, ce qui donne alors une tex­ture. Le pas­sage à la troi­sième dimen­sion per­met d’obtenir un ter­rain, ce qui est rela­ti­ve­ment tri­vial : il suf­fit d’interpréter la valeur du niveau de gris comme une hau­teur.

Bruit de Perlin en dimensions 1, 2 et 3
Bruit de Perlin en dimen­sions 1, 2 et 3

Un nouveau processus de conception

Générer du conte­nu pro­cé­du­ra­le­ment au lieu de le créer à la main a de mul­tiples avan­tages :

  • Réduction des coûts de main d’œuvre. Concevoir et para­mé­trer un algo­rithme qui génère une forêt n’est pas tri­vial, mais ce sera tou­jours moins long que de des­si­ner et pla­cer chaque arbre.
  • Diminution des besoins de sto­ckage et de bande pas­sante. Par exemple si l’on veut des tex­tures hau­te­ment réa­listes, il suf­fit de sto­cker l’algorithme qui les génére à la volée, et pas les lourdes images finales. C’est ce qui per­met à cer­tains de créer des démos gra­phiques spec­ta­cu­laires avec un fichier d’origine pesant quelques dizaines de Ko, alors que l’équivalent en vidéo pèse­rait beau­coup plus. Voir par exemple .kkrie­ger.

Cette approche a évi­dem­ment des limites. Générer pro­cé­du­ra­le­ment un objet revient à auto­ma­ti­ser sa créa­tion, ce qui implique dans une cer­taine mesure qu’on le com­prenne. Par exemple, créer des récits vrai­sem­blables sup­pose que l’on sache ce qui fait qu’une his­toire est bonne. Il faut au pire avoir de bonnes intui­tions et heu­ris­tiques à ce sujet, au mieux avoir iso­lé des inva­riants et savoir les com­bi­ner. Cela fait écho à la quête des théo­ri­ciens du récit et des spé­cia­listes des séries télé­vi­sées qui cherchent à trou­ver des arché­types et des méca­nismes pré­sents dans tout récit.

Ces limites sug­gèrent une méthode de concep­tion dif­fé­rente de celle fré­quem­ment en vigueur. Les jeux vidéo pour le grand public sont sou­vent très linéaires, avec une suite d’évènements scrip­tés minu­tieu­se­ment. Par exemple, un avion doit pas­ser au-dessus du joueur pré­ci­sé­ment au moment où il sort d’un tun­nel. Le but est de contrô­ler autant que pos­sible l’expérience du joueur, dans la pers­pec­tive clas­sique d’un artiste démiurge et tota­le­ment maitre de l’univers fic­tion­nel. Cet idéal devient impos­sible dans une pers­pec­tive pro­cé­du­rale, puisque le conte­nu est lar­ge­ment aléa­toire1. Par exemple, on ne peut pas savoir la dis­po­si­tion exacte des arbres et des clai­rières dans une forêt.

Pourtant, on regagne en faci­li­tés de macro-gestion ce qu’on perd en contrôle minu­tieux. On ne peut pas pla­cer telle espèce d’arbre à tel endroit, mais on peut faire des chan­ge­ments glo­baux sur la flore sim­ple­ment en modi­fiant l’algorithme. Ce nou­vel état d’esprit peut se répandre dans tout le pro­ces­sus de concep­tion. Par exemple, puisqu’on ne peut pas pla­ni­fier pré­ci­sé­ment l’emplacement d’une ren­contre en forêt, on peut lais­ser le pro­gramme s’en occu­per en sui­vant cer­taines condi­tions (« dans une clai­rière à moins d’un kilo­mètre de la ville »). Ensuite, on peut être ten­té de rendre aléa­toire la sur­ve­nue elle-même des évè­ne­ments. Certains moments clés dans le scé­na­rio peuvent res­tés pré-codés, tan­dis que d’autres peuvent se faire au hasard (par exemple les ren­contres que le joueur ferait dans une ville).

De nouveaux types d’interactions

L’approche pro­cé­du­rale change aus­si beau­coup la manière de jouer. Certains jeux pro­mettent en effet une re-jouabilité poten­tiel­le­ment infi­nie, puisque la car­to­gra­phie des niveaux, l’emplacement des objets, les objec­tifs à rem­plir, etc. sont dif­fé­rents pour chaque nou­velle par­tie et chaque joueur. La ques­tion de la durée de vie d’un jeu doit donc être repen­sée, puisqu’elle dépend plus de la pro­pen­sion du joueur à se las­ser que de l’imagination du déve­lop­peur. À charge pour ce der­nier de créer un pro­gramme qui génère des envi­ron­ne­ments et des aven­tures inté­res­santes, le reste se passe entre le jeu et le joueur. C’est à nou­veau une perte de contrôle pour le créa­teur, mais qui se révèle payante, puisqu’elle per­met au joueur de mieux s’approprier le jeu et de se faire sa « propre » aven­ture.

Plus géné­ra­le­ment, le centre de gra­vi­té se déplace du créa­teur vers la créa­tion elle-même. Dans beau­coup de jeux clas­siques, le joueur essaye de com­po­ser avec ce qu’il devine des inten­tions du créa­teur, en essayant de pré­dire où un piège a été pla­cé, ou quel va être le pro­chain rebon­dis­se­ment dans l’intrigue. Dans un jeu géné­ré pro­cé­du­ra­le­ment, on cherche plu­tôt la logique qui gou­verne la géné­ra­tion de ces struc­tures variées. Passé l’émerveillement ini­tial, on cherche la néces­si­té der­rière la contin­gence appa­rente des formes.

L’approche pro­cé­du­rale est ain­si très pro­met­teuse. Il existe même des tra­vaux qui tentent de rendre auto­ma­ti­sable la géné­ra­tion des règles elles-mêmes, notam­ment Angelina, un moteur aléa­toire de créa­tion de jeux. Toutefois, étant don­né les limi­ta­tions de concep­tion, ne sont envi­sa­geables que des méthodes où seul un aspect du jeu est pro­cé­du­ral.


  1. Dans les faits, peu de jeux sont géné­rés inté­gra­le­ment de manière pro­cé­du­rale. De plus, on peut tech­ni­que­ment rendre l’environnement iden­tique à chaque géné­ra­tion, puisque le géné­ra­teur est pseudo-aléatoire : il suf­fit d’entrer à chaque fois les même para­mètres de départ.