!-- **************************************************************************** -->

Formation I.S.N.

Dédale

sortir d'un labyrinthe

On utilise une grille pour représenter un labyrinthe.

Plus précisément, on modélise ici un labyrinthe par une liste de listes. 0 indique un passage, 1 indique un mur, 2 indique la sortie. L'entrée est dans les exemples ci-dessous en (0,0). 


# un premier labyrinthe possible :

dedale = [  
    [0,1,1,1,1,1],   
    [0,0,1,1,1,1],   
    [1,0,1,1,1,1],   
    [1,0,1,0,0,0],   
    [0,0,0,0,1,2],  
    [0,0,0,1,1,1], 
    [1,1,1,1,1,1]
    ] 


# un second labyrinthe possible :

dedale = [
	[0,0,0,0,0,0,1,1,1,1],
	[0,1,0,0,1,1,1,1,0,1],
	[0,1,0,1,0,0,0,0,0,2],
	[0,1,0,0,0,1,1,1,1,1],
	[0,1,1,1,0,1,0,0,0,2],
	[0,0,0,1,0,0,0,1,0,1]
]

Un robot entre en (0,0) et doit sortir seul du labyrinthe. Le robot sait détecter qu'une case est bouchée, le robot peut mémoriser le fait qu'une case a déjà été visitée, il peut se déplacer dans les 4 directions principales nord, est, ouest, sud.

Proposer une fonction python récursive pour faire sortir ce robot.

  • principe
  • un code
  • à poursuivre
  • Cas de base : le robot est sur une case marquée 2, c'est terminé.
  • Sinon, le robot essaie d'abord le sud (par exemple !) : si cela le mène à une case qui elle-même peut mener jusqu'à la sortie, il continue. Sinon, il essaie l'est... puis le nord puis l'ouest.

Il ne faut pas oublier de marquer les cases déjà visitées pour éviter les allers-retours incessants ou les boucles.

On marque par un 3 les cases visitées.

La sortie est marquée 5 lors de sa visite (ce n'est pas nécessaire, ici c'est un choix pour l'affichage).


    
dedale = [
	[0,0,0,0,0,0,1,1,1,1],
	[0,1,0,0,1,1,1,1,0,1],
	[0,1,0,1,0,0,0,0,0,2],
	[0,1,0,0,0,1,1,1,1,1],
	[0,1,1,1,0,1,0,0,0,2],
	[0,0,0,1,0,0,0,1,0,1]
]
    
    
nbLignes = len(dedale)
nbColonnes = len(dedale[0])
 

def affiche_etat(ligne,colonne):      
	""" affiche l'état mur, ouvert ou sortie de la 'cellule' """
	if dedale[ligne][colonne] == 1:     
		print('Mur aux coordonnées {},{}.'.format(ligne,colonne))
	elif dedale[ligne][colonne] == 0:    
		print('Passage aux coordonnées {},{}.'.format(ligne,colonne))
	elif dedale[ligne][colonne] == 2:    
		print('Sortie aux coordonnées {},{}.'.format(ligne,colonne))



def affiche_dedale(dedale):
	""" affiche le labyrinthe """
	print(' ', end = ' ')
	for i in range(nbColonnes) : print('_', end = ' ')
	print()
	for l,ligne in enumerate(dedale) :
		if l == 0 : print('\u2192', end = ' ')
		else : print('|', end = ' ')
		for e, element in enumerate(ligne) :
			if element == 1 : print('X', end=" ")
			elif element == 0 or element == 2 : print(' ', end=" ")
			elif element == 3 : print( '\u2658', end = ' ')
			else : print('\u2658', end=" ") # cas 5 : sortie visitée
			if e == nbColonnes-1 :
				if element != 2 and element != 5 : print('|', end = ' ')
				else : print('\u2192', end = ' ')
		print()
	print(' ', end = ' ')
	for i in range(nbColonnes) : print('\u0305', end = '  ')
	print()
        
        
        

def deplacement(ligne,colonne, trace ):
	
	if trace : affiche_etat(ligne,colonne)
	
	if   dedale[ligne][colonne] == 2 : 
		dedale[ligne][colonne] += 3
		return True
	elif dedale[ligne][colonne] == 1 : return False
	elif dedale[ligne][colonne] == 3 : return False
	else : dedale[ligne][colonne] = 3      

	# à partir d'une cellule, on essaie les quatre directions
	# la première menant jusqu'à la sortie est retenue
	if ligne < nbLignes-1 and deplacement(ligne+1, colonne, trace) : return True
	if colonne > 0 and deplacement(ligne, colonne-1, trace)  : return True 
	if ligne > 0 and deplacement(ligne-1, colonne, trace) : return True 
	if colonne < nbColonnes-1 and deplacement(ligne, colonne+1, trace) : return True 
		 

	return False

print("Labyrinthe : ")
affiche_dedale(dedale)
print("Parcours du labyrinthe :\n ")
deplacement(0, 0, trace = True)
affiche_dedale(dedale)

On obtient (les cavaliers marquent les cases par lesquelles le robot est passé) : 

  _ _ _ _ _ _ _ _ _ _ 
→ ♘ ♘ ♘       X X X X | 
| ♘ X ♘   X X X X   X | 
| ♘ X ♘ X             → 
| ♘ X ♘ ♘ ♘ X X X X X | 
| ♘ X X X ♘ X ♘ ♘ ♘ ♘ → 
| ♘ ♘ ♘ X ♘ ♘ ♘ X ♘ X | 
  ̅  ̅  ̅  ̅  ̅  ̅  ̅  ̅  ̅  ̅

Dans le cadre d'un projet, il resterait beaucoup à faire :

  • Tracer le chemin menant de l'entrée à la sortie.
  • Lorsque plusieurs chemins de sortie existent, trouver le plus court.
  • Tester d'autres algorithmes de résolution, comparer leurs complexités.
  • Ajouter une interface graphique pour représenter le labyrinthe et le chemin de sortie.
  • Générer de façon automatique de nouveaux labyrinthes.
  • etc...

dessiner un labyrinthe

On représente dans cet exercice une grille, ou plutôt un quadrillage de murs avec la fonction suivante : 


def dessine_grille(largeur, hauteur) :
	vertical = [["|  "] * largeur + ['|'] for _ in range( hauteur)] 
	horizontal = [["+--"] * largeur + ['+'] for _ in range( hauteur + 1)]
	for i in range(hauteur) :
		print(*horizontal[i]) # utilisation de * pour unpacking
		print(*vertical[i])
	print(*horizontal[hauteur])
	
dessine_grille(3,5)

on obtient : 

+-- +-- +-- +
|   |   |   |
+-- +-- +-- +
|   |   |   |
+-- +-- +-- +
|   |   |   |
+-- +-- +-- +
|   |   |   |
+-- +-- +-- +
|   |   |   |
+-- +-- +-- +

Pour créer un labyrinthe à partir de ce quadrillage de murs, on va utiliser le même principe de parcours en profondeur que celui utilisé dans l'exercice précédent pour sortir du labyrinthe.

Le robot se trouve au départ dans une cellule quelconque.

  1. Il marque cette case comme étant visitée.
  2. Si cette case a des voisines non visitées, il va dans l'une de ces cases voisines au hasard, en détruisant au passage le mur séparateur et retourne au point 1.
  3. Sinon (toutes les voisines sont déjà visitées), il remonte à contre-sens les cases visitées jusqu'à en trouver une ayant encore des voisines non visitées, il va alors dans l'une de ces cases voisines au hasard, en détruisant au passage le mur séparateur et retourne au point 1.

Remarque : les murs extérieurs restent en place dans ce processus.

Proposer une fonction python récursive de ce principe.

  • principe
  • un code
  • avec la tortue

Le principe peut s'énoncer plus explicitement avec une pile.

La pile au départ est vide. Le robot est sur une case prise au hasard au départ.

  1. On place la case sur laquelle le robot se trouve au sommet de la pile et on marque cette case comme étant visitée.
  2. Si la case actuelle (sommet de la pile) a des voisines non visitées, on en choisit une au hasard, on fait tomber le mur entre la case actuelle et la case que l'on vient de choisir et on retourne au point 1.
  3. Si la case actuelle (sommet de la pile) a toutes ses voisines visitées, on remonte la pile (en dépilant) jusqu'à la première case ayant encore des voisines non visitées. On choisit l'un de ces voisines au hasard, on fait tomber le mur entre la case actuelle (sommet de la pile) et la case que l'on vient de choisir et on retourne au point 1.
  4. Si on remonte toute la pile (toutes les cases avaient toutes leurs voisines visitées), la pile est vide et on a terminé. 

from random import shuffle, randint

def voisinage(x,y, largeur, hauteur) :
	"""
	retourne les voisins de la case [y][x]
	(en tenant compte des bords) 
	"""
	voisins = []
	for (xx,yy) in [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)] :
		if 0 <= xx < largeur and 0 <= yy < hauteur :
			voisins.append((xx,yy))
	shuffle(voisins)
	return voisins
 
def cree_dedale(largeur, hauteur):
	
	# aucune cellule n'est visitée (donc elles sont toutes mises à False) :
	vu = [[False] * largeur   for _ in range(hauteur)]  
	
	vertical = [["|  "] * largeur + ['|'] for _ in range( hauteur)] 
	horizontal = [["+--"] * largeur + ['+'] for _ in range( hauteur + 1)]

	def on_visite(x, y):
		# on marque la cellule actuelle comme étant visitée :
		vu[y][x] = True
		
		# pour chaque voisine  de la cellule actuelle :
		for (xx, yy) in voisinage(x,y, largeur, hauteur) :
			# si elle est visitée, on ne fait rien :
			if vu[yy][xx]: continue
			# sinon on fait tomber le mur séparateur : 
			if xx == x: horizontal[max(y, yy)][x] = "+  "
			if yy == y: vertical[y][max(x, xx)] = "   "
			# et on repart de cette nouvelle cellule :
			on_visite(xx, yy)

	# on part d'une cellule au hasard : 
	on_visite( randint(0,largeur-1) , randint(0,hauteur-1) )
	
	# on dessine la grille :
	for i in range(hauteur) :
		print(*horizontal[i]) # utilisation de * pour unpacking
		print(*vertical[i])
	print(*horizontal[hauteur])

	
 
cree_dedale(15,10)

On obtient par exemple : 

+-- +-- +-- +-- +-- +-- +-- +-- +-- +-- +-- +-- +-- +-- +-- +
|   |                           |                           |
+   +   +-- +-- +   +-- +-- +   +-- +-- +-- +   +   +-- +   +
|   |       |       |       |       |       |   |   |   |   |
+   +-- +   +   +-- +   +   +-- +   +   +   +-- +   +   +   +
|           |           |   |           |           |   |   |
+   +-- +-- +-- +   +-- +   +-- +-- +-- +-- +-- +-- +   +   +
|       |       |       |               |               |   |
+-- +-- +   +   +-- +-- +   +-- +-- +   +   +-- +-- +   +   +
|           |           |           |   |   |           |   |
+   +-- +-- +-- +-- +   +-- +   +-- +   +   +-- +-- +   +   +
|   |   |           |       |   |       |           |   |   |
+   +   +-- +   +   +-- +   +   +   +-- +   +-- +   +-- +   +
|       |       |       |   |   |   |       |   |       |   |
+-- +-- +   +-- +-- +-- +   +-- +   +   +-- +   +-- +   +   +
|   |           |       |           |       |   |       |   |
+   +   +-- +   +   +   +-- +-- +-- +-- +   +   +   +-- +   +
|       |   |   |   |       |           |       |           |
+   +-- +   +   +   +-- +   +   +   +-- +-- +   +-- +-- +-- +
|           |           |       |                           |
+-- +-- +-- +-- +-- +-- +-- +-- +-- +-- +-- +-- +-- +-- +-- +


from random import shuffle, randint
import turtle as tl

U = 20  # unité pour le dessin


def voisinage(x,y, largeur, hauteur) :
	"""
	retourne les voisins de la case [y][x]
	(en tenant compte des bords) 
	"""
	voisins = []
	for (xx,yy) in [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)] :
		if 0 <= xx < largeur and 0 <= yy < hauteur :
			voisins.append((xx,yy))
	shuffle(voisins)
	return voisins
 
def cree_dedale(largeur, hauteur):
	
	# aucune cellule n'est visitée (donc elles sont toutes mises à False) :
	vu = [[False] * largeur   for _ in range(hauteur)]  
	
	# on pose des murs partout :
	vertical = [ [True for j in range(largeur + 1)]  for i in range(hauteur)] 
	horizontal = [ [True for j in range(largeur)]    for i in range(hauteur + 1)]

	def on_visite(x, y):
		# on marque la cellule actuelle comme étant visitée :
		vu[y][x] = True
		
		# pour chaque voisine  de la cellule actuelle :
		for (xx, yy) in voisinage(x,y, largeur, hauteur) :
			# si elle est visitée, on ne fait rien :
			if vu[yy][xx]: continue
			# sinon on fait tomber le mur séparateur : 
			if xx == x: horizontal[max(y, yy)][x] = False
			if yy == y: vertical[y][max(x, xx)] = False
			# et on repart ... :
			on_visite(xx, yy)

	# on part d'une cellule au hasard : 
	on_visite( randint(0,largeur-1) , randint(0,hauteur-1) )
	
	# on dessine la grille :
	dessine_dedale(vertical, horizontal, largeur, hauteur)
	

def dessine_mur(xa,ya, xb, yb) :
	"""
	Trace le segment d'extrémités (xa, ya) et (xb,yb).
	"""
	xa, ya = xa * U, ya * U
	xb, yb = xb * U, yb * U
	tl.hideturtle()
	tl.speed(0)
	tl.pencolor('black')
	tl.pensize(2)
	tl.penup()
	tl.setposition(xa, ya)
	tl.pendown()
	tl.setposition(xb, yb)
	tl.penup()
	
	
def dessine_dedale(vert, hor, l, h) :
	tl.setworldcoordinates(0, -(h+1)*U, (l+1)*U, 0)
	for x in range(l+1) :
		for y in range(h) :
			if vert[y][x] : dessine_mur(x, -y, x, -y-1)
	for x in range(l) :
		for y in range(h+1) :
			if hor[y][x] : dessine_mur(x, -y, x+1, -y)
	tl.exitonclick()
 
cree_dedale(15,10)

On obtient par exemple :
dessin de labyrinthe