Labyrinthe créé par une Division Récursive (taille de 75x50)

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

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

La Division Récursive est l'algorithme le plus rapide de génération de labyrinthes sans biais directionnels. Alors que la division récursive se démarque vraiment avec la parallélisation facile du processus, cet algorithme est aussi particulièrement fascinant en raison de sa nature fractale : vous pouvez théoriquement continuer le processus indéfiniment à des niveaux de détail toujours plus fins (échelles toujours plus petites).

Cet algorithme est un peu similaire au retour arrière récursif (recursive backtracking) : ils sont tous deux basés sur une stratégie exploitant la pile (stack). La différence se trouve dans le fait que la Division Récursive construit des murs plutôt que des passages. En tant que constructeur de murs, le processus commence par un grand espace vide (toutes les cellules sont connectées) et ajoute récursivement des murs (déconnexions de cellules) jusqu'à l'obtention d'un labyrinthe.

L'idée générale d'une division récursive est très simple : commençons avec une "pièce" vide, divisons-la en deux, et ouvrons une porte dans le mur. Nous repétons ensuite le processus sur les deux pièces nouvellement créées.

Etapes

• Commencer par un grand espace vide (toutes les cellules sont connectées).
• 1. Construire un mur de manière aléatoire pour séparer cet espace en deux.
• 2. Ouvrir un chemin au hasard dans ce mur.
• 3. Réitérer des deux côtés du mur.

A chaque étape, le labyrinthe sera toujours valide. Chaque répétition de l'algorithme augmente simplement le niveau de détail; cela pourrait conduire à une animation de plongée infinie dans le labyrinthe.

Code

Maze RecursiveDivisionWrapper(int width, int height)
{
  Maze maze(width, height, Cell::Connected);
  RecursiveDivision(maze, width, height);

  return maze;
}

RecursiveDivision(Maze maze, int width, int height, Cell offSet = [0, 0]})
{
  // Recursion Termination
  if (width < 2 || height < 2)
    return;

  // Randomly build the wall either horizontally or vertically
  auto isHorizontal = Random() % 2;

  // Randomly select the position to build the wall (disconnect cells along the line)
  auto wallIdx = Random(width, height, isHorizontal);
  maze.BuildWall(wallIdx, isHorizontal);

  // Randomly select the position to carve a unique path within this wall
  auto pathIdx = Random(width, height, !isHorizontal);
  maze.CarvePath(pathIdx, !isHorizontal);

  // Recurse on sub areas
  if (isHorizontalCut)
  {
    // Top and Bottom areas
    RecursiveDivision(maze, width, wallIdx, offSet);
    RecursiveDivision(maze, width, height - wallIdx, offSet{y +=  wallIdx});
  }
  else
  {
    // Left and Right areas
    RecursiveDivision(maze, wallIdx, height, offSet);
    RecursiveDivision(maze, width - wallIdx, height, offSet{x +=  wallIdx});
  }
}

Les labyrinthes générés par un algorithme de division récursive sont sous la forme d'une fractale rectangulaire imbriquée. La méthode donne des labyrinthes avec de longs murs droits traversant leur espace, ce qui rend plus aisée la détection des sous-espaces à éviter. Ils ont aussi tendance à avoir beaucoup d'impasses courtes.

1. Construction au hasard d'un mur et d'un passage dans un espace vide.

2. Réitération dans la partie supérieure.

3. Une nouvelle itération depuis la partie supérieure dans l'espace de gauche nouvellement crée.

4. Quelques récursions plus tard... la partie supérieure est construite.

4. Le même processus se produit sur la zone inférieure (deuxième récurrence principale), et enfin le labyrinthe est complet !

Sautez à bord de l' H.urna Explorer pour créer et voir vos labyrinthes avec la Division Récursive.