Labyrinthe crée par un algorithme de Prim depuis le coin supérieur gauche (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.

Labyrinthe crée par un algorithme de Prim depuis le centre (taille de 75x50).

Inondation (Flooding) depuis le milieu.

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

Le générateur de labyrinthe de Prim est une version aléatoire de l'algorithme "Prim's" : une méthode pour produire un Minimal Spanning Tree (Arbre couvrant de poids minimal* - *traduction litéral) à partir d'un graphe non-orienté et pondéré.

L'algorithme de Prim crée un arbre de parcours en choississant en premier la cellule adjacente la plus proche pour voyager (de poids le plus faible). Pour générer des labyrinthes avec Prim, nous allons simplement utiliser une cellule voisine au hasard pour continuer notre chemin.

Bien que l'algorithme classique de Prim conserve une liste des chemins, ici sera étudiée une version modifiée plus optimale. Notre algorithme maintiendra une liste de cellules (bien plus faible en nombre) pour aller plus vite. Il reste néanmoins toujours nécessaire d'utiliser un stockage proportionnel à la taille du labyrinthe.

L'approche de Prim permet de commencer de n’importe quelle cellule et se répand ensuite de proche en proche. Cet algorithme conserve un ensemble de cellules possibles par lesquelles le labyrinthe peut être étendu. À chaque étape le labyrinthe s'agrandit dans une direction aléatoire tant que le chemin ne se reconnecte pas avec une autre partie du labyrinthe.

Etapes

L'algorithme aléatoire modifie simplement la première étape de la boucle de sorte qu'au lieu de tirer la cellule voisine disponible avec le poids le plus faible, est tirée une voisine au hasard ;)

Code

Maze Prims(int width, int height, Cell startCell)
{
  Maze maze(width, height);
  Set pathSet(startCell);

  // While the set of cells is not empty
  while (!pathSet.empty())
  {
    // Select randomly a cell to extend the path and remove it from the set
    // Mark the cell as visited
    auto cell = Cell::Visite(pathSet.GetRandom());

    // Get available neighbours from bottom, left, right, top and visited
    // Randomly connect to one
    auto neighbours = GetVisitedNeighbours(maze, cell);
    if (!neighbours.empty())
    {
      // Randomly connect to an available cell
      auto randIdx = Random() % neighbours.size();
      Connect(cell, neighbours[randIdx]);
    }

    // Add all unvisted neighbours to the set
    pathSet.insert(GetNeighbours(maze, cell));
  }

  return maze;
} 

Les labyrinthes générés par l’algorithme de Prim partagent bon nombre des caractéristiques avec ceux créés via l'algorithme de Kruskal. Par exemple, l'abondance de cul-de-sac très courts, donnant au labyrinthe un aspect "hérissé". L’algorithme génère également des labyrinthes avec un faible facteur de "rivière".

Il sera relativement facile de trouver le chemin vers la cellule de départ, mais difficile de trouver le chemin de la sortie.

1. Commencer depuis n'importe quelle cellule de la grille.

2. Ajouter tous les voisins non visités à l'ensemble (voisins non connectés).

3. Prendre au hasard une des cellules et la connecter.

4. Ajouter toutes les autres voisines disponibles à l'ensemble.

5. Prendre une des cellules de l'ensemble et la connecter à une de ses voisinnes connectée au labyrinthe.

6. Après quelques itérations.

7. Toutes les cellules sont traitées (l'ensemble est vide) : le labyrinthe est terminé !

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