Boohu : version 0.9, tuiles et génération de cartes

Dans la dépêche précédente, il était question des nouveautés de la version 0.6 de Break Out Of Hareka’s Underground (Boohu), un jeu libre roguelike « pause‐café » d’exploration de donjon au tour par tour. Après plus de 500 commits, la version 0.9 vient d’être publiée, apportant moult nouveautés, dont une version graphique Web avec des tuiles grâce à WebAssembly.

Au passage, anaseto profite de cette occasion pour faire un petit résumé des différents algorithmes de génération de carte utilisés dans Boohu, avec captures d’écran à l’appui, comme annoncé dans la première dépêche il y a presque un an.

Sommaire

• Résumé des nouveautés
  • De 0.6 à 0.7
  • 0.8 et 0.9
• Génération de cartes
  • La marche aléatoire
  • L’automate cellulaire
  • Génération de tunnels
  • Partition binaire de l’espace
  • Petites retouches finales
  • Les monstres
• Conclusion

N. D. M. : Dans la suite de la dépêche, nous avons laissé les parties où anaseto, auteur du jeu, s’exprime à la première personne.

Résumé des nouveautés

Les nouveautés sont diverses, le journal des modifications en donne une liste assez exhaustive mais un peu longue à lire, donc on va plutôt faire un résumé ici.

De 0.6 à 0.7

Le passage de 0.6 à 0.7 apportait déjà son lot d’améliorations, en particulier d’un point de vue interface et narration. Par exemple, des animations aident à voir ce qui se passe d’important sur la carte, que ce soit les combats, un monstre qui meurt, une explosion de boule de feu, etc. De plus, le jeu offre enfin une narration ! La voici :

Chaque année, les anciens envoient quelqu’un cueillir des plantes médicinales nommées « simellas » dans les Souterrains. Cette année, l’honneur est retombé sur toi et donc te voilà ici. D’après les dires des anciens, profondément enfouis dans les Souterrains, des escaliers magiques vont te ramener dans ton village. En chemin, tu vas cueillir des simellas, ainsi que divers objets qui t’aideront à faire face aux monstres, que tu pourras combattre ou fuir…

Le gameplay s’est doté de quelques nouvelles fonctionnalités, comme les incendies et les magaras explosives. :-)

0.8 et 0.9

Concernant l’interface, je me suis bien amusé avec GrafX2, et une version Web graphique alternative avec tuiles a fait son apparition lors de la dernière version 0.9. Soit dit en passant, c’est fou ce que font deux ou trois pixels colorés de plus ou de moins, on passe facilement d’un ver de terre à un dragon !

Cette version Web utilise la nouvelle cible WebAssembly de la version en développement du compilateur Go, ce qui signifie qu’en dehors d’une petite surcouche JavaScript pour communiquer avec les API du navigateur, cela n’a pas requis de changements substantiels dans le reste du code.

D’autres améliorations d’interface ont vu le jour. Il est par exemple possible de redéfinir les raccourcis clavier, de modifier le style clair ou sombre de la zone de visibilité du joueur, ou encore d’alterner entre une mise en page par défaut avec des boutons pour la souris, et une mise en page plus compacte pour les utilisateurs n’utilisant que le clavier.

La gestion de la souris a également été améliorée, avec des boutons pour les actions courantes, un menu pour les moins courantes et une interface qui répond au mouvement de la souris et pas seulement aux clics.

Les versions 0.8 et 0.9 ont, par ailleurs, apporté beaucoup de changements au niveau gameplay, avec l’apparition de nombreux nouveaux objets, en particulier des armes (trois nouvelles et deux modifiées), des potions (quatre nouvelles) ou des bâtons magiques (deux nouveaux). Par exemple, on trouvera les gantelets d’har‐kar qui effectuent une « attaque du vent » : lors de l’attaque, tous les monstres adjacents dans une direction sont frappés et le joueur se déplace après le dernier monstre. Le nouveau bâton magique de sommeil permet de faire faire de beaux rêves aux monstres et de pouvoir les éviter. Une potion de creusement permet au personnage de creuser des murs, une autre permet d’échanger temporairement de position avec les monstres plutôt que de les combattre, et la potion de rêves permet d’obtenir par magie la position actuelle de tous les monstres qui dorment.

Deux nouveaux monstres (milfides ailées et les nixes folles) ont aussi fait leur apparition et d’autres ont maintenant plus de caractère. Par exemple, les chiens sont capables de suivre leur proie au flair, et les roches jetées par les cyclopes peuvent devenir des obstacles, dont l’emplacement varie si l’on a évité la roche, ou bien si on se l’est prise en plein dans la figure, ou bien si on l’a bloquée avec le bouclier. Il y a maintenant vingt‐deux monstres différents dans le jeu, chacun avec ses particularités. De plus, dans chaque partie, un ou deux niveaux spéciaux autour d’une certaine thématique (choisie aléatoirement) apparaissent : par exemple, un niveau rempli d’ogres et un autre où abondent les hydres sont à craindre. ;-)

Le donjon s’est aussi doté de trois niveaux supplémentaires optionnels, pour lorsque l’on se sent fort ou téméraire et que l’on veut tenter sa chance pour trouver plus de simellas.

Le jeu fournit aussi maintenant des statistiques bien plus détaillées sur les parties, avec des informations diverses, dont certaines par carte.

Enfin, une autre nouveauté, c’est la migration du site et des dépôts principaux de GitHub vers TuxFamily !

Génération de cartes

Boohu utilise six générateurs de cartes différents. Ces générateurs correspondent à quatre ou cinq méthodes assez classiques, avec quelques ajouts et combinaisons pour donner du caractère au résultat et une saveur « en ruine » adaptée aux Souterrains. La plupart des idées sont tirées d’articles de RogueBasin, le wiki le plus connu concernant les roguelikes. Dans la suite j’explique les idées telles que je les ai implémentées dans Boohu, c’est‐à‐dire sans chercher à faire l’algorithme le plus générique ou le plus paramétrable. J’avoue que mon objectif, c’est essentiellement de faire un jeu, donc j’utilise des trucs ad hoc ici et là sans me casser la tête lorsque ça a l’air d’améliorer les cartes que je veux générer pour Boohu. :)

Pour tester avec des paramètres variés sur des algos génériques, je conseille gf qui s’accompagne d’un petit programme gf_dungeons pour générer des cartes. Et c’est fait par un « Linuxfrien » aussi !

La marche aléatoire

La marche aléatoire est probablement l’algorithme le plus simple, mais il n’en est pas moins efficace. L’idée de base est la suivante : on part d’une case au hasard dans une carte remplie de murs, on enlève le mur dans cette case, on choisit ensuite une case voisine au hasard, on lui enlève le mur à son tour et puis on continue comme ça. Il y a quelques subtilités liées à ce qu’il faut faire lorsque l’on est sur un bord de la carte — si l’ on s’y prend naïvement, le résultat peut laisser à désirer ; donc on peut par exemple simuler une carte plus grande que la réelle, mais alors il faut faire attention à avoir un truc connexe (bien connecté) à la fin. Boohu évite le problème en ayant une approche mixte, simulant une carte plus grande ; mais si, lors d’une excursion en dehors de la vraie carte, on revient sur la vraie carte sur une case qui n’est pas libre, on retente la promenade. Cela a tendance à donner des cartes qui ressemblent à des grottes assez larges, avec des irrégularités ici et là.

L’idée de marche aléatoire peut prendre diverses formes. Une autre façon de faire, c’est de partir de quelques cases libres quelque part vers le milieu de la carte et avec des murs partout ailleurs. On choisit alors une case de mur au hasard et l’on démarre une marche aléatoire à partir de cette case. Dès que l’on arrive sur une case qui est déjà connectée au reste des cases libres, on s’arrête, on choisit une autre case avec un mur et on recommence. Ça donne des cartes avec plein de « branches » (chemins aléatoires) qui partent dans les coins et avec peu de boucles.

Ces algorithmes sont paramétrables, permettant d’offrir plus de diversité de cartes. Par exemple, on peut donner plus ou moins de chances de choisir certains voisins plus que d’autres, favoriser les diagonales ou les directions cardinales. Toutes les possibilités ne se valent pas toujours. Par exemple, dans le cas de Boohu, comme les cartes sont plus larges que hautes, donner plus de chances aux directions ouest et est donne de meilleurs résultats en général.

L’automate cellulaire

L’automate cellulaire, en plus de permettre de jouer au jeu de la vie, est un outil bien pratique pour générer des grottes qui ont l’air naturelles. L’idée est la suivante : initialement, on met des murs et des cases libres au hasard sur toute la carte. On peut choisir la distribution, par exemple 45 % de murs. Ensuite, on effectue des itérations sur la carte comme suit : si une case avait plus de cinq voisins qui étaient des murs, elle devient un mur à son tour, sinon elle devient libre. Après plusieurs itérations, on s’arrête et l’on a le résultat.

En vrai, c’est un peu plus compliqué que ça. On peut par exemple varier la formule et ne pas utiliser la même à chaque itération. Dans Boohu, cinq itérations sont effectuées, mais la quatrième utilise une formule sensiblement différente pour adoucir le résultat et elle considère non pas seulement les huit voisins immédiats de chaque case, mais les vingt‐quatre cases les plus proches.

De plus, l’utilisation d’automates cellulaires pose le problème de la connexité : rien dans l’algorithme n’assure que toutes les parties de la cartes sont connectées entre elles. En pratique, avec les paramètres utilisés dans Boohu, c’est presque le cas, donc la solution utilisée est de choisir une partie connectée au hasard et, dans les rares cas où elle est petite, relancer l’algorithme.

Tu as peut‐être remarqué que dans les cartes précédentes, il n’y a pas que des murs et des cases libres, il y a aussi des cases avec des herbes. Eh bien, ces herbes‐là sont générées à l’aide d’un automate cellulaire également, mais avec des paramètres différents, tant pour l’initialisation que pour les itérations.

Génération de tunnels

Une autre approche, en fait la plus utilisée à l’origine dans les roguelikes, consiste à créer des pièces, puis les connecter à l’aide de tunnels. Il y a sans doute diverses approches ; dans Boohu, c’est fait comme ça : on place une pièce — de dimensions variables — au hasard dans la carte, puis on continue à créer de nouvelles pièces de sorte que pour chaque nouvelle pièce, on crée un tunnel qui la connecte à l’une des précédentes.

Plein de paramètres peuvent entrer en jeu : la taille et la forme des pièces, la forme des tunnels (anguleux, diagonaux, etc.), s’ils ont ou non le droit de se recouper entre eux, etc. Dans Boohu, par exemple, l’algorithme autorise les tunnels à se recouper entre eux, ce qui donne souvent des boucles intéressantes, bien que moins réalistes, même si l’on peut se dire que, comme les tunnels sont en ruines, c’est normal qu’il y ait des effondrements. :)

Par exemple, avec beaucoup de petites pièces et des tunnels divers, style ruines :

Avec des pièces plus grandes et surtout des tunnels anguleux :

Partition binaire de l’espace

Une dernière méthode !

La partition binaire de l’espace permet, par exemple, de générer des cartes ressemblant à des villes : on partitionne la carte par itérations successives. Initialement, on n’a qu’une partie : la carte dans son ensemble. Ensuite, on la divise en deux horizontalement ou verticalement. On répète le processus sur les sous‐parties jusqu’à obtenir des rectangles d’une taille qui nous plaît. Alors, on peut faire quelque chose avec ces rectangles. Dans Boohu, chaque rectangle va donner une pièce rectangulaire avec une ou plusieurs portes.

Le résultat, ce sont des cartes censées représenter des petites villes souterraines abandonnées :

Bien sûr, plein de paramètres entrent en jeu ici aussi : préférer diviser horizontalement ou verticalement, un peu d’aléatoire pour choisir quand est‐ce que l’on est content avec un rectangle, où est‐ce que l’on effectue la division des rectangles (toujours pile au milieu c’est pas marrant), essayer de faire en sorte qu’il y ait quelques grosses pièces, mais aussi des petites, rajouter des jardins potagers, etc.

Petites retouches finales

Boohu fait pas mal de petites retouches sur les cartes après avoir appliqué l’algorithme principal.

Par exemple, comme je l’ai dit, on rajoute des herbes à l’aide d’un automate cellulaire sur un calque différent, puis on l’intègre simplement à la carte. Il y a juste un choix à faire, à savoir, quel calque on met au‐dessus : par exemple, dans certaines cartes avec des pièces et juste un peu d’herbe, c’est l’herbe qui l’emporte sur les murs, pour donner un style en ruine où la nature reprend le dessus. Dans les cartes qui représentent déjà des grottes naturelles, c’est le contraire qui est fait.

Dans diverses cartes, il y a aussi des portes. Parfois elles sont ajoutées en des points naturels, là où l’on s’y attend dans une pièce. D’autres fois, plus rarement, elles peuvent apparaître en des lieux moins probables, laissant penser que quelque tremblement de terre ou autre destruction sont passés par là, ou bien un architecte excentrique :). Elles sont souvent plus là pour leur intérêt d’un point de vue gameplay que pour le réalisme, et ça se sent parfois. :)

Une autre retouche finale, c’est l’ajout de quelques pièces spéciales avec divers styles (colonnes en diagonale ou non) et de diverses façons dans la plupart des cartes.

Les monstres

Enfin, il reste bien sûr à ajouter les monstres, sans lesquels le jeu serait un peu trop facile :).

   Capture d’écran en mode « wizard »

Boohu fait assez simple pour leur placement (beaucoup moins pour le choix des monstres !). Les monstres appartiennent chacun à une bande (éventuellement réduite à un seul monstre), et chaque bande est placée aléatoirement sur la carte, juste pas trop près du joueur.

Conclusion

Voilà, tout est dit — en tout cas, c’est plutôt long :). J’espère que cette dépêche aura éveillé ta curiosité pour Boohu ou du moins pour le développement d’un roguelike en général. Auquel cas, je conseille la lecture de cette FAQ, probablement la plus riche sur le sujet, traitant une multitude d’aspects dans la création du jeu.

Aller plus loin

• Nouveau site du jeu (483 clics)
• Jouer dans le navigateur (367 clics)
• FAQ sur le développement de roguelikes (51 clics)
• Articles Roguebasin sur le développement de roguelikes (50 clics)