Génération de niveau dans Ruggnar
Par : Cyrille BONARD
@ : ProcGen AT ruggnar DOT com

Pour ceux ne connaissant pas Ruggnar, il s’agit d’un jeu de plateforme se déroulant dans des environnements sombres, dans lesquels le joueur contrôle un nain (du nom de Ruggnar) qui utilise des bougies pour s’éclairer, à la recherche de trésor.

Dans le jeu, il y a plusieurs modes. Un mode histoire, avec des niveaux faits main et un mode aléatoire. C’est ce dernier qui nous intéresse aujourd’hui.

Je vais essayer de vous présenter la méthode que j’utilise de manière claire.


Un peu d'histoire

Ruggnar est mon premier jeu, et son développement a commencé le 22 septembre 2016.
J’ai pris très tôt la décision de participer à un événement local mensuel autour du jeu indé à Metz (France).

Lors de ma première participation, on m’a incité à faire un générateur de niveau et on m’a mentionné Spelunky.
J’aime beaucoup Spelunky, je savais que les niveaux étaient générés, mais je ne m’étais jamais intéressé au sujet avant qu’on m’en parle.

Je suis tombé sur un article traitant justement de la méthode utilisée dans Spelunky.
Je l’ai lu, relu et j’ai décidé de m’en inspirer en partie.


Une grille et des sections

Dans un niveau de Ruggnar, je dois avoir un point de départ et un point d’arrivée dans un espace clos.
Je suis ainsi parti sur une grille de taille variable, composée de sections.
J’ai pris la décision de faire mes sections à la main, chacune ayant une taille définie.
La raison est assez simple : je veux m’assurer qu’une section est bien faisable.

Voici un exemple :

Chaque section a une disposition qui lui est propre, avec sols, murs, éléments de déco, pièges, pièces…
Elle a aussi un point de départ, un trésor (point d’arrivée), un point de sauvegarde, une clé et une bougie.


Définition des sections

Une section est définie par ses bords, chaque bord représentant un type de sortie possible.
Lors de la génération du donjon, une section ajoutée doit avoir des bords compatibles avec les sections déjà présentent sur la grille.

Sur l’image précédente, il y a des cases à bordures grises. Ces cases sont les sorties de la section.
Pour simplifier, nous appellerons Sorties les bordures de sections, que ce soient des murs extérieurs ou plafond/sol.

Voici un exemple de Sorties :

Type 1 Type 2 Type 3 Type 4 Type 5 Type 6

Une section étant composée de 4 bords, il faut piocher dans les sorties correspondantes, 2 pour les sols et plafonds et 2 pour les murs.

Selon le nombre de type de Sorties prévues, le nombre de sections à faire va vite augmenter :

Sorties Verticales (v)Sorties Horizontales (h)# de Sections (s)
111
2216
2336
3381
44256
55625

La formule est donc : s = (v * h)²

Selon les nombres de sorties prévues, il est important d’avoir l’ensemble des sections sous peine de se retrouver avec un trou dans la grille.

Mais en ne faisant que le strict minimum, on va vite retrouver les mêmes zones. C’est pourquoi, il faut penser à en faire plusieurs de chaque type pour qu’il y ait plus de choix lors de la génération de la carte.

Dans Ruggnar, j’ai encore un autre moyen pour générer de la variété.
Dans la partie précédente, je vous ai parlé de ce qu’il y a dans une section.
Parmi toutes les sections de ma grille finale, je choisi un point de départ et un trésor.
Les pièges ont une probabilité d’apparition, plus ou moins grande.
Les pièces, bougies, clé et points de sauvegarde sont placés selon la taille de la grille finale.
Une même zone apparaîtra ainsi différemment d’une partie à l’autre.


Génération de la carte

La zone de jeu est créée sur une grille où chaque case est une section. Une fois le processus terminé, le niveau est créé selon les sections choisies.
Dans cet article, je vais travailler sur une grille de 5x5.


Etape 1

La génération du niveau commence par la mise en place dans la grille de sections infranchissables.
La grille ne sera ainsi plus un simple rectangle, mais une zone en partie infranchissable. Ainsi, on impose des structures moins rectilignes, moins prévisibles

On peut observer ici que 2 zones sont fermées. Il sera impossible de passer par là, les murs seront pleins.


Etape 2

Chaque case libre de la grille est donc une section.
Pour chaque case, je dois chercher les sections compatibles (parmi toutes les sections créées) avec les voisins directs (Nord, Sud, Est, Ouest) :

  • - Chaque mur doit être compatible avec le mur adjacent
  • - Les murs en bordure de grille sont obligatoirement des murs fermés, pour que la zone soit une zone close.

## Nouvel ajout 11 Mai 2018##

Si vous regardez attentivement le niveau généré sur l'image suivante, vous remarquerez des zones redondantes.
Pour éviter ce comportement, avant d'ajouter une section, je vérifie combien de fois celle-ci a été utilisée dans le niveau. Idéalement, aucune.
L'idée ici est d'avoir un niveau avec seulement des sections différentes.

Sur un seul niveau, j'ai toutes les pièces dont j'ai besoin pour créer un niveau.
Mais avec le nouveau mode de jeu, le joueur pénètre dans un château de 10 étages, je dois vérifier, étage par étage, avec la même technique pour avoir un château sans sections répétées d'un étage à l'autre.
Donc, je vérifie d'abord les sections jamais placées, puis placées une fois, deux fois, et ainsi de suite, tant que je n'ai pas trouvé de section compatible.
Maintenant, avec ce système, les niveaux sont encore plus tordus.


La grille générée montre 1 nouvelle zone fermée.
On peut observer que les murs sont bien identiques bord à bord.

Ici vous pouvez voir un niveau généré, plus visuel que la grille simulée.
Il s'agit de la grille dans laquelle les sections ont été ajoutées


Etape 3

En laissant la grille ainsi, et en la remplissant, on prend le risque d’enfermer le joueur dans une zone sans point de sortie, ou n’ayant pas le bon nombre de clé.
On va simplement utiliser un algorithme de remplissage par diffusion pour identifier les zones ceintes par des murs.

Chaque couleur représente une zone fermée.
Ici, il y a 3 zones différentes, les sections fermées ne comptant pas.

  • - la zone rouge a une taille de 11 sections
  • - la zone bleue a une taille de 9 sections
  • - la zone verte a une taille de 2 sections

Etape 4

Il s’agit de la dernière étape avant la création finale du niveau.
Pour que le joueur ait une zone de jeu conséquente, je ne conserve que la zone la plus grande.
Je vais donc nettoyer la grille en ne conservant que la zone rouge.

## Nouvel ajout 10 janvier 2019 ##

Lorsqu'il y a plusieurs zones séparées, l'algorithme, dorénavant, conserve la plus grande zone, comme précédement, mais conserve aussi la seconde zone la plus grande (sous réserve qu'elle respecte une taille minimale requise).
En l'état, le joueur ne pourrait pas compléter le niveau. Des pièces, ou la sortie, risquent de se retrouver dans l'autre zone.
L'idée est, ici, de relier les 2 zones entre-elles en utilisant des zones de "téléportation". Une porte est positionnée dans chaque zone, le joueur pouvant ainsi passer de l'une à l'autre.


Etape 5

Ma grille est terminée, il me reste les sections dans lesquelles le joueur va évoluer. Je vais donc pouvoir créer mon niveau en y mettant mes tuiles, mes décors, mes pièges




Conclusion (pour le moment)

Avec ce mode aléatoire, vous avez accès a un nombre conséquent de niveaux. Chaque partie sera différente de la précédente, le challenge sans cesse renouvelé.
Cet article sera complété par la suite à mesure de l'évolution du mode aléatoire de Ruggnar.

Si vous avez des questions, des commentaires, n'hésitez pas à me contacter via Twitter, si vous désirez des infos sur Ruggnar.

Ruggnar est en Accès Anticipé sur itch.io. Si vous souhaitez donner un coup de pouce, ça peut vraiment aider.



Bonus - Simulateur