labyrinthe — Générateur de labyrinthes

Description

Voici un programme pour générer aléatoirement des labyrinthes. Comme montré dans la partie algorithmes, l’algorithme lui même est très simple.

On part d’un ensemble de zones, séparées par des murs. Puis on détruit des murs les uns après les autres, jusqu’à ce qu’il ne reste plus qu’une zone.

C’est une des méthodes possibles. Elle, ainsi qu’une autre possibilité, est discutée sur Wikipédia.

Algorithme

Une fois débarrassé de toutes les difficultés techniques, l’algorithme est assez simple, comme le montre le code de la fonction LabyrintheBase.construit().

1    def construit(self):
2        """Détruit des murs jusqu'à obtention d'un labyrinthe connexe."""
3        while list(self.murs_inter()):
4            mur = random.choice(list(self.murs_inter()))
5            mur.detruit()

Tant qu’il reste des murs inter-zones (c’est-à-dire des murs entre deux zones différentes), ce qui aurait aussi pu être rédigé comme tant qu’il reste plus d’une zone, on détruit un mur au hasard, ce qui a pour effet de rassembler deux zones.

Représentation des données

Un intérêt de l’implémentation faite ici est la liberté qu’elle procure quant à la forme du labyrinthe : il n’est pas fait la supposition que le labyrinthe est fait sur la base d’un maillage carré. Une zone est seulement un objet entouré de murs, et un mur est un objet adjacent à deux zones.

Avec cette représentation, on peut implémenter un labyrinthe plan avec une base carrée, triangulaire ou aléatoire, mais aussi (je ne l’ai pas implémenté) un labyrinthe en trois dimensions (ou plus), ou un labyrinthe sur la surface d’un cube, ou n’importe quoi d’autre.

../_images/triangle.png

Fig. 16 Base triangulaire

../_images/random1.png

Fig. 17 Base aléatoire

../_images/square.png

Fig. 18 Base carrée

Usage

  • Génération d’un labyrinthe à base carrée:

    labyrinthe turtle square
    
  • Génération d’un labyrinthe à base triangulaire:

    labyrinthe turtle triangle
    
  • Génération d’un labyrinthe à base aléatoire:

    labyrinthe turtle random1
    
  • D’autres options disponibles. Pour les découvrir:

    labyrinthe [COMMANDE] --help