Espace de génération et espace d'opportunité

Dans ce tutoriel, je vais parler de deux termes que j'utilise pour décrire les générateurs procéduraux: un espace génératif et un espace de possibilité . Nous définirons ces deux termes et considérerons ensuite des exemples interactifs pour comprendre la différence entre eux. Ces termes sont vraiment utiles pour décrire un générateur procédural et pour comprendre la différence entre deux générateurs. Commençons!


Imaginez un énorme livre qui fournit une capture d'écran de chaque monde Minecraft individuel. Chaque capture d'écran est marquée d'une graine aléatoire , un numéro unique que vous pouvez entrer dans Minecraft et générer ce monde. La première page montre le monde généré à partir de seed = 0, la page suivante montre le monde à partir de seed = 1, etc. En général, le générateur de monde Minecraft contient 2 ⁶⁴ valeurs de génération aléatoires, et c'est un nombre énorme: le jeu peut générer 18 446 744 073 709 551 616 mondes. Chaque fois que vous cliquez sur «Nouveau monde», un monde est créé à partir de l'une de ces graines. Le nombre 2 ⁶⁴ est la taille de l'espace de génération Minecraft, beaucoup de tout ce que le jeu peut générer.


Imaginez maintenant que le monde Minecraft se compose uniquement d'herbe ordinaire, se répandant sans fin dans toutes les directions. En dessous, il n'y a pas de grottes, pas de pierre, pas d'arbres et de collines, pas d'animaux. Une seule couche de tuiles d'herbe. En plus d'être très ennuyeux, un tel monde ne sera jamais généré dans Minecraft (sauf si le modding est utilisé). Nous pouvons l'imaginer, nous pouvons le décrire, même ouvrir Minecraft et le créer nous-mêmes manuellement - mais Minecraft ne peut pas le générer. Comment le savons-nous? Vous pouvez le prouver de différentes manières, mais la façon la plus simple de se souvenir des biomes de Minecraft est dans des zones telles que le désert ou la jungle dispersées à travers le monde. Dans notre exemple avec le monde de l'herbe, ils ne sont pas, donc, nous savons qu'il ne peut pas être créé avec un générateur standard.

Le monde de l'herbe se trouve dans ce que nous appelons l' espace des opportunités des mondes Minecraft - l'ensemble de tous les mondes Minecraft possibles que nous pouvons imaginer, imaginer ou décrire. Mais le monde de l'herbe n'est pas dans l' espace de génération Minecraft, car il ne peut pas être créé par le générateur procédural du jeu. Nous pouvons imaginer le monde Minecraft avec une réplique exacte de Persépolis à l'échelle, ou le monde sous la forme de votre sculpture en pierre assis et lisant cet article - ce sont tous des mondes Minecraft possibles , mais ils ne seront pas générés par le jeu.


Le diagramme ci-dessus nous donne une idée de ce à quoi tout cela ressemble. Tout ce qui se trouve dans l'espace de génération de Minecraft doit également être dans son espace de possibilités, car si Minecraft peut générer quelque chose, il devrait être possible de le créer dans Minecraft! Mais tout l'espace des possibilités n'est pas dans l'espace de génération, y compris notre exemple avec un monde composé d'herbe. Mais l'échelle n'est pas respectée dans ce schéma. En fait, l'espace des possibilités de Minecraft est beaucoup, beaucoup plus grand que son espace de génération.

Pour comprendre sa taille, calculons la taille d'un seul monde Minecraft. Le volume est la largeur multipliée par la hauteur, multipliée par la profondeur. Par défaut, les mondes Minecraft ont une hauteur de 256 tuiles, et ils commencent à se diviser en environ 30 000 000 de tuiles dans toutes les directions à partir du point de départ, c'est-à-dire que le volume approximatif du monde est:

256 x 60 000 000 x 60 000 000 = 921 600 000 000 000 000

Chacun de ces blocs peut être n'importe quel élément: pierre, herbe, eau, air. Pour notre évaluation, nous serons généreux et n'utiliserons que des "blocs du monde", qui, selon le wiki Minecraft, sont de 64 types . Cela signifie que chaque bloc dans le monde Minecraft a 64 états possibles. La formule de calcul du nombre de mondes possibles est égale au nombre d'options d'état pour chaque bloc élevé à la puissance du nombre de blocs:

64 921 600 000 000 000 000 Minecraft

Ce nombre est si grand que je n'ai pas pu trouver sur Internet une calculatrice capable de le calculer.


Pour aller encore plus loin dans les espaces de génération et de possibilités, nous avons besoin d'un exemple que nous pourrions mieux mettre en tête. Par conséquent, dans le reste du tutoriel, nous examinerons les niveaux d'un jeu de plateforme 2D pour des jeux comme Super Mario Bros. ou Spelunky . Nous examinerons plusieurs générateurs de niveaux pour les plateformes 2D. Dans l'article d'origine, ils sont tous interactifs, vous pouvez donc générer vos propres niveaux. Au cours de leur étude, nous poserons des questions sur leur espace de génération. Tous les exemples sont disponibles sur notre GitHub sous forme d'esquisse open source écrite dans Processing .

En cours d'étude, je vais poser des questions en gras, par exemple: quelle est la taille de l'espace d'opportunités pour ces niveaux de plateforme? Vous pouvez les ignorer en toute sécurité si vous voulez simplement lire l'article et jouer avec des exemples. J'ajoute parfois des conseils pour répondre aux questions, par exemple:

Astuce: les niveaux ont une largeur de 40 tuiles et une hauteur de 10 tuiles, et chaque tuile peut être l'un des trois éléments: un vide, un sol ou un bloc bonus.

Vous pouvez faire une pause à l'invite et ne pas faire défiler la page si vous ne voulez pas lire la réponse finale. Jetons donc un œil à notre premier générateur.

Algorithme 1: aléatoire

Notre générateur de premier niveau est très simple - il est complètement aléatoire. Chaque carte a une tuile départ gauche et une tuile sortie droite. Toutes les autres tuiles de carte ont 33% de chances d'être vides, 33% d'être occupées et 33% d'être un bloc bonus.


Vous avez probablement remarqué que ce n'est pas un très bon générateur de niveau. En fait, la plupart de ces niveaux sont même impossibles à jouer, sans parler de leur intérêt. Générez quelques niveaux supplémentaires et réfléchissez à la question: quelle est la taille de l'espace de génération d'un tel générateur par rapport à l'espace des possibilités?

Astuce: pouvez-vous trouver un niveau qui soit dans l'espace des possibilités, mais pas dans l'espace de la génération? Pouvez-vous trouver un niveau que ce générateur ne peut pas créer?

La bonne réponse est que l'espace de génération de ce générateur est le même que l'espace des possibilités. N'importe quelle tuile sur la carte peut prendre n'importe quelle valeur, donc tout niveau que nous pouvons imaginer se trouve dans l'espace de génération. Les niveaux les plus fascinants et les plus intéressants se trouvent dans cet espace de génération, même la carte sur laquelle SUPER MARIO EST IMPRESSIONNANT est écrite en blocs bonus. Malheureusement, l'espace de génération est si grand qu'il est extrêmement peu probable de trouver un bon niveau. Comme vous pouvez le voir en cliquant sur le générateur, la plupart des niveaux ne sont que des ordures.

Algorithme 2: dessiner des formes aléatoires

Notre prochain algorithme est un peu plus compliqué, et il crée des niveaux qui ressemblent davantage à ce que vous pouvez appliquer dans le jeu. À partir d'un niveau vide, il sélectionne un point aléatoire quelque part, puis trace une ligne ou un carré de blocs de bonus ou de terrain. Il effectue cette opération 20 fois, créant plusieurs formes tirées au hasard sur le niveau. Comme précédemment, vous pouvez cliquer sur l'exemple de l'article d'origine pour redémarrer l'algorithme et générer un nouveau niveau.


Cela commence déjà à ressembler à un niveau pour le jeu de plateforme, non? Lorsque vous générez des niveaux, imaginez mentalement comment vous les jouez (soyez généreux si nécessaire - ajoutez la capacité de double saut, si nécessaire, ou la capacité de sauter en dehors du plafond de la carte).

Combien de niveaux doivent être générés avant d'en trouver au moins un que vous pouvez traverser?

Ne vous efforcez pas d'obtenir une précision absolue dans vos procédures mentales, faites simplement une estimation approximative.

Lorsque je fais cet exercice avec le public, il faut généralement environ 10 tentatives pour trouver le niveau en moyenne. De combien aviez-vous besoin? Rappelez-vous ce nombre et regardez maintenant la variation du même générateur illustré ci-dessous. Le générateur est le même que nous venons de voir, mais maintenant il dessine au niveau non pas 20, mais 10 chiffres. Maintenant, comptez encore: combien de niveaux devez-vous générer avant de trouver celui que vous pouvez traverser?


Il vous a probablement fallu moins de temps pour trouver un niveau jouable. Arrêtons-nous une minute et réfléchissons aux différences entre les deux générateurs, qui sont presque identiques, à l'exception d'une légère différence de paramètres. Quel générateur a un plus grand espace de génération - un générateur à 20 chiffres ou à 10?

Astuce: pensez au niveau créé par un générateur à 10 chiffres - un générateur à 20 chiffres peut-il le créer? Et puis pensez à l'exemple inverse.

La bonne réponse est qu'un générateur à 20 chiffres a un plus grand espace de génération; en fait, il contient tout l'espace de génération du générateur à 10 chiffres. Pour le montrer, imaginez n'importe quel niveau d'un générateur à 10 chiffres. Notre générateur à 20 chiffres peut le créer en rendant accidentellement les mêmes dix chiffres, puis en les dessinant accidentellement une deuxième fois les uns sur les autres. Cependant, aucun niveau à vingt chiffres séparés ne peut être tracé à l'aide d'un générateur à 10 chiffres.

Cela signifie que le générateur à 20 chiffres a plus de niveaux, y compris des niveaux intéressants. Mais il convient de rappeler qu'il était beaucoup plus facile de trouver un niveau jouable avec un générateur à 10 chiffres. Si vous deviez choisir un générateur pour votre jeu vidéo, lequel utiliseriez-vous? Il n'y a pas de réponses correctes, mais c'est une décision très importante, qui doit souvent être prise lorsque l'on travaille avec des générateurs procéduraux. Un générateur peut générer plus de variabilité et a plus de surprises, l'autre est plus fiable et moins stressant pour le joueur.

Algorithme 3: Fragments de niveau

Cet algorithme est basé sur le générateur de niveau utilisé dans Spelunky; Vous pouvez en lire plus ici . Le générateur de niveau sélectionne au hasard un fragment d'un niveau créé par une personne (moi) et l'insère dans un niveau. Il sélectionne ensuite un autre fragment aléatoire du niveau et l'insère côte à côte, et ainsi de suite, jusqu'à ce que le niveau soit terminé. Voici le générateur, le fond est assombri pour que les bordures des fragments soient clairement visibles:


Combien de temps faut-il maintenant pour générer un niveau jouable? Vous constaterez que presque tous les niveaux sont jouables. Nous savons exactement ce qu'il y a dans chaque fragment, c'est-à-dire que nous pouvons garantir qu'il y aura des objets intéressants au niveau sur lesquels vous pourrez sauter et des obstacles que vous devrez éviter. En même temps, il est plus dynamique que le niveau statique - nous ne savons pas quels fragments y apparaîtront et dans quel ordre. L'algorithme Spelunky est encore plus riche que cela, il prend en compte le mouvement vertical et des variations aléatoires sont ajoutées à chaque fragment. Darius Casemi a créé le génial générateur de niveau interactif Spelunky, que vous pouvez trouver ici .

De tels générateurs sont un bon compromis entre d'agréables surprises et la capacité de contrôle. Lorsqu'un générateur effectue une sélection à partir d'un catalogue d'éléments et les connecte entre eux (parfois selon des règles spéciales, comme dans Spelunky), nous l'appelons un générateur basé sur la grammaire . La grammaire nous permet de décider quels blocs de construction un générateur procédural doit utiliser, mais moins rigoureux sur la façon de les connecter. Mais ce contrôle et cette sécurité ont un prix. Examinez à nouveau le générateur, puis réfléchissez aux exemples précédents. À quelle fréquence un tel générateur de niveau nous surprendra-t-il?

Au départ, le générateur est plein de surprises, car nous rencontrons chaque fragment pour la première fois. Mais si vous jouez plus, vous commencez rapidement à remarquer où se termine l'un et où commence un autre fragment. Même s'il y a des centaines de combinaisons de fragments dans ce générateur, en quelques niveaux vous commencez à vous sentir comme si vous les aviez tous vus. La simplicité et la facilité de compréhension de la grammaire des fragments sont excellentes pour les développeurs, mais elles peuvent être un inconvénient en termes de plaisir pour les joueurs.

Algorithme 4: Conception humaine

Comme dernier exemple, nous ne considérerons pas un algorithme, mais un type de processus créatif très différent: le travail des personnes en level design. Cliquez sur le générateur dans l'article original et vous obtiendrez l'un des deux premiers niveaux de Super Mario Bros. (plus précisément, leur tout début).


En commençant par une coïncidence absolue, nous nous sommes retrouvés avec cela, l'un des exemples les plus célèbres de conception de plateformes 2D dans l'histoire. Bien sûr, ce n'est pas un générateur, mais dans un sens, ces niveaux peuvent être perçus comme des générateurs qui ne créent qu'un seul niveau de haute qualité. Le compromis maximum entre contrôle et qualité. En regardant ce niveau, pensez à tous les générateurs que nous avons examinés aujourd'hui et réfléchissez à la question: lequel de ces générateurs contient ces fameux niveaux dans leur espace de génération? .

• Génération aléatoire
• Génération de 20 formes
• Génération de 10 formes
• Fragments de niveau

Seul le premier générateur est capable de créer de tels niveaux. Les générateurs de formes pourraient les créer si nous augmentions le nombre de formes possibles à dessiner, mais cela augmenterait également considérablement le nombre de niveaux mauvais ou étranges. Un générateur de fragments de niveau pourrait le faire si nous lui donnions un ensemble différent de fragments, mais toutes les autres combinaisons de ces fragments seraient-elles jouables?

Cela nous montre combien il est difficile de créer un générateur procédural. Nous voulons considérer nos générateurs comme le contenu habituel du jeu, imaginer comment le joueur passe par un certain niveau et l'apprécie. Mais en tant que concepteurs de génération, nous devons penser à tout l'espace de génération, et pas seulement à un seul exemple de celui-ci. Quelle est la taille de l'espace? Quelle est sa richesse en surprises? À quelle fréquence cela crée-t-il quelque chose d'ennuyeux ou de mauvais? Pouvons-nous détecter et filtrer ces cas, ou devons-nous rechercher une solution? Ce ne sont que quelques-uns des problèmes que vous devez prendre en compte lors de la création de quelque chose pour la génération.

Pour résumer

Aujourd'hui, nous avons découvert les concepts suivants:

Espace de génération

L'espace de génération du générateur de contenu procédural (par exemple, le générateur de monde Minecraft) est l'ensemble de tous les résultats qu'il peut générer. Si nous changeons l'algorithme ou définissons une valeur différente pour la variable, l'espace de génération changera.

Espace d'opportunité

L'espace des possibilités pour un certain type de contenu (par exemple, le monde Minecraft) est l'ensemble de tous les exemples d'un tel contenu que nous pouvons présenter ou décrire. Habituellement, mais pas toujours, il est beaucoup plus grand que l'espace de génération d'un générateur procédural.

Plus n'est pas toujours mieux

Un générateur avec un grand espace de génération a généralement plus de bon contenu, un contenu plus inattendu et un contenu plus diversifié. Mais généralement, il a plus de contenu indésirable, plus de contenu ennuyeux et plus de contenu inapproprié.

Un générateur avec moins d'espace de génération est plus facile à contrôler, plus facile à tester et plus facile à comprendre. Mais cela peut le rendre plus prévisible et moins surprenant.

Trouver des moyens d'équilibrer les forces et les faiblesses de ces deux opposés est l'art de créer des logiciels de génération!

Lecture supplémentaire et remerciements

Ceci conclut mon tutoriel! Merci d'avoir lu.

Parmi les documents intéressants sur le sujet que nous avons examiné, je recommande ce qui suit:

• Spelunky de Derek Yu est une excellente histoire sur la création de Spelunky, y compris une discussion sur le générateur de procédures du jeu.
• Tracery Tutorials, par Kate Compton - Apprenez à écrire de la grammaire textuelle, une excellente façon de pratiquer la réflexion sur l'espace de génération!
• L'excellent chapitre du livre du Dr Gillian Smith sur la gamme de l'expressivité (que nous couvrirons dans un futur tutoriel).
• Le Dr Smith a également de nombreuses ressources gratuites, comme son excellent discours de GDC sur les compromis dans la génération procédurale.
• Et enfin, n'oubliez pas que tous les générateurs de l'article se trouvent dans le sketch open source Processing ( ici ).