Latest article: Exporter des données depuis Excel

Générer des maps de façon procédurale

Découvrez l’algorithme utilisé dans Reckless Squad pour générer des niveaux aléatoirement.

… à la manière de Reckless Squad.

Cet article est une traduction en français légèrement revue d’un article technique que j’ai écrit l’an dernier pour le site de D2P Games.

Pour Reckless Squad nous voulions un jeu qui soit hautement rejouable. Pour cela nous devions générer aléatoirement beaucoup de choses, de cette façon, le jeu continue de se réinventer lui même.

C’est aussi un gros avantage pour nous, développeurs, parce qu’on ne peut pas vraiment se permettre de réaliser toutes les maps du jeu à la main (même si on en a déjà fait pas mal pour les missions).

Alors comment marche notre algorithme ?

 

Dans Reckless Squad, chaque map est un “chemin” allant d’un point de départ à un point d’arrivée. Mais nous voulions ajouter quelques cavités pour le rendre plus naturel.

La première étape a été de choisir où commencera le chemin. Nous avons choisis le côté gauche de l’écran, parce que c’est ce à quoi nous sommes habitués dans les cultures occidentales : nous lisons de gauche à droite. Ce point de départ sera alors situé sur l’un des bords de l’écran. Nous déterminons la position exacte aléatoirement.

Une fois que nous avons ce point de départ, nous avons besoin d’un point d’arrivée. Même technique, sauf que le point se situe maintenant sur le côté droit de l’écran.

Nous avons également décidés que le chemin passerait toujours pas le centre de la map, donc j’ajoute ce point entre les deux autres. A ce moment là, j’ai déjà trois points qui forment mon chemin :

La map est une grille 2D, comme vous pouvez le voir les points sont “dessinés” dessus avec des croix.

J’itère ensuite sur les points, deux par deux, et trouve un nouveau point entre chacun d’eux. Ensuite je le déplace légèrement et aléatoirement tout en faisant attention à ce qu’il reste bien à l’intérieur de la map :

En gris vous pouvez voir l’ancien chemin, le nouveau est en blanc. Je répète l’opération :

Encore et encore :

Et après beaucoup d’autres itérations, j’ai le contour de ma map :

En noir, la “zone bloquante” et en blanc le chemin.

Il est possible de contrôler les différents paramètres de l’algorithme, comme le nombres d’itérations, la distance autorisée entre chaque points et la taille de la map pour obtenir des résultats très différents. Par exemple, voici un niveau que se devait d’être long :

Maintenant je veux “habiller” la map de façon à ce qu’elle soit jolie : ma première étape consiste à séparer les “éléments isolés” du reste de la “zone bloquante”. Les éléments isolés seront représentés par des arbres, des rochers, etc. Ils sont en vert sur cette image :

Arrivé là, je vais ajouter du “volume” aux maps car Reckless Squad utilise une perspective vue de dessus de 4/3 comme les vieux RPG 2D.

J’ai décidé que les deux tiles les plus basses seront vues de face, et le reste du dessus. Souvenez-vous des maps de la bonne vieille ère SNES :

La partie en rouge constituera la “zone bloquante”, vue de dessus. La partie verte est la bordure qui fait la transition entre cette zone et ce que j’appelle “la falaise”, à savoir la partie bleue. Il s’agit du mur vu de face.

J’applique le même principe aux maps de Reckless squad :

La bordure est ici dessinée avec cette atroce couleur rose, les deux tiles en dessous représentent la falaise.

Une fois que toutes mes tiles sont marquées “herbe”, “zone bloquante”, “bordure”, “falaise” ou “élément isolé”, je peux leur ajouter des images. Cette partie est plutôt simple : je colle des sprites par dessus. Les sprites sont triés par calques pour conserver l’effet de perspective : les unités sont dessinés par dessus l’herbe et la falaise, mais sous la zone bloquante et la bordure.

Et voilà le résultat final !

Bien que générée aléatoirement, cette map peut être retrouvée et recrée à loisir grâce au numéro que vous voyez en haut à gauche sur les captures d’écran précédentes. Il s’agit de la “seed”, le nombre qui détermine le tirage des nombres aléatoires.

En effet, ce n’est un secret pour personne mais les ordinateurs n’ont absolument aucune imagination et les nombres aléatoires sont en réalité des listes prédéfinies. La seed (graine) détermine quelle liste de nombres utiliser. En spécifiant la même seed à notre algorithme, il produira exactement le même résultat.

Et petit bonus qui n’était pas dans l’article originel, une fois que la map est générée, j’applique le pathfinding entre le point de départ et le point d’arrivée pour déterminer le chemin qu’empruntera le convoi. Cela me permet de dessiner la route que vous voyez sur la capture d’écran précédente, elle permet au joueur d’anticiper les mouvements du convoi qu’il doit protéger.

Mais ce n’est pas tout, a partir de là, je peux appliquer un coefficient à chaque tile pour savoir sa distance par rapport à ce chemin idéal. Cette distance me permet de positionner les coffres légèrement en retrait du chemin, forçant le joueur à abandonner temporairement son convoi et le mettre en danger pour aller les chercher.

Voilà ! Je pense traduire d’autres articles que j’avais écris à l’époque, donc stay tuned !

Mentions

    Discussion

    1. Jeff

      August 18, 2012
      10:32 pm

      Merci pour avoir partagé cette méthode de génération de carte très intéressante !

      Toutefois, je ne comprends pas comment tu choisis les “éléments isolés” (en vert) ; Y aurait-il une méthode pour obtenir simplement et rapidement les éléments qui touchent le chemin créé ?

      Bonne continuation !

      Reply

      • Dri

        August 18, 2012
        11:35 pm

        Pour chaque tile bloquante (noir) de la grid, je compte le nombre de voisins qui sont eux aussi bloquants. S’il y en a moins de deux, c’est un élément isolé et je le marque en vert.

        Ensuite je refais une passe : vues que les tiles marquées comme isolées sont devenues vertes, elles ne comptent plus comme voisins. Si une tile précédemment considérée comme bloquante se révèle être elle aussi isolée, je réitère. Et ce jusqu’à ce que tout soit correctement marqué.

        Reply

    Reply to Dri (cancel)