2024-02-28 05:55:10 +00:00
|
|
|
|
#
|
|
|
|
|
# Chapitre 8 - Exercice Initié 14 - Sortie de labyrinthe
|
|
|
|
|
#
|
|
|
|
|
|
2024-02-28 07:08:02 +00:00
|
|
|
|
from random import randint, choice
|
2024-02-28 05:55:10 +00:00
|
|
|
|
from math import sqrt, ceil, floor
|
|
|
|
|
|
|
|
|
|
# Changements de directions possibles depuis les
|
|
|
|
|
# coordonnées d'une salle du labyrinthe :
|
|
|
|
|
# Haut, droite, bas, gauche
|
|
|
|
|
direction_diff = [(0, 1), (1, 0), (0, -1), (-1, 0)]
|
|
|
|
|
|
|
|
|
|
class Salle:
|
|
|
|
|
def __init__(self, mur=True, entree=False, sortie=False):
|
|
|
|
|
self.mur = mur
|
|
|
|
|
self.entree = entree
|
|
|
|
|
self.sortie = sortie
|
|
|
|
|
self.visites = 0
|
|
|
|
|
|
|
|
|
|
def __repr__(self):
|
|
|
|
|
""" Fonction appelée par défaut par `print()`
|
|
|
|
|
pour représenter un objet sous forme
|
|
|
|
|
textuelle. """
|
|
|
|
|
|
|
|
|
|
resultat = ""
|
|
|
|
|
if self.mur:
|
|
|
|
|
resultat += "Mur"
|
|
|
|
|
elif self.entree:
|
|
|
|
|
resultat += "Entrée"
|
|
|
|
|
elif self.sortie:
|
|
|
|
|
resultat += "Sortie"
|
|
|
|
|
else:
|
|
|
|
|
resultat += "Salle"
|
|
|
|
|
|
|
|
|
|
if self.visites > 0:
|
|
|
|
|
resultat += f" [{self.visites}]"
|
|
|
|
|
return resultat
|
|
|
|
|
|
|
|
|
|
class Labyrinthe:
|
|
|
|
|
|
|
|
|
|
def __init__(self, salles, entree, sortie):
|
|
|
|
|
self.salles = salles
|
|
|
|
|
self.coord_entree = entree # coordonnées
|
|
|
|
|
self.coord_sortie = sortie # coordonnées
|
|
|
|
|
self.direction = 0
|
|
|
|
|
|
|
|
|
|
def __repr__(self):
|
|
|
|
|
""" Fonction appelée par défaut par `print()`
|
|
|
|
|
pour représenter un objet sous forme
|
|
|
|
|
textuelle. """
|
|
|
|
|
|
|
|
|
|
return f"Labyrinthe de {len(self.salles)} x {len(self.salles[0])} : {self.coord_entree} vers {self.coord_sortie}"
|
|
|
|
|
|
2024-02-28 07:08:02 +00:00
|
|
|
|
def salle(self, coords) -> Salle:
|
2024-02-28 05:55:10 +00:00
|
|
|
|
""" Renvoie la Salle correspondant aux `coords`
|
|
|
|
|
passées en argument, si elle existe. """
|
|
|
|
|
|
|
|
|
|
if 0 <= coords[0] < len(self.salles):
|
|
|
|
|
if 0 <= coords[1] < len(self.salles[coords[0]]):
|
|
|
|
|
return self.salles[coords[0]][coords[1]]
|
|
|
|
|
|
|
|
|
|
return None
|
|
|
|
|
|
|
|
|
|
def montrer(self):
|
|
|
|
|
""" Renvoie une représentation textuelle du
|
|
|
|
|
labyinthe représentant ses murs, son entrée,
|
|
|
|
|
sa sortie, et les salles déjà visitées. """
|
|
|
|
|
|
|
|
|
|
resultat = " " + "-"*2*len(self.salles[0]) + "\n|"
|
|
|
|
|
for l in range(len(self.salles)):
|
|
|
|
|
for h in range(len(self.salles[l])):
|
|
|
|
|
if self.salles[l][h].mur:
|
|
|
|
|
resultat += "█▊"
|
|
|
|
|
elif self.salles[l][h].entree:
|
|
|
|
|
resultat += 'E '
|
|
|
|
|
elif self.salles[l][h].sortie:
|
|
|
|
|
resultat += 'S '
|
|
|
|
|
elif self.salles[l][h].visites > 0:
|
|
|
|
|
resultat += '. '
|
|
|
|
|
else:
|
|
|
|
|
resultat += ' '
|
|
|
|
|
if h < len(self.salles[0])-1:
|
|
|
|
|
resultat += "-"*2*(len(self.salles[0])-len(self.salles[-1]))
|
|
|
|
|
resultat += "|\n|"
|
|
|
|
|
resultat = resultat[:-1] + "-"*2*len(self.salles[-1])
|
|
|
|
|
return resultat
|
|
|
|
|
|
|
|
|
|
def reinitialiser(self):
|
|
|
|
|
""" Remet à zéro le nombre de visites
|
|
|
|
|
des salles du labyrinthe. """
|
|
|
|
|
|
|
|
|
|
for i in range(len(self.salles)):
|
|
|
|
|
for j in range(len(self.salles[i])):
|
|
|
|
|
self.salles[i][j].visites = 0
|
|
|
|
|
|
|
|
|
|
def voisins(self, coords):
|
|
|
|
|
""" Retourne la liste des coordonnées des salles
|
|
|
|
|
voisines à la salle aux coordonnées `coords`. """
|
|
|
|
|
|
|
|
|
|
global direction_diff
|
|
|
|
|
voisins = [ [ coords[i]+direction_diff[j][i]
|
|
|
|
|
for i in range(len(coords)) ]
|
|
|
|
|
for j in range(len(direction_diff)) ]
|
|
|
|
|
|
|
|
|
|
return [ tuple(v) for v in voisins if self.salle(v) is not None ]
|
|
|
|
|
|
|
|
|
|
def nb_aretes(self, coords):
|
|
|
|
|
""" Nombre « d'arêtes » de la salle aux coordonnées
|
|
|
|
|
fournies, c'est à dire le nombre de ses voisins
|
|
|
|
|
qui ne sont pas des murs. """
|
|
|
|
|
nb_aretes = 0
|
|
|
|
|
for v in self.voisins(coords):
|
|
|
|
|
s = self.salle(v)
|
|
|
|
|
if (s is not None) and (not s.mur) and (not s.entree) and not s.sortie:
|
|
|
|
|
nb_aretes += 1
|
|
|
|
|
return nb_aretes
|
|
|
|
|
|
|
|
|
|
def coords_direction(self, coords, nombre):
|
|
|
|
|
""" Met à jour self.direction de `nombre`
|
|
|
|
|
quarts de tour dans le sense antihoraire,
|
|
|
|
|
et renvoie les coordonnées contigues à
|
|
|
|
|
`coords` dans cette direction. """
|
|
|
|
|
|
|
|
|
|
global direction_diff
|
|
|
|
|
self.direction = (self.direction + nombre) % 4
|
|
|
|
|
diff = direction_diff[self.direction]
|
|
|
|
|
return (coords[0] + diff[0], coords[1] + diff[1])
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
def creer_labyrinthe(nb_salles):
|
|
|
|
|
""" Fonction utilisée pour générer des labyrinthes
|
|
|
|
|
simples lors du chargement de `labyrinthe.py`. """
|
|
|
|
|
|
|
|
|
|
largeur = int( floor( sqrt( nb_salles ) ) )
|
|
|
|
|
hauteur = int( ceil( nb_salles / largeur ) )
|
|
|
|
|
salles = [ [ Salle() for i in range(hauteur) ] for j in range(largeur) ]
|
|
|
|
|
|
|
|
|
|
coord_entree = (randint(1, largeur//2-1), 0)
|
|
|
|
|
coord_sortie = (randint(largeur//2, largeur-1), hauteur-1)
|
|
|
|
|
salles[coord_entree[0]][coord_entree[1]].entree = True
|
|
|
|
|
salles[coord_sortie[0]][coord_sortie[1]].sortie = True
|
|
|
|
|
salles[coord_entree[0]][coord_entree[1]].mur = False
|
|
|
|
|
salles[coord_sortie[0]][coord_sortie[1]].mur = False
|
|
|
|
|
|
|
|
|
|
x = coord_entree[0]
|
|
|
|
|
cds = False
|
|
|
|
|
for h in range(1, hauteur):
|
|
|
|
|
salles[x][h].mur = False
|
|
|
|
|
if ((h%2==0) or abs(coord_sortie[0]-x)==hauteur-h) and x != coord_sortie[0]:
|
|
|
|
|
diff = coord_sortie[0] - x
|
|
|
|
|
x += diff // abs(diff)
|
|
|
|
|
salles[x][h].mur = False
|
|
|
|
|
|
|
|
|
|
if cds:
|
|
|
|
|
cds = False
|
|
|
|
|
elif randint(0, 10) > 2:
|
|
|
|
|
cds = True
|
|
|
|
|
direction = randint(0, 1) * 2 - 1
|
|
|
|
|
for i in range(x+direction, max(1, min(largeur-1, x + 4 * direction)), direction):
|
|
|
|
|
salles[i][h].mur = False
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
return Labyrinthe(salles, coord_entree, coord_sortie)
|
|
|
|
|
|
|
|
|
|
labyrinthe_simple = creer_labyrinthe(200)
|
|
|
|
|
|
|
|
|
|
salles2 = [ [Salle() for i in range(10)] for j in range(10) ]
|
|
|
|
|
salles2[0][5].entree = True
|
|
|
|
|
salles2[5][5].sortie = True
|
|
|
|
|
salles2[0][5].mur = False
|
|
|
|
|
salles2[5][5].mur = False
|
|
|
|
|
for i in range(1, 9):
|
|
|
|
|
salles2[i][1].mur = False
|
|
|
|
|
salles2[i][8].mur = False
|
|
|
|
|
salles2[1][i].mur = False
|
|
|
|
|
salles2[8][i].mur = False
|
|
|
|
|
salles2[6][5].mur = False
|
|
|
|
|
salles2[7][5].mur = False
|
|
|
|
|
labyrinthe_complexe_1 = Labyrinthe(salles2, (0, 5), (5, 5))
|
|
|
|
|
|
|
|
|
|
salles3 = [ [Salle() for i in range(10)] for j in range(10) ]
|
|
|
|
|
salles3[0][5].entree = True
|
|
|
|
|
salles3[5][5].sortie = True
|
|
|
|
|
salles3[0][5].mur = False
|
|
|
|
|
salles3[5][5].mur = False
|
|
|
|
|
for i in range(1, 9):
|
|
|
|
|
salles3[i][1].mur = False
|
|
|
|
|
salles3[i][8].mur = False
|
|
|
|
|
salles3[1][i].mur = False
|
|
|
|
|
salles3[8][i].mur = False
|
|
|
|
|
labyrinthe_complexe_2 = Labyrinthe(salles3, (0, 5), (5, 5))
|
|
|
|
|
|
|
|
|
|
def sortie_main_droite(l: Labyrinthe):
|
|
|
|
|
nodes = []
|
|
|
|
|
current = l.coord_entree
|
|
|
|
|
while current != l.coord_sortie:
|
|
|
|
|
new_current = l.coords_direction(current, 1)
|
|
|
|
|
if new_current in [coord for coord in l.voisins(current) if not l.salle(coord).mur]:
|
|
|
|
|
nodes.append(current)
|
|
|
|
|
current = new_current
|
|
|
|
|
if current == l.coord_sortie:
|
|
|
|
|
nodes.append(current)
|
|
|
|
|
break
|
|
|
|
|
else:
|
|
|
|
|
l.coords_direction(current, -2)
|
|
|
|
|
return nodes
|
|
|
|
|
|
|
|
|
|
print(labyrinthe_simple.montrer())
|
|
|
|
|
print(sortie_main_droite(labyrinthe_simple))
|
2024-02-28 07:08:02 +00:00
|
|
|
|
|
|
|
|
|
def sortie_tremaux(l: Labyrinthe):
|
|
|
|
|
nodes = [l.coord_entree]
|
|
|
|
|
l.salle(nodes[-1]).visites += 1
|
|
|
|
|
while nodes[-1] != l.coord_sortie:
|
|
|
|
|
voisins = [coord for coord in l.voisins(nodes[-1]) if not l.salle(coord).mur]
|
|
|
|
|
voisins_non_visite = [coord for coord in voisins if l.salle(coord).visites == 0]
|
|
|
|
|
if voisins_non_visite:
|
|
|
|
|
nodes.append(choice(voisins_non_visite))
|
|
|
|
|
l.salle(nodes[-1]).visites += 1
|
|
|
|
|
else:
|
|
|
|
|
nodes.pop()
|
|
|
|
|
return nodes
|
|
|
|
|
|
|
|
|
|
print(labyrinthe_complexe_1.montrer())
|
2024-02-28 07:38:34 +00:00
|
|
|
|
print(sortie_tremaux(labyrinthe_complexe_1))
|
|
|
|
|
|
|
|
|
|
def genere_labirinthe_aleatoire(nb_salles, max_aretes):
|
|
|
|
|
salles = [ [Salle() for x in range(nb_salles)] for y in range(nb_salles) ]
|
|
|
|
|
entree = (randint(0, nb_salles-1), randint(0, nb_salles-1))
|
|
|
|
|
sortie = (randint(0, nb_salles-1), randint(0, nb_salles-1))
|
|
|
|
|
l = Labyrinthe(salles, entree, sortie)
|
|
|
|
|
l.salle(entree).mur = False
|
|
|
|
|
l.salle(entree).entree = True
|
|
|
|
|
l.salle(sortie).mur = False
|
|
|
|
|
l.salle(sortie).sortie = True
|
|
|
|
|
|
|
|
|
|
visited = [entree]
|
|
|
|
|
current = entree
|
|
|
|
|
while current != sortie:
|
|
|
|
|
voisins = []
|
|
|
|
|
for voisin in [coord for coord in l.voisins(current) if coord not in visited]:
|
|
|
|
|
voisins_of_voisin = [coord for coord in l.voisins(voisin) if coord != current]
|
|
|
|
|
for coord in voisins_of_voisin:
|
|
|
|
|
if coord in visited:
|
|
|
|
|
break
|
|
|
|
|
else:
|
|
|
|
|
voisins.append(voisin)
|
|
|
|
|
|
|
|
|
|
if not voisins:
|
|
|
|
|
for x in range(nb_salles):
|
|
|
|
|
for y in range(nb_salles):
|
|
|
|
|
l.salle((x, y)).mur = True
|
|
|
|
|
visited = [entree]
|
|
|
|
|
current = entree
|
|
|
|
|
continue
|
|
|
|
|
|
|
|
|
|
current = choice(voisins)
|
|
|
|
|
visited.append(current)
|
|
|
|
|
if current != sortie:
|
|
|
|
|
l.salle(current).mur = False
|
|
|
|
|
|
|
|
|
|
for i in range(nb_salles):
|
|
|
|
|
for j in range(nb_salles):
|
|
|
|
|
for voisin in l.voisins((i, j)):
|
|
|
|
|
if not l.salle(voisin).mur:
|
|
|
|
|
break
|
|
|
|
|
else:
|
|
|
|
|
current = (i, j)
|
|
|
|
|
a = [current]
|
|
|
|
|
l.salle((i, j)).mur = False
|
|
|
|
|
while current not in visited:
|
|
|
|
|
current = choice(l.voisins(current))
|
|
|
|
|
l.salle(current).mur = False
|
|
|
|
|
a.append(current)
|
|
|
|
|
for x in a:
|
|
|
|
|
visited.append(x)
|
|
|
|
|
|
|
|
|
|
return l
|
|
|
|
|
|
2024-02-28 07:58:41 +00:00
|
|
|
|
#print(genere_labirinthe_aleatoire(10, 10).montrer())
|
2024-02-28 07:38:34 +00:00
|
|
|
|
|
2024-02-28 07:58:41 +00:00
|
|
|
|
def inside(x, y, nb_salles):
|
|
|
|
|
return x >= 0 and x < nb_salles and y >= 0 and y < nb_salles
|
|
|
|
|
|
|
|
|
|
def vrai_labyrinthe(nb_salles):
|
|
|
|
|
if nb_salles % 2 == 0: nb_salles += 1
|
|
|
|
|
nodes = [[x % 2 == 0 or y % 2 == 0 for x in range(nb_salles)] for y in range(nb_salles)]
|
|
|
|
|
visited = set([(1, 1)])
|
|
|
|
|
stack = [(1, 1)]
|
|
|
|
|
while stack:
|
|
|
|
|
x, y = stack[-1]
|
|
|
|
|
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
|
|
|
|
|
directions = [(dx, dy) for dx, dy in directions if inside(x+dx*2, y+dy*2, nb_salles)]
|
|
|
|
|
directions = [(dx, dy) for dx, dy in directions if (x+dx*2, y+dy*2) not in visited]
|
|
|
|
|
if not directions:
|
|
|
|
|
stack.pop()
|
|
|
|
|
else:
|
|
|
|
|
dx, dy = choice(directions)
|
|
|
|
|
nodes[x+dx][y+dy] = False
|
|
|
|
|
stack.append((x+dx*2, y+dy*2))
|
|
|
|
|
visited.add((x+dx*2, y+dy*2))
|
|
|
|
|
return Labyrinthe([[Salle(node) for node in row] for row in nodes], (1, 1), (nb_salles-2, nb_salles-2))
|
|
|
|
|
|
|
|
|
|
print(vrai_labyrinthe(40).montrer())
|