Labyrinthe : Génération et résolution
Voir le code
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Jul 2 20:54:38 2021
@author: Jason L*, SKun*
"""
from PIL import Image
import random
class Labyrinthe:
def __init__(self, m:int, n:int):
'''
Parameters
----------
m : int
nombre de lignes (hors cases de portes ou murs)
n : int
nombre de colonnes (hors cases de portes ou murs)
Génére une grille de taille (2m+1) x (2n+1) qui sera utilisée pour construire un labyrinthe.
Entre deux cases "vides" se trouve soit un mur, soit une porte, qui occupe également une case. Au départ, il n'y a
pas de portes, seulement des cases vides et des murs. Les murs horizontaux ou verticaux n'ont de différent que le fait
qu'ils séparent soit deux cases adjacentes verticalement, soit deux cases adjacentes horizontalement. Mais ils occupent
tous les deux une case complète à l'instar d'une case occupable.
les indices (i, j) de type (impair, impair) sont les seuls correspondant aux cases du labyrinthe
les indices (i, j) de type (pair, impair) ou (impair, pair) correspondent aux emplacements des murs (ou des portes)
les indices (i, j) de type (pair, pair) correspondent aux coins.
exemple : labyrinthe (3, 4) -> de taille (7, 9):
j 0 1 2 3 4 5 6 7 8
i
0 B B B B B B B B B
1 B 0 | 1 | 2 | 3 B
2 B - + - + - + - B
3 B 4 | 5 | 6 | 7 B
4 B - + - + - + - B
5 B 8 | 9 |10 |11 B
6 B B B B B B B B B
On numérote les cases de passage du labyrinthe obtenues pour : i et j impairs
les B correspondentaux murs de bord et de coin
les - correspondent aux cases de murs horizontaux : codés "H" : i pair, j impair
les V correspondent aux cases de murs verticaux : codés "V" : i impair, j pair
les + correspondent aux cases de murs de coin reliant un mur horizontal et un mur vertical : i pair, j pair
codés "B"
Donc après _init_grid_and_walls(), self.grid contient le tableau suivant :
j 0 1 2 3 4 5 6 7 8
i
0 B B B B B B B B B
1 B 0 V 1 V 2 V 3 B
2 B H B H B H B H B
3 B 4 V 5 V 6 V 7 B
4 B H B H B H B H B
5 B 8 V 9 V 10 V 11 B
6 B B B B B B B B B
'''
self.m, self.n = m, n #nombre de cases vides avant suppression des murs
self.l = 2*m + 1 # nombre de lignes
self.c = 2*n + 1 # nombres de colonnes
self.grid = [["B"]*(2*n + 1) for i in range(2*m + 1)] # Tableau (2m+1) x (2n+1)
self.walls = [] # liste des murs à casser pour créer le labyrinthe donnés comme couples (i, j)
self.chemins = {} # dictionnaire (identifiant: {cellules d'une même composante connexe})
self.images_en_construction = [] # images créées à chaque étape du creusement du labyrinthe.
self.palette_couleurs = []
self.nb_composantes_connexes = m * n # quand cet attribut vaut 1, on peut arrêter de détruire des murs
self.init_palette()
self._init_grid_and_walls(m, n) # Pour obtenir le tableau ci-dessus avec les nombres et "B", "V", "H"
self._init_chemins(m, n) # à initialiser après les numéros de cellule
self.genere_laby(mode = 1) # mode = 1 : on crée les images intermédiaires de construction
def get_dimensions(self):
return self.l, self.c
def get_grid(self):
return self.grid
def get_walls(self):
return self.walls
def init_palette(self):
'''
crée une palette de couleurs pour associer à chaque composante connexe une couleur
donnée de la palette
'''
self.palette_couleurs = palette_couleurs(self.m * self.n)
def _init_grid_and_walls(self, m, n):
'''
A partir du tableau (2m+1) x (2n+1), rempli de "B", crée le tableau mentionné
dans la fonction __init__ et le stocke dans self.grid
'''
self._numerote_cases_de_passage(m, n)
self._init_murs_verticaux(m, n)
self._init_murs_horizontaux(m, n)
def _numerote_cases_de_passage(self, m, n):
'''Numérote les cases de passage de 0 à m*n - 1'''
#i impair et j impairs: cases de passage numérotées de manière croissante
cpt = 0
for i in range (1, 2*m + 1, 2):
for j in range(1, 2*n, 2): #i impair, j impair
self.grid[i][j] = cpt
cpt += 1
def _init_murs_verticaux(self, m, n):
for i in range (1, 2*m + 1, 2):
for j in range(2, 2*n, 2): #i impair, j pair
self.walls.append((i, j))
self.grid[i][j] = "V"
def _init_murs_horizontaux(self, m, n):
for i in range (2, 2*m , 2):
for j in range(1, 2*n, 2): #i pair, j impair
self.walls.append((i, j))
self.grid[i][j] = "H"
def _init_chemins(self, m, n):
for i in range (1, 2*m + 1, 2):
for j in range(1, 2*n, 2): #i impair, j impair
val = self.grid[i][j]
#au départ les chemins sont constitués d'une seule cellule
#le numéro attribué à celle-ci est l'identifiant du chemin
self.chemins[val] = {(i, j)}
def genere_laby(self, mode = 0):
'''
Tant qu'il reste des murs à retirer, on les retire. Quand il n'y en a plus,
le labyrinthe est terminé.
après genere_laby(), self.grid ne contient plus que des 0, des B, des V et des H
Les V et H ont été remplacés par l'étiquette la plus basse des deux chemins
fusionnés, s'ils sont transformés en case de passage ou bien
sont restés intacts si la suppression du mur avait abouti à créer un cycle.
mode 0 : ne crée pas les images de construction
mode 1 : crée les images de construction
(couteux, et peut faire exploser la mémoire pour m, n ~ 50, ok pour m, n ~ 10->20)
'''
murs = self.get_walls()
self.ajoute_image(mode)
while murs != [] and self.nb_composantes_connexes > 1:
mur = random.choice(murs)
self.ajoute_image_clignotante(mur, mode) #pas propre. A améliorer avec une classe Cellule
self.walls.remove(mur) #qu'on le casse ou non, ce mur n'est plus a examiner
if self.mur_cassable(mur):
self.retire_mur(mur)
self.ajoute_image(mode)
self.nb_composantes_connexes -= 1
def mur_cassable(self, mur):
'''
renvoie True si mur est cassable, c'est-à-dire si les voisins séparés par
le mur ne sont pas sur le même chemin. S'ils le sont, alors casser le mur crée un cycle,
ce qu'on veut éviter dans cette version du programme.
'''
i, j = mur
laby = self.get_grid()
etat_mur = laby[i][j]
cassable = (etat_mur == 'V' and laby[i][j-1] != laby[i][j+1]) or \
(etat_mur == 'H' and laby[i-1][j] != laby[i+1][j])
return cassable
def retire_mur(self, mur_a_casser):
'''
retire un mur dans un labyrinthe étant donnée son étiquette "V" ou "H"
et la valeurs des étiquettes des cases de passage que ce mur sépare.
Si les cases appartiennent déjà à la même composante connexe (même étiquette),
retirer le mur aboutirait à créer un cycle, donc on ne le détruit pas.
Si les cases n'appartiennent pas à la même composante connexe (étiquette différente)
on détruit le mur en lui attribuant comme étiquette de case de passage l'étiquette la plus basse
et on fusionne les deux chemins
'''
laby = self.get_grid()
i, j = mur_a_casser[0], mur_a_casser[1]
etat_mur = laby[i][j]
if etat_mur == 'V':
# on crée un chemin en détruisant le mur et en propageant l'indice le plus petit des deux cases
# que le mur séparait
minimum = min(laby[i][j-1], laby[i][j+1])
maximum = max(laby[i][j-1], laby[i][j+1])
self.fusionne_chemin(i, j, minimum, maximum)
elif etat_mur == 'H': #idem pour un mur horizontal
minimum = min(laby[i-1][j], laby[i+1][j])
maximum = max(laby[i-1][j], laby[i+1][j])
self.fusionne_chemin(i, j, minimum, maximum)
def fusionne_chemin(self, i, j, minimum, maximum):
'''
i, j repèrent un mur qu'on a fait sauter, séparant deux chemins dont les cases contiennent
pour l'un l'étiquette minimum et pour l'autre l'etiquette maximum
La fusion des deux chemins consiste à affecter l'etiquette minimum au chemin qui contient les
case d'étiquette maximum. Pour ceci, on parcourt toutes les cases du chemin maximum, et on modifie
leur étiquette en : mininum.
'''
laby = self.get_grid()
laby[i][j] = minimum
self.chemins[minimum].add((i, j))
for cell in self.chemins[maximum]:
self.chemins[minimum].add(cell)
laby[cell[0]][cell[1]] = minimum
del self.chemins[maximum]
def affiche(self):
'''affichage en mode texte de la grille du labyrinthe
'''
for ligne in self.grid:
print(ligne)
def cree_image(self):
'''
renvoie une image de (2m+1)x(2n+1) pixels pour un labyrinthe (m, n)
qu'on agrandit x 10 sans antialiasing pour obtenir une image assez grande.
La solution reliant l'entrée à la sortie est affichée en vert'.
'''
laby = self.get_grid()
lignes, colonnes = self.get_dimensions()
result = Image.new('RGB', (colonnes, lignes))
for i in range(lignes):
for j in range(colonnes):
if str(laby[i][j]) in 'BVH':
result.putpixel((j, i), (0, 0, 0))
elif laby[i][j] == 'P': #pour afficher le chemin solution
result.putpixel((j, i), (0, 255, 0))
else:
result.putpixel((j, i), (255, 255, 255))
result = result.resize((colonnes*15, lignes*15), 0)
return result
def voisins(self, i, j):
'''Renvoie la liste des voisins accessibles de la case de passage (i, j)
Pour ce faire, on teste les cases adjacentes (murs ou case devenue case de passage : porte).
Si c'est une porte (contient 0), alors la case de passage adjacente à la porte dans la même direction est
un voisin accessible depuis (i, j)
'''
liste_voisins = []
# (i+1, j), (i-1, j), (i, j+1), (i, j-1) sont des emplacements de portes (0) ou de murs ("B", "H", ou "V")
if self.est_une_porte(i+1, j):
liste_voisins.append((i+2, j))
if self.est_une_porte(i-1, j):
liste_voisins.append((i-2, j))
if self.est_une_porte(i, j+1):
liste_voisins.append((i, j+2))
if self.est_une_porte(i, j-1):
liste_voisins.append((i, j-2))
return liste_voisins
def est_une_porte(self, i, j):
return self.grid[i][j] == 0
def parcours_largeur(self, source:tuple) -> dict:
'''Effectue un parcours en largeur du labyrinthe à partir du sommet source
et renvoie un dictionnaire {sommets:distance à la source}. Un sommet est ici
une case de passage du labyrinthe repérée par ses coordonnées (i, j).
'''
dist = {source: 0}
courant = {source}
suivant = set()
while len(courant) > 0:
i, j = courant.pop()
for v in self.voisins(i, j):
if v not in dist:
suivant.add(v)
dist[v] = dist[(i, j)] + 1
if len(courant) == 0:
courant, suivant = suivant, set()
return dist
# Inutile pour le moment.
# def distance(self, s1:tuple, s2:tuple) -> int:
# '''renvoie la distance entre les cases s1 et s2 du labyrinthe '''
# dist = self.parcours_largeur(s1)
# if s2 in dist:
# return dist[s2]
def chemin(self, s1, s2):
'''
Au moyen d'un parcours en largeur à partir de s1, détermine le plus court chemin
entre s1 et s2. C'est aussi ici le seul chemin qui ne repasse pas deux fois par la
même case (qui rebrousse pas chemin), puisqu'il n'y a pas de cycles.
On construit le chemin de s1 à s2 en partant de la fin :
on part du sommet s2 et considérant sa distance à s1, on cherche parmi ses voisins
celui à qui a une distance à s1 inférieure de 1. On le concatène au chemin en construction,
jusqu'à aboutir à s1.
'''
dist = self.parcours_largeur(s1)
sommet = s2
path = [s2] #plus court chemin en construction (par la fin)
while sommet != s1:
i, j = sommet
lst_voisins = self.voisins(i, j)
for v in lst_voisins:
if dist[v] == dist[sommet] - 1:
sommet = v
path = [v] + path #pour avoir le chemin dans le bon ordre de s1 vers s2
break
return path
def affiche_chemin(self, chemin):
'''
chemin est une liste de couples (i, j)
Si n est la longueur du chemin, cette fonction crée un gif de n images, dont
ajoutant à la précédente une case de plus du chemin coloriée en vert.
'''
laby = self.get_grid().copy()
images = [self.cree_image()]
i, j = chemin[0]
laby[i][j] = 'P'
images.append(self.cree_image())
for k in range(1, len(chemin)):
i, j = chemin[k]
laby[i][j] = 'P'
i = (chemin[k][0] + chemin[k-1][0]) // 2 #pour les cases de portes dont les index sont la moyenne des cases de passage
j = (chemin[k][1] + chemin[k-1][1]) // 2
laby[i][j] = 'P'
images.append(self.cree_image())
images[0].save('laby.gif', save_all = True, append_images = images, duration = 100, optimize = True, loop = 0)
def ajoute_image(self, mode = 1):
'''
ajoute l'image du labyrinthe dans son état actuel en construction à l'attribut images_en_construction
'''
if mode == 0:
return
else :
image = self.cree_image_en_construction()
self.images_en_construction.append(image)
def ajoute_image_clignotante(self, mur, mode = 1): #fonction pas très propre (liée à notre mode de fabrication des images)
'''
Signale le mur en examen lors du processus de destruction de mur
au moyen du symbole "S", qui servira à colorer le mur en examen en blanc
'''
if mode == 0:
return
else:
i, j = mur[0], mur[1]
tmp = self.grid[i][j]
self.grid[i][j] = "S"
self.ajoute_image()
self.grid[i][j] = tmp
def cree_image_en_construction(self):
'''
Crée une image du labyrinthe dans l'état de génération où il se trouve.
- Les cellules de murs "B", "V", "H" (bords, murs verticaux et horizontaux)
sont représentées par un pixel noir.
- Une cellule de mur "S" est le mur en cours d'examen dans la fonction
ajoute_image_clignotante, liée à la fonction cree_image (pas très propre)
on lui associe la couleur blanc.
- Les cellules contenant une étiquette numérique sont représentées par
un pixel de couleur correspondant à leur étiquette, prise dans la palette
de couleurs générée aléatoirement lors de la création du labyrinthe.
'''
laby = self.get_grid()
lignes, colonnes = self.get_dimensions()
result = Image.new('RGB', (colonnes, lignes))
for i in range(lignes):
for j in range(colonnes):
if str(laby[i][j]) in 'BVH':
result.putpixel((j, i), (0, 0, 0))
elif laby[i][j] == 'S':
result.putpixel((j, i), (255, 255, 255))
else:
index_couleur = laby[i][j]
color = self.palette_couleurs[index_couleur]
result.putpixel((j, i), color)
result = result.resize((colonnes*15, lignes*15), 0)
return result
def cree_gif_generation(self):
'''
Crée un gif de la génération pas à pas du labyrinthe
'''
if len(self.images_en_construction) != 0:
images = self.images_en_construction
images[0].save('laby_construction.gif', save_all = True, append_images = images, duration = 500, optimize = True, loop = 0)
def palette_couleurs(n):
'''
Renvoie une liste de n couleurs aléatoires sous forme de triplet (r, g, b)
'''
couleurs = [(random.randint(0, 255), random.randint(0, 255), random.randint(0,255)) for k in range(n)]
couleurs_choisies = []
for _ in range(n):
c = random.choice(couleurs)
couleurs.remove(c)
couleurs_choisies.append(c)
return couleurs_choisies
#Programme principal
i = 10
j = 15
laby = Labyrinthe(i, j)
solution = laby.chemin((1, 1), (2*i - 1, 2*j - 1))
laby.affiche_chemin(solution)
laby.cree_gif_generation()
Réalisé avec Jason, le labyrinthe est modélisé par une grille où initialement chaque case est entourée de murs sur ses quatre bords. Pour générer le labyrinthe, on casse des murs au hasard en s'assurant qu'on ne crée pas de cycle. Voir cette page pour l'algorithme utilisé.
On calcule ensuite au moyen d'un algorithme de parcours en largeur le plus court chemin entre l'entrée et la sortie du labyrinthe (les coins opposés), cela évite d'avoir des chemins qui rebroussent (puisque sans cycle, il n'y a en réalité qu'un seul chemin qui relie sans repasser deux fois par la même case deux points quelconque du labyrinthe).
Le programme produit deux gifs animés illustrant ces algorithmes.
On peut produire de très grands labyrinthes (à un seul chemin), mais la génération d'images intermédiaires fait exploser la mémoire pour l'instant.
