Comment coder votre propre générateur de carte de donjon procédural à l'aide de l'algorithme Random Walk

À mesure que la technologie évolue et que le contenu des jeux génère de plus en plus d’algorithmes, il n’est pas difficile d’imaginer la création d’une simulation réaliste offrant des expériences uniques pour chaque joueur.

Les percées technologiques, la patience et des compétences raffinées nous y conduiront, mais la première étape consiste à comprendre la génération de contenu procédural.

Bien qu'il existe de nombreuses solutions prédéfinies pour la génération de cartes, ce tutoriel vous apprendra à créer votre propre générateur de cartes de donjon à deux dimensions à l'aide de JavaScript.

Il existe de nombreux types de cartes en deux dimensions et toutes présentent les caractéristiques suivantes:

1. Zones accessibles et inaccessibles (tunnels et murs).

2. Un itinéraire connecté sur lequel le joueur peut naviguer.

L'algorithme de ce didacticiel provient de l'algorithme Random Walk, une des solutions les plus simples pour la génération de cartes.

Après avoir créé une carte de murs semblable à une grille, cet algorithme commence à un endroit aléatoire de la carte. Il continue à faire des tunnels et à effectuer des tours aléatoires pour compléter le nombre de tunnels souhaité.

Pour voir une démonstration, ouvrez le projet CodePen ci-dessous, cliquez sur la carte pour créer une nouvelle carte et modifiez les valeurs suivantes:

  1. Dimensions: la largeur et la hauteur de la carte.
  2. MaxTunnels: le plus grand nombre de tours que l’algorithme peut prendre pour créer la carte.
  3. Longueur maximale: longueur maximale de chaque tunnel choisi par l'algorithme avant d'effectuer un virage horizontal ou vertical.

Remarque: plus la valeur maxTurn comparée aux dimensions est grande, plus la carte sera dense. Plus la longueur de maxLength est grande comparée aux dimensions, plus le résultat sera «tunnel-y».

Passons maintenant à l’algorithme de génération de carte pour voir comment il:

  1. Fait une carte en deux dimensions des murs
  2. Choisit un point de départ aléatoire sur la carte
  3. Bien que le nombre de tunnels ne soit pas nul
  4. Choisit une longueur aléatoire parmi la longueur maximale autorisée
  5. Choisit une direction aléatoire vers laquelle se tourner (droite, gauche, haut, bas)
  6. Dessine un tunnel dans cette direction en évitant les bords de la carte
  7. Décrémente le nombre de tunnels et répète la boucle while
  8. Renvoie la carte avec les modifications

Cette boucle continue jusqu'à ce que le nombre de tunnels soit égal à zéro.

L'algorithme en code

Étant donné que la carte est constituée de cellules de tunnel et de paroi, nous pourrions la décrire comme des zéros et des unités dans un tableau à deux dimensions comme suit:

map = [[1,1,1,1,0],
       [1,0,0,0,0]
       [1,0,1,1,1],
       [1,0,0,0,1],
       [1,1,1,0,1]]

Comme chaque cellule est dans un tableau à deux dimensions, nous pouvons accéder à sa valeur en connaissant sa ligne et sa colonne, telles que map [row] [column].

Avant d'écrire l'algorithme, vous avez besoin d'une fonction d'assistance qui prend un caractère et une dimension en argument et renvoie un tableau à deux dimensions.

createArray (num, dimensions) {
    var array = [];
    pour (var i = 0; i 

Pour implémenter l'algorithme Random Walk, définissez les dimensions de la carte (largeur et hauteur), la variable themaxTunnels et la variable themaxLength.

createMap () {
 laisser dimensions = 5,
 maxTunnels = 3,
 longueur maximale = 3;

Créez ensuite un tableau à deux dimensions à l'aide de la fonction d'assistance prédéfinie (un tableau à deux dimensions).

let map = createArray (1, dimensions);

Configurez une colonne et une ligne aléatoires pour créer un point de départ aléatoire pour le premier tunnel.

let currentRow = Math.floor (dimensions Math.random () *),
    currentColumn = Math.floor (Math.random () * dimensions);

Pour éviter la complexité des virages en diagonale, l'algorithme doit spécifier les directions horizontale et verticale. Chaque cellule se trouve dans un tableau à deux dimensions et peut être identifiée avec sa ligne et sa colonne. Pour cette raison, les instructions peuvent être définies comme des soustractions et / ou des ajouts aux numéros de colonnes et de lignes.

Par exemple, pour accéder à une cellule autour de la cellule [2] [2], vous pouvez effectuer les opérations suivantes:

  • pour monter, soustrayez 1 de sa ligne [1] [2]
  • pour descendre, ajoutez 1 à sa ligne [3] [2]
  • pour aller à droite, ajouter 1 à sa colonne [2] [3]
  • pour aller à gauche, soustrayez 1 de sa colonne [2] [1]

La carte suivante illustre ces opérations:

Affichage des indications sur la carte.

Maintenant, définissez la variable directions sur les valeurs suivantes dans lesquelles l'algorithme choisira avant de créer chaque tunnel:

let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

Enfin, initialisez la variable randomDirection pour contenir une valeur aléatoire du tableau de directions et définissez la variable lastDirection sur un tableau vide contenant la valeur la plus ancienne randomDirection.

Remarque: le tableau lastDirection est vide sur la première boucle car il n'y a pas de valeur randomDirection plus ancienne.

laissez lastDirection = [],
    randomDirection;

Ensuite, assurez-vous que maxTunnel n'est pas zéro et que les dimensions et les valeurs maxLength ont été reçues. Continuez à trouver des directions aléatoires jusqu’à ce que vous en trouviez une qui n’est pas inversée ou identique à lastDirection. Cette boucle do while empêche d’écraser le tunnel récemment dessiné ou de dessiner deux tunnels dos à dos.

Par exemple, si votre lastTurn est [0, 1], la boucle do while empêche la fonction d'avancer jusqu'à ce que randomDirection soit défini sur une valeur autre que [0, 1] ou opposée [0, -1].

faire {
randomDirection = directions [Math.floor (Math.random () * directions.length)];
} while ((randomDirection [0] === -lastDirection [0] &&
          randomDirection [1] === -lastDirection [1]) ||
         (randomDirection [0] === lastDirection [0] &&
          randomDirection [1] === lastDirection [1]));

Dans la boucle do while, il y a deux conditions principales qui sont divisées par un || (OU) signe. La première partie de la condition comprend également deux conditions. Le premier vérifie si le premier élément de randomDirection est l’inverse du premier élément de lastDirection. Le second vérifie si le second élément de randomDirection est l’inverse du second élément de lastTurn.

Pour illustrer cela, si lastDirection est [0,1] et randomDirection est [0, -1], la première partie de la condition vérifie si randomDirection [0] === - lastDirection [0]), ce qui correspond à 0 == = - 0 et est vrai.

Ensuite, il vérifie si (randomDirection [1] === - lastDirection [1]) est égal à (-1 === -1) et est également vrai. Puisque les deux conditions sont vraies, l'algorithme retourne pour trouver une autre randomDirection.

La deuxième partie de la condition vérifie si les première et deuxième valeurs des deux tableaux sont identiques.

Après avoir choisi une direction aléatoire qui satisfait les conditions, définissez une variable pour choisir de manière aléatoire une longueur de maxLength. Définissez la variable tunnelLength sur zéro sur le serveur en tant qu'itérateur.

let randomLength = Math.ceil (Math.random () * maxLength),
    tunnelLength = 0;

Créez un tunnel en faisant passer la valeur des cellules de un à zéro alors que tunnelLength est inférieur à randomLength. Si le tunnel se trouve à l'intérieur de la boucle, il devrait se rompre.

while (tunnelLength 

Sinon, définissez la cellule actuelle de la carte sur zéro à l'aide de currentRow et currentColumn. Ajoutez les valeurs du tableau randomDirection en définissant currentRow et currentColumn où elles doivent figurer dans la prochaine itération de la boucle. Maintenant, incrémentez l'itérateur tunnelLength.

autre{
  map [currentRow] [currentColumn] = 0;
  currentRow + = randomDirection [0];
  currentColumn + = randomDirection [1];
  tunnelLength ++;
 }
}

Après que la boucle ait créé un tunnel ou rompu en touchant un bord de la carte, vérifiez si le tunnel a au moins une longueur de bloc. Si tel est le cas, définissez lastDirection sur randomDirection et décrémentez maxTunnels, puis revenez pour créer un autre tunnel avec une autre randomDirection.

si (longueur du tunnel) {
 lastDirection = randomDirection;
 maxTunnels--;
}

Cette instruction IF empêche la boucle for d'atteindre le bord de la carte et de ne pas créer de tunnel d'au moins une cellule pour décrémenter maxTunnel et modifier la lastDirection. Lorsque cela se produit, l'algorithme cherche une autre randomDirection à continuer.

Quand il a fini de dessiner les tunnels et que maxTunnels est à zéro, renvoyez la carte obtenue avec tous ses tournants et tunnels.

}
 retourner la carte;
};

Vous pouvez voir l'algorithme complet dans l'extrait suivant:

Félicitations pour la lecture de ce tutoriel. Vous êtes maintenant bien équipé pour créer votre propre générateur de carte ou améliorer cette version. Découvrez le projet sur CodePen et sur GitHub en tant qu'application de réaction.

N’oubliez pas de partager vos projets dans la section commentaires. Si vous avez aimé ce projet, appliquez-le s'il vous plaît et suivez-moi pour des tutoriels similaires.

Un merci spécial à Tom (@ moT01 sur Gitter) pour avoir co-écrit cet article.