Labyrinthe crée par un algorithme Sidewinder (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.

Le générateur de labyrinthe Sidewinder est très similaire à l'algorithme d'Arbre Binaire, et seulement un tout petit peu plus compliqué. L'algorithme Sidewinder ne doit prendre en compte que la ligne en cours de traitement et peut donc être utilisé pour générer des labyrinthes infiniment grands (comme pour l'Arbre Binaire).

Alors que les labyrinthes d’arbres binaires ont deux de ses quatre côtés constitués d'un long passage, les labyrinthes Sidewinder réduisent ce défaut à un seul long passage.

Bien qu’il soit un peu plus compliqué que l’algorithme d'Arbre Binaire, les mots ne rendent pas justice : cela reste vraiment facile.

Etapes

• Pour chaque ligne de la grille :
• 1. Pour chaque cellule, décidez au hasard de créer ou non un passage menant à l'Est.
• a. Si le passage est crée : ajouter la cellule au chemin en cours de construction.
• b. Si le passage n'est pas crée : prendre au hasard une cellule du passage précédent et y tailler un passage menant au nord; réinitialiser ensuite le chemin en cours de traitement.

Code

Maze Sidewinder(int width, int height)
{
  Maze maze(width, height);

  // First row can only be a single passage (cannot crave north), crave it.
  for (auto x = 0; x + 1 < width; ++x)
    maze[x][0]->Connect(maze[x + 1][0]);

  // Scan grid row by row (starting from the second one)
  for (auto y = 1; y < height; ++y)
  {
    // Initialize an empty “run” set to keep track of the current run path
    Set runSet;

    for (auto x = 0; x < width; ++x)
    {
      // Add current cell to the path
      runSet.insert(maze[x][y]);

      // Randomly carve to east (if possible) or not
      if ((x + 1) < width && Random() % 2)
      {  mazeMatrix[x][y]->Connect(mazeMatrix[x + 1][y]); }
      // Otherwise carve to the north from a random cell of the run set
      else
      {
        auto cell = runSet.GetRandom();
        cell->Connect(cell{y -= 1});

        // Empty the run set and continue row scan
        runSet.clear();
      }
    }
  }

  return maze;
}

Tout labyrinthe généré par l’algorithme Sidewinder ne contiendra jamais d'impasse vers le nord. Cela signifie que vous ne serez jamais bloqué lorsque vous vous déplacez du sud au nord.

Un labyrinthe sidewinder a tendance à avoir une solution élitiste : où le chemin est très direct. Cependant, il contient beaucoup de longs et faux chemins descendant au sud.

La solution est déterministe (sans erreur) allant du sud au nord : elle ne visitera jamais une rangée plus d'une fois bien qu'il puisse y avoir du vent (ou vague) d'un côté à l'autre dans sa recherche.

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

2. La première cellule décide de créer un passage vers l'est ; on ajoute cellule au chemin.

3. La deuxième cellule décide au hasard d'ouvrir un passage au nord, elle se sélectionne au hasard pour ouvrir le passage.
Le chemin en mémoire est effacé.

4. Les deux celulles suivantes décident d'ouvrir un passage vers l'est (elles sont ajoutées au chemin actuel).

5. La dernière de la rangée doit ordonner d'ouvrir un passage vers le nord pour le chemin actuel. Elle choisit le premier (du chemin) pour être celui qui ouvre.

6. Quelques lignes de la grille plus tard...

7. Une fois toutes les lignes traitées, le labyrinthe est généré !

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