Le générateur de labyrinthe utilisant la recherche en profondeur (DFS) est une version aléatoire de l'algorithme classique de parcours de chemins en profondeur d'abord. Implémentée avec une pile (stack), cette approche est l’une des plus simples pour générer un labyrinthe.

Regardons tout d'abord l'algorithme de parcours de chemins en profondeur : nous commençons à partir de n'importe quelle cellule et explorons le plus loin possible un chemin avant d'être bloqué et de revenir en arrière.

Pour générer un labyrinthe, il suffit de rendre aléatoire ce parcours : Cela signifie que nous choisissons un voisin non visité au hasard pour poursuivre notre chemin (d'où le serpentage du couloir). Lorsque nous nous trouvons dans une impasse (cellule sans voisins non visités), nous faisons un retour en arrière vers la cellule la plus récente (dessus de la pile).

Etapes

  • Choisir une cellule de départ et l'ajouter à la pile.
  • Tant qu'il y a une cellule dans la pile :
  • 1. Prendre la cellule en haut de la pile.
  • 2. Connecter-la à celle actuelle et visiter toutes les voisines disponibles. Les voisinnes étant: celles en bas, à gauche, à droite, en haut et non visitées.
  • 3. Sélectionner au hasard celle qui se retrouvera en haut de la pile et y introduire les autres.

Pseudo-Code

Maze DFS(int width, int height, Cell startCell)
{
  Maze maze(width, height);
  Stack pathStack(startCell);

  // While there is node to be handled in the stack
  while (!pathStack.empty())
  {
    // Handle the cell at the top of the stack:
    // Get available neighbours from bottom, left, right, top and unvisited
    Cell cell = pathStack.pop();
    auto neighbours = GetAvailableNeighbours(maze, cell);

    // If there is avaible node to process (loop to backtrack - 'pop' otherwise)
    if (!neighbours.empty())
    {
      // Randomly select a node to be processed
      auto randIdx = Random() % neighbours.size();

      // For each available node: connect to the cell, mark it as visited
      // and push it into the stack.
      for (auto i = 0; i < neighbours.size(); ++i)
      {
        cell->Connect(Cell::Visite(neighbours[i]));

        // Only the choosen item should be add to the top following a DFS strategy
        if (i != randIdx) pathStack.push(neighbours[i]);
      }

      // Add the choosen node as the next one to be processed
      pathStack.push(neighbours[randIdx]);
    }
  }

  return maze;
} 

Les labyrinthes générés ont un facteur de ramification très faible et contiennent de nombreux longs couloirs. En effet, l'algorithme explore autant que possible chaque branche avant de "revenir en arrière" (en utilisant la cellule précédente dans la pile).

La texture en forme de rivière signifie que lors de la création du labyrinthe, l'algorithme va rechercher et avancer en profondeur dans les cellules proches: Il coule dans le labyrinthe comme de l'eau. Les labyrinthes DFS ont généralement une rivière principale, ce qui entraîne une grande quantité de petites impasses.

Tout cela fait de lui un bon algorithme pour générer des labyrinthes dans les jeux vidéo.
Dans ces labyrinthes, il sera généralement relativement facile de trouver le chemin de la racine (entrée) puisque la plupart des chemins principaux y mennent. Cependant, il sera difficile d'en trouver la sortie.
Sautez à bord de l' H.urna Explorer pour créer et voir vos labyrinthes avec la Recherche en Profondeur (DFS).