Créer et resoudre un labyrinthe
Les scripts suivants permettent de créer un labyrinthe de manière aléatoire, et d’exploiter la structure de données de ce labyrinthe. On pourra ainsi tester quelques algorithmes relatifs au parcours de ce labyrinthe. Les scripts en permettent une visualisation.
Définitions des classes
class Pile:
def __init__(self):
self.lst = []
def empty(self):
return self.lst == []
def push(self, x):
self.lst.append(x)
def pop(self):
if self.empty():
raise ValueError("pile vide")
return self.lst.pop()
def explorer(laby):
pile = Pile()
pile.push((0, laby.q - 1))
laby.tab[0][laby.q - 1].etat = False
while True:
i, j = pile.pop()
if i == laby.p - 1 and j == 0:
break
if j > 0 and laby.tab[i][j].S and laby.tab[i][j-1].etat:
pile.push((i, j))
pile.push((i, j-1))
laby.tab[i][j-1].etat = False
elif i < laby.p-1 and laby.tab[i][j].E and laby.tab[i+1][j].etat:
pile.push((i, j))
pile.push((i+1, j))
laby.tab[i+1][j].etat = False
elif j < laby.q-1 and laby.tab[i][j].N and laby.tab[i][j+1].etat:
pile.push((i, j))
pile.push((i, j+1))
laby.tab[i][j+1].etat = False
elif i > 0 and laby.tab[i][j].W and laby.tab[i-1][j].etat:
pile.push((i, j))
pile.push((i-1, j))
laby.tab[i-1][j].etat = False
return pile.lst
class Case:
def __init__(self):
self.N = False
self.W = False
self.S = False
self.E = False
self.etat = False
class Labyrinthe:
def __init__(self, p, q):
self.p = p
self.q = q
self.tab = [[Case() for j in range(q)] for i in range(p)]
def show(self):
plt.plot([0, 0, self.p, self.p, 0], [0, self.q, self.q, 0, 0], linewidth=2)
for i in range(self.p-1):
for j in range(self.q):
if not self.tab[i][j].E:
plt.plot([i+1, i+1], [j, j+1], 'b')
for j in range(self.q-1):
for i in range(self.p):
if not self.tab[i][j].N:
plt.plot([i, i+1], [j+1, j+1], 'b')
plt.axis([-1, self.p+1, -1, self.q+1])
plt.show()
def solution(self):
sol = explorer(self)
X, Y = [], []
for (i, j) in sol:
X.append(i+.5)
Y.append(j+.5)
X.append(self.p-.5)
Y.append(.5)
plt.plot(X, Y, 'r', linewidth=2)
self.show()
def creation(p, q):
laby = Labyrinthe(p, q)
pile = Pile()
i, j = randint(p), randint(q)
pile.push((i, j))
laby.tab[i][j].etat = True
while not pile.empty():
i, j = pile.pop()
v = []
if j < q-1 and not laby.tab[i][j+1].etat:
v.append('N')
if i > 0 and not laby.tab[i-1][j].etat:
v.append('W')
if j > 0 and not laby.tab[i][j-1].etat:
v.append('S')
if i < p-1 and not laby.tab[i+1][j].etat:
v.append('E')
if len(v) > 1:
pile.push((i, j))
if len(v) > 0:
c = v[randint(len(v))]
if c == 'N':
laby.tab[i][j].N = True
laby.tab[i][j+1].S = True
laby.tab[i][j+1].etat = True
pile.push((i, j+1))
elif c == 'W':
laby.tab[i][j].W = True
laby.tab[i-1][j].E = True
laby.tab[i-1][j].etat = True
pile.push((i-1, j))
elif c == 'S':
laby.tab[i][j].S = True
laby.tab[i][j-1].N = True
laby.tab[i][j-1].etat = True
pile.push((i, j-1))
else:
laby.tab[i][j].E = True
laby.tab[i+1][j].W = True
laby.tab[i+1][j].etat = True
pile.push((i+1, j))
return laby
Librairies
from numpy.random import randint
import matplotlib.pyplot as plt
Un premier exemple
laby = creation(6, 5)
laby.solution()
Exploration de la structure de données
def directions(laby,i,j):
"""les directions possibles pour la case courante
i : int numero de ligne
j : numero de la colonne
retourne une liste (tuple) des points cardinaux possibles
"""
L = []
if laby.tab[j][i].N == True: L.append('N')
if laby.tab[j][i].S == True: L.append('S')
if laby.tab[j][i].E == True: L.append('E')
if laby.tab[j][i].W == True: L.append('W')
return tuple(L)
Un labyrinthe est un tableau de cases laby.tab[j][i] ayant chacune pour propriétés : N,S,E,W
- i : int numero de ligne
- j : numero de la colonne
Pour chacune de ces propriétés, par exemple laby.tab[j][i].Non renseigne une valeur True ou False
- True : direction possible
- False : impossible (mur)
Créer un labyrinthe vide
def labyrinthe(lines,col):
"""
Params :
--------
lines : int : nombre de lignes du labyrinthe
col : int : nombre de colonnes
Returns :
---------
tab2 : list : tuples de 1 à 4 éléments correspondants aux directions libres ('N', 'S', E', 'W')
sortie : tracé du labyrinthe
Variables :
-----------
p : nombre de colonnes (=largeur)
q : nombre de lignes (=hauteur)
"""
laby = creation(col, lines)
tab2 = [[0]*laby.p for i in range(laby.q)]
for i in range(laby.q):
for j in range(laby.p):
tab2[i][j] = directions(laby,i,j)
Labyrinthe.show(laby)
return tab2
tab=labyrinthe(5,6)
tab
[[('N',), ('N', 'E'), ('E', 'W'), ('E', 'W'), ('E', 'W'), ('N', 'W')],
[('N', 'S'), ('S', 'E'), ('N', 'W'), ('N', 'E'), ('W',), ('N', 'S')],
[('N', 'S', 'E'), ('N', 'W'), ('N', 'S'), ('S', 'E'), ('E', 'W'), ('S', 'W')],
[('N', 'S'), ('N', 'S'), ('S', 'E'), ('N', 'W'), ('N', 'E'), ('N', 'W')],
[('S',), ('S', 'E'), ('E', 'W'), ('S', 'E', 'W'), ('S', 'W'), ('S',)]]
Remarque : Les lignes sont mises dans l’ordre inverse du dessin du labyrinthe :
Tracé du labyrinthe
def mur(dir,i,j):
"""trace les murs des directions fermées
dir est un tuple contenant les directions libres
"""
line = 10
if not('N' in dir[i][j]) : plt.plot([j,j+1],[i+1,i+1],'black',linewidth=line)
if not('S' in dir[i][j]) : plt.plot([j,j+1],[i,i],'black',linewidth=line)
if not('E' in dir[i][j]) : plt.plot([j+1,j+1],[i,i+1],'black',linewidth=line)
if not('W' in dir[i][j]) : plt.plot([j,j],[i,i+1],'black',linewidth=line)
def murs(tab):
for i in range(len(tab)):
for j in range(len(tab[i])):
mur(tab,i,j)
plt.plot([0, 0, len(tab[0]), len(tab[0]), 0], [0, len(tab), len(tab), 0, 0], 'blue',linewidth=10)
plt.savefig('labyrinthe.png')
On peut faire l’économie du tracé eventuel côté S et côté W grace au tracé des cases adjacentes.
murs(tab)
Parcours du labyrinthe
fonctions utiles
def nexto(c,direc):
"""retourne les coordonnées lors du deplacement
selon la position actuelle et la direction
Params :
--------
c : tuple (ligne,colonne) correspondant à (y,x) dans le plan cartesien
direct : str : 'N', 'S', E', 'W'
Returns :
---------
tuple : (int,int) correspondant à (ligne,colonne)
"""
i,j = c[0],c[1]
if direc=='N' : return (i+1,j)
if direc=='S' : return (i-1,j)
if direc=='E' : return (i,j+1)
if direc=='W' : return (i,j-1)
def visited(c,L,couleur):
"""retourne la couleur du noeud de coord c et
de liste de directions possibles L selon celle de ses voisins
Params :
--------
c : tuple : (ligne,colonne) correspondant à (y,x) dans le plan cartesien
L : list : tuples de 1 à 4 éléments correspondants aux directions libres ('N', 'S', E', 'W')
couleur : List dimension 2 contenant des elements str
'white' si noeud non visité,
'green' si le noeud est en cours de visite,
'red' si tous les noeuds ont été visités autour de lui
Returns :
---------
couleur : str : 'green' si le noeud est en cours de visite, 'red' si tous les noeuds
ont été visités autour de lui
"""
i,j = c[0],c[1]
coul='red'
for direc in L:
coord = nexto(c,direc)
if couleur[coord[0]][coord[1]]=='white':coul='green'
print(c,coul)
return coul
une premiere idée : colorer les noeuds du chemin en vert
def trouvercheminiter(start,end,tab):
"""recherche du chemin jusqu'à la sortie dans le labyrinthe
en utilisant une technique qui s'apparente au parcours en profondeur
avec backtracking
on utilise une pile de noeuds visités
Params :
--------
start : tuple de coord dans le labyrinthe
end : tuple de coord dans le labyrinthe
tab : liste de liste contenant pour chaque tuple de coordonnées un tuple de directions possibles
Variables :
-----------
couleur : une table de la couleur du noeud ('red' si aucune nouvelle direction possible,
'green' si en cours de visite, 'white' si jamais visité)
Returns:
--------
la liste couleur
"""
p = Pile()
p.push(start)
c = start
couleur = [['white']*len(tab[0]) for i in range(len(tab))]
# precaution pour eviter debordement
compt = 0
while (not p.empty()) and (not c == end) and compt<100:
compt+=1
c = p.pop()
L = tab[c[0]][c[1]]
couleur[c[0]][c[1]]=visited(c,L,couleur) # c est retiré de la pile et coloré en green ou red
for direc in L:
coord = nexto(c,direc)
if couleur[coord[0]][coord[1]]=='white': # le noeud fils est coloré en blanc dans la direction D
for n in tab[coord[0]][coord[1]]:
p.push(coord)
# alors on ajoute le noeud fils dans la direction D au sommet de la pile
# n fois afin de reconsidérer sa couleur à chaque fois que l'on depile
return couleur
trouvercheminiter((len(tab)-1,0),(0,len(tab[0])-1),tab)
(4, 0) green
(3, 0) green
(2, 0) green
(2, 1) green
(3, 1) green
(4, 1) green
(4, 2) green
(4, 3) green
(4, 4) green
(3, 4) green
(3, 5) green
(4, 5) red
(3, 5) red
(3, 4) red
(4, 4) red
(3, 3) green
(3, 2) green
(2, 2) green
(1, 2) green
(1, 1) green
(0, 1) green
(0, 2) green
(0, 3) green
(0, 4) green
(0, 5) green
[['white', 'green', 'green', 'green', 'green', 'green'],
['white', 'green', 'green', 'white', 'white', 'white'],
['green', 'green', 'green', 'white', 'white', 'white'],
['green', 'green', 'green', 'green', 'red', 'red'],
['green', 'green', 'green', 'green', 'red', 'red']]
Une autre approche : mémoriser les étapes de la solution
def solution(start,end,tab):
"""trouve la solution au labyrinthe et trace ce chemin
La recherche du chemin jusqu'à la sortie dans le labyrinthe
utilise une technique qui s'apparente au parcours en profondeur
avec backtracking
on utilise une pile de noeuds visités
Params :
--------
start : tuple de coord dans le labyrinthe
end : tuple de coord dans le labyrinthe
tab : liste de liste contenant pour chaque tuple de coordonnées un tuple de directions possibles
Returns:
--------
la liste couleur
Variables :
-----------
couleur : une table de la couleur du noeud ('red' si aucune nouvelle direction possible,
'green' si en cours de visite, 'white' si jamais visité)
p : Pile() utile pour la recherche du parcours
pchemin : Pile() utile pour memoriser ce chemin
"""
p = Pile()
pchemin = Pile()
p.push(start)
c = start
couleur = [['white']*len(tab[0]) for i in range(len(tab))]
while (not p.empty()) and (not c == end):
c = p.pop()
pchemin.push(c)
L = tab[c[0]][c[1]]
couleur[c[0]][c[1]]=visited(c,L,couleur) # c est retiré de la pile et coloré en green ou red
noeud = pchemin.pop()
while couleur[noeud[0]][noeud[1]] == 'red':
noeud = pchemin.pop() # il peut y avoir plusieurs fois le noeud successivement dans la pile
pchemin.push(noeud) # on remet le dernier noeud retiré non rouge
for direc in L:
coord = nexto(c,direc)
if couleur[coord[0]][coord[1]]=='white': # le noeud fils est coloré en blanc dans la direction D
#for n in tab[coord[0]][coord[1]]:
p.push(c)
p.push(coord)
# alors on ajoute le noeud fils dans la direction D au sommet de la pile
# ainsi que son noeud parent
return pchemin.lst
def murSolution(tab,L):
xList=[]
yList=[]
for i in range(len(tab)):
for j in range(len(tab[i])):
mur(tab,i,j)
plt.plot([0, 0, len(tab[0]), len(tab[0]), 0], [0, len(tab), len(tab), 0, 0], 'blue',linewidth=10)
for n in range(len(L)):
yList.append(L[n][0]+0.5)
xList.append(L[n][1]+0.5)
plt.plot(xList,yList,'red',linewidth=2)
L= solution((len(tab)-1,0),(0,len(tab[0])-1),tab)
L
(4, 0) green
(3, 0) green
(2, 0) green
(2, 1) green
(3, 1) green
(4, 1) green
(4, 2) green
(4, 3) green
(4, 4) green
(3, 4) green
(3, 5) green
(4, 5) red
(3, 5) red
(3, 4) red
(4, 4) red
(4, 3) green
(3, 3) green
(3, 2) green
(2, 2) green
(1, 2) green
(1, 1) green
(0, 1) green
(0, 2) green
(0, 3) green
(0, 4) green
(0, 5) green
[(4, 0),
(3, 0),
(2, 0),
(2, 1),
(3, 1),
(4, 1),
(4, 2),
(4, 3),
(4, 3),
(3, 3),
(3, 2),
(2, 2),
(1, 2),
(1, 1),
(0, 1),
(0, 2),
(0, 3),
(0, 4),
(0, 5)]
murSolution(tab,L)
mémoriser TOUTES les étapes du parcours
def parcours(start,end,tab):
"""trouve la solution au labyrinthe et trace ce chemin
p : Pile() utile pour la recherche du parcours
pchemin : Pile() utile pour memoriser tout le chemin
on insère dans le chemin toutes les arêtes empruntées :
pour le chemin entre c1 et c2, on insère c1 puis c2
"""
p = Pile()
pchemin = Pile()
p.push(start)
c = start
couleur = [['white']*len(tab[0]) for i in range(len(tab))]
while (not p.empty()) and (not c == end):
c = p.pop()
pchemin.push(c) # chaque fois que l'on depile, on rempile dans pchemin
L = tab[c[0]][c[1]]
couleur[c[0]][c[1]]=visited(c,L,couleur) # c est retiré de la pile et coloré en green ou red
for direc in L:
coord = nexto(c,direc)
if couleur[coord[0]][coord[1]]=='white': # le noeud fils est coloré en blanc dans la direction D
p.push(c) # on remet le noeud parent afin de reconsidérer sa couleur à chaque fois que l'on depile
# et le chemin arriere CONTINU pour le tracé
p.push(coord)
# alors on ajoute le noeud fils dans la direction D au sommet de la pile
return pchemin.lst
L = parcours((len(tab)-1,0),(0,len(tab[0])-1),tab)
L
(4, 0) green
(3, 0) green
(2, 0) green
(2, 1) green
(3, 1) green
(4, 1) green
(4, 2) green
(4, 3) green
(4, 4) green
(3, 4) green
(3, 5) green
(4, 5) red
(3, 5) red
(3, 4) red
(4, 4) red
(4, 3) green
(3, 3) green
(3, 2) green
(2, 2) green
(1, 2) green
(1, 1) green
(0, 1) green
(0, 2) green
(0, 3) green
(0, 4) green
(0, 5) green
[(4, 0),
(3, 0),
(2, 0),
(2, 1),
(3, 1),
(4, 1),
(4, 2),
(4, 3),
(4, 4),
(3, 4),
(3, 5),
(4, 5),
(3, 5),
(3, 4),
(4, 4),
(4, 3),
(3, 3),
(3, 2),
(2, 2),
(1, 2),
(1, 1),
(0, 1),
(0, 2),
(0, 3),
(0, 4),
(0, 5)]
murSolution(tab,L)
