FAOD-DUI4/maze/maze.md

title	author	date
TP - Structure de données linéaire - La pile	TODARO Cédric	06 juin 2021

Sortir d'un labyrinthe

On peut modéliser un labyrinthe par une chaîne de caractères de la manière suivante :

maze_str="""
################
#e             #
##### ###### ###
#  #   #     #s#
## ##### ### # #
#          #   #
################
"""

• e : Entrée du labyrinthe
• s : Sortie du labyrinthe
• # : Mur
• Une position dans le labyrinthe peut-être modèlisé par un tuple (ligne,colonne)

Pour pouvoir accéder à une case du labyrinthe de manière plus pratique : maze[ligne][colonne], vous pouvez transformer cette chaîne de caractères en listes :

maze = maze_str.split("\n")          # La première et dernière ligne sont vides (cela n'influence pas l'algorithme)
>>> maze[2][2]                       # Ligne n°2 , Colonne n°2 : position non explorée
' '
>>> maze[2][1]                       # Ligne n°2 , Colonne n°1 : entrée du labyrinthe
'e'
>>> maze[4][0]                       # Ligne n°4 , Colonne n°0 : un mur
'#'

Pour trouver la sortie du labyrinthe à l'aide d'une pile :

• Empiler la position de départ sur la pile
• Tant que la pile n'est pas vide :
  • Se rendre sur la position "du haut" de la pile
  • Marquer notre position comme explorée (X)
  • Empiler les positions adjacentes inexplorées (en haut, en bas, à gauche ,à droite)

Pour écrire l'algorithme permettant d'explorer un labyrinthe, je vous conseille d'écrire les fonctions suivantes :

• aff(t) : Affichage du labyrinthe t, t étant une liste de chaîne de caractères représentant chacune une ligne du labyrinthe.
• find_e(t) : Retourne la ligne et la colonne où se situe l'entrée dans t.
• avance(t, p) : p étant la pile des positions inexplorées, cette fonction doit faire :
  • Avance sur la position inexplorée suivante.
  • Marque la position courante comme explorée.
  • Empile les positions adjacentes inexplorées dans p.
  • Si on a trouvé la sortie s, on vide la pile p.

Écrire les fonctions ci-dessus et tester les à l'aide de :

import time

...

# Tant que la pile n'est pas vide ... on avance
p = Pile()
p.add(find_e(maze))
while(not p.is_empty()):
    avance(maze,p)
    aff(maze)
    time.sleep(0.5)

Vous trouverez à la fin du fichier, des exmeples de labyrithes pour tester votre algorithme :

maze_str = """
######################################
#e         # #   #   #               #
######  ## # # # # #  # ##############
#      ##  # #   #   #  #        ##s #
######  ## # # ####   # # ## # #  ## #
#       #            #     #   ## #  #
# ############## # # ########  #  # ##
# #        #       # #     #   # ##  #
# ##### ############ # # #   ###    ##
#              #       # # #   ## # ##
######################################
"""
... etc ...

Bonus : tkinter

Réaliser l'affichage du labyrinthe à l'aide de la bibliothèque tkinter.

Vous pouvez consulter la documentation suivante : Tkinter pour ISN notament la partie sur Canvas :

from tkinter import *
root = Tk()
root.title = 'Titre fenêtre'

canevas = Canvas(root, width=400, height=400, background="#FFFFFF")
canevas.create_rectangle(10, 20, 40, 50, fill="#00FF00")
canevas.create_rectangle(40, 50, 100, 100, fill="#0000FF")
canevas.pack()

root.mainloop()

Remarque :

after(delai_ms, fonc=None, *args)

Demande à Tkinter d’appeller la fonction de rappel fonc avec les arguments args après l’écoulement du délai delai_ms donné en millisecondes. Votre fonction de rappel ne peut pas être appelée avant ce délai (même si son appel effectif peut le dépasser) et elle ne sera appelée qu’une fois.

Exemple d'utilisation :

from tkinter import *

root = Tk()

def task():
    print("hello")
    root.after(2000, task)  # reschedule event in 2 seconds

root.after(2000, task)
root.mainloop()

Remerciements

Merci à Quentin Konieczko pour son cours sur la POO.