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.

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

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