Bruit Perlin, génération de contenu procédural et espace intéressant

Probablement la pire chose qui soit arrivée dans le domaine de la génération de contenu procédural (en supposant que c'est effectivement le domaine de la génération de contenu procédural, dont je ne suis pas entièrement sûr) est le bruit de Perlin. Le bruit de Perlin est incroyablement bien adapté (du moins si vous n'y regardez pas de trop près) pour générer des paysages intéressants. Dans la génération subreddit / r / procedural, une semaine ne passe pas sans que quelqu'un publie un "système de génération procédurale" qui se révèle être le bruit de Perlin visualisé en différentes couleurs. (Pendant la rédaction de cet article, deux de ces articles sont apparus!)


Je ne veux pas humilier le bruit de Perlin. Il s'agit d'un outil incroyablement utile pour la génération de procédures, qui est devenu un point d'entrée dans ce domaine pour de nombreuses personnes, dont moi. Mais en même temps, c'est très déroutant, car cela implique que la génération procédurale est beaucoup plus simple qu'elle ne l'est vraiment. La plupart des publications hebdomadaires sur les «systèmes de génération procédurale» dans / r / proceduralgeneration disparaissent sans laisser de trace lorsque leurs auteurs constatent que la prochaine étape de la génération procédurale est beaucoup plus compliquée. La vérité est que le bruit de Perlin était une sorte de coïncidence heureuse. C'est génial pour générer des paysages intéressants, mais il n'y a pas de raisons systématiques ou répétables.

Mike Cook a récemment publié un tutoriel qui contraste l'espace des possibilités avec l'espace de génération. Si vous créez un système de génération pour créer X, alors l'espace de possibilités est égal à tous les X possibles, et l'espace de génération est tout X que votre système peut réellement générer. Mike illustre cette idée avec Minecraft:


Dans le cas de mon jeu Dragons Abound , l'espace des possibilités comprend toutes les cartes possibles, y compris de nombreux cas dégénérés, par exemple, une carte entièrement composée de l'océan avec une petite île. L'espace de génération est l'espace plus petit de toutes les cartes que Dragons Abound peut réellement générer. Grâce aux différentes règles utilisées, Dragons Abound ne peut pas générer une carte de l'océan avec une petite île, donc cette carte n'est pas dans l'espace de génération de jeu. La comparaison de l'espace des possibilités avec l'espace de génération est un regard intéressant et utile sur la génération procédurale, je vous recommande donc de lire l'article de Mike , qui explique cette idée plus en détail, et il existe plusieurs exemples interactifs.

En plus de l'espace des possibilités et de l'espace de génération, il est également utile de penser à un «espace intéressant». Si nous créons X, alors c'est l'espace de tous les X intéressants . C'est-à-dire, dans le cas de mon jeu, c'est l'espace de toutes les cartes fantastiques intéressantes . Un espace intéressant est un sous-ensemble de l'espace des possibilités et, nous l'espérons, se croise avec l'espace de génération - par exemple, j'espère qu'au moins certaines des cartes générées par mon jeu se révèlent intéressantes.

Avant de poursuivre, j'admets volontiers que «l'intérêt» est un concept vague et subjectif. Mes et vos idées sur des choses intéressantes ne coïncident probablement pas. Je ne sais même pas toujours ce qui me semblera intéressant - je vois souvent quelque chose de nouveau et je le trouve intéressant, même si je ne pensais pas que j'aimerais ça avant de l'avoir vu. Pire, plus nous voyons intéressant, moins il devient intéressant. Lorsque vous voyez une fonctionnalité intéressante sur vingt cartes d'affilée, elle ne semble plus intéressante. Par conséquent, «l'intérêt» n'est pas si facile à saisir. À l'avenir, je parlerai davantage de ce qui rend les choses intéressantes (et dans le passé, j'avais quelque chose à dire sur l'idée proche d'un espace de créativité ), mais jusqu'à présent, ce n'est pas très important. Il nous suffit de convenir que certaines choses sont plus intéressantes que d'autres, et que des choses plus intéressantes sont dans un «espace intéressant», alors que des choses moins intéressantes ne le sont pas.

Est-il possible d'illustrer un espace intéressant de la même manière que Mike a montré l'espace des possibilités et l'espace de génération? Comme suggéré ci-dessus, un espace intéressant est un sous-ensemble de l'espace des possibilités, qui (si vous avez de la chance) coupe l'espace de génération:


Un bon générateur intersecte fortement avec un espace intéressant; un mauvais générateur est faible.

Ces motifs ne sont qu'une métaphore, mais dans le cadre de cette métaphore, je veux poser la question suivante: ai-je correctement indiqué les formes des différents espaces? La forme de l'espace des possibilités n'est pas vraiment importante, il suffit de contenir deux autres espaces. Mais les formes de l'espace de génération et de l'espace intéressant sont des questions plus intéressantes (sic). Je les ai peints tous les deux comme des formes compactes uniques dans l'espace des possibilités. Est-ce raisonnable?

Je crois que désigner l'espace de génération comme une ellipse compacte est un bon choix pour de nombreux générateurs procéduraux, et en particulier pour quelque chose comme le bruit Perlin. La forme implique que le générateur crée toutes les solutions dans un seul espace clairement défini et compact. Si le générateur peut créer X, il peut généralement créer tous les voisins de X. Habituellement, il n'y a pas de grands «trous» ou d'étranges distorsions dans l'espace de génération.

Les espaces de génération ressemblent généralement à ceci pour deux raisons. Premièrement, au niveau de l'application pratique, un générateur est une petite quantité de code associée à un espace de possibilités. Actuellement, Dragons Abound contient environ 28 000 lignes de code source. Comparé à de nombreux autres générateurs de cartes procédurales, c'est beaucoup (peut-être même un record), mais il est toujours extrêmement petit par rapport à l'espace de possibilités de toutes les cartes fantaisie. Par conséquent, peu importe à quel point le code du jeu est intelligent, son espace de génération n'occupera qu'une petite partie de l'espace des possibilités, et puisque le code informatique est, par définition, algorithmique et déterministe, cet espace sera relativement compact. Autrement dit, si le jeu peut créer un type de carte, il créera presque certainement de nombreuses autres cartes similaires.

La deuxième raison pour laquelle les espaces de génération sont compacts est stratégique. Pour moi, l'objectif de créer Dragons Abound est de générer des cartes intéressantes afin qu'elles se croisent autant que possible avec l'espace intéressant. Et c'est difficile d'entrer dans un espace intéressant, c'est très petit par rapport à l'espace des possibilités. En fait, c'est très, très petit. Tous ces espaces ont un grand nombre de dimensions, et la taille de l'espace augmente essentiellement en fonction du nombre de dimensions. La vraie relation entre l'espace intéressant et l'espace des possibilités ressemble à ceci:


Seul un espace intéressant est beaucoup, beaucoup plus petit. Cela oblige la génération procédurale à adhérer à certaines stratégies. Par exemple, pourquoi le jeu ne crée-t-il pas des cartes complètement aléatoires? Ensuite, l'espace de génération ressemblerait à ceci:


Seuls les points verts sont beaucoup plus petits. Les chances de passer d'une des cartes aléatoires dans un petit espace intéressant sont essentiellement nulles. Pour augmenter les chances d'entrer dans un espace intéressant, le créateur de la génération procédurale utilise des connaissances sur l'espace des possibilités et l'espace intéressant pour contrôler la génération - le créateur déplace l'espace de génération de sorte qu'il soit principalement situé dans le voisinage de l'espace intéressant, et pas seulement distribué de façon aléatoire.

Pour toutes ces raisons, il sera logique de percevoir l'espace de génération comme un espace connecté et compact.

Mais je pense que dessiner un espace aussi intéressant serait probablement complètement faux. Il doit être décrit comme un ensemble dispersé et divisé de zones de forme étrange. Pourquoi? Parce que (1) les choses peuvent être intéressantes pour diverses raisons orthogonales, et (2) l'intérêt est une fonction discontinue.

Considérez, par exemple, ces deux fragments de carte:



Le premier fragment est intéressant en ce que le littoral est finement détaillé et contient de nombreuses petites îles. Le deuxième fragment a un littoral lisse et ennuyeux, mais la côte a des caractéristiques intéressantes - elle est inhabitée et porte le nom inquiétant de «Bleak Shore». Dans un sens, ces deux fragments sont intéressants, mais pour des raisons complètement différentes. Par conséquent, nous ne nous attendons pas à ce que ces deux parties de l'espace intéressant soient voisines.

De plus, ces deux parties de l'espace intéressant ne sont probablement même pas connectées. Il ne sera en aucun cas possible de convertir progressivement la première carte intéressante en une deuxième carte intéressante sans créer plusieurs cartes sans intérêt en cours de route. Par conséquent, ces deux parties de l'espace intéressant sont séparées.

Ainsi, un espace intéressant n'est pas une zone unique, mais un ensemble de zones divisées. Tous ces espaces intéressants ont-ils des formes lisses et compactes?

Je le répète, je ne déclare pas pouvoir donner une définition complète de «l'intérêt». Mais à certains égards, nous pouvons convenir de plusieurs points. Premièrement, si X est intéressant, cela ne signifie pas que 2X sera deux fois plus intéressant. Prenons l'exemple de la côte triste - une zone de la côte mystérieuse sur la carte est intéressante, mais une douzaine d'entre elles seront très inintéressantes. Vous pouvez probablement trouver d'autres exemples de la façon dont «l'intérêt» se comporte d'une manière étrange et contre-intuitive. L'intérêt comporte donc certains éléments de discontinuité - ce n'est pas une fonction fluide qui change de manière rationnelle et prévisible lors du déplacement dans l'espace des possibilités.

Tout cela nous fait comprendre que nous devons désigner un espace intéressant comme une série de zones divisées d'une forme étrange.


Vous commencez déjà à comprendre pourquoi la création d'un bon générateur de procédures est une tâche difficile. En raison du fonctionnement des algorithmes et des limites de nos capacités, l'espace de génération sera petit et compact. Dans le même temps, nous voulons entrer dans autant de zones étranges et dispersées d'espace intéressant que possible. C'est incroyable que nous parvenions même à y entrer!

Permettez-moi maintenant de revenir au sujet du bruit Perlin. À quoi ressemblera ce schéma pour l'espace de génération de bruit Perlin dans l'espace paysager? Je pense quelque chose comme ça:


Le générateur de bruit de Perlin a plus d'intersection avec un espace particulièrement intéressant dans l'univers de tous les paysages possibles. Et c'est excellent - presque tout ce qui peut être créé en utilisant le bruit Perlin tombe dans ce domaine et semble assez intéressant.

Mais ce succès rapide est trompeur. Si vous êtes nouveau dans la génération procédurale, vous verrez comment le bruit Perlin fonctionne bien et déciderez très probablement que le bruit Perlin est une baguette magique pour générer toutes sortes de paysages intéressants, sans parler de tous les types de génération procédurale. Mais comme le montre le diagramme, l'espace de génération de bruit de Perlin est en réalité loin de beaucoup d'autres parties de l'espace paysager intéressant. La deuxième étape standard de la génération d'un paysage procédural est l'ajout de rivières. Mais si vous essayez de réaliser les rivières à l'aide du bruit de Perlin, vous constaterez que c'est impossible! En aucun cas, on ne peut étendre les limites de l'espace de génération de bruit de Perlin pour atteindre des espaces distants intéressants contenant des rivières réalistes.

Le bruit de Perlin est trompeur dans un autre sens. Plus tôt, j'ai parlé du fait que l'espace intéressant est si petit que si vous voulez y entrer, vous devez avoir une certaine connaissance de l'espace des possibilités et de l'espace intéressant afin de contrôler la génération procédurale. Mais l'algorithme de bruit de Perlin ne sait rien des paysages, des processus géologiques, de ce que les gens trouvent intéressant, et pourtant, d'une certaine manière, cela fonctionne bien sans cette connaissance! Le bruit de Perlin s'est avéré être l'exception, confirmant la règle (*). Mais si vous débutez dans la génération procédurale, vous ne connaissez probablement pas cette règle. En fait, vous déduisez une règle erronée - toute la génération procédurale dans son ensemble devrait fonctionner comme du bruit Perlin.

(* Ce n'est pas par hasard qu'il s'est avéré être une exception. Le bruit de Perlin est devenu un point de départ populaire précisément parce que c'est une exception. Il est très facile de commencer avec le bruit de Perlin sans avoir à étudier une grande quantité d'informations sur les paysages.)

Considérons un autre point de départ populaire dans la génération de contenu procédural: les schémas de donjon. Contrairement à la génération de paysages, les schémas de donjons n'ont pas d'algorithme similaire au bruit de Perlin, qui crée comme par magie des solutions dans un espace intéressant. Sur la base de ce que nous savons de l'espace de génération et de l'espace intéressant, nous pouvons supposer que les générateurs de donjons devraient soit (1) inclure des connaissances spécifiques sur les jours ultérieurs et l'intérêt, ou (2) créer des donjons pour la plupart sans intérêt. En effet, si vous regardez les générateurs de donjons publiés au cours de la dernière année dans / r / proceduralgeneration, vous verrez que la plupart d'entre eux ne contiennent aucune connaissance sur les donjons autre que la vérification de la connexion de toutes les salles, et donc les données affichées par ces projets sont plus probables qu'intéressantes .


Donc, si vous considérez que vous êtes plus ou moins d'accord avec ce que j'ai écrit, quelles leçons peut-on tirer de ce concept d'espace intéressant?

• La génération procédurale est fondamentalement complexe car l'espace intéressant est une cible très petite et difficile à atteindre.
• Malgré les exceptions occasionnelles comme le bruit Perlin, il ne faut pas s'attendre à ce que des algorithmes simples et naïfs génèrent avec succès du contenu intéressant. Une bonne génération de procédures doit inclure et utiliser une connaissance approfondie et approfondie du sujet et une compréhension de ce qui rend le contenu intéressant.
• Mais même dans les meilleurs algorithmes de génération, l'espace de génération est compact, et l'espace intéressant n'est pas, par conséquent, il est prévu que la génération procédurale manquera souvent, et il est donc nécessaire de construire les systèmes en conséquence.
• Dans les sujets complexes, l'espace intéressant est divisé et a une forme étrange. Vous ne devez pas vous attendre à ce qu'un algorithme ou une approche qui fonctionne bien dans une partie d'un espace intéressant fonctionne nécessairement aussi bien dans une autre partie. Par conséquent, nous devrions nous attendre à ce que la génération procédurale inclue de nombreux algorithmes différents utilisant différentes parties de l'espace intéressant.

Si vous commencez tout juste à travailler avec la génération procédurale, je vous recommande de penser au plaisir. Qu'est-ce qui rendra la sortie intéressante? Que doit comprendre l'algorithme pour produire des données souvent intéressantes? Quelle autre façon de produire des données pourrait être intéressante? De quel nouvel algorithme ai-je besoin pour générer ce genre d'intérêt? Comment le combiner / équilibrer avec le premier algorithme?

Par exemple, si je voulais créer un générateur de donjon, alors j'ai pensé aux donjons pendant un certain temps, et j'ai décidé qu'à mon avis, les donjons sont intéressants si:

1. On dirait qu'ils ont été créés pour devenir des entrepôts, des cellules de prison
   et autres infrastructures souterraines du grand château
2. Plus tard, ils ont été remplis de monstres et reconstruits par eux pour satisfaire leurs besoins en abris, nourriture, eau, protection contre les attaques, etc.

Vous pouvez maintenant penser à quoi devrait ressembler le niveau des entrepôts souterrains, à quoi pourrait ressembler l'algorithme pour la génération procédurale des variations de ce thème et comment les monstres peuvent changer ce schéma. Je pense que la réflexion sur de telles questions vous permettra d'en savoir plus sur la génération procédurale que sur la mise en œuvre d'un autre générateur de paysage sur le bruit de Perlin ou d'un générateur de donjon à partir de pièces et de couloirs aléatoires.