Nous proposons de travailler sur la réalisation d'un générateur de labyrinthes rectangulaires. Plus précisément des labyrinthes parfaits, que nous définissons plus loin. Nous utiliserons pour ceci le langage Python dans un paradigme de programmation objet. Au travers d'exercices guidés, nous réaliserons les objectifs suivants :

• Dénombrement des murs de deux types de labyrinthe
• Implémentation en Python d'une classe modélisant des labyrinthes rectangulaires
• Implémentation en Python d'un algorithme de génération de labyrinthe utilisant de l'aléatoire
• Représentation 2D des labyrinthes générés en utilisant la librairie matplotlib de Python.
• Représentation 3D des labyrinthes générés en utilisant une libriairie JavaScript.

Les réalisations pourront éventuellement aboutir sur d'autres séquences comme la résolution de labyrinthe ou des projets transversaux comme la conception d'objets imprimés en coopération avec une filière STI2D .

Nous nous intéresserons seulement à des labyrinthes rectangulaires composés de n lignes et m colonnes sur une grille régulière composée de n×m cellules. Chaque cellules comportant 4 côtés dont chacun peut être ouvert ou fermé (présence d'un mur). Deux cellules sont consécutives si elles partagent un côté. Un chemin dans un labyrinthe est une suite finie de n cellules C1, C2,...,Ck où chacune est consécutive avec sa suivante. Nous souhaitons générer des labyrinthes parfaits : Un labyrinthe est dit parfait si pour tout couple de cellules C1 et C2 il existe un et un seul chemin connectant C1 à C2. Avant de se lancer tête baissée dans la programmation, il est nécessaire de mieux connaître l'ensemble sur lequel nous allons travailler. Nous commençons avec un exercice de dénombrement : Montrer que pour un labyrinthe rectangulaire de n lignes et m colonnes le nombre maximal de murs internes fermés est : 2 n m - n - m

Indice 1

Pour ne pas compter deux fois chaque mur, ne considérer que ceux du bas et de droite

Indice 2

Pour la dernière ligne et la dernière colonne on ne compte qu'un mur interne (sauf pour le coin). Comme il existe un chemin unique entre n'importe quelle paire de cellules, on peut choisir n'importe quel point de départ et d'arrivée. On prend généralement deux coins opposés ou au moins sur des bords opposés. On peut aussi choisir le centre comme point de départ.

Commencer par créer un fichier labyrinthe.py qui contiendra le travail réalisé dans cette partie. Nous choisissons comme modèle de représentation une classe Labyrinthe qui contiendra les méthodes et les attributs suivants : afin de modéliser des labyrinthes rectangulaires nous allons créer une classe respectant les conditions suivantes : Définir une classe Labyrinthe prenant deux arguments widthle nombre de colonnes de la grille et height, le nombre de lignes. La classe devra comprendre :

• un constructeurLe constructeur d'une classe en programmation objet est la première méthode appelée lorsque l'on instancie un nouvel objet. Il permet d'initialiser les attributs de l'objet. En python ce constructeur est toujours la méthode __init__() __init__(self, width, height)
• des attributs self.width et self.height définis dans le constructeur
• un attribut self.cells représentant les cellules du labyrinthe. Pour l'instant on lui affectera une liste vide.

Indice 1

Déclarer une classe en python : class NomClasse:
  ...

Indice 2

La variable self représentera l'instance de la classe Labyrinthe. Ici un labyrinthe particulier.

Indice 3

Les arguments width et height doivent être affecté aux attributs self.width et self.height. Pour l'instant, les cellules n'existent pas, il va falloir les modéliser. Une cellule doit posséder 4 murs : Nord N, Est E, Sud S et Ouest O. Nous représenterons une cellule à l'aide d'un dictionnaire dont les clés sont N, E, S et O et dont les valeurs sont des booléens : True si on peut passer (pas de mur), False sinon. Le dictionnaire ci-dessous représente une cellule entièrement murée : {'N':False, 'E':False, 'S':False, 'O':False} Dans le constructeur __init__(), à la suite de l'affectation des attributs, initialiser l'attribut cells comme un tableau à height lignes et width colonnes contenant des cellules entièrement murées.

Indice 1

Parcourir les cellules avec une double boucle itérant i sur les lignes et j sur les colonnes de la grille.

Indice 2

On peut ajouter un élément aà une liste Lavec la méthode L.append(a)

Indice 3

Une grille à n lignes et m colonnes peut être modélisé par une liste de n listes à m éléments. Afin de visualiser les labyrinthes dans la console (en ascii art), on ajoutera la méthode suivante print()à la classe Labyrinthe : Télécharger la méthode Labyrinthe.print.py def print(self, print_zones=False): from math import floor #alias : w=self.width;h=self.height;c=self.cells; #si on imprime les zones, il faut élargir la taille des couloirs if(print_zones): len_zone=max([ max([ len(str(laby.cells[i][j]['zone'])) for i in range(laby.height) ]) for j in range(laby.width) ])+1 inters=[' ','╴','╷', '┐','╶','─','┌','┬','╵','┘','│','┤','└','┴','├','┼'] t="" #la grille des intersections de cases est de taille (N+1)(M+1) for i in range(h+1): interligne="" for j in range(w+1): #up, right, bottom, left : les 4 parties de la croix "┼" #False = mur, True = pas mur #Coins et bords: up=False if i==0 else None left=False if j==0 else None right=False if j==w else None bottom=False if i==h else None if j==w: if up==None:up=not c[i-1][j-1]['E'] if bottom==None:bottom=not c[i][j-1]['E'] if i==h: bottom=False if right==None:right=not c[i-1][j]['S'] if left==None:left=not c[i-1][j-1]['S'] #intérieur : if up==None:up=not c[i-1][j]['W'] if right==None:right=not c[i][j]['N'] if bottom==None:bottom=not c[i][j]['W'] if left==None:left=not c[i][j-1]['N'] #-> mot binaire à 4 bits. 16 cas qu'on a mis dans l'ordre dans la liste inters #indice inters k=-up*8+right*4+bottom*2+left if not print_zones: #espacement horizontal supplémentaire sep= "─" if left else " " t+=sep+inters[k] if j==self.width:t+="\n" else: sep= (len_zone+2)*"─" if right else (len_zone+2)*" " #num_zone=self.zones[self.cells[i][j]["zone"]] if i -1 and num_zone <10 else "*" interligne+=("│" if bottom else " ")+" "*(len_sp_left+1)+txt_num_zone+" "*(len_sp_right+1) t+=inters[k]+sep if j==self.width: t+="\n" + interligne + "\n" print(t) ┌─────┬─┬─────┬─┬───┬─────┬───┐ ├─╴ ╶─┤ └─╴ ╶─┘ ╵ ╶─┼─╴ ┌─┼─╴ │ │ ┌─╴ │ ╷ ╷ ╶─┬─┐ ╷ └─╴ │ │ ╷ │ ├─┘ ╶─┤ ├─┼─╴ │ └─┘ ┌─╴ │ ╵ └─┤ │ ┌───┤ │ ╵ ┌─┴─────┤ ╷ ╵ ┌─┐ │ │ ╵ ┌─┤ └───┘ ╶─┬─╴ └─┼─╴ ╵ │ │ │ ╷ ╵ │ ╶─┐ ╷ ╶─┤ ╶───┴─┐ ╶─┤ │ ├─┤ ╶─┼───┤ └───┼─╴ ╶─┬─┴───┴─┤ │ ╵ ┌─┴─╴ ╵ ╷ ╷ ├─╴ ╷ │ ┌─┐ ╷ │ │ ╶─┴─┐ ┌───┘ │ ├─┐ └─┤ ╵ ├─┘ │ ├─╴ ╶─┼─┼─┬───┴─┤ │ ╶─┤ ╶─┤ ╶─┤ ├─╴ ╷ │ ╵ │ ┌───┘ └─╴ └─╴ └─┐ │ │ ╶─┼─┼─┐ ╵ ├───╴ ╷ ┌─┐ ╷ ┌─┘ │ ├─╴ ╵ ╵ │ ┌─┘ ┌─┐ └─┘ └─┴─┼─╴ │ │ ╶─┐ ╷ ╵ ╵ ╷ ╵ └─┐ ╶─┐ ╷ │ ╷ │ └───┴─┴─────┴─────┴───┴─┴─┴─┴─┘ La classe Labyrinthe peut maintenant être instanciée, c'est à dire construire des objets labyrinthes (seulement des labyrinthes murés pour l'instant). Afin d'instancier un objet de la classe Labyrinthe de largeur 5 et de hauteur 4 il suffit d'utiliser la syntaxe : mon_laby = Labyrinthe(5,4) Afin d'appliquer la méthode d'un objet il suffit d'utiliser la syntaxe : mon_laby.print() Pour faire référence à un attribut et le modifier, il suffit d'utiliser la syntaxe : mon_laby.nom_attribut = nouvelle_valeur Visualiser une instance à l'aide de la méthode print() un labyrinthe de taille 3×2 avec tous ses murs fermés. En modifiant (en dehors de la classe) les cellules de l'attribut cells, construire un labyrinthe de cette forme :

┌──┬─────┐ │ │ │ │ │ │ └─────┴──┘

L'objectif principal de ces exercices est de générer des labyrinthes parfaits (et rectangulaires). Il existe plusieurs méthodes généralement basées sur la même idée :

• Partir d'un labyrinthe entièrement fermé
• Fermer des murs successivement sans créer plusieurs chemins entre deux cellules
• Arrêter quand toutes les cellules sont atteintes par un unique chemin

Les étapes ci-dessus ne constituent pas entièrement un algorithme car elles manquent de précision. Notamment elles n'indiquent pas comment choisir le mur à enlever. La nature de ce choix peut aboutir à différents algorithmes. Le but de l'exercice suivant est de démontrer que les étapes ci-dessus sont toujours réalisables et aboutissent à un labyrinthe parfait : On se place dans le cadre d'une étape de la stratégie avec une grille séparée par des murs en différentes zones. De plus, chaque zone est parfaiteUne zone d'un labyrinthe est un ensemble de cellules toutes reliées par des chemins. La zone est parfaite si aucun de ses chemins internes n'a de cellule en commun avec un autre. Nous émettons l'hypothèse (H) selon laquelle à chaque étape, la grille est divisée en zones parfaites. Justifier qu'à l'initialisation, l'hypothèse (H) est vérifiée. Expliquer pourquoi si on relie deux zones parfaites limitrophesDeux zones sont limitrophes si elles ont un mur fermé en commun. en ouvrant un mur, la zone obtenue est toujours parfaite Justifier que les itérations s'arrêtent et aboutissent bien à un labyrinthe parfait.

Indice 1

A l'initialisation toutes les zones sont des cellules fermées.

Indice 2

Pour relier deux cellules C (zone 1) et C' (zone 2) par où doit passer un chemin pour les relier ?

Indice 3

Il y a 2 choses à démontrer : l'arrêt (facile) et le caractère parfait du résultat (utiliser la question 2). Sachant maintenant que la stratégie aboutit, nous souhaitons évaluer le nombre d'itérations nécessaires. On souhaite compter le nombre de murs qu'on va devoir ouvrir pour générer un labyrinthe parfait. Pour cela, on commence par compter les murs ouverts dans les zones parfaites de notre grille : Soit Z une zone parfaite possédant n cellules : Si Z est un chemin, exprimer le nombre de murs ouverts en fonction de n. Expliquer pourquoi le résultat ne change pas si la zone parfaite n'est pas un chemin. Soit un labyrinthe parfait rectangulaire de largeur n et de hauteur m. Exprimer en fonction de n et m le nombre de murs ouverts. En conclusion, quel sera le nombre d'étapes nécessaires à la construction d'un labyrinthe parfait ?

Indice 1a

Chaque cellule d'un chemin n'a qu'un mur interne ouvert (sauf le dernier)

Indice 1b

Compter le nombre de murs ouverts avant et après que deux zones fusionnent dans l'algorithme...

Indice 2

On peut le démontrer par récurrence forte sur le nombre n de cellules dans la zone parfaite.

Indice 3

L'algorithme s'arrête quand il a ouvert suffisamment de murs pour arriver à un labyrinthe parfait Précisons l'algorithme précédent : le choix des murs à ouvrir peut se faire de différentes manières. La solution que nous proposons ici est de le faire au hasard, de la manière suivante :

• Partir d'un labyrinthe de largeur n et de hauteur m entièrement fermé. Chacune des n×m cellules est donc une zone.
• A chaque itération on choisit un mur au hasard entre deux zones distinctes puis on l'ouvre pour les fusionner en une nouvelle zone
• Arrêter quand il n'existe plus qu'une seule zone.

Nous allons implémenter cet algorithme dans notre classe Labyrinthe. Pour débugger, il pourra être utile de visualiser les objets avec la numérotation des zones de chaque cellule comme ceci : ┌─────────┬────┬────┬────┐ │ 5 5 │ 2 │ 3 │ 14 │ │ ┌────┴────┴────┤ │ │ 5 │ 7 7 7 │ 14 │ ├────┼──────────────┤ │ │ 10 │ 16 16 16 │ 14 │ ├────┘ ┌────┐ ├────┤ │ 16 16 │ 17 │ 16 │ 19 │ ├────┬────┴────┼────┴────┤ │ 20 │ 22 22 │ 24 24 │ └────┴─────────┴─────────┘ Pour cela, il suffira de préciser en argument une liste (pas un tableau) des numéros de zones comme ceci : mon_laby.print([5,5,2,3,14,...,22,24,24]) Modifier la classe Labyrinthe, de la manière suivante : Pour chacune des cellules (dictionnaires) de l'attribut cells ajouter une clé zone ayant pour valeur le numéro de la zone à laquelle appartient la cellule : {'N':False, 'E':False, 'S':False, 'O':False, 'zone':1} Modifier l'initialisation pour qu'au début la grille compte autant de zones que de cellules. Créer une méthode fusionner(self, i, j, dir) où :

• i et j sont les coordonnées dans la grille de la cellule concernée .
• dir est un caractère parmi 'N', 'E', 'S', 'O' indiquant le mur de la cellule à ouvrir.

Cette méthode devra vérifier que derrière le mur à ouvrir se trouve bien une zone différente. Si ce n'est pas le cas, la méthode ne fait rien et renvoie False. Si la méthode ouvre le mur, elle devra modifier la zone de toutes les cellules de la deuxième zone fusionnée à la première. Créer une méthode generer(self) qui à partir de l'état de départ génère un labyrinthe parfait. Elle créer une pile de de tous les murs (fermés au départ) et les ouvrir un par un à l'aide de la méthode fusionner.

• Pour visualiser les zones dans la méthode on peut utiliser la syntaxe : self.print(self.zones)
• Pour utiliser le hasard : la librairie random permet notamment d'utiliser :

  méthode	description
  randint(a,b)	Renvoie un entier aléatoire entre a et b inclus.
  choice(liste)	Renvoie un élément choisi aléatoirement dans la liste
  shuffle(liste)	Mélange de manière aléatoire la liste (modification)

  Pour plus d'informations voir la documentation.
• Il y a 4 murs par cellule. Modéliser un mur peut se faire à l'aide d'un triplet (i,j,dir) où i,j sont les coordonnées de la cellule et dir une direction parmi N,E,S,O.
• Recalculer les murs limitrophes à mettre dans la pile peut vite devenir compliqué, mais ce n'est pas nécessaire. Au départ, les murs sont tous limitrophes (tous fermés). A chaque étape quand on ouvre un mur, on le dépile. Il ne reste donc à chaque étape que des murs limitrophes. Ne pas oublier de dépiler !
• Concernant l'arrêt de l'algorithme. Y a t'il besoin d'épuiser la pile pour être sûr qu'on a un labyrinthe parfait ou peut-on s'arrêter avant?

Dans cette partie, nous allons utiliser la librairie matplotlib.pyplot afin de tracer graphiquement un labyrinthe généré dans un repère orthogonal. Pour importer la librairie, ajouter en début de fichier : import matplotlib.pyplot as plt Pour tracer une liste brisée de segments [A1A2], [A2A3],...,[An-1An] où les points Ai ont pour coordonnées (xi, yi) (i=1,...,n), on peut utiliser la syntaxe : plt.plot([x1,x2,...,xn],[y1,y2,...,yn]) La figure n'est pas affichée immédiatement. On peut encore tracer plusieurs figures puis pour les afficher : plt.show() import matplotlib.pyplot as plt ... plt.plot([0,1,2],[0,1,0],'r')#couleur rouge plt.plot([1,1],[0,1],'b')#couleur bleue plt.show() Créer une méthode print_plot() qui permet d'afficher un objet Labyrinthe tel que :

• Chaque cellule est un carré de longueur 1
• La cellule dont les coordonnées dans la grille est (0,0) se trouve en haut à gauche

Le résultat devra être similaire à celui obtenu avec la méthode print() : ┌───┬─────┐ │ ╷ ├─╴ ╷ │ │ └─┤ ┌─┴─┤ ├─┐ │ └─╴ │ │ ╵ ╵ ╷ ╶─┤ └─────┴───┘ Affichage avec print() Dans cette partie, nous allons utiliser une librairie JavaScript pour visualiser les labyrinthes générés en Python dans un navigateur web. Cette librairie javaScript rudimentaire permet de réaliser en langages web (html-css-js) des objets simples en 3d (cubes, rectangles, sprites animés) dans une scène, de les positionner (translations, rotations) et d'y déplacer une caméra en gérant les collisions. La scène peut être visualisée par les navigateurs récents (Firefox, Chrome, Edge, pas testé sur Safari), mais tourne (beaucoup) mieux sous Chrome... :/ Ci-dessous, un exemple de scène 3D dans laquelle on peut interagir de la manière suivante :

• déplacer la caméra avec les touches de direction
• orienter la caméra avec les mouvements de la souris
• pour que la souris ne soit pas bloquée par les bords de l'écran :
  • cliquer sur la scène 3d pour capturer le curseur de la souris
  • appuyer sur Echap pour sortir (libérer la curseur)

Télécharger et décompresser dans le dossier de travail l'archive suivante: L'archive est un exemple simple contenant : un fichier html, un fichier javascript, un dossier d'images pour les textures et un dossier contenant la librairie. Editer les fichiers exemple0.html et exemple0.js avec un éditeur du type Notepad++, Sublime Text ou Scite. Les fichiers sont organisés de la manière suivante : Ce fichier, en l'ouvrant avec le navigateur, affichera la scène 3d. Il sert à charger les fichiers 3d-world.css et 3d-world.js de la librairie et le fichier exemple0.js qui réalise la scène de l'exemple : <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"/> <link rel="stylesheet" type="text/css" href="3d/3d-world.css" /> <script src="3d/3d-world.js"></script> </head> ... <script src="exemple0.js"></script> Il définit aussi l'élément html dans lequel sera affiché la scène 3d : <div class="theater"></div> Le fichier javascript exemple0.js réalise une scène basique comprenant un Rectangle (pour le sol), un Cube, deux Sprite, une Skybox pour le ciel et une Camera. Le but de cette partie sera de modifier ce fichier pour modéliser un labyrinthe généré précédemment. Voici une courte descriptions des objets et de leur utilisation :

Objet	Description
Environment3d(div)	Objet principal auquel on ajoutera tous les objets de la scène par la méthode addObject(). l'argument div est un élement HTML dans lequel sera visualisé la scène.
Rectangle(x,y,z,w,h,texture)	Rectangle vertical dont le coin bas-gauche est positionné à (x,y,z) de largeur w et longeur h. La texture peut être l'url d'une image ou un objet d'attributs-valeurs de CSS.
Box(x,y,z,w, h, d, texture)	Pavé droit dont le point de référence est le coin en bas à droite de la face visible. d est la profondeur. La texture peut être la même pour chaque face (même syntaxe que pour le rectangle).
Cube(x,y,z,h,texture)	Même résultat que Box(x,y,z,h,h,h,texture)
Sprite(x,y,z,w,h, img,   w_img, h_img, dt, m, n)	img est l'url d'un image de type sprite organisée en motifs de largeur w_img et hauteur h_img sur m lignes et n colonnes. dt est l'intervalle de temps en ms entre deux frames. Pour un sprite non animé, ignorer les derniers arguments.
Camera(x,y,z,rx, ry,rz)	Caméra fixe pouvant être activée via sa méthode activate(). x,y,z sont ses coordonnées et rx,ry,rz les angles de rotations pour l'orienter (facultatifs, la direction par défaut est l'axe z).
Perso(x,y,z,h,controls)	Personnage à la première personne. C'est en fait une caméra mobile.x,y,z sont les coordonnées du point le plus bas. La hauteur h est la hauteur du point de vue. Les contrôles par défaut sont les flèches de directions et la souris.

• Pour être visualisé, un object obj doit être ajouté à l'environnement via la méthode addObject(Object)
• Par défaut le centre de rotation d'un objet Rectangleest son centre de gravité. Il est possible de la changer avec la méthode setTransformOrigin(xo, yo). Les arguments peuvent être des entiers (unité pixel) ou les mots-clés left, right, center pour xo et bottom, top, center pour yo.
• De même pour les objets Box et Cube. On peut ajouter un 3ème argument zo, un entier en pixels.
• Un objet Camera ou Perso, pour être le point de vue principal, doit être activé par la méthode activate()
• Un object Perso se déplace sur un plan horizontal par défaut (mode 'fps'). Il peut se déplacer librement dans l'espace avec la méthode setMode('freecam').
• Dans les objets Box et Cube, on peut préciser les textures de chaque face de la manière suivante : {'top': txT, 'bottom':txB, 'left':txL,
      'right':false, 'front':false, 'back':false} Une valeur false permet d'omettre une face.

Pour des exemples plus précis, éditer le fichier exemple0.js. Chaque commande est commentée et des variables aux noms explicites sont utilisées.

• Dupliquer et renommer les fichiers exemple0.html et exemple0.js en fichiers labyrinthe.html. Changer également l'url du script dans le fichier html.
• Générer un labyrinthe en Python et recopier l'attribut cells pour l'utiliser dans labyrinthe.js
• Construire les murs du labyrinthe à parcourir à l'aide des objets Box. Le choix est laissé libre dans les textures utilisées. Les dimensions des couloirs et la hauteur des murs devront être en cohérence avec la hauteur de la caméra et les dimensions du sol.

• Les objets JavaScript sont proches du dictionnaire Python. On peut copier-coller directement l'attribut cells du labyrinthe généré en Python. Attention cependant, en Python les booléens sont True,False et en JavaScript true, false
• Commencer par un petit labyrinthe. La librairie n'est pas adaptée pour afficher un grand nombre d'objets 3D...
• Utiliser des objets Box pour modéliser les murs. Tenir compte de l'épaisseur des murs pour les positions
• Utiliser des variables bien nommées (ex : w_cell , h_cell , d_cell , ep_mur , x0_laby , y0_laby , z0_laby) plutôt que des valeurs calculées...