En informatique, la génération procédurale (ou modèle procédural) est la création de contenu numérique (niveau de jeu, modèles 3D, dessins 2D, animation, son, musique, histoire, dialogues) à une grande échelle (en grande quantité), de manière automatisée répondant à un ensemble de règles définies par des algorithmes[1],[2]. Le modèle procédural s’appuie sur les informations d'un algorithme pour créer[3].
La méthode de génération procédurale trouve principalement application dans les domaines du jeu vidéo et du cinéma. Dans le domaine du jeu vidéo, il y a la notion de création à portée artistique ainsi que de conception de contenu à grande échelle, c'est pourquoi la notion de génération procédurale s'associe avec un contrôle a posteriori par l'artiste qui modifie l’environnement (simulation, modélisation) (aléatoire contrôlé)[1].
La génération procédurale est une catégorie des techniques de modélisation (les deux autres étant la simulation informatique et la modélisation par esquisses ou par édition) permettant la création d'un monde virtuel cohérent[4].
Ken Perlin propose en 1985 la fonction de bruit pseudo-aléatoire qui porte son nom. Cette fonction devient très vite un outil indispensable dans tous les domaines de la génération procédurale. Ken Musgrave(en) propose ensuite une approche à base de fractales pour la génération procédurale, notamment pour la création des textures et de terrains [6]. Aujourd'hui, de nombreux jeux vidéo comme Elite: Dangerous ou No Man's Sky utilisent la génération procédurale pour créer des mondes gigantesques allant jusqu'à la taille de l'univers. Plusieurs logiciels commerciaux proposent d'utiliser la génération procédurale pour la création de contenu numérique, comme Houdini ou encore SpeedTree(en).
Les applications de génération procédurale
Les besoins en détails et en taille des mondes virtuels étant toujours plus grands, l'automatisation de la création de contenu numérique (par la génération procédurale ou une autre technique) est un enjeu important[7]. L'enjeu de la création de paysages complexes est d'y apporter un réalisme plus important, avec la prise en compte des interactions entre les éléments, d'adaptation à leur environnement[4]. Les formes complexes comprennent les surplombs, des arches, des grottes, des couches de matières, l'empilement de pierre, les routes urbaines et de campagnes, et les espaces urbains etc[4].
Génération de terrains
La génération de terrains tient une place importante dans la génération procédurale du fait de son importance visuelle à toutes les échelles, de l'arrière-plan jusqu'au premier plan. La génération de cartes de hauteurs (heightmap ou heightfield) s'intéresse à la surface du terrain pour la représenter en deux dimensions, excluant ainsi des éléments comme les grottes, les arches ou les surplombs au profit d'une représentation plus compacte en mémoire. Les modèles volumiques (souvent limités à l'utilisation de voxels) peuvent quant à eux représenter tous les types de caractéristiques de terrains trouvées sur terre, au prix d'un cout mémoire plus important.
Approche surfacique
Les modèles de terrains surfaciques sont basés sur les cartes de hauteurs. La forme du terrain est défini par une grille régulière en deux dimensions dont chaque point est associé à une hauteur. Les premiers terrains utilisant ce modèle étaient générés par l'approche fractale[8],[9]. L'approche surfacique permet de représenter des terrains pour un cout mémoire faible et est donc souvent l'approche privilégiée dans les jeux vidéo. Cette représentation permet également l'utilisation d'algorithme d'érosion (hydraulique(en) ou thermique(en)), qui est l'élément central du point de vue géologique. C'est le modèle mis en avant dans de nombreux logiciels de modélisation de terrains ou de mondes virtuels, comme Unity, World Creator, World Machine ou encore Instant Terra de la société Wysilab.
Cette représentation a fait l'objet de beaucoup de recherches dans le monde universitaire, et plus d'informations peuvent être trouvé dans les références[10],[11].
Approche volumique
Les terrains à partir de voxels permettent de représenter des caractéristiques de terrains plus variées que les modèles surfaciques, au prix d'un cout mémoire plus important. Plusieurs travaux mettant en avant des grottes, des arches ou des surplombs[4],[12]. Certains jeux vidéo comme Minecraft ou Astroneer profitent de l'utilisation d'une telle structure dans leur gameplay. Pour être utilisé à grande échelle, de nombreuses structures de données efficaces telles que les octree doivent être développées.
Végétation et écosystème
La végétation et l'écosystème sont définis par l'ensemble des arbres et plantes interagissant avec l'environnement.
Les plantes représentent un défi à représenter du fait de leur complexité d’éléments (racines, troncs, branches, fleurs, fruits, feuilles)[4]. Il existe différentes techniques pour leur création avec des embranchements (ramification) à chaque niveau, ou bien avec l'utilisation d'automates cellulaires pour définir les branches d'un arbre[4],[13],[14],[15],[16]. Le réalisme des structures de plantes est notamment possible grâce à des diagrammes de structures de plantes et de fleurs[17], combinées à une hiérarchie de plans[18].
Des plantes grimpantes peuvent être créées en fonction de l’environnement lui-même, et non plus de manière indépendante, en gérant la distribution des racines en fonction de l'eau dans le sol[4].
Pour la distribution de ces éléments, il existe plusieurs moyens : avec la simulation d'une croissance des plantes avec compétition entre elles, avec une carte de densité ou avec la méthode de pavage (efficace pour de grandes échelles, en distribuant par groupe et par duplication) avec la répétition d'une instance[4].
Une autre technique consiste à utiliser plusieurs photographies avec de la simulation de particules peut générer des arbres avec un volume de voxels[7].
Il existe des méthodes pour animer le comportement des plantes qui se scindent en deux objectifs, chercher la lumière et conquérir le plus d'espace.
Un des moyens de simuler l'écosystème est de représenter les éléments avec un point et une taille du point, lorsque les points se touchent, c'est la plus grande plante qui reste, l'autre disparaît lorsqu'elle atteint son espérance de vie ; et de la combiner avec une règle de groupe, qui fait que la même famille de plantes s'installe par groupe (en mourant d'autres apparaissent à côté d'elle), donc propagation de l'espèce. Cette méthode n'est cependant pas bien représentative car exclusive (aucune pousse n'est admise près d'un grand arbre)[4]. Le contrôle de ce processus peut se faire avec des cartes de densité, qui est fonction de la distribution de l'eau et de la capacité d'absorption par plante[4].
Paysages urbains
Un paysage urbain est constitué d'un réseau de rues, de routes avec des blocs de bâtiments, de quartiers[4],[7]. Plusieurs travaux ont été effectués pour la génération automatique de réseaux routiers complexes (par l'utilisation d'un algorithme de plus court chemin pondéré par l'environnement) [1][2] ainsi que des villages [3].
La génération par esquisses consiste à modéliser en contrôlant la forme du relief[19],[20]. Cela définit les éléments importants (vallées, crêtes), le système construit alors le sol (génère le relief) à partir de l'empreinte (ligne pour vallées ou crêtes) de la montagne associée à ses lignes de vallées ou de crêtes, un contrôle a posteriori peut se faire par l'utilisateur[4].
Applications
Jeux vidéo
L'utilisation dans le jeu vidéo en massif, notamment dans le jeu vidéo indépendant permettant de répondre a des attentes spécifique aux joueurs, notamment la rejouabilité[1].
Cette idée est souvent liée aux applications de synthèse d'image et au level design dans les jeux vidéo.
Dans le jeu vidéo la génération procédurale correspond à l'application d'un aléatoire contrôlé (ou d'un faux aléatoire)[1] régie par des règles définies dans le but de générer quelque chose d'unique mais en conservant une cohérence.
L'objectif étant de pouvoir créer une très grande quantité de contenu tout en assurant une cohérence de l’environnement, en lui donnant un aspect unique[21].
L'enjeu étant d'un point de vue du game design de proposer un nombre infini de niveaux uniques tout en contrôlant l'équilibrage de la difficulté pour le joueur.
La génération d'objets par fragments permet de multiplier la variété des scènes et de leur réalisme[7].
Contrainte spécifique liée aux jeux vidéo
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?
La génération procédurale dans le cadre du jeu vidéo impose des contraintes à l'utilisation de cette méthode, en effet, le rendu des calculs de la génération procédurale doit permettre d'avoir un affichage en temps réel à l’écran (output), dans le cas contraire cela cassera l'immersion du joueur dans le jeu vidéo (lag, bug, glitch, bug graphique).
Développement de la technologie dans le jeu vidéo[22]
Avant d'avoir une interface graphique complexe, les jeux type Rogue-like, comme Beneath Apple Manor (1978) et Rogue (1980), utilisait la génération procédurale pour construire des donjons affichés en caractères ASCII ou des systèmes à base de tuiles régulières (regular tile-based systems). Des jeux dans lesquels, la génération procédurale permet de générer des pièces, des couloirs, des monstres et trésors que le joueur aurait en récompense. Les jeux type Rogue-like, utilisent toujours aujourd'hui ce système de création de contenu, car il permet le développement d'obtenir un gameplay complexe sans avoir à passer trop de temps à créer le monde d'un jeu[23].
Les premiers jeux informatiques graphiques étaient limités par de fortes contraintes de quantité de mémoire. Cela a poussé les développeurs à la création de contenu — tels que des cartes — généré algorithmiquement : il n'y avait tout simplement pas assez d'espace pour stocker une grande quantité de niveaux et d'illustrations (qui auraient dû être créés préalablement à la main). Les générateurs de nombres pseudo-aléatoires sont souvent utilisés conjointement avec des valeurs de graine aléatoire (seed) présélectionnées afin de créer de vastes mondes de jeu qui paraissaient avoir été préfabriquées. Avec certains algorithmes pseudo-aléatoires, si la graine ne change pas, le résultat de l'algorithme reste identique. Cela permet à partir d'un nombre unique d'obtenir toujours le même monde.
Il est possible que le premier jeu utilisant une graine pour la création de monde soit Akalabeth: World of Doom (1980) de Richard Garriott, avec l'utilisation de la même graine, le joueur pouvait toujours retourner à un endroit précis du monde[24].
The Sentinel, se déroulant dans un paysage à génération fractale, était censé avoir 10 000 niveaux différents stockés dans seulement 48 et 64 kilooctets. Un cas extrême était Elite, qui a été initialement prévu pour contenir un total de 2⁴⁸ (environ 282 000 000 000 000, 282 billions) galaxies avec 256 systèmes solaires chacun. L'éditeur, cependant, avait peur qu'un tel univers gigantesque cause l'incrédulité chez les joueurs, et seulement huit de ces galaxies ont donc été choisies pour la version finale[25].
À mesure des avancées matérielles du matériel informatiques et de l'adoption par le marché du CD (pouvant contenir 682 Mo (652 Mio)), il a été possible de stocker des dizaines de milliers de fois plus de données que ce qui était possible dans les années 1980, rendant moins utile l'utilisation de la génération procédurale pour construire de grands mondes. Au contraire, des contenus — tels que les textures, les modèles de personnages et l'environnement — sont créés par des artistes à l'avance, afin de maintenir une qualité de contenu constamment élevée.
Le stockage de modèle unique dans la mémoire du jeu — plutôt que de produire plusieurs objets à l'aide des lignes directrices similaires — permet une diversité de modèles détaillés qui sont chacun sensiblement différent. Toutefois, la création à la main (de modèle unique), implique par conséquent une existence d'objet limité en nombre[pas clair]. Dit plus simplement, créer des modèles uniques et détaillés assure que chaque modèle soit différent et cohérent à côté des autres, mais le temps de création manuel de ces modèles implique qu'il n'est pas possible d'en créer en trop grande quantité, voir infiniment. Certaines approches initiales à la création procédurale ont tenté de résoudre ce problème en déplaçant la charge de la génération de contenu par les artistes, vers les programmeurs qui peuvent créer du code générant automatiquement des maillages différents à l'aide de paramètres d'entrées.
Il a été reconnu que l'application d'un modèle purement procédural est souvent difficile, et au mieux il nécessite des quantités énormes de temps pour évoluer vers une méthode fonctionnelle, utilisable et rendant un aspect réaliste.
Au lieu d'écrire une procédure qui construit complètement le contenu, la technique actuelle d'utilisation de cette technologie — pour être beaucoup moins chère et plus efficace — est de compter sur l'artiste pour la création de détails. Par exemple, SpeedTree(en) est un middleware utilisé pour générer une grande variété d'arbres procéduralement, permettant a l'utilisateur de modifier les textures des feuilles — à partir de fichiers ordinaires — , permettant de représenter un feuillage réel numériquement acquis. D'autres méthodes hybrides peuvent être efficaces pour générer du contenu, avec par une utilisation combinée des procédures préconçues et d'une application de distorsions.
Envisageons qu'un seul algorithme puisse générer un arbre d'aspect réaliste, l'algorithme pourrait être alors appelé à générer des arbres aléatoires, remplissant ainsi une forêt entière en temps réel, au lieu de stocker tous les sommets requis par les différents modèles. Cela permettrait d'économiser de l'espace de stockage et de réduire la charge sur les artistes, tout en offrant un niveau similaire d'immersion au joueur. Cette méthode nécessiterait beaucoup plus de puissance de traitement, mais en raison de l'augmentation de la puissance des processeurs (Loi de Moore) cela fait de moins en moins obstacle.
Usage moderne
Bien que les jeux informatiques modernes ne possèdent pas les mêmes restrictions de mémoire et de matériel, que les jeux précédents avaient, l'utilisation de la génération procédurale est fréquemment employée pour créer des jeux aléatoires, des cartes, des niveaux, des personnages, ou d'autres facettes qui sont uniques sur chaque usage[26].
En 2004, le jeu de tir à la première personne.kkrieger sort, il se base sur un usage intensif de la synthèse procédurale : tout en étant assez courte et très simple, les effets visuels pèsent seulement 96 ko. Au contraire, de nombreux jeux modernes qui ont la possibilité d'être publiés sur le support DVD, dépassant souvent 2 gigaoctets, soit une taille plus grande de 20 000 fois. Le jeu Naked Sky de RoboBlitz utilise la génération procédurale pour réduire l'espace de stockage utilisé par le jeu à moins de 50 MB. Spore de Will Wright fait également usage de cette technologie.
La génération procédurale est souvent utilisée dans les systèmes de butin — comme dans des RPG, ou des MMORPG. Bien que les quêtes puissent comporter des récompenses fixes, d'autres butins, comme les armes et armures, peuvent être générés pour le joueur en fonction de plusieurs paramètres comme le niveau du personnage, le niveau de la quête ou bien sa performance dans la recherche etc. Souvent cela conduit à avoir des récompenses d'une qualité rare pour tenir compte du système de génération d'items avec des caractéristiques supérieures à la moyenne. Par exemple, la série Borderlands est basée sur un système de génération procédurale pour la création d'armes et d'équipements uniques[27].
De nombreux jeux de survie ou en monde ouvert utilisent la génération procédurale pour la création de monde avec une graine (seed) permettant l'utilisation d'environnements à chaque fois nouveau.
Ces systèmes de génération créent de nombreux biomes (basés sur le voxel ou le pixel) avec une répartition des ressources, des objets et des créatures. Fréquemment, le joueur a la possibilité de régler certains paramètres de génération. Des exemples de ces jeux incluent Dwarf Fortress et Minecraft.
La génération procédurale est également utilisée dans les jeux avec des mondes ouvert de très grande échelle, en particulier les space opera. Elite: Dangerous, utilise les 400 milliards d'étoiles connues de la Voie lactée comme monde de base, il utilise également la génération procédurale pour simuler les planètes dans ces systèmes solaires. Infinity dispose d'une multitude de planètes générées procéduralement et entre lesquelles le joueur peut voyager par l'intermédiaire de vaisseaux spatiaux. Outerra Anteworld est un jeu vidéo utilisant dans son développement la génération procédurale avec les données du monde réel pour créer une réplique virtuelle de la planète Terre en grandeur nature. No Man's Sky dispose d'un univers contenant 18 quintillion de planètes qui ont toutes été générées avec la génération procédurale, cela a aussi été utilisé pour la génération du terrain, de la météo, de la flore, de la faune et pour un certain nombre d'espèces spatiales exotiques. Son univers est généré par l'utilisation d'un seul numéro de départ aléatoire (« seed aléatoire ») à son moteur de jeu, assurant que la même planète puisse être visitée par les joueurs juste avec l'information de son emplacement[28],[29].
Certains jeux comportant un mode coopératif utilisent la génération procédurale pour élaborer des expériences uniques pour les joueurs car ils complètent le jeu. La série Left 4 Dead, situé dans un monde post-apocalyptique, utilise un directeur AI, une intelligence artificielle qui surveille le comportement des joueurs et permet de créer une expérience dynamique pour garder les joueurs alerte. En effet celui-ci agit, en envoyant des zombies lorsqu'il détecte une situation de confiance du joueur, ordonnant aux zombies d'attaquer les joueurs de niveau intermédiaire et de modifier leur itinéraires possibles. Des concepts similaires sont utilisés pour des jeux comme Warhammer: End Times, Vermintide et Evolve[30].
En 2014 commence la première Procjam, une game jam spécialisée dans la génération procédurale de contenu[31].
Cinéma
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?
La génération procédurale est souvent utilisée dans le cinéma pour créer rapidement des espaces visuellement intéressants et précis. Ceci est vrai pour une grande variété d'applications.
L'application la plus répandue c'est celle de l' « usine imparfaite » où les artistes peuvent rapidement générer un grand nombre d'objets similaires. Ce processus se fait pour un souci de réalisme, dans la vraie vie, deux objets ne sont jamais exactement semblables. Par exemple, un artiste peut modéliser un produit pour une tablette de magasin d'épicerie, puis il peut générer — à l'aide de cette méthode — un grand nombre d'objets similaires pour remplir l'étagère.
MASSIVE est une animation haut de gamme par ordinateur et un logiciel d'intelligence artificielle utilisée pour générer une multitude d'effets visuels pour le cinéma et la télévision. Il a été développé pour générer automatiquement les soldats — dans une bataille qui en comptaient des centaines de milliers — dans Le Seigneur des anneaux[réf. nécessaire].
Le Coherent noise) peut être extrêmement important dans flux de travail procédural pour film. Le Simplex noise est souvent plus rapide avec moins d'artefacts, mais une fonction plus ancienne bruit de Perlin peut aussi être utilisé. Coherent noise, dans ce cas, se réfère à une fonction qui génère de pseudo-aléatoire en n dimensions.
Développement de la technologie au cinéma
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?
Exemple de génération procédurale
L'un des premiers jeux utilisant cette technologie est le jeu Elite (sorti en 1984), permettant aux joueurs d'explorer 8 galaxies contenant 256 systèmes solaires, soit 2 500 mondes, le tout tenant sur une disquette de 20 ko de mémoire[32]. Ce jeu utilise des formules mathématiques précises comme la suite de Fibonacci (créée par le mathématicien Leonardo Fibonacci en 1202)[33],[32]. Dans Minecraft, la génération procédurale est un des éléments au cœur du processus de développement de Notch pour son jeu, en ajoutant au fur et à mesure une meilleure cohérence à l'univers, et une plus grande diversité (création de biomes, de temps différents, de rivières, de villages, de donjons etc.)[34].
No Man's Sky utilise la génération procédurale pour les terrains des planètes et les noms de planètes, de vaisseaux, de plantes, d'animaux, de lieux, de systèmes et les prénoms de la plupart des créatures intelligentes (les Korvax, les Gek, les Vy'keen et certains voyageurs).
La génération procédurale utilise un large nombre d'outils mathématiques dans le processus de création de contenu de la génération procédurale notamment le diagramme de Voronoï (qui y détermine a une étape la zone d'influence d'un point), il peut être utilisé pour y mettre des valeurs de vitesse (représentant la pression) pour y simuler les montagnes[2],[35].
La suite de Fibonacci (créée par le mathématicien Leonardo Fibonacci en 1202) est utilisé pour la création de nombre aléatoire (faussement aléatoire).
Les fractales avec le mouvement Brownien fractionnaire peut permettre de créer des cartes de hauteur (heightmap)[2] pour les rivières et montagnes par exemple (érosion).
↑ ab et chttp://www.di.ens.fr/~bouillar/Stages/Rapports/rapport_Michel.pdf École Normale Supérieure, Département d'Informatique, Rapport de Stage L3 - Génération procédurale de paysages à partir de cartes vectorielles - Intégration d'une mini-simulation géologique par Élie MICHEL le 29 août 2014
↑Le transpositeur ou l'improvisateur de tissus appareil non breveté basé sur la théorie des nombres premiers et des progressions arithmétiques ascendantes donnant un nombre infini de combinaisons à l'usage des compositeurs de tissus et des dessinateurs, Paris, J. Baudry, (BNF30479000, lire en ligne)
↑(en) Ken Musgrave, « Texturing and Modeling: a Procedural Approach », Texturing and Modeling: a Procedural Approach,
↑B. B. Mandelbrot. The Fractal Geometry of Nature. W. H. Freeman &
Co Ltd, 1982.
↑Musgrave, F. K., Kolb, C. E., & Mace, R. S. (1989, July). The synthesis and rendering of
eroded fractal terrains. In ACM SIGGRAPH Computer Graphics (Vol. 23, No. 3, p. 41-50). ACM.
↑Natali, M., Lidal, E. M., Viola, I., & Patel, D. (2013). Modeling terrains and subsurface geology. Proceedings of EuroGraphics 2013 State of the Art Reports (STARs), 155-173.
↑Smelik, R. M., De Kraker, K. J., Tutenel, T., Bidarra, R., & Groenewegen, S. A. (2009, June). A survey of procedural methods for terrain modelling. In Proceedings of the CASA Workshop on 3D Advanced Media In Gaming And Simulation (3AMIGAS) (p. 25-34).
↑Stefan Bornhofen and Claude Lattaud. Competition and evolution in virtual plant communities : a new modeling approach. Natural Computing : an international journal, 8(2) :349 385, 2009.
↑Bedrich Bene² and Erik Uriel Millán. Virtual climbing plants competing for space. In Proceedings of the Computer Animation, page 33, 2002.
↑N. Greene. Voxel space automata : modeling with stochastic growth processes in voxel space. In Proceedings of the 16th annual conference on Computer graphics and interactive techniques, pages 175-184, 1989.
↑Wojtek Palubicki. Fuzzy Plant Modeling with OpenGL- Novel Approaches in Simulating Phototropism and Environmental Conditions. 2007.
↑T. Ijiri, S. Owada, M. Okabe, and T. Igarashi. Floral diagrams and inflorescences : interactive flower modeling using botanical structural constraints. ACM Transactions on Graphics, 24(3) :720–726, 2005.
↑T. Ijiri, S. Owada, and T. Igarashi. Seamless integration of initial sketching and subsequent detail editing in flower modeling. Computer Graphics Forum, 25(3) :617–624, 2006.
↑J. M. Cohen, J. F. Hughes, and R. C. Zeleznik. Harold : a world made of drawings. In Proceedings of the 1st international symposium on Nonphotorealistic animation and rendering, pages 83 90, 2000.
↑N. Watanabe and T. Igarashi. A sketching interface for terrain modeling. In ACM SIGGRAPH Posters, page 73, 2004.
