Génération aléatoire de maps

Par haveo, le jeudi 23 juillet 2009, à 15:31 | Catégorie : | Mots-clés : novendiales, algorithme, maps et roguelike | Source

Dans le cadre d’(un)faithful, notre projet pour les Novendiales, nous avons eu à coder un générateur de maps aléatoires.

Traditionnellement, dans un rogue-like les maps ne sont en effet pas dessinées à l’avance mais générées on-the-fly pour offrir une plus grande durée de vie (il est courant de recommencer un rogue-like des dizaines voire des centaines de fois avant de le finir).

De nombreux algorithmes permettent d’accomplir cette tâche. Il y en a des plus ou moins subtils, plus ou moins efficaces et les résultats varient grandement d’un algorithme à l’autre. Au final, c’est surtout une question de goût.

Cet article a pour but de décrire l’algorithme utilisé dans (un)faithful qui sans être révolutionnaire produit des résultats assez satisfaisants.

Imaginez un instant que vous êtes l’heureux possesseur d’un donjon sous-terrain flambant neuf, malheureusement rempli de terre. La façon la plus naturelle de construire un dédale de salles et de couloirs serait de creuser une première salle puis de partir de là en creusant un peu partout. C’est exactement ce que fait le générateur de maps d’(un)faithful.

Un des aspects important du système est qu’on travaille sur des briques élémentaires. Dans (un)faithful leur nombre est limité, ce sont les couloirs et les salles. Les salles se déclinent en plusieurs briques en fonction des monstres qu’on peut trouver dedans, par exemple.

Pour placer ces briques dans notre niveau en construction on maintient une liste des "murs", endroits où on peut placer de nouvelles briques. La liste des briques fournissant des probabilités on choisit ainsi la brique qu’on veut placer. L’algorithme boucle ensuite jusqu’à trouver un mur où il peut placer cette brique. Une fois la brique placée la fonction correspondante renvoie une liste de murs à ajouter à la liste actuelle et il suffit de continuer. Généralement, on définit a priori un nombre de briques à placer. 

            ++++++	    ++++++
  +    +	    +    ++++
  +    O	    +    *  +
  +    +	    +    +  +
  ++++++	    +++++++++

O est l’endroit où l’on place la nouvelle pièce.

Cette méthode telle quelle présente un gros inconvénient. Les couloirs ne débouchent génŕalement sur rien ce qui est assez frustrant pour le joueur et peu réaliste. Ainsi, en tant que post-traitement on parcourt la map pour supprimer les bouts de couloir inutiles. Deux cas se présentent alors. Certains couloirs ont simplement besoin d’être amputés à partir du moment où ils deviennent inutiles. D’autres doivent être intégralement supprimés, y compris la porte qui y mène. 

                ++++++
  OOOOo    *#####OOO
      +    + +++*++
      +    + +    +
      ++++++ +    +
             +    +
             ++++++

Les deux types de couloirs à enlever. Les O sont des couloirs qui vont être supprimés, le o est une porte qui va disparaitre.

On parcourt toute la carte précédemment générée et pour chaque case on teste si c’est :

Si la case satisfait ces conditions, on la supprime mais on supprime également la porte qu’elle touche et le parcours de la map continue. Sinon, si la case est :

Auquel cas on supprime le couloir et on recommence les tests sur le couloir adjacent. Si la case ne vérifie aucune de ces conditions on continue à parcourir la carte.

Cette procédure permet de supprimer tous les couloirs qui ne débouchent sur rien. Les couloirs qui se divisent sans être utilisés par la suite sont aussi nettoyés. Dans un premier temps une première branche est supprimée jusqu’à arriver à l’embranchement qui a 2 voisins donc ne peut pas être suprrimé. Dans un deuxième temps la seconde branche est supprimée et quand l’algorithme arrive à l’embranchement il n’a plus qu’un voisin.

Au niveau du comportement des briques il est intéressant d’ajouter un facteur aléatoire, la position de la porte sur la pièce nouvellement créée afin de rendre les niveaux plus variés. La taille des pièces peut également varier, en revanche les couloirs sont de taille fixe puisque de toute façon ils seront nettoyés par la suite.

Nous avons aussi utilisé une technique pour tracer des murs plus jolis qu’un simple caractère. Il existe des caractères Unicode (vous pouvez aussi travailler avec des symboles ASCII ou des tiles graphiques) qui représentent tous les embranchements possibles, par exemple : "┼", "─", "│", "┌", "┬", etc. 

            ┌─────┐
  │     │
  │     ├──┐
  │     *  │
  └─────┤  │
        └──┘

        

            mur_a_droite + mur_a_gauche * 2 + mur_en_haut * 4 + mur_en_bas * 8

qui génère un entier différent pour chacune des 16 configurations (mur_foo vaut 0 ou 1). Stockez ensuite les 16 tiles correspondantes dans un tableau (certaines peuvent être identiques) et le tour est joué :-) . Pour des résultats convenables il faut tout de même associer à chaque mur un identifiant correspondant au numéro (unique) de la salle à laquelle il appartient. Un mur n’est alors adjacent à un autre que s’ils ont le même numéro. Losrqu’une salle partage un mur avec une autre celui-ci doit alors porter les deux identifiants. On peut aussi imaginer utiliser cette méthode pour dessiner des portes orientées.

Il est enfin intéressant d’apporter un soin particulier à la première salle générée. Dans notre jeu, celle-ci contient toujours un escalier, montant ou descendant. Ainsi, il ne nous reste plus qu’à placer l’autre ce que nous faisons en calculant la case la plus éloignée (:-’). Cette salle initiale peut aussi être l’antre d’un monstre particulièrement puissant qui garderait l’escalier. Si vous désirez y placer un complexe de plusieurs salles formant une suite logique il est conseillé de ne spécifier qu’une des cases comme mur. Ainsi, le jeu ne permettra pas au joueur d’accéder à une salle sans passer par la précédente. Combinée avec notre système d’effets, cette astuce permet de réaliser des niveaux où le joueur doit rejoindre la première pièce générée, tuer le boss qu’y s’y trouve et ainsi ouvrir une salle annexe contenant un escalier descendant.

L’article qui m’a inspiré : Dungeon-Building Algorithm - Mike Anderson .