Générateur graphique de labyrinthe sous Python

2016/2017          

TERMINALE S6                                                            

GÉNÉRATEUR DE         LABYRINTHE

[pic 1]

LYCEE GENERAL ET TECHNOLOGIQUE JEAN BAPTISTE SAY

11 BIS RUE D’AUTEUIL

75016 PARIS

FRANCE

SOMMAIRE

Sommaire…………………………………………………………………………………..………… 2

Introduction............................................................................................................................................3

I- Qu’est-ce qu’un labyrinthe……………………………………………………......….…..…………3

1. Définition....................................................................................................................................3

1. Labyrinthe parfait………………………………………………………….…………..3    
2.  Labyrinthe imparfait…………………………………………………………………..4                                                                                                                                                

1.  L’algorithme exploité……………………………………………….………………….……. 4                                            

II. Le programme détaillé…………………....…………………...………………...……………….…4

1.  La définition des fonctions…………………………………………………...………….……4
2.  Les fonctions.............................................................................................................................5    

1) Fonction d’ouverture entre deux cellules………………………………………….…... 5                            2) La fonction de l’exploration exhaustive...........................................................................6                 3) La fonction dessin…........................................................................................................8        

Conclusion………………………………………………………………………………………..…....9

Index………………………………………………………………………………………………….10

Lorsque nous avons choisi notre thème de projet sur celui des labyrinthes, nous avons tout de suite chercher à savoir sur quoi cela pourrait nous amener. Nous étions alors partagés entre deux idées: celle qui porterait le projet vers un générateur de labyrinthe et l’autre plutôt vers sa résolution. Nous avons unanimement émis le souhait de vouloir nous diriger vers le générateur de labyrinthe, sûrement pour l’idée de créativité qui en découlait.  

1. Qu’est-ce qu’un labyrinthe ?

Une fois notre thème de projet décidé et notre ligne directrice choisie il a fallu penser à la partie la plus importante : l’algorithmie. Pour nous aider à démarrer nous voulions partir de notre propre définition du labyrinthe mais rapidement nous nous sommes rendus compte que sa définition ne nous était pas claire, et ce malgré que son concept soit notoirement connu.

1. Définition

D’après le dictionnaire, un labyrinthe est un édifice composé d'un grand nombre de pièces disposées de telle manière qu'on en trouve que très difficilement l'issue. Si cette première définition permet une compréhension du concept, elle nous est reste encore trop spécifique pour l'élaboration d'un programme.

Un labyrinthe est plus précisément, une surface connexe (chaque partie de la surface est reliée à une autre). Ces surfaces peuvent avoir des topologies différentes : simple, ou comportant des anneaux ou îlots. La topologie renvoie ainsi à la caractéristique primaire d’un labyrinthe : parfait ou imparfait.

1. Labyrinthe parfait

Un labyrinthe parfait correspond à un chemin unique, il n’existe qu’une solution directe.

1. Labyrinthe imparfait

Un labyrinthe imparfait correspond à un chemin se recoupant pouvant éventuellement isoler des pièces.

Une fois l’esprit plus clair et surtout la reconnaissance évidente, que pourtant que nous avions omise, de la différence entre labyrinthe parfaits et imparfaits, nous avons affiné la direction de notre ligne déjà directrice : générer un labyrinthe oui, mais un labyrinthe parfait.

1.  L’algorithme exploité

        Lors de nos recherches de la définition de labyrinthe, nous avons remarqué que la génération de labyrinthe avait été étudié sous tous ses aspects mathématiques, ce qui a donné naissance à différentes méthodes pour en générer. Nous avons donc compris qu’il nous faudrait en adopter une et en créer l’algorithme qui lui correspondrait. Bien qu’il en existe d’autres, une a particulièrement retenu notre attention (parmi ceux qui génèrent des labyrinthes parfaits, bien entendu) : la méthode de l’exploration exhaustive dont j’expliquerai le principe lors de la description détaillé du programme.

1. Le programme détaillé

1. La définition des fonctions

Pour penser le labyrinthe nous sommes partis sur une logique de tableau à double dimension qui se présenterait sous forme de grillage.

Chaque case représente une salle, chaque ligne horizontale et verticale représente un mur. Le but de notre programme est d’abattre ces murs le plus aléatoirement possible afin d’aboutir finalement à un labyrinthe parfait tout aussi aléatoire.

Pour créer ce programme nous avons réfléchi logiquement à 5 étapes :

1. La définition des entrées-sorties,
2. La fonction qui permet l’ouverture entre 2 cellules adjacentes,
3. La fonction qui définit l’exploration exhaustive, soit celle qui définit le labyrinthe,
4. Celle qui trace le labyrinthe dans la console,
5. La fonction qui regroupe toutes les autres et qui construit le labyrinthe à partir des vœux de l’utilisateur,
6. Enfin tout adapter à une interface graphique Tkinter.

Je me suis personnellement occupée de la fonction qui permet l’ouverture entre deux cases (2), celle qui définit l’exploration exhaustive (3) et enfin celle qui trace le labyrinthe dans la console (4).

...