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

Version originale de Prim Version pour la génération de labyrinthes
  • Choisir une cellule de départ et l'ajouter à la liste.
  • Tant qu'il y a une cellule à manipuler dans la liste:
  • 1. Connecter la cellule voisine disponible avec le plus petit poids (e.g. la plus proche).
  • 2. Ajouter toutes les autres voisines disponibles à la liste.
  • Choisir une cellule de départ et l'ajouter à la liste.
  • Tant qu'il y a une cellule à manipuler dans la liste:
  • 1. Connecter une cellule voisine disponible au hasard.
  • 2. Ajouter toutes les autres voisines disponibles à la liste.

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

Pseudo-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.
Sautez à bord de l' H.urna Explorer pour créer et voir vos labyrinthes avec Prim.