Comment coder votre propre générateur de carte de donjon procédural à l'aide de l'algorithme de marche aléatoire

À mesure que la technologie évolue et que le contenu du jeu est généré de manière plus algorithmique, il n'est pas difficile d'imaginer la création d'une simulation réaliste avec des expériences uniques pour chaque joueur.

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

Bien qu'il existe de nombreuses solutions prêtes à l'emploi pour la génération de cartes, ce tutoriel vous apprendra à créer votre propre générateur de cartes de donjon bidimensionnel à partir de zéro en utilisant JavaScript.

Il existe de nombreux types de cartes bidimensionnelles, et toutes présentent les caractéristiques suivantes:

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

2. Un itinéraire connecté que le joueur peut parcourir.

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

Après avoir créé une carte des murs en forme de grille, cet algorithme part d'un endroit aléatoire sur la carte. Il continue à faire des tunnels et à prendre des virages aléatoires pour compléter le nombre de tunnels souhaité.

Pour voir une démo, 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 lors de la création de la carte.
  3. MaxLength: la plus grande longueur de chaque tunnel que l'algorithme choisira avant d'effectuer un virage horizontal ou vertical.

Remarque: plus le maxTurn est grand par rapport aux dimensions, plus la carte sera dense. Plus le maxLength est grand par rapport aux dimensions, plus il aura l'air «tunnel-y».

Ensuite, passons en revue l'algorithme de génération de carte pour voir comment cela:

  1. Crée une carte bidimensionnelle des murs
  2. Choisit un point de départ aléatoire sur la carte
  3. Alors que le nombre de tunnels n'est pas nul
  4. Choisit une longueur aléatoire à partir de la longueur maximale autorisée
  5. Choisit une direction aléatoire vers laquelle tourner (droite, gauche, haut, bas)
  6. Dessine un tunnel dans cette direction tout 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 se poursuit jusqu'à ce que le nombre de tunnels soit nul.

L'algorithme dans le code

Étant donné que la carte se compose de cellules de tunnel et de paroi, nous pourrions la décrire comme des zéros et des uns dans un tableau bidimensionnel 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]]

Étant donné que chaque cellule est dans un tableau à deux dimensions, nous pouvons accéder à sa valeur en connaissant sa ligne et sa colonne comme map [ligne] [colonne].

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

createArray(num, dimensions) { var array = []; for (var i = 0; i < dimensions; i++) { array.push([]); for (var j = 0; j < dimensions; j++) { array[i].push(num); } } return array; } 

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

createMap(){ let dimensions = 5, maxTunnels = 3, maxLength = 3; 

Ensuite, créez un tableau bidimensionnel à l'aide de la fonction d'assistance prédéfinie (tableau bidimensionnel de uns).

let map = createArray(1, dimensions);

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

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

Pour éviter la complexité des virages diagonaux, 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 directions peuvent être définies comme des soustractions et / ou des ajouts aux numéros de colonne et de ligne.

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 , ajoutez 1 à sa colonne [2] [3]
  • pour aller à gauche , soustrayez 1 de sa colonne [2] [1]

La carte suivante illustre ces opérations:

Maintenant, définissez la directionsvariable sur les valeurs suivantes que l'algorithme choisira avant de créer chaque tunnel:

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

Enfin, lancez randomDirectionvariable pour contenir une valeur aléatoire du tableau de directions et définir la lastDirectionvariable sur un tableau vide qui contiendra l'ancienrandomDirectionvaleur.

Remarque: le lastDirectiontableau est vide sur la première boucle car il n'y a pas de randomDirectionvaleur plus ancienne .

let lastDirection = [], randomDirection;

Ensuite, assurez-vous que ce maxTunneln'est pas zéro et que les dimensions et les maxLengthvaleurs 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 permet d'éviter d'écraser le tunnel récemment dessiné ou de dessiner deux tunnels dos à dos.

Par exemple, si votre lastTurnest [0, 1], la boucle do while empêche la fonction d'avancer jusqu'à ce qu'elle randomDirectionsoit définie sur une valeur qui n'est pas [0, 1] ou l'inverse [0, -1].

do { 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 se compose également de deux conditions. Les premiers on vérifie si le randomDirection« premier élément s est l'inverse de la lastDirection» s premier élément. Le second vérifie si le randomDirectiondeuxième élément du 's est l'inverse du lastTurndeuxième élément du ' s.

Pour illustrer, si le lastDirectionest [0,1] et randomDirectionest [0, -1], la première partie de la condition vérifie si randomDirection[0] === - lastDirection[0]), ce qui équivaut à 0 === - 0, et c'est vrai.

Then, it checks if (randomDirection[1] === — lastDirection[1]) which equates to (-1 === -1) and is also true. Since both conditions are true, the algorithm goes back to find another randomDirection.

The second part of the condition checks if the first and second values of both arrays are the same.

After choosing a randomDirection that satisfies the conditions, set a variable to randomly choose a length from maxLength. Set tunnelLength variable to zero to server as an iterator.

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

Make a tunnel by turning the value of cells from one to zero while the tunnelLength is smaller than randomLength. If within the loop the tunnel hits the edges of the map, the loop should break.

while (tunnelLength < randomLength) { if(((currentRow === 0) && (randomDirection[0] === -1))|| ((currentColumn === 0) && (randomDirection[1] === -1))|| ((currentRow === dimensions — 1) && (randomDirection[0] ===1))|| ((currentColumn === dimensions — 1) && (randomDirection[1] === 1))) { break; }

Else set the current cell of the map to zero using currentRow and currentColumn. Add the values in the randomDirection array by setting currentRow and currentColumn where they need to be in the upcoming iteration of the loop. Now, increment the tunnelLength iterator.

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

After the loop makes a tunnel or breaks by hitting an edge of the map, check if the tunnel is at least one block long. If so, set the lastDirection to the randomDirection and decrement maxTunnels and go back to make another tunnel with another randomDirection.

if (tunnelLength) { lastDirection = randomDirection; maxTunnels--; } 

This IF statement prevents the for loop that hit the edge of the map and did not make a tunnel of at least one cell to decrement the maxTunnel and change the lastDirection. When that happens, the algorithm goes to find another randomDirection to continue.

When it finishes drawing tunnels and maxTunnels is zero, return the resulting map with all its turns and tunnels.

} return map; };

You can see the complete algorithm in the following snippet:

Congratulations for reading through this tutorial. You are now well-equipped to make your own map generator or improve upon this version. Check out the project on CodePen and on GitHub as a react application.

Thanks for reading! If you liked this story, don't forget to share it on social media.

Special thanks to Tom  for co-writing this article.