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).

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 !

Pseudo-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.

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