305 lines
11 KiB
Python
305 lines
11 KiB
Python
#
|
||
# Chapitre 8 - Exercice Initié 14 - Sortie de labyrinthe
|
||
#
|
||
|
||
from random import randint, choice
|
||
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}"
|
||
|
||
def salle(self, coords) -> Salle:
|
||
""" 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))
|
||
|
||
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())
|
||
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
|
||
|
||
#print(genere_labirinthe_aleatoire(10, 10).montrer())
|
||
|
||
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())
|