Série 5

Exercice 1

Dans ce premier exercice, nous allons créer un générateur de labyrinthes ! Voici un exemple de labyrinthe que votre programme pourrait générer à la fin de l'exercice :

Dans cet exercice, le but sera d'implémenter la méthode generer_labyrinthe dont voilà la signature :

def generer_labyrinthe(largeur, hauteur):
    pass

La méthode générera une image de la librairie Pillow que vous pourrez ensuite afficher ou sauvegarder. Par exemple :

if __name__ == "__main__":
    img = generer_labyrinthe(75, 50)
    img.show()

Étape 1 - Création du canvas

Pour la première étape, nous allons créer l'image qui servira de support au labyrinthe. Dans un premier temps, cette image représentera largeur * hauteur petites cellules blanches entourées de murs noirs. L'image suivante montre l'image attendue pour des dimensions 40 par 20.

À noter que l'image est zoomée ici, mais il est plus simple de travailler sur une image où un pixel correspond à la taille d'une cellule blanche.

Étape 2 - Faire sauter les murs

Chaque cellule (marquée en blanc dans l'image précédente) est actuellement entourée de murs noirs. Dans cette étape, le but sera de faire sauter certains de ces murs (en les affichant en blanc) afin de connecter toutes les cellules du labyrinthe ensemble.

Pour ce faire, on utilisera l'algorithme suivant :

• On débute sur une cellule (affichée en blanche) aléatoire du labyrinthe, que l'on note comme cellule courante et que l'on considère visitée. À noter qu'il vous faudra prendre note, pour chaque cellule, de si la cellule a été visitée ou non.
• On se déplace ensuite sur un des voisins non-visités de la cellule, au hasard. Ce voisin devient notre cellule courante et on le note comme visité. Au passage, on abat le mur entre les deux cellules. Il suffit d'abattre le mur dans l'image, cette information n'étant pas importante pour le déroulement de l'algorithme.
  • Si la cellule n'a pas de voisins non-visités, on est arrivé dans un cul de sac. Dans ce cas, on réessaie avec la cellule d'où on est venu. Pour cela, il vous faudra noter le chemin entre la cellule initiale et la cellule courante. Lorsqu'on remonte au parent on raccourcit ce chemin, alors que lorsqu'on visite un voisin, on le rallonge.
  • Si la cellule n'a pas de voisins non-visités et n'a pas de parent, c'est que le travail est terminé !

Conseil : La librarie random de Python, qui fait partie de l'installation standard, permet d'obtenir des valeurs (pseudo)-aléatoire. Nous vous invitons à consulter sa documentation. Les méthodes qui vous intéresserons certainement le plus sont randint et choice.

Conseil : Il serait avisé de faire une méthode voisins qui retourne une liste de voisins valides.

Conseil : Utilisez une liste (de longueur largeur) de listes (de longueurs hauteur) remplies de booléens afin de garder trace des cellules visitées.

Conseil : Utilisez une simple liste pour maintenir le chemin de la cellule initiale à la cellule courante.

À la fin de cette étape, on obtient normalement des labyrithes comme ceci :

Étape 3 - Entrée et sortie

Dans cette troisième étape, on crée simplement une entrée sur le haut du labyrinthe et une sortie sur le bas. Les ordonnées des ouvertures sont prises au hasard. Une sortie possible à la fin de cette étape serait :

Étape 4 - Souris et fromage

À cette étape, il s'agira de redimensionner l'image (par exemple en multipliant la taille de ses côtés par 5) puis de la coller dans une image blanche plus haute (afin de laisser de la place pour la souris et le fromage).

On ajoutera ensuite l'image de la souris et celle du fromage. L'idéal serait de faire en sorte que les deux images soient proches de l'entrée et respectivement de la sortie du labyrinthe.

Conseil : Utilisez la méthode paste de Image afin de coller une image dans une autre. Vous pouvez consulter la documentation pour vous aider.

Exercice 2

Une pauvre souris se retrouve devant un interminable labyrinthe. Saurez-vous la guider jusqu'au fromage ?

Aidez-vous de cette image simplifiée pour résoudre le labyrinthe :

• Affichez en rouge le chemin direct entre l'entrée et la sortie du labyrinthe (pas question de revenir sur ses pas).
• Affichez en gris les cases visitées mais non retenues.
• Laissez les autres cases intacts.

L'image en dessous donne un exemple de solution pour un labyrinthe plus petit. Les chemins en gris peuvent variés selon l'implémentation.