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 deuxième jeu. Le premier étant DualRUN, un jeu android (j’en reparlerai plus tard).
Le développement a commencé le 22 septembre 2016 et 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.


Histoire de Compatibilité

Mon premier jeu Android est un infinite runner dans lequel le joueur déplace 2 vaisseaux en même temps dans des couloirs en évitant les murs.
Les couloirs sont générés aléatoirement, en appliquant des règles de compatibilités.
Il faut dans un premier temps savoir qu’un élément de bordure a un début (le bas) d’un certain type et une fin (le haut) d’un certain type.
Chaque portion est ainsi compatible bord à bord avec une à plusieurs portions. On va donc créer la route en piochant dans les bordures.

Les règles de compatibilités sont très simples :

  • - la portion qu’on ajoute doit avoir un bas compatible avec le haut de la portion précédente
  • - l’écartement de la route doit toujours respecter un seuil mini

Et c’est tout. Le principe était simple, pas optimal, mais fonctionnel.

Pour Ruggnar, j’ai décidé de m’inspirer de cette méthode, mais en la poussant un peu plus loin.


Une grille et des sections

Contrairement à DualRUN où les niveaux sont infinis, dans 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, des sections 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 VerticalesSorties HorizontalesNombre de Sections
111
2216
2336
3381
44256
55625

La formule est : Nb Section = Nombre de sorties Verticales ² x Nombre de sorties Horizontales ²

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 May ##

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.


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