Labyrinthe crée par un algorithme de recherche en profondeur depuis le coin supérieur gauche (taille de 75x50).

Inondation (Flooding) depuis le noeud racine (coin supérieur gauche).

L'arbre de décision présentant la topologie de la structure de données.

Labyrinthe crée par un algorithme de recherche en profondeur depuis le centre (taille de 75x50).

Inondation (Flooding) depuis le noeud racine (centre).

L'arbre décisionnel présentant la topologie de la structure de données (depuis le centre).

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.

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.

1. L'algorithme DFS peut être démarré n’importe où, commençons au milieu.

2. Connection et visite de tous les voisins. La cellule Ouest/Gauche (sélectionnée au hasard) sera ajoutée au dessus de la pile et son chemin prolongé (cf. diapositive suivante).

Les cellules de couleur bleue signifient être dans la pile et en attente de traitement.

3. La cellule Ouest est ensuite traitée. Une fois encore, la cellule Ouest/Gauche est sélectionnée au hasard pour prolonger le chemin.

4. Après quelques itérations, l’algorithme est sur le point d’avoir visité toutes les cellules.

5. Toutes les cellules sont traitées, la pile est vide: le labyrinthe est terminé !

Sautez à bord de l' H.urna Explorer pour créer et voir vos labyrinthes avec la Recherche en Profondeur (DFS).