Labyrinthe crée par un algorithme d'Arbre Binaire en dimensions 75x50.

Inondation (Flooding) depuis le noeud racine: améliore la visualisation de l'uniformité de sa structure.

L'arbre binaire représentant la topologie de la structure de données.

L'algorithme de construction de labyrinthes en arbres binaires est l’un des rares ayant la capacité de générer des labyrinthes parfaits sans utilisation de mémoire (aucun état n'est utilisé). Le labyrinthe est crée en processant chaque cellule indépendamment, il est ainsi possible de créer des labyrinthes sans limite de taille. Ce générateur de labyrinthe est fondamentalement le plus simple et le plus rapide.

Les labyrinthes générés sont de véritables structures de données d’arbres binaires (cf. images suivantes) et ont malheureusement une texture très biaisée (cf. section Texture).

Un labyrinthe plus petit, sur lequel nous pouvons déjà voir la structure d'arbre binaire.

Tournons le de 45° pour aider la visualisation.

Représenter le labyrinthe en un arbre de décisions rend complètement clair sa structure (visualisation miroir avec la diapositive précédente)

Comme son nom l'indique, il consiste simplement à choisir entre deux options possibles à chaque étape: Pour chaque cellule de la grille, lancer une pièce pour ouvrir un passage soit au nord (dessus), soit à l'ouest (gauche).

Etapes

• Pour chaque cellule de la grille :
• 1. Prendre, si elles existent, la voisine de gauche et celle du dessus.
• 2. Lancer une pièce pour choisir avec laquelle on crée un passage.
• C'est déjà fini !

Code

Maze BinaryTree(int width, int height)
{
  // For each existing cell in the grid, randomly carve a passage either north or west
  Maze maze(width, height);
  for (auto y = 0; y < height; ++y)
    for (auto x = 0; x < width; ++x)
    {
      // Get available neighbours (nort + west)
      if (x > 0) neighbours.push_back(maze[x - 1][y]);
      if (y > 0) neighbours.push_back(maze[x][y - 1]);

      // No possible connection
      if (neighbours.empty())
        continue;

      // Randomly connect whether south or east
      auto tossCoin = Random() % neighbours.size();
      mazeMatrix[x][y]->Connect(neighbours[tossCoin]);
    }

  return maze;
} 

Les labyrinthes binaires sont différents des labyrinthes parfaits standard car près de la moitié des topologies possibles de cellule ne sont jamais présentes. Par exemple, il n'y aura jamais de carrefour (une cellule connectée avec toutes ses voisines). Aussi, tous les chemins ont des passages vers le bas ou vers la droite, mais jamais vers le haut ou la gauche (en commençant la marche en partant du coin haut gauche).

Les labyrinthes ont tendance à présenter un énorme biais diagonal allant du coin supérieur gauche au coin inférieur droit. Il sera donc extrêmement facile de trouver l'entrée du labyrinthe (coin haut gauche) en partant de n'importe quel endroit. Il suffira de monter quand cela est possible, ou tourner à gauche pour atteindre la racine sans se heurter à aucune barrière.

Enfin, deux des quatre côtés du labyrinthe seront toujours des couloirs droits. Cela est dû à la nature directionnelle de sa construction.

1. Cet algorithme ne considère pas l’état des cellules, il peut de ce fait être démarré n'importe où. Par commodité, commençons par le coin supérieur gauche.

2. Au bord du labyrinthe nous sommes obligé de connecter toutes les cellules avec leur voisine de droite (impossible de créer un passage vers le nord). C’est l’un des effets secondaires mentionnés dans la section Texture.

3. Ligne de cellules suivantes :
a. La première cellule ne peut être connectée qu'au nord (pas de voisine à l'ouest)
b. La Deuxième cellule sera connectée à sa copine nord (hasard)
c. La Troisième à celle de l'Ouest (hasard)
d. La pièce est en train d'être lancée pour la 4ème cellule.

4. L'itération sur chaque cellule est faite : le labyrinthe est terminé !

Sautez à bord de l' H.urna Explorer pour créer et voir vos labyrinthes d'Arbres Binaires.