Wiki du LAMA (UMR 5127) - Contributions [fr]

VISI301 CMI : projet de recherche et développement

2021-11-19T10:42:10Z

Theodet : Typo et modification mineure de lien GitHub

* Cours du semestre 3 du parcours CMI informatique (licence info) et, jusqu'en 2021, CMI mathématique (licence math).

* Responsables pour 2021--2022 : Pierre Hyvernat et Jacques-Olivier Lachaud

= Descriptif =

L'objectif de ce cours est de développer des compétences dans différents domaines de l'algorithmique et la programmation Python, au travers du développement d'un jeu. Les étudiants découvrent aussi les outils modernes de développement collaboratif (gestionnaire de version, pull requests, intégration continue). 8 séances sont prévues dans l'EDT mais il est attendu du travail personnel supplémentaire. Les projets se font par binôme ou trinôme. Le travail est évalué sur la base d'une démo et du rendu sur le serveur GitHub.

Les étudiants rencontreront à intervalle régulier leurs enseignants tuteurs pour le projet afin de rendre compte de leur avancée dans leur projet (démarche similaire à celle des Travaux Personnels Encadrés). Le type de jeu choisi est laissé volontairement assez libre, de manière à ce que les étudiants développent leur imagination ainsi que leur capacités de réflexion et discussion collaboratives (brain-storming). Ils pourront aussi faire des recherches pour affiner leur modèle de jeu choisi.

= Objectifs =

L'idée est de réaliser un jeu en python. L'objectif est de finir avec un jeu simple mais fonctionnel. (Par exemple, il est préférable de n'avoir qu'un seul niveau à avoir 99 niveau si le personnage ne peut pas encore se déplacer...)

Voici quelques exemples de jeux dont vous pouvez vous inspirer :
* jeu en mode "tour par tour" sur une grille discrète
** [http://www.ehttps://en.wikipedia.org/wiki/NetHack nethack]
** [https://en.wikipedia.org/wiki/Sokoban sokoban]
** [https://en.wikipedia.org/wiki/Boulder_Dash boulder dash]
** pacman

* jeu en mode "temps réel" avec des coordonnées flottantes
** [https://en.wikipedia.org/wiki/XPilot xpilot]
** [https://en.wikipedia.org/wiki/Breakout_clone casse briques]
** agar.io

* [https://en.wikipedia.org/wiki/Colossal_Cave_Adventure jeu d'aventure en mode "textuel"]

Le type de jeu que vous choisirez aura des conséquences sur le type de code que vous écrirez. Attention, les jeux "textuels" nécessitent, encore plus que les autres, une histoire bien racontée !

Quel que soit votre choix, nous donnerons probablement des consignes supplémentaires.

Si vous ne trouvez pas d'idée, nous imposerons un jeu du premier type avec les consignes suivantes :
* la carte est représenté par une ou plusieurs grilles de jeu,
* un ou plusieurs personnages se déplacent dans la grille (le(s) joueur(s), le(s) monstre(s)),
* actions en tour par tour,
* des niveaux générés aléatoirement.

Cela permettra de développer pas mal d'aspects différents de l'algorithmique et de la programmation:
* structures de données pour représenter les plans de jeu, les personnages, les objets éventuels
* algorithmes de graphes pour générer des niveaux labyrinthiques
* programmation graphique pour afficher le décor et les éléments de jeu
* interfaces homme-machine pour diriger le jeu
* un peu d'intelligence artificielle pour faire jouer les personnages non joueurs (monstres, ennemis, amis ).
* entrées/sorties pour sauvegarder le jeu/ les niveaux

= Ressources =

On pourra se baser sur [https://www.pygame.org/news pygame] , une bibliothèque Python conçue pour faire des jeux.

* [https://inventwithpython.com/pygame/chapters/ chapitres ]
* [https://inventwithpython.com/makinggames.pdf Livre]

Cela permet de faire facilement:
* les boucles d'interactions
* les affichages graphiques
* la gestion du clavier ou de la souris.

= Contraintes =

* le projet sera fait en python (plus simple, développement plus rapide)
* les binômes (ou trinôme) seront tirés aléatoirement pour mélanger les promotions (CMI-math et CMI-info)
* vous utiliserez une plateforme de développement collaboratif [https://www.github.com Github]

= Critères d'évaluation =

* Conception du jeu, réflexion initiale, originalité du jeu
* Réalisation, fluidité, ressenti général
* Intérêt du jeu, jouabilité, progressivité, richesse
* Méthodologie, régularité de l'avancement, communication avec les tuteurs
* Rendu final, doc utilisateur, packaging, installation
* Autonomie, recherches personnelles, montée en compétence

= résumé des commandes git de base =
configuration (une seule fois sur votre machine)
------------------------------------------------

$ git config --global user.name "PRENOM NOM"
$ git config --global user.email "MON@ADRESSE.EMAIL"

information (à utiliser sans modération)
----------------------------------------

$ git status
affiche l'état du dépot (en fait, de la branche courante) : nouveaux
fichiers, fichiers modifiés, etc.

$ git log
affiche la liste des commits du dépot (en fait, de la branche
courante)

$ git diff
ou
$ git diff FICHIERS
affiche les différences entre le dépot actuel et le dernier commit
(éventuellement, seulement pour les fichiers donnés en argument)

sauvegarde des modifications ("commit")
---------------------------------------

$ git add FICHIERS
demande à git de gérer les fichiers FICHIERS
(On peut donner plusieurs fichiers en même temps, ou utiliser les
motifs du shell comme "git add *.py")
ATTENTION : le fichier n'est pas sauvegardé par cette commande

$ git commit
ou plus souvent
$ git commit -a -m "MESSAGE"
enregistre l'état du dépot (en fait, de la branche courante)
- l'option '-a' permet d'enregistrer __tous__ les fichiers
modifiés. Sans elle, il faut faire "git add FICHIERS" avant le
"git commit"
ATTENTION, les nouveaux fichiers ne sont pas ajoutés par l'option
'-a', il faut impérativement faire "git add FICHIERS" pour les
nouveaux fichiers.
- l'option '-m "MESSAGE"' permet de donner une description de ce
commit
Sans cette option, un éditeur de texte (probablement vi) sera
lancé pour taper la description du commit. (Si vous ne savez pas
utiliser vi, vous pouvez configurer un autre éditeur avec
$ git config --global core.editor "MON_EDITEUR_FAVORI"
)

communication avec un autre dépot
---------------------------------

$ git pull REMOTE
ou
$ git pull
récupère l'état du dépot (en fait de la branche) depuis REMOTE
Si un dépot distant est configuré (automatiquement si vous avez
récupéré le dépot avec "git clone URL"), vous pouvez omettre REMOTE

$ git push REMOTE
ou
$ git push
envoie l'état du dépot (en fait de la branche) vers REMOTE.
Si un dépot distant est configuré (automatiquement si vous avez
récupéré le dépot avec "git clone URL"), vous pouvez omettre REMOTE

importer un nouveau dépot ("fork", "clone")
-------------------------------------------
$ git clone URL
récupère un dépot git dans un nouveau répertoire dans le répertoire
courant.
Typiquement, URL est récupérée sur github ("Clone or download")

revenir en arrière
------------------

$ git checkout HASH
remet le dépot dans l'état correspondant au commit de hash HASH
Le hash d'un commit est affiché par "git log". Ça ressemble à
ddca8e4f15958e4f5151c5e23c4d673a132334b2
(il faut donner au moins les 4 premiers caractères du hash...)

ATTENTION, ceci n'est possible que si vous n'avez aucun changement non
enregistré.

ATTENTION, il est déconseillé de modifier les fichiers lorsque le
dépot est dans un état antérieur. Au besoin, vous pouvez faire
$ git reset --hard
pour remettre votre dépot dans l'état exact du commit correspondant.

$ git checkout master
ou
$ git checkout -
remet le dépot dans l'état final

Utilisation typique
-------------------

0/ création d'un dépot vide depuis github ("New" depuis la page
"Repositories" de votre compte github)

ou bien

0'/ récupération d'un dépot existant avec "git clone URL"

Lors d'une séance de travail :

1/ synchronisation pour récupérer les changement du dépot central (sur
github)
$ git pull
Normalement, il n'y aura jamais de conflit à cette étape.

2/ visualiser les nouveautés avec
$ git log

3/ travail, modification de fichiers, création de fichiers, etc.

4/ lorsque vos modifications fonctionnent et sont finies :
$ git add NOUVEAUX_FICHIERS
$ git commit -a -m "MESSAGE"

5/ sauvegarde sur le dépot central
$ git push

5/ en cas de conflit (parce que quelqu'un a modifié le dépot central
entre temps), résolution du conflit et nouveau commit :
$ git commit -a -m "RESOLUTION CONFLIT"
$ git push

Pour aller plus loin
--------------------

Lorsque vous maitrisez les commandes et concepts précédents, vous pouvez
vous renseigner sur

- les "branches" qui permettent d'avoir plusieurs versions du dépots
"en parallèle"

- les "remotes" qui permettent de communiquer avec plusieurs dépots
lors des "git pull" et "git push"

- "git stash" qui permet de mettre de coté des modification
momentanément

- les "pull-requests", qui permettent d'avoir plusieurs dépots
principaux, et d'échanger des modifications entre eux. (Ceci est un
mécanisme propre à github)

= Equipes (2021-2022) =

* Paul AUBRY, Alexandre DESBOS, Nolan SANMARTI
* Andrien MONTMAYEUR, Maxent BERNIER, Baptiste GRIVA
* Théo CONNETABLE, Emilien BOITOUZET, Lucas POLICASTRO

= Sujets réalisés (2020-2021) =

Responsables pour 2020--2021 : Jacques-Olivier Lachaud et Pierre Hyvernat

* Théo GUESDON, Evan L'HUISSIER, et Aurélien PARDO [https://github.com/Kroklethon/TotalCMIWar Total CMI War]
* Louise BOLLARD, Romain NEGRO et Julien DUCREY [https://github.com/romain22222/PROJET-CMI-LABYRINTHE Labyrinthe]
* Romain PAJEAN, Hugo REY et Simon MARSAN [https://github.com/Hearstgo/LostColor LostColor]
* Juliette NEYRAT, Simon PICHENOT et Léa DEVAUX [https://github.com/JediSim/color_mario Color Mario]
* Simon LEONARD, Florian DUFAURE, Reham NASSIF [https://github.com/Matows/slowed Slow motion]

= Sujets réalisés (2019-2020) =

Responsables pour 2019--2020 : Jacques-Olivier Lachaud et Pierre Hyvernat

* Loïc Dornel et Anne Perez [https://github.com/CreeperStone72/visi301 Le donjon d'Azorius]
* Yohann Thepault et Ewan Rakotoanosy [https://github.com/ythepaut/visi301_univdefender UnivDefender]
* Lucas Chardonnet et François D'alayer [https://github.com/LucCha42/VISI301 GooDoo]
* Christophe Carmagnac et Martin Rialhe-Badet [https://github.com/445654/Escape Escape]
* Romain THEODET et Sarah Crumiere [https://github.com/RomainTHD/CruCru.io CruCru.io]

= Sujets réalisés (2018-2019) =

Responsables pour 2018--2019 : Jacques-Olivier Lachaud et Pierre Hyvernat

* Rémi Bouvier et Nils Ruet [https://github.com/NilsRuet/VISI301 SnowForest]
* Tristan Porteries et Robin Wagner [https://github.com/panzergame/CrazyClass Crazy Class]

= Sujets réalisés (2017-2018) =

Responsables pour 2017--2018 : Jacques-Olivier Lachaud et Pierre Hyvernat

* Ambroise Decouttère et Raphaël Tournafond, [https://github.com/Ambrdctr/MazeRunner MazeRunner]

Génération et résolution de labyrinthes II

2021-11-19T10:40:38Z

Theodet : Changement d'URL GitHub

__FORCETOC__[[Fichier:labyrinthe_photo.png|vignette|300px|Exemple de labyrinthe généré et résolu. En rouge foncé, l'entrée. En vert, la sortie. En bleu, le chemin entre le départ et l'arrivée. En rouge clair, les cellules visitées lors de la résolution.|alt="Labyrinthe"]]

L'objectif de ce projet est de générer des labyrinthes aussi grands et complexes que possible.
Nous allons voir comment toujours avoir un chemin entre l'entrée et la sortie, et comment trouver la sortie une fois notre labyrinthe généré.

== Représentation ==

=== Propriétés ===

Tout d'abord, de manière assez informelle, un labyrinthe est une grille de cellules reliées, ou non, entre elles.

Deux cellules sont reliées entre elles par une '''porte''', ou séparées par un '''mur'''.

Tout labyrinthe a '''une entrée''' et '''une sortie''', et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est '''unique'''.
Nous verrons cependant que ce dernier point peut varier, et introduire de nouvelles formes de labyrinthe.

=== Modélisation en graphe ===

En théorie des graphes, un graphe est un ensemble de '''points''' (ou nœuds ou sommets) reliés ensemble par des '''lignes''' (ou liens ou arêtes).

[[Fichier:graphe_cyclique.png|vignette|left|300px|Exemple de graphe connexe cyclique non orienté|alt=Graphe cyclique]]

Un graphe peut être dit '''connexe''' (d'un seul tenant) ou '''non connexe''' (en plusieurs morceaux).

Un graphe peut aussi être '''cyclique''' s'il existe au moins un chemin formant une boucle ou '''acyclique'''.

Enfin, un graphe peut être '''orienté''' (si les arêtes sont à sens unique) ou '''non orienté'''.

[[Fichier:Arbre.PNG|vignette|left|300px|Exemple d'arbre|alt=Arbre]]

Un '''arbre''' est un graphe connexe, acyclique et non orienté.

Chaque feuille n'est connectée qu'à un seul autre nœud, et chaque sommet interne relie au moins deux nœuds.

[[Fichier:labyrinthe_avec_arbre.png|vignette|right|300px|Exemple de labyrinthe avec son arbre. Pour plus de simplicité, à chaque nœud est attribué une position.|alt=Labyrinthe avec arbre]]

En plaçant un sommet sur chaque cellule de notre labyrinthe, et en reliant deux sommets par une arête si leurs cellules sont séparées par une porte, il devient possible de dessiner un arbre à partir de n'importe quel labyrinthe.

Sur notre graphe, un arête est donc un passage dans notre labyrinthe.

== Génération ==

Un labyrinthe rectangulaire de largeur <math> L </math> et de hauteur <math> H </math> contient exactement <math>L \times H - 1</math> portes.

Du point de vue du graphe, il y a donc <math>L \times H - 1</math> arêtes.

Maintenant, comment répartir toutes ces portes de manière à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?

De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal.
Chaque algorithme est différent et produit des labyrinthes visuellement différents.

=== Parcours en profondeur ===

[[Fichier:recursive_backtracker.gif|vignette|left|500px|Illustration du parcours en profondeur|alt=Parcours en profondeur]]

L'algorithme du parcours en profondeur (ou "recursive backtracker" en anglais) commence sur une cellule aléatoire dans le labyrinthe.

Il suffit ensuite de se diriger dans une direction aléatoire et de casse le mur face à soi, tout en marquant la cellule précédente comme visitée.

Lorsque plus aucune direction n'est disponible, l'algorithme "remonte" à la position précédente : c'est le backtracking.

[[Fichier:pile.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

Une implémentation possible et pertinente pour sauvegarder l'historique des positions est la '''pile'''.

Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.

Une pile est donc principalement composée de 2 méthodes :
* <code>push : elt -> ∅</code> : ajoute un élément à la pile
* <code>pop : ∅ -> elt</code> : retourne le sommet de notre pile en retirant cet élément

Dans l'implémentation de la pile proposée, une erreur sera levée si la méthode méthode <code>pop</code> est appelée sur une pile vide.

=== Kruskal ===

[[Fichier:kruskal.gif|vignette|left|500px|Illustration de l'algorithme de Kruskal.|alt=Kruskal]]

Alors que le parcours en profondeur s'intéressait aux sommets, l'algorithme de Kruskal s'applique lui sur les arêtes.

Tout d'abord, chaque cellule se voit attributée un identifiant unique, dans un labyrinthe empli de murs.

Un mur aléatoire est ensuite choisi. Si les cellules séparées par ce mur ont des identifiants différents, le même identifiant leur sera associé, et il faudra alors abattre le mur.

Sinon, un autre mur sera choisi.

[[Fichier:union_find.png|vignette|300px|Représentation d'une structure Union-Find avec find(a,b) et find(b,c).|alt=Union-Find]]

Pour mettre en œuvre cet algorithme, la structure la plus adaptée à utiliser est une structure de données appelée '''Union-Find''', qui permet de mettre en relation des éléments partageant un même représentant (ou un même identifiant).

Il existe plusieurs variantes d'Union-Find, dont notamment la compression de chemin, qui permet de n'avoir qu'un ou deux éléments à parcourir pour obtenir le représentant d'un élément.

Union-Find fonctionne comme un arbre. 'a' a un représentant 'A', etc..., qui lui même a un représentant '<math>\alpha</math>', qui est son propre représentant.

Union-Find est composé de deux méthodes :
* <code>union : a, b -> ∅</code> : associe à 'a' et 'b' le même représentant, par exemple 'A' le représentant de 'a'
* <code>find : a -> r</code> : tant que l'élément n'est pas son propre représentant, <code>find</code> est appliqué au représentant de l'élément. On commence donc par find(a), puis find(A) (si 'A' est le représentant de 'a'), etc... La méthode de la compression de chemin permet d'éviter trop de récursivité en écrivant : représentant de 'a' = 'r'.

Pour les plus curieux, cette structure de données est décrite plus en détails dans un cours d'INFO602 qu'il est possible de retrouver [https://www.lama.univ-savoie.fr/mediawiki/images/f/fa/INFO602-Lesson-3.pdf ici].

=== Labyrinthes cycliques ===

Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.

Cependant, certains algorithmes de résolution n'adopteront pas le même comportement, voire ne fonctionneront même plus du tout.

=== Comparaison ===

Il est possible de comparer un labyrinthe généré avec l'algorithme du parcours en profondeur à un labyrinthe généré avec l'algorithme de Kruskal. 
Alors que ces deux algorithmes n'ont bien tous les deux qu'une unique solution, ils apparaissent néanmoins différents visuellement, et adoptent chacun leur propre structure.

[[Fichier:recursive_backtracker_comparaison.png|vignette|left|500px|Parcours en profondeur. Notons la "netteté" des chemins.|alt=Parcours en profondeur]]
[[Fichier:kruskal_comparaison.png|vignette|right|500px|Algorithme de Kruskal. Les murs de taille 1 sont bien plus fréquents.|alt=Kruskal]]

== Résolution ==

Il existe là encore de nombreux algorithmes de résolution de labyrinthes, plus ou moins efficaces, et surtout ne fonctionnant pas tous dans les mêmes conditions.

=== Parcours en profondeur ===

Cet algorithme est quasiment identique à celui du parcours en profondeur pour la génération.

Il est très efficace et trouvera une solution en minimisant le nombre de cases visitées.

Il s'adapte aux labyrinthes cycliques. En cas de boucle, il ne fera pas la boucle vu que l'intersection a déjà été visitées, il reviendra sur ses pas.

Il s'adapte aux labyrinthes sans solution. En effet, s'il n'y a pas de sortie, il va revenir à sa position de départ sans position précédente (pile vide) et en ayant parcouru toutes les cases.

=== Mur droit ===

Cet algorithme va suivre de la main droite le mur de droite.

Il est relativement inefficace, et va visiter un grand nombre de cases.

Il s'adapte assez mal aux labyrinthes cycliques. En effet, si la sortie n'est pas dans la même boucle que l'entrée, il ne la trouvera jamais.

Il ne s'adapte pas aux labyrinthes sans solution, et fera le tour de la grille à l'infini.

[[Fichier:labyrinthe_exp_exhaust.png|vignette|left|500px|Labyrinthe résolu en utilisant le parcours en profondeur. 660 cellules visitées, 1179 déplacements, chemin de 142 cellules.|alt=Parcours en profondeur]]
[[Fichier:labyrinthe_right_hand.png|vignette|right|500px|Labyrinthe résolu en utilisant le mur droit. 1068 cellules visitées, 1995 déplacements, chemin de 142 cellules.|alt=Mur droit]]

On remarquera que des deux algorithmes, celui du mur droit explorera toutes les cellules situées en dessous du chemin optimal. Il sera donc plus efficace lorsque le chemin de solution est vers le bas de la grille.

== Bilan personnel ==

Ce projet m'a permis de découvrir plusieurs structures de données qui, avec plusieurs années de recul, m'ont réellement été utiles.

J'ai aussi pu me familiariser avec Tkinter, avec la programmation orientée objets en Python (notamment héritage et méthodes statiques) et avec le multithreading, le projet ayant été pensé et codé en parallèle avant d'être entièrement refait plus "monolithique" une semaine avant l'oral.

J'ai aussi pu comprendre la complexité mathématique derrière un labyrinthe, et aborder certains aspects des graphes.

Pour résumer, ce projet a vraiment pris tout son sens en L3, où certains concepts m'ont enfin été expliqués et où j'ai enfin pu avoir le recul nécessaire pour saisir l'essence même de la problématique.

== Code source ==

Le code source est disponible sur Github à [https://github.com/RomainTHD/Labyrinthe_VISI201 cette adresse]. N'hésitez pas à jeter un œil aux autres projets en cours 😉

Il suffit d'avoir installé Python 3 et Tkinter.

== Sources et liens utiles ==

Génération
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li>
</ul>

Résolution
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li>
</ul>

Structures de données
<ul>
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li>
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li>
</ul>

Python
<ul>
<li> [https://docs.python.org/3.6/reference/datamodel.html Classes et types de variables personnalisés (en)] </li>
<li> [http://effbot.org/tkinterbook/canvas.htm Canvas Tkinter (en)] </li>
</ul>

Génération et résolution de labyrinthes II

2021-04-09T20:23:27Z

Theodet :

__FORCETOC__[[Fichier:labyrinthe_photo.png|vignette|300px|Exemple de labyrinthe généré et résolu. En rouge foncé, l'entrée. En vert, la sortie. En bleu, le chemin entre le départ et l'arrivée. En rouge clair, les cellules visitées lors de la résolution.|alt="Labyrinthe"]]

L'objectif de ce projet est de générer des labyrinthes aussi grands et complexes que possible.
Nous allons voir comment toujours avoir un chemin entre l'entrée et la sortie, et comment trouver la sortie une fois notre labyrinthe généré.

== Représentation ==

=== Propriétés ===

Tout d'abord, de manière assez informelle, un labyrinthe est une grille de cellules reliées, ou non, entre elles.

Deux cellules sont reliées entre elles par une '''porte''', ou séparées par un '''mur'''.

Tout labyrinthe a '''une entrée''' et '''une sortie''', et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est '''unique'''.
Nous verrons cependant que ce dernier point peut varier, et introduire de nouvelles formes de labyrinthe.

=== Modélisation en graphe ===

En théorie des graphes, un graphe est un ensemble de '''points''' (ou nœuds ou sommets) reliés ensemble par des '''lignes''' (ou liens ou arêtes).

[[Fichier:graphe_cyclique.png|vignette|left|300px|Exemple de graphe connexe cyclique non orienté|alt=Graphe cyclique]]

Un graphe peut être dit '''connexe''' (d'un seul tenant) ou '''non connexe''' (en plusieurs morceaux).

Un graphe peut aussi être '''cyclique''' s'il existe au moins un chemin formant une boucle ou '''acyclique'''.

Enfin, un graphe peut être '''orienté''' (si les arêtes sont à sens unique) ou '''non orienté'''.

[[Fichier:Arbre.PNG|vignette|left|300px|Exemple d'arbre|alt=Arbre]]

Un '''arbre''' est un graphe connexe, acyclique et non orienté.

Chaque feuille n'est connectée qu'à un seul autre nœud, et chaque sommet interne relie au moins deux nœuds.

[[Fichier:labyrinthe_avec_arbre.png|vignette|right|300px|Exemple de labyrinthe avec son arbre. Pour plus de simplicité, à chaque nœud est attribué une position.|alt=Labyrinthe avec arbre]]

En plaçant un sommet sur chaque cellule de notre labyrinthe, et en reliant deux sommets par une arête si leurs cellules sont séparées par une porte, il devient possible de dessiner un arbre à partir de n'importe quel labyrinthe.

Sur notre graphe, un arête est donc un passage dans notre labyrinthe.

== Génération ==

Un labyrinthe rectangulaire de largeur <math> L </math> et de hauteur <math> H </math> contient exactement <math>L \times H - 1</math> portes.

Du point de vue du graphe, il y a donc <math>L \times H - 1</math> arêtes.

Maintenant, comment répartir toutes ces portes de manière à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?

De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal.
Chaque algorithme est différent et produit des labyrinthes visuellement différents.

=== Parcours en profondeur ===

[[Fichier:recursive_backtracker.gif|vignette|left|500px|Illustration du parcours en profondeur|alt=Parcours en profondeur]]

L'algorithme du parcours en profondeur (ou "recursive backtracker" en anglais) commence sur une cellule aléatoire dans le labyrinthe.

Il suffit ensuite de se diriger dans une direction aléatoire et de casse le mur face à soi, tout en marquant la cellule précédente comme visitée.

Lorsque plus aucune direction n'est disponible, l'algorithme "remonte" à la position précédente : c'est le backtracking.

[[Fichier:pile.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

Une implémentation possible et pertinente pour sauvegarder l'historique des positions est la '''pile'''.

Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.

Une pile est donc principalement composée de 2 méthodes :
* <code>push : elt -> ∅</code> : ajoute un élément à la pile
* <code>pop : ∅ -> elt</code> : retourne le sommet de notre pile en retirant cet élément

Dans l'implémentation de la pile proposée, une erreur sera levée si la méthode méthode <code>pop</code> est appelée sur une pile vide.

=== Kruskal ===

[[Fichier:kruskal.gif|vignette|left|500px|Illustration de l'algorithme de Kruskal.|alt=Kruskal]]

Alors que le parcours en profondeur s'intéressait aux sommets, l'algorithme de Kruskal s'applique lui sur les arêtes.

Tout d'abord, chaque cellule se voit attributée un identifiant unique, dans un labyrinthe empli de murs.

Un mur aléatoire est ensuite choisi. Si les cellules séparées par ce mur ont des identifiants différents, le même identifiant leur sera associé, et il faudra alors abattre le mur.

Sinon, un autre mur sera choisi.

[[Fichier:union_find.png|vignette|300px|Représentation d'une structure Union-Find avec find(a,b) et find(b,c).|alt=Union-Find]]

Pour mettre en œuvre cet algorithme, la structure la plus adaptée à utiliser est une structure de données appelée '''Union-Find''', qui permet de mettre en relation des éléments partageant un même représentant (ou un même identifiant).

Il existe plusieurs variantes d'Union-Find, dont notamment la compression de chemin, qui permet de n'avoir qu'un ou deux éléments à parcourir pour obtenir le représentant d'un élément.

Union-Find fonctionne comme un arbre. 'a' a un représentant 'A', etc..., qui lui même a un représentant '<math>\alpha</math>', qui est son propre représentant.

Union-Find est composé de deux méthodes :
* <code>union : a, b -> ∅</code> : associe à 'a' et 'b' le même représentant, par exemple 'A' le représentant de 'a'
* <code>find : a -> r</code> : tant que l'élément n'est pas son propre représentant, <code>find</code> est appliqué au représentant de l'élément. On commence donc par find(a), puis find(A) (si 'A' est le représentant de 'a'), etc... La méthode de la compression de chemin permet d'éviter trop de récursivité en écrivant : représentant de 'a' = 'r'.

Pour les plus curieux, cette structure de données est décrite plus en détails dans un cours d'INFO602 qu'il est possible de retrouver [https://www.lama.univ-savoie.fr/mediawiki/images/f/fa/INFO602-Lesson-3.pdf ici].

=== Labyrinthes cycliques ===

Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.

Cependant, certains algorithmes de résolution n'adopteront pas le même comportement, voire ne fonctionneront même plus du tout.

=== Comparaison ===

Il est possible de comparer un labyrinthe généré avec l'algorithme du parcours en profondeur à un labyrinthe généré avec l'algorithme de Kruskal. 
Alors que ces deux algorithmes n'ont bien tous les deux qu'une unique solution, ils apparaissent néanmoins différents visuellement, et adoptent chacun leur propre structure.

[[Fichier:recursive_backtracker_comparaison.png|vignette|left|500px|Parcours en profondeur. Notons la "netteté" des chemins.|alt=Parcours en profondeur]]
[[Fichier:kruskal_comparaison.png|vignette|right|500px|Algorithme de Kruskal. Les murs de taille 1 sont bien plus fréquents.|alt=Kruskal]]

== Résolution ==

Il existe là encore de nombreux algorithmes de résolution de labyrinthes, plus ou moins efficaces, et surtout ne fonctionnant pas tous dans les mêmes conditions.

=== Parcours en profondeur ===

Cet algorithme est quasiment identique à celui du parcours en profondeur pour la génération.

Il est très efficace et trouvera une solution en minimisant le nombre de cases visitées.

Il s'adapte aux labyrinthes cycliques. En cas de boucle, il ne fera pas la boucle vu que l'intersection a déjà été visitées, il reviendra sur ses pas.

Il s'adapte aux labyrinthes sans solution. En effet, s'il n'y a pas de sortie, il va revenir à sa position de départ sans position précédente (pile vide) et en ayant parcouru toutes les cases.

=== Mur droit ===

Cet algorithme va suivre de la main droite le mur de droite.

Il est relativement inefficace, et va visiter un grand nombre de cases.

Il s'adapte assez mal aux labyrinthes cycliques. En effet, si la sortie n'est pas dans la même boucle que l'entrée, il ne la trouvera jamais.

Il ne s'adapte pas aux labyrinthes sans solution, et fera le tour de la grille à l'infini.

[[Fichier:labyrinthe_exp_exhaust.png|vignette|left|500px|Labyrinthe résolu en utilisant le parcours en profondeur. 660 cellules visitées, 1179 déplacements, chemin de 142 cellules.|alt=Parcours en profondeur]]
[[Fichier:labyrinthe_right_hand.png|vignette|right|500px|Labyrinthe résolu en utilisant le mur droit. 1068 cellules visitées, 1995 déplacements, chemin de 142 cellules.|alt=Mur droit]]

On remarquera que des deux algorithmes, celui du mur droit explorera toutes les cellules situées en dessous du chemin optimal. Il sera donc plus efficace lorsque le chemin de solution est vers le bas de la grille.

== Bilan personnel ==

Ce projet m'a permis de découvrir plusieurs structures de données qui, avec plusieurs années de recul, m'ont réellement été utiles.

J'ai aussi pu me familiariser avec Tkinter, avec la programmation orientée objets en Python (notamment héritage et méthodes statiques) et avec le multithreading, le projet ayant été pensé et codé en parallèle avant d'être entièrement refait plus "monolithique" une semaine avant l'oral.

J'ai aussi pu comprendre la complexité mathématique derrière un labyrinthe, et aborder certains aspects des graphes.

Pour résumer, ce projet a vraiment pris tout son sens en L3, où certains concepts m'ont enfin été expliqués et où j'ai enfin pu avoir le recul nécessaire pour saisir l'essence même de la problématique.

== Code source ==

Le code source est disponible sur Github à [https://github.com/Rominos111/Labyrinthe_VISI201 cette adresse]. N'hésitez pas à jeter un œil aux autres projets en cours 😉

Il suffit d'avoir installé Python 3 et Tkinter.

== Sources ==

Génération
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li>
</ul>

Résolution
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li>
</ul>

Structures de données
<ul>
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li>
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li>
</ul>

Python
<ul>
<li> [https://docs.python.org/3.6/reference/datamodel.html Classes et types de variables personnalisés (en)] </li>
<li> [http://effbot.org/tkinterbook/canvas.htm Canvas Tkinter (en)] </li>
</ul>

Génération et résolution de labyrinthes II

2019-05-22T17:33:02Z

Theodet :

__FORCETOC__[[Fichier:labyrinthe_photo.png|vignette|300px|Exemple de labyrinthe généré et résolu. En rouge foncé, l'entrée. En vert, la sortie. En bleu, le chemin entre le départ et l'arrivée. En rouge clair, les cellules visitées lors de la résolution.|alt="Labyrinthe"]]

L'objectif de ce projet est de générer des labyrinthes aussi grands et complexes que possible. Nous allons voir comment toujours avoir un chemin entre l'entrée et la sortie, et comment trouver la sortie une fois notre labyrinthe généré.

== Représentation ==

=== Propriétés ===

Un labyrinthe est une grille de cellules reliées, ou non, entre elles.

Deux cellules sont reliées entre elles par une '''porte''', ou séparées par un '''mur'''.

Tout labyrinthe a '''une entrée''' et '''une sortie''', et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est '''unique'''.

=== Modélisation en graphe ===

En théorie des graphes, un graphe est un ensemble de '''points''' (ou nœuds ou sommets) reliés ensemble par des '''lignes''' (ou liens ou arêtes).

[[Fichier:graphe_cyclique.png|vignette|left|300px|Exemple de graphe connexe cyclique non orienté|alt=Graphe cyclique]]

Un graphe peut être '''connexe''' (en un seul morceau) ou '''non connexe''' (en plusieurs morceaux).

Un graphe peut aussi être '''cyclique''' si les points sont reliés en formant une boucle ou '''acyclique'''.

Enfin, un graphe peut être '''orienté''' (si les arêtes sont à sens unique) ou '''non orienté'''.

[[Fichier:Arbre.PNG|vignette|left|300px|Exemple d'arbre|alt=Arbre]]

Un '''arbre''' est un graphe connexe, acyclique et non orienté.

En plaçant un point sur chaque cellule de notre labyrinthe, et en reliant deux cellules séparées par une porte, on peut dessiner un arbre à partir de n'importe quel labyrinthe.

Sur notre graphe, un arête est donc un passage dans notre labyrinthe.

[[Fichier:labyrinthe_avec_arbre.png|vignette|centre|300px|Exemple de labyrinthe avec son arbre. Pour plus de simplicité, on attribue à chaque nœud une position.|alt=Labyrinthe avec arbre]]

== Génération ==

Un labyrinthe rectangulaire de largeur <math> L </math> et de hauteur <math> H </math> contient exactement <math>L \times H - 1</math> portes.

Du point de vue du graphe, il y a donc <math>L \times H - 1</math> arêtes.

Maintenant, comment répartir toutes ces portes de façon à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?

De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal.
Chaque algorithme est différent et produit des labyrinthes visuellement différents.

=== Parcours en profondeur ===

[[Fichier:recursive_backtracker.gif|vignette|left|500px|Illustration du parcours en profondeur|alt=Parcours en profondeur]]

Dans l'algorithme du parcours en profondeur ("recursive backtracker" en anglais), on commence sur une cellule aléatoire dans le labyrinthe.

On se dirige dans une direction aléatoire et on casse le mur en face, tout en marquant la cellule précédente comme visitée.

Lorsque aucune direction n'est disponible, on remonte à la position précédente.

[[Fichier:pile.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

Pour sauvegarder l'historique des positions, on peut utiliser une '''pile'''.

Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.

Une pile contient 2 méthodes :
* push(elem) : ajoute elem à la pile
* pop() -> elem : retourne le dernier élément de la pile (elem dans notre cas)

Dans mon implémentation de la pile, une erreur est levée si l'on appelle la méthode pop sur une pile vide.

=== Kruskal ===

[[Fichier:kruskal.gif|vignette|left|500px|Illustration de l'algorithme de Kruskal.|alt=Kruskal]]

Alors que pour le parcours en profondeur on partait des cellules, l'algorithme de Kruskal s'applique sur des murs.

On attribue à chaque cellule un identifiant unique.

On choisit un mur aléatoire. Si les cellules séparées par ce mur ont des identifiants différents, on leur associe le même identifiant et on casse le mur.

Sinon, on passe à un autre mur.

[[Fichier:union_find.png|vignette|300px|Représentation d'une structure Union-Find avec find(a,b) et find(b,c).|alt=Union-Find]]

Pour mettre en œuvre cet algorithme, on utilise une structure de données appelée '''Union-Find''', qui permet de mettre en relation des éléments partageant un même représentant (ou un même identifiant).

Il existe plusieurs variantes d'Union-Find, dont notamment la compression de chemin, qui permet de n'avoir qu'un ou deux éléments à parcourir pour obtenir le représentant d'un élément.

Union-Find fonctionne comme un arbre. 'a' a un représentant 'A', etc..., qui lui même a un représentant '<math>\alpha</math>', qui est son propre représentant.

Union-Find est composé de deux méthodes :
* union(a, b) : associe à 'a' et 'b' le même représentant, par exemple 'A' le représentant de 'a'
* find(a) -> <math>\alpha</math> : tant que l'élément n'est pas son propre représentant, on applique find au représentant de l'élément. On commence donc par find(a), puis find(A) (si 'A' est le représentant de 'a'), etc... La méthode de la compression de chemin permet d'éviter trop de récursivité en écrivant : représentant de 'a' = <math>\alpha</math>

=== Labyrinthes cycliques ===

Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.

Cependant, certains algorithmes de résolution n'adopteront pas le même comportement.

=== Comparaison ===

Si nous comparons un labyrinthe généré avec l'algorithme du parcours en profondeur à un labyrinthe généré avec l'algorithme de Kruskal, bien qu'ils aient tous les deux une solution unique, ils apparaissent néanmoins différents visuellement.

[[Fichier:recursive_backtracker_comparaison.png|vignette|left|500px|Parcours en profondeur. On remarque des chemins proprement dessinés.|alt=Parcours en profondeur]]
[[Fichier:kruskal_comparaison.png|vignette|right|500px|Algorithme de Kruskal. On remarque des murs de 1 de longueur çà et là.|alt=Kruskal]]

== Résolution ==

Il existe là encore de nombreux algorithmes de résolution de labyrinthes, plus ou moins efficaces, et surtout ne fonctionnant pas tous dans les mêmes conditions.

=== Parcours en profondeur ===

Cet algorithme est quasiment identique à celui du parcours en profondeur pour la génération.

Il est très efficace et trouvera une solution en minimisant le nombre de cases visitées.

Il s'adapte aux labyrinthes cycliques. En cas de boucle, il ne fera pas la boucle vu que l'intersection a déjà été visitées, il reviendra sur ses pas.

Il s'adapte aux labyrinthes sans solution. En effet, s'il n'y a pas de sortie, il va revenir à sa position de départ sans position précédente (pile vide) et en ayant parcouru toutes les cases.

=== Mur droit ===

Cet algorithme va suivre de la main droite le mur de droite.

Il est relativement inefficace, et va visiter un grand nombre de cases.

Il s'adapte assez mal aux labyrinthes cycliques. En effet, si la sortie n'est pas dans la même boucle que l'entrée, il ne la trouvera jamais.

Il ne s'adapte pas aux labyrinthes sans solution, et fera le tour de la grille à l'infini.

[[Fichier:labyrinthe_exp_exhaust.png|vignette|left|500px|Labyrinthe résolu en utilisant le parcours en profondeur. 660 cellules visitées, 1179 déplacements, chemin de 142 cellules.|alt=Parcours en profondeur]]
[[Fichier:labyrinthe_right_hand.png|vignette|right|500px|Labyrinthe résolu en utilisant le mur droit. 1068 cellules visitées, 1995 déplacements, chemin de 142 cellules.|alt=Mur droit]]

On remarquera que des deux algorithmes, celui du mur droit explorera toutes les cellules situées en dessous du chemin optimal. Il sera donc plus efficace lorsque le chemin de solution est vers le bas de la grille.

== Bilan personnel ==

Ce projet m'a permis de découvrir plusieurs structures de données qui me seront utiles à l'avenir.

J'ai aussi pu me familiariser avec tkinter, avec la programmation orientée objets en Python (notamment héritage et méthodes statiques) et avec le multithreading (j'avais codé mon projet en programmation parallèle avant de le refaire entièrement un un seul thread une semaine avant l'oral).

J'ai aussi pu comprendre la complexité mathématique derrière un labyrinthe.

== Code source ==

Mon projet total contenant plusieurs milliers de lignes de code réparties dans une dizaine de fichiers, je ne peux évidemment pas l'insérer directement dans cette page.

Le code source est disponible sur Github à [https://github.com/Rominos111/Labyrinthe_VISI201 cette adresse]

Il suffit d'avoir installé Python 3 et tkinter.

== Sources ==

Génération
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li>
</ul>

Résolution
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li>
</ul>

Structures de données
<ul>
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li>
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li>
</ul>

Python
<ul>
<li> [https://docs.python.org/3.6/reference/datamodel.html Classes et types de variables personnalisés (en)] </li>
<li> [http://effbot.org/tkinterbook/canvas.htm Canvas Tkinter (en)] </li>
</ul>

Génération et résolution de labyrinthes II

2019-05-22T17:30:06Z

Theodet :

__FORCETOC__[[Fichier:labyrinthe_photo.png|vignette|300px|Exemple de labyrinthe généré et résolu. En rouge foncé, l'entrée. En vert, la sortie. En bleu, le chemin entre le départ et l'arrivée. En rouge clair, les cellules visitées lors de la résolution.|alt="Labyrinthe"]]

On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Et comment trouver la sortie quand on est perdu dans le labyrinthe ?

== Représentation ==

=== Propriétés ===

Un labyrinthe est une grille de cellules reliées, ou non, entre elles.

Deux cellules sont reliées entre elles par une '''porte''', ou séparées par un '''mur'''.

Tout labyrinthe a '''une entrée''' et '''une sortie''', et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est '''unique'''.

=== Modélisation en graphe ===

En théorie des graphes, un graphe est un ensemble de '''points''' (ou nœuds ou sommets) reliés ensemble par des '''lignes''' (ou liens ou arêtes).

[[Fichier:graphe_cyclique.png|vignette|left|300px|Exemple de graphe connexe cyclique non orienté|alt=Graphe cyclique]]

Un graphe peut être '''connexe''' (en un seul morceau) ou '''non connexe''' (en plusieurs morceaux).

Un graphe peut aussi être '''cyclique''' si les points sont reliés en formant une boucle ou '''acyclique'''.

Enfin, un graphe peut être '''orienté''' (si les arêtes sont à sens unique) ou '''non orienté'''.

[[Fichier:Arbre.PNG|vignette|left|300px|Exemple d'arbre|alt=Arbre]]

Un '''arbre''' est un graphe connexe, acyclique et non orienté.

En plaçant un point sur chaque cellule de notre labyrinthe, et en reliant deux cellules séparées par une porte, on peut dessiner un arbre à partir de n'importe quel labyrinthe.

Sur notre graphe, un arête est donc un passage dans notre labyrinthe.

[[Fichier:labyrinthe_avec_arbre.png|vignette|centre|300px|Exemple de labyrinthe avec son arbre. Pour plus de simplicité, on attribue à chaque nœud une position.|alt=Labyrinthe avec arbre]]

== Génération ==

Un labyrinthe rectangulaire de largeur <math> L </math> et de hauteur <math> H </math> contient exactement <math>L \times H - 1</math> portes.

Du point de vue du graphe, il y a donc <math>L \times H - 1</math> arêtes.

Maintenant, comment répartir toutes ces portes de façon à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?

De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal.
Chaque algorithme est différent et produit des labyrinthes visuellement différents.

=== Parcours en profondeur ===

[[Fichier:recursive_backtracker.gif|vignette|left|500px|Illustration du parcours en profondeur|alt=Parcours en profondeur]]

Dans l'algorithme du parcours en profondeur ("recursive backtracker" en anglais), on commence sur une cellule aléatoire dans le labyrinthe.

On se dirige dans une direction aléatoire et on casse le mur en face, tout en marquant la cellule précédente comme visitée.

Lorsque aucune direction n'est disponible, on remonte à la position précédente.

[[Fichier:pile.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

Pour sauvegarder l'historique des positions, on peut utiliser une '''pile'''.

Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.

Une pile contient 2 méthodes :
* push(elem) : ajoute elem à la pile
* pop() -> elem : retourne le dernier élément de la pile (elem dans notre cas)

Dans mon implémentation de la pile, une erreur est levée si l'on appelle la méthode pop sur une pile vide.

=== Kruskal ===

[[Fichier:kruskal.gif|vignette|left|500px|Illustration de l'algorithme de Kruskal.|alt=Kruskal]]

Alors que pour le parcours en profondeur on partait des cellules, l'algorithme de Kruskal s'applique sur des murs.

On attribue à chaque cellule un identifiant unique.

On choisit un mur aléatoire. Si les cellules séparées par ce mur ont des identifiants différents, on leur associe le même identifiant et on casse le mur.

Sinon, on passe à un autre mur.

[[Fichier:union_find.png|vignette|300px|Représentation d'une structure Union-Find avec find(a,b) et find(b,c).|alt=Union-Find]]

Pour mettre en œuvre cet algorithme, on utilise une structure de données appelée '''Union-Find''', qui permet de mettre en relation des éléments partageant un même représentant (ou un même identifiant).

Il existe plusieurs variantes d'Union-Find, dont notamment la compression de chemin, qui permet de n'avoir qu'un ou deux éléments à parcourir pour obtenir le représentant d'un élément.

Union-Find fonctionne comme un arbre. 'a' a un représentant 'A', etc..., qui lui même a un représentant '<math>\alpha</math>', qui est son propre représentant.

Union-Find est composé de deux méthodes :
* union(a, b) : associe à 'a' et 'b' le même représentant, par exemple 'A' le représentant de 'a'
* find(a) -> <math>\alpha</math> : tant que l'élément n'est pas son propre représentant, on applique find au représentant de l'élément. On commence donc par find(a), puis find(A) (si 'A' est le représentant de 'a'), etc... La méthode de la compression de chemin permet d'éviter trop de récursivité en écrivant : représentant de 'a' = <math>\alpha</math>

=== Labyrinthes cycliques ===

Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.

Cependant, certains algorithmes de résolution n'adopteront pas le même comportement.

=== Comparaison ===

Si nous comparons un labyrinthe généré avec l'algorithme du parcours en profondeur à un labyrinthe généré avec l'algorithme de Kruskal, bien qu'ils aient tous les deux une solution unique, ils apparaissent néanmoins différents visuellement.

[[Fichier:recursive_backtracker_comparaison.png|vignette|left|500px|Parcours en profondeur. On remarque des chemins proprement dessinés.|alt=Parcours en profondeur]]
[[Fichier:kruskal_comparaison.png|vignette|right|500px|Algorithme de Kruskal. On remarque des murs de 1 de longueur çà et là.|alt=Kruskal]]

== Résolution ==

Il existe là encore de nombreux algorithmes de résolution de labyrinthes, plus ou moins efficaces, et surtout ne fonctionnant pas tous dans les mêmes conditions.

=== Parcours en profondeur ===

Cet algorithme est quasiment identique à celui du parcours en profondeur pour la génération.

Il est très efficace et trouvera une solution en minimisant le nombre de cases visitées.

Il s'adapte aux labyrinthes cycliques. En cas de boucle, il ne fera pas la boucle vu que l'intersection a déjà été visitées, il reviendra sur ses pas.

Il s'adapte aux labyrinthes sans solution. En effet, s'il n'y a pas de sortie, il va revenir à sa position de départ sans position précédente (pile vide) et en ayant parcouru toutes les cases.

=== Mur droit ===

Cet algorithme va suivre de la main droite le mur de droite.

Il est relativement inefficace, et va visiter un grand nombre de cases.

Il s'adapte assez mal aux labyrinthes cycliques. En effet, si la sortie n'est pas dans la même boucle que l'entrée, il ne la trouvera jamais.

Il ne s'adapte pas aux labyrinthes sans solution, et fera le tour de la grille à l'infini.

[[Fichier:labyrinthe_exp_exhaust.png|vignette|left|500px|Labyrinthe résolu en utilisant le parcours en profondeur. 660 cellules visitées, 1179 déplacements, chemin de 142 cellules.|alt=Parcours en profondeur]]
[[Fichier:labyrinthe_right_hand.png|vignette|right|500px|Labyrinthe résolu en utilisant le mur droit. 1068 cellules visitées, 1995 déplacements, chemin de 142 cellules.|alt=Mur droit]]

On remarquera que des deux algorithmes, celui du mur droit explorera toutes les cellules situées en dessous du chemin optimal. Il sera donc plus efficace lorsque le chemin de solution est vers le bas de la grille.

== Bilan personnel ==

Ce projet m'a permis de découvrir plusieurs structures de données qui me seront utiles à l'avenir.

J'ai aussi pu me familiariser avec tkinter, avec la programmation orientée objets en Python (notamment héritage et méthodes statiques) et avec le multithreading (j'avais codé mon projet en programmation parallèle avant de le refaire entièrement un un seul thread une semaine avant l'oral).

J'ai aussi pu comprendre la complexité mathématique derrière un labyrinthe.

== Code source ==

Mon projet total contenant plusieurs milliers de lignes de code réparties dans une dizaine de fichiers, je ne peux évidemment pas l'insérer directement dans cette page.

Le code source est disponible sur Github à [https://github.com/Rominos111/Labyrinthe_VISI201 cette adresse]

Il suffit d'avoir installé Python 3 et tkinter.

== Sources ==

Génération
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li>
</ul>

Résolution
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li>
</ul>

Structures de données
<ul>
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li>
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li>
</ul>

Python
<ul>
<li> [https://docs.python.org/3.6/reference/datamodel.html Classes et types de variables personnalisés (en)] </li>
<li> [http://effbot.org/tkinterbook/canvas.htm Canvas Tkinter (en)] </li>
</ul>

Génération et résolution de labyrinthes II

2019-05-22T12:40:53Z

Theodet : /* Résolution */

__FORCETOC__[[Fichier:labyrinthe_photo.png|vignette|300px|Labyrinthe généré avec Kruskal et résolu avec le parcours en profondeur. En rouge foncé, l'entrée. En vert, la sortie. En bleu, le chemin. En rouge clair, les cellules visitées lors de la résolution.|alt="Labyrinthe"]]

On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Et comment trouver la sortie quand on est perdu dans le labyrinthe ?

== Représentation ==

=== Propriétés ===

Un labyrinthe est une grille de cellules reliées, ou non, entre elles.

Deux cellules sont reliées entre elles par une '''porte''', ou séparées par un '''mur'''.

Tout labyrinthe a '''une entrée''' et '''une sortie''', et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est '''unique'''.

=== Modélisation en graphe ===

En théorie des graphes, un graphe est un ensemble de '''points''' (ou nœuds ou sommets) reliés ensemble par des '''lignes''' (ou liens ou arêtes).

[[Fichier:graphe_cyclique.png|vignette|left|300px|Exemple de graphe connexe cyclique non orienté|alt=Graphe cyclique]]

Un graphe peut être '''connexe''' (en un seul morceau) ou '''non connexe''' (en plusieurs morceaux).

Un graphe peut aussi être '''cyclique''' si les points sont reliés en formant une boucle ou '''acyclique'''.

Enfin, un graphe peut être '''orienté''' (si les arêtes sont à sens unique) ou '''non orienté'''.

[[Fichier:Arbre.PNG|vignette|left|300px|Exemple d'arbre|alt=Arbre]]

Un '''arbre''' est un graphe connexe, acyclique et non orienté.

En plaçant un point sur chaque cellule de notre labyrinthe, et en reliant deux cellules séparées par une porte, on peut dessiner un arbre à partir de n'importe quel labyrinthe.

[[Fichier:labyrinthe_avec_arbre.png|vignette|centre|300px|Exemple de labyrinthe avec son arbre. Pour plus de simplicité, on attribue à chaque nœud une position.|alt=Labyrinthe avec arbre]]

== Génération ==

Un labyrinthe rectangulaire de largeur <math> L </math> et de hauteur <math> H </math> contient exactement <math>L \times H - 1</math> portes.

Du point de vue du graphe, il y a donc <math>L \times H - 1</math> arêtes.

Maintenant, comment répartir toutes ces portes de façon à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?

De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal.
Chaque algorithme est différent et produit des labyrinthes visuellement différents.

En effet, si nous comparons un labyrinthe généré avec l'algorithme du parcours en profondeur à un labyrinthe généré avec l'algorithme de Kruskal, bien qu'ils aient tous les deux une solution unique, ils apparaissent néanmoins différents visuellement.

[[Fichier:recursive_backtracker_comparaison.png|vignette|left|500px|Parcours en profondeur. On remarque des chemins proprement dessinés.|alt=Parcours en profondeur]]
[[Fichier:kruskal_comparaison.png|vignette|right|500px|Algorithme de Kruskal. On remarque des murs de 1 de longueur çà et là.|alt=Kruskal]]

=== Parcours en profondeur ===

[[Fichier:recursive_backtracker.gif|vignette|left|500px|Illustration du parcours en profondeur|alt=Parcours en profondeur]]

Dans l'algorithme du parcours en profondeur ("recursive backtracker" en anglais), on commence sur une cellule aléatoire dans le labyrinthe.

On se dirige dans une direction aléatoire et on casse le mur en face, tout en marquant la cellule précédente comme visitée.

Lorsque aucune direction n'est disponible, on remonte à la position précédente.

[[Fichier:pile.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

Pour sauvegarder l'historique des positions, on peut utiliser une '''pile'''.

Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.

Une pile contient 2 méthodes :
* push(elem) : ajoute elem à la pile
* pop() -> elem : retourne le dernier élément de la pile (elem dans notre cas)

Dans mon implémentation de la pile, une erreur est levée si l'on appelle la méthode pop sur une pile vide.

=== Kruskal ===

[[Fichier:kruskal.gif|vignette|left|500px|Illustration de l'algorithme de Kruskal.|alt=Kruskal]]

Alors que pour le parcours en profondeur on partait des cellules, l'algorithme de Kruskal s'applique sur des murs.

On attribue à chaque cellule un identifiant unique.

On choisit un mur aléatoire. Si les cellules séparées par ce mur ont des identifiants différents, on leur associe le même identifiant et on casse le mur.

Sinon, on passe à un autre mur.

[[Fichier:union_find.png|vignette|300px|Représentation d'une structure Union-Find avec find(a,b) et find(b,c).|alt=Union-Find]]

Pour mettre en œuvre cet algorithme, on utilise une structure de données appelée '''Union-Find''', qui permet de mettre en relation des éléments partageant un même représentant (ou un même identifiant).

Il existe plusieurs variantes d'Union-Find, dont notamment la compression de chemin, qui permet de n'avoir qu'un ou deux éléments à parcourir pour obtenir le représentant d'un élément.

Union-Find fonctionne comme un arbre. <math>a</math> a un représentant <math>A</math>, etc..., qui lui même a un représentant <math>\alpha</math>, qui est son propre représentant.

Union-Find est composé de deux méthodes :
* union(a, b) : associe à <math>a</math> et <math>b</math> le même représentant, par exemple <math>A</math> le représentant de <math>a</math>
* find(a) -> <math>\alpha</math> : tant que l'élément n'est pas son propre représentant, on applique find au représentant de l'élément. On commence donc par find(a), puis find(A) (si <math>A</math> est le représentant de <math>a</math>), etc... La méthode de la compression de chemin permet d'éviter trop de récursivité en écrivant : représentant de <math>a</math> := <math>\alpha</math>

=== Labyrinthes cycliques ===

Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.

Cependant, certains algorithmes de résolution n'adopteront pas le même comportement.

== Résolution ==

Il existe là encore de nombreux algorithmes de résolution de labyrinthes, plus ou moins efficaces, et surtout ne fonctionnant pas tous dans les mêmes conditions.

=== Parcours en profondeur ===

Cet algorithme est quasiment identique à celui du parcours en profondeur pour la génération.

Il est très efficace et trouvera une solution en minimisant le nombre de cases visitées.

Il s'adapte aux labyrinthes cycliques. En cas de boucle, il ne fera pas la boucle vu que l'intersection a déjà été visitées, il reviendra sur ses pas.

Il s'adapte aux labyrinthes sans solution. En effet, s'il n'y a pas de sortie, il va revenir à sa position de départ sans position précédente (pile vide) et en ayant parcouru toutes les cases.

=== Mur droit ===

Cet algorithme va suivre de la main droite le mur de droite.

Il est relativement inefficace, et va visiter un grand nombre de cases.

Il s'adapte assez mal aux labyrinthes cycliques. En effet, si la sortie n'est pas dans la même boucle que l'entrée, il ne la trouvera jamais.

Il ne s'adapte pas aux labyrinthes sans solution, et fera le tour de la grille à l'infini.

[[Fichier:labyrinthe_exp_exhaust.png|vignette|left|500px|Labyrinthe résolu en utilisant le parcours en profondeur. 660 cellules visitées, 1179 déplacements, chemin de 142 cellules.|alt=Parcours en profondeur]]
[[Fichier:labyrinthe_right_hand.png|vignette|right|500px|Labyrinthe résolu en utilisant le mur droit. 1068 cellules visitées, 1995 déplacements, chemin de 142 cellules.|alt=Mur droit]]

On remarquera que des deux algorithmes, celui du mur droit explorera toutes les cellules situées en dessous du chemin optimal. Il sera donc plus efficace lorsque le chemin de solution est vers le bas de la grille.

== Code source ==

Mon projet total contenant plusieurs milliers de lignes de code réparties dans une dizaine de fichiers, je ne peux évidemment pas l'insérer directement dans cette page.

Le code source est disponible sur Github à [https://github.com/Rominos111/Labyrinthe_VISI201 cette adresse]

Il suffit d'avoir installé Python 3 et tkinter.

== Sources ==

Génération
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li>
</ul>

Résolution
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li>
</ul>

Structures de données
<ul>
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li>
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li>
</ul>

Python
<ul>
<li> [https://docs.python.org/3.6/reference/datamodel.html Classes et types de variables personnalisés (en)] </li>
<li> [http://effbot.org/tkinterbook/canvas.htm Canvas Tkinter (en)] </li>
</ul>

Génération et résolution de labyrinthes II

2019-05-20T06:51:31Z

Theodet :

__FORCETOC__[[Fichier:labyrinthe_photo.png|vignette|300px|Labyrinthe généré avec Kruskal et résolu avec le parcours en profondeur. En rouge foncé, l'entrée. En vert, la sortie. En bleu, le chemin. En rouge clair, les cellules visitées lors de la résolution.|alt="Labyrinthe"]]

On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Et comment trouver la sortie quand on est perdu dans le labyrinthe ?

== Représentation ==

=== Propriétés ===

Un labyrinthe est une grille de cellules reliées, ou non, entre elles.

Deux cellules sont reliées entre elles par une '''porte''', ou séparées par un '''mur'''.

Tout labyrinthe a '''une entrée''' et '''une sortie''', et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est '''unique'''.

=== Modélisation en graphe ===

En théorie des graphes, un graphe est un ensemble de '''points''' (ou nœuds ou sommets) reliés ensemble par des '''lignes''' (ou liens ou arêtes).

[[Fichier:graphe_cyclique.png|vignette|left|300px|Exemple de graphe connexe cyclique non orienté|alt=Graphe cyclique]]

Un graphe peut être '''connexe''' (en un seul morceau) ou '''non connexe''' (en plusieurs morceaux).

Un graphe peut aussi être '''cyclique''' si les points sont reliés en formant une boucle ou '''acyclique'''.

Enfin, un graphe peut être '''orienté''' (si les arêtes sont à sens unique) ou '''non orienté'''.

[[Fichier:Arbre.PNG|vignette|left|300px|Exemple d'arbre|alt=Arbre]]

Un '''arbre''' est un graphe connexe, acyclique et non orienté.

En plaçant un point sur chaque cellule de notre labyrinthe, et en reliant deux cellules séparées par une porte, on peut dessiner un arbre à partir de n'importe quel labyrinthe.

[[Fichier:labyrinthe_avec_arbre.png|vignette|centre|300px|Exemple de labyrinthe avec son arbre. Pour plus de simplicité, on attribue à chaque nœud une position.|alt=Labyrinthe avec arbre]]

== Génération ==

Un labyrinthe rectangulaire de largeur <math> L </math> et de hauteur <math> H </math> contient exactement <math>L \times H - 1</math> portes.

Du point de vue du graphe, il y a donc <math>L \times H - 1</math> arêtes.

Maintenant, comment répartir toutes ces portes de façon à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?

De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal.
Chaque algorithme est différent et produit des labyrinthes visuellement différents.

En effet, si nous comparons un labyrinthe généré avec l'algorithme du parcours en profondeur à un labyrinthe généré avec l'algorithme de Kruskal, bien qu'ils aient tous les deux une solution unique, ils apparaissent néanmoins différents visuellement.

[[Fichier:recursive_backtracker_comparaison.png|vignette|left|500px|Parcours en profondeur. On remarque des chemins proprement dessinés.|alt=Parcours en profondeur]]
[[Fichier:kruskal_comparaison.png|vignette|right|500px|Algorithme de Kruskal. On remarque des murs de 1 de longueur çà et là.|alt=Kruskal]]

=== Parcours en profondeur ===

[[Fichier:recursive_backtracker.gif|vignette|left|500px|Illustration du parcours en profondeur|alt=Parcours en profondeur]]

Dans l'algorithme du parcours en profondeur ("recursive backtracker" en anglais), on commence sur une cellule aléatoire dans le labyrinthe.

On se dirige dans une direction aléatoire et on casse le mur en face, tout en marquant la cellule précédente comme visitée.

Lorsque aucune direction n'est disponible, on remonte à la position précédente.

[[Fichier:pile.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

Pour sauvegarder l'historique des positions, on peut utiliser une '''pile'''.

Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.

Une pile contient 2 méthodes :
* push(elem) : ajoute elem à la pile
* pop() -> elem : retourne le dernier élément de la pile (elem dans notre cas)

Dans mon implémentation de la pile, une erreur est levée si l'on appelle la méthode pop sur une pile vide.

=== Kruskal ===

[[Fichier:kruskal.gif|vignette|left|500px|Illustration de l'algorithme de Kruskal.|alt=Kruskal]]

Alors que pour le parcours en profondeur on partait des cellules, l'algorithme de Kruskal s'applique sur des murs.

On attribue à chaque cellule un identifiant unique.

On choisit un mur aléatoire. Si les cellules séparées par ce mur ont des identifiants différents, on leur associe le même identifiant et on casse le mur.

Sinon, on passe à un autre mur.

[[Fichier:union_find.png|vignette|300px|Représentation d'une structure Union-Find avec find(a,b) et find(b,c).|alt=Union-Find]]

Pour mettre en œuvre cet algorithme, on utilise une structure de données appelée '''Union-Find''', qui permet de mettre en relation des éléments partageant un même représentant (ou un même identifiant).

Il existe plusieurs variantes d'Union-Find, dont notamment la compression de chemin, qui permet de n'avoir qu'un ou deux éléments à parcourir pour obtenir le représentant d'un élément.

Union-Find fonctionne comme un arbre. <math>a</math> a un représentant <math>A</math>, etc..., qui lui même a un représentant <math>\alpha</math>, qui est son propre représentant.

Union-Find est composé de deux méthodes :
* union(a, b) : associe à <math>a</math> et <math>b</math> le même représentant, par exemple <math>A</math> le représentant de <math>a</math>
* find(a) -> <math>\alpha</math> : tant que l'élément n'est pas son propre représentant, on applique find au représentant de l'élément. On commence donc par find(a), puis find(A) (si <math>A</math> est le représentant de <math>a</math>), etc... La méthode de la compression de chemin permet d'éviter trop de récursivité en écrivant : représentant de <math>a</math> := <math>\alpha</math>

=== Labyrinthes cycliques ===

Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.

Cependant, certains algorithmes de résolution n'adopteront pas le même comportement.

== Résolution ==

Il existe là encore de nombreux algorithmes de résolution de labyrinthes, plus ou moins efficaces, et surtout ne fonctionnant pas tous dans les mêmes conditions.

=== Parcours en profondeur ===

Cet algorithme est quasiment identique à celui du parcours en profondeur pour la génération.

Il est très efficace et trouvera une solution en minimisant le nombre de cases visitées.

Il s'adapte aux labyrinthes cycliques. En cas de boucle, il ne fera pas la boucle vu que l'intersection a déjà été visitées, il reviendra sur ses pas.

Il s'adapte aux labyrinthes sans solution. En effet, s'il n'y a pas de sortie, il va revenir à sa position de départ sans position précédente (pile vide) et en ayant parcouru toutes les cases.

=== Mur droit ===

Cet algorithme va suivre de la main droite le mur de droite.

Il est relativement inefficace, et va visiter un grand nombre de cases.

Il s'adapte assez mal aux labyrinthes cycliques. En effet, si la sortie n'est pas dans la même boucle que l'entrée, il ne la trouvera jamais.

Il ne s'adapte pas aux labyrinthes sans solution, et fera le tour de la grille à l'infini.

[[Fichier:labyrinthe_exp_exhaust.png|vignette|left|500px|Labyrinthe résolu en utilisant le parcours en profondeur. 660 cellules visitées, 1179 déplacements, chemin de 142 cellules.|alt=Parcours en profondeur]]
[[Fichier:labyrinthe_right_hand.png|vignette|right|500px|Labyrinthe résolu en utilisant le mur droit. 1068 cellules visitées, 1995 déplacements, chemin de 142 cellules.|alt=Mur droit]]

== Code source ==

Mon projet total contenant plusieurs milliers de lignes de code réparties dans une dizaine de fichiers, je ne peux évidemment pas l'insérer directement dans cette page.

Le code source est disponible sur Github à [https://github.com/Rominos111/Labyrinthe_VISI201 cette adresse]

Il suffit d'avoir installé Python 3 et tkinter.

== Sources ==

Génération
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li>
</ul>

Résolution
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li>
</ul>

Structures de données
<ul>
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li>
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li>
</ul>

Python
<ul>
<li> [https://docs.python.org/3.6/reference/datamodel.html Classes et types de variables personnalisés (en)] </li>
<li> [http://effbot.org/tkinterbook/canvas.htm Canvas Tkinter (en)] </li>
</ul>

Génération et résolution de labyrinthes II

2019-05-20T06:47:19Z

Theodet :

__FORCETOC__[[Fichier:labyrinthe_photo.png|vignette|300px|Labyrinthe généré avec Kruskal et résolu avec le parcours en profondeur. En route foncé, l'entrée. En vert, la sortie. En bleu, le chemin. En rouge clair, les cellules visitées lors de la résolution.|alt="Labyrinthe"]]

On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Et comment trouver la sortie quand on est perdu dans le labyrinthe ?

== Représentation ==

=== Propriétés ===

Un labyrinthe est une grille de cellules reliées, ou non, entre elles.

Deux cellules sont reliées entre elles par une '''porte''', ou séparées par un '''mur'''.

Tout labyrinthe a '''une entrée''' et '''une sortie''', et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est '''unique'''.

=== Modélisation en graphe ===

En théorie des graphes, un graphe est un ensemble de '''points''' (ou nœuds ou sommets) reliés ensemble par des '''lignes''' (ou liens ou arêtes).

[[Fichier:graphe_cyclique.png|vignette|left|300px|Exemple de graphe connexe cyclique non orienté|alt=Graphe cyclique]]

Un graphe peut être '''connexe''' (en un seul morceau) ou '''non connexe''' (en plusieurs morceaux).

Un graphe peut aussi être '''cyclique''' si les points sont reliés en formant une boucle ou '''acyclique'''.

Enfin, un graphe peut être '''orienté''' (si les arêtes sont à sens unique) ou '''non orienté'''.

[[Fichier:Arbre.PNG|vignette|left|300px|Exemple d'arbre|alt=Arbre]]

Un '''arbre''' est un graphe connexe, acyclique et non orienté.

En plaçant un point sur chaque cellule de notre labyrinthe, et en reliant deux cellules séparées par une porte, on peut dessiner un arbre à partir de n'importe quel labyrinthe.

[[Fichier:labyrinthe_avec_arbre.png|vignette|centre|300px|Exemple de labyrinthe avec son arbre. Pour plus de simplicité, on attribue à chaque nœud une position.|alt=Labyrinthe avec arbre]]

== Génération ==

Un labyrinthe rectangulaire de largeur <math> L </math> et de hauteur <math> H </math> contient exactement <math>L \times H - 1</math> portes.

Du point de vue du graphe, il y a donc <math>L \times H - 1</math> arêtes.

Maintenant, comment répartir toutes ces portes de façon à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?

De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal.
Chaque algorithme est différent et produit des labyrinthes visuellement différents.

En effet, si nous comparons un labyrinthe généré avec l'algorithme du parcours en profondeur à un labyrinthe généré avec l'algorithme de Kruskal, bien qu'ils aient tous les deux une solution unique, ils apparaissent néanmoins différents visuellement.

[[Fichier:recursive_backtracker_comparaison.png|vignette|left|500px|Parcours en profondeur. On remarque des chemins proprement dessinés.|alt=Parcours en profondeur]]
[[Fichier:kruskal_comparaison.png|vignette|right|500px|Algorithme de Kruskal. On remarque des murs de 1 de longueur çà et là.|alt=Kruskal]]

=== Parcours en profondeur ===

[[Fichier:recursive_backtracker.gif|vignette|left|500px|Illustration du parcours en profondeur|alt=Parcours en profondeur]]

Dans l'algorithme du parcours en profondeur ("recursive backtracker" en anglais), on commence sur une cellule aléatoire dans le labyrinthe.

On se dirige dans une direction aléatoire et on casse le mur en face, tout en marquant la cellule précédente comme visitée.

Lorsque aucune direction n'est disponible, on remonte à la position précédente.

[[Fichier:pile.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

Pour sauvegarder l'historique des positions, on peut utiliser une '''pile'''.

Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.

Une pile contient 2 méthodes :
* push(elem) : ajoute elem à la pile
* pop() -> elem : retourne le dernier élément de la pile (elem dans notre cas)

Dans mon implémentation de la pile, une erreur est levée si l'on appelle la méthode pop sur une pile vide.

=== Kruskal ===

[[Fichier:kruskal.gif|vignette|left|500px|Illustration de l'algorithme de Kruskal.|alt=Kruskal]]

Alors que pour le parcours en profondeur on partait des cellules, l'algorithme de Kruskal s'applique sur des murs.

On attribue à chaque cellule un identifiant unique.

On choisit un mur aléatoire. Si les cellules séparées par ce mur ont des identifiants différents, on leur associe le même identifiant et on casse le mur.

Sinon, on passe à un autre mur.

[[Fichier:union_find.png|vignette|300px|Représentation d'une structure Union-Find avec find(a,b) et find(b,c).|alt=Union-Find]]

Pour mettre en œuvre cet algorithme, on utilise une structure de données appelée '''Union-Find''', qui permet de mettre en relation des éléments partageant un même représentant (ou un même identifiant).

Il existe plusieurs variantes d'Union-Find, dont notamment la compression de chemin, qui permet de n'avoir qu'un ou deux éléments à parcourir pour obtenir le représentant d'un élément.

Union-Find fonctionne comme un arbre. <math>a</math> a un représentant <math>A</math>, etc..., qui lui même a un représentant <math>\alpha</math>, qui est son propre représentant.

Union-Find est composé de deux méthodes :
* union(a, b) : associe à <math>a</math> et <math>b</math> le même représentant, par exemple <math>A</math> le représentant de <math>a</math>
* find(a) -> <math>\alpha</math> : tant que l'élément n'est pas son propre représentant, on applique find au représentant de l'élément. On commence donc par find(a), puis find(A) (si <math>A</math> est le représentant de <math>a</math>), etc... La méthode de la compression de chemin permet d'éviter trop de récursivité en écrivant : représentant de <math>a</math> := <math>\alpha</math>

=== Labyrinthes cycliques ===

Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.

Cependant, certains algorithmes de résolution n'adopteront pas le même comportement.

== Résolution ==

Il existe là encore de nombreux algorithmes de résolution de labyrinthes, plus ou moins efficaces, et surtout ne fonctionnant pas tous dans les mêmes conditions.

=== Parcours en profondeur ===

Cet algorithme est quasiment identique à celui du parcours en profondeur pour la génération.

Il est très efficace et trouvera une solution en minimisant le nombre de cases visitées.

Il s'adapte aux labyrinthes cycliques. En cas de boucle, il ne fera pas la boucle vu que l'intersection a déjà été visitées, il reviendra sur ses pas.

Il s'adapte aux labyrinthes sans solution. En effet, s'il n'y a pas de sortie, il va revenir à sa position de départ sans position précédente (pile vide) et en ayant parcouru toutes les cases.

=== Mur droit ===

Cet algorithme va suivre de la main droite le mur de droite.

Il est relativement inefficace, et va visiter un grand nombre de cases.

Il s'adapte assez mal aux labyrinthes cycliques. En effet, si la sortie n'est pas dans la même boucle que l'entrée, il ne la trouvera jamais.

Il ne s'adapte pas aux labyrinthes sans solution, et fera le tour de la grille à l'infini.

[[Fichier:labyrinthe_exp_exhaust.png|vignette|left|500px|Labyrinthe résolu en utilisant le parcours en profondeur. 660 cellules visitées, 1179 déplacements, chemin de 142 cellules.|alt=Parcours en profondeur]]
[[Fichier:labyrinthe_right_hand.png|vignette|right|500px|Labyrinthe résolu en utilisant le mur droit. 1068 cellules visitées, 1995 déplacements, chemin de 142 cellules.|alt=Mur droit]]

== Code source ==

Mon projet total contenant plusieurs milliers de lignes de code réparties dans une dizaine de fichiers, je ne peux évidemment pas l'insérer directement dans cette page.

Le code source est disponible sur Github à [https://github.com/Rominos111/Labyrinthe_VISI201 cette adresse]

Il suffit d'avoir installé Python 3 et tkinter.

== Sources ==

Génération
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li>
</ul>

Résolution
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li>
</ul>

Structures de données
<ul>
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li>
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li>
</ul>

Python
<ul>
<li> [https://docs.python.org/3.6/reference/datamodel.html Classes et types de variables personnalisés (en)] </li>
<li> [http://effbot.org/tkinterbook/canvas.htm Canvas Tkinter (en)] </li>
</ul>

Dilemme du prisonnier

2019-05-19T21:21:48Z

Theodet : Juste 2 ou 3 fautes de français et vu que je suis gentil je veux pas que les profs les voient lol

== Introduction ==

Le dilemme du prisonnier à été inventé en 1950 par Albert William Tucker et fait partie de la théorie des jeux qui est un domaine des mathématiques étudiant les interactions entre différents individus qui sont conscients ou non de ces interactions. Ils devront donc faire des choix dont ils sont conscients ou non lors de ces interactions.

== Le dilemme du prisonnier ==

Les individus sont soumis dans le dilemme du prisonnier à une interaction où ils ont deux choix : soit ils coopèrent avec l’autre individu, soit ils le trahissent. Les individus sont récompensés selon la matrice des Paiements suivante :

[[Fichier:Tableau matrice paiements.PNG]]

L’intérêt de la configuration actuelle de la matrice des Paiements actuelle est que les individus ont un intérêt certain à trahir l’autre mais que la coopération est la meilleur option pour les deux individus. On représente l’intérêt à trahir par rapport à la coopération par la variable B qui dans notre exemple est égale à 1,85.

Afin de simplifier notre modèle nous ne considérerons que deux comportements possibles qui sont :

-Le Croyant qui coopérera systématiquement

-Le Traître qui trahira systématiquement

== Spatialisation du Dilemme du prisonnier ==

Nous spatialisons le dilemme du prisonnier afin d’expliquer en partie des observations dans le vivant où les êtres vivants coopèrent entre eux alors qu’ils ont tout à y gagner en ne le faisant pas. Pour étayer nos propos on propose la citation suivante :« The prisoners’ Dilemma is an interesting metaphor for the fundamental biological problem of how cooperative behaviour may evolve and be maintained »([https://www.researchgate.net/publication/216634494_Evolutionary_Games_and_Spatial_Chaos Nowak, M.A. et May, R.M. 1992. Evolutionary games and spatial chaos]). En spatialisant le dilemme du prisonnier nous pouvons observer l’évolution des pratiques dans des situations variées. Il est à noter que nous pouvons aussi établir des liens entre les domaines de l’économie et de la sociologie notamment.

Les prisonniers sont au voisinage de Moore (8 voisins) de telle sorte à ce que dans l’espace les voisins d’un prisonnier lambda soient disposés de la manière suivante :

1 2 3

4 P 5

6 7 8

L’espace dans lequel ils évoluent est un espace toroïdale (bordures ouvertes) en forme de carré de dimension n*n. On peut aussi le représenter comme une matrice carré avec les bordures qui communiquent entre elles.

À chaque tour les prisonniers vont jouer au dilemme du prisonnier avec chacun de leurs voisins. Ils obtiendront un score conformément à leurs choix et à la matrice des Paiements. Puis chacun leur tour mettre à jour leur stratégie en fonction du score des voisins.

Afin de pouvoir visualiser l'évolution de notre espace nous avons créé un programme en Java afin de profiter des aspects suivant de Java:

Le premier est la programmation objet, cela nous permet de diviser la complexité de notre programme dans plusieurs objets interagissants entre eux. Nous pouvons aussi créer des abstractions d'objets qui nous permettent d'avoir des objets qui ont des comportements différents les uns des autres mais ayants tous des points communs ce qui permet de les manipuler plus facilement.

Le second est la bibliothèque Abstract Windows Toolkit (ou AWT pour faire plus court), qui nous permet de faire sans trop de problèmes une fenêtre personnalisable qui affiche des composants graphiques. Ces composants étant eux mêmes variés, on utilisera surtout les propriétés du composant Canvas dans ce programme. Grâce à l’héritage permis par la programmation objet nous pouvons créer nos propres composants graphiques pour afficher nos résultats.

Notre programme crée donc une fenêtre qui affiche les prisonniers en fonction de leur stratégie actuelle et de leur dernière stratégie. Le code couleur est le suivant :

-en rouge les Traîtres qui l’ont été pendant 2 tours consécutifs

-en jaune les Croyants qui sont devenus Traîtres

-en vert les Traîtres devenus Croyants

-en bleu les Croyants qui l’ont été pendant 2 tours consécutifs

== Une expérience intéressante ==

On propose dans cette partie de commencer à étudier un cas en particulier. Dans cette première expérience nous fixons B à 1,85 et plaçons un traître au milieu de croyants dans une grille de 301 par 301. Nous pensons que cette configuration donnera des résultats intéressants car B n'est pas assez grand pour permettre une domination complète des Traîtres ou pas assez petit pour permettre une domination complète des Croyants.

Après quelques tours de la simulation nous observons l'image suivante:

[[Fichier:Screen_première_exp.PNG]]

Nous pouvons voir grâce à la bordure verte que le carré de traîtres au centre de l'image est en train de rétrécir alors que dans les coins des îlots de traîtres apparaissent comme nous le montre la grand quantité de jaune.

Nous passons sous silence quelques tours pour arriver à la situation suivante:

[[Fichier:Screen première exp 2.PNG]]

Nous pouvons voir à présent que les comportements dans la simulation varient beaucoup comme témoignent l'abondance de prisonniers affichés en jaune et en vert.

Lors du déroulé de cette simulation nous avons pus récolter C qui est le rapport entre le nombre de croyants dans la matrice sur le nombre de prisonniers au total. Cette variable nous permettra de visualiser l'évolution du nombre de croyants dans la simulation rapidement. Nous allons maintenant montrer son évolution au court du temps dans la simulation.

[[Fichier:Screen Graph_première exp.PNG]]

Nous pouvons ainsi observer sur le graphique que C semble tendre vers environ 0.3 montrant de ce fait que la simulation est dominé par les traîtres mais que les croyants résistent tout de même. Les variations de C ne sont pas de ce que l'on observe sur le graphique et la simulation cycliques ce qui veut dire que même si le nombre de croyants semble à peut près stable il n'en reste pas moins fluctuant.

== Automatisation des expériences ==

Nous avons pus observer une simulation particulière mais nous devons maintenant pouvoir faire des observations autres que visuelles car nous n’avons pas le temps de le faire pour toutes les expériences permisses par notre modèle. On n’as alors décidé donc de créer un objet dans le programme pour extraire les données des expériences et nous les résumées. Nous ne montrerons toutefois que les expériences que l’on juge intéressantes.

Nous voulons tout d'abord mesurer l'influence de B sur l'évolution d'une répartition aléatoire. Pour cela nous fixerons les paramètres suivants pour chaque simulation. Dans chaque simulation on aura systématiquement 10% de traîtres répartis aléatoirement parmi 90% de croyants. La dimension des matrices sera de 200*200. Nous ferons variez B entre 1.75 et 2.

Pour un B appartenant à [1.75;1.8[ On observe la simulation suivante au bout de 400 tours:

[[Fichier:Screen_B_1,75_10%.PNG]]

On observe des réseaux de traîtres interconnectés entre eux mais pouvant être indépendants avec une taille minimale d'un carré de 4 traîtres. On observe aussi des zones ou les prisonniers alternent entre traître et croyant, on les repères en cherchant les zones en jaune ou en vert.

Le graphique de l'évolution de C est le suivant:

[[Fichier:Screen Graph B 1,75 10%.PNG]]

Ce graphique nous permet d'affirmer que la simulation est à peut près stable car on observe toujours des petits chutes du nombre de croyants. C semble tendre par ailleurs vers 0.7.

Pour un B appartenant à [1.8;2[ On observe la simulation suivante au bout de 400 tours:

[[Fichier:Screen B 1,9 10%.PNG]]

On observe une situation chaotique avec une majorité de Traîtres et des îlots de Croyants apparaissant et disparaissant au fur et à mesure de la simulation. On remarque aussi beaucoup de jaune et de verts sur les images cela nous montre que les comportements des prisonniers changent beaucoup.

Le graphique de l'évolution de C est le suivant:

[[Fichier:Screen Graph B 1,9 10%.PNG]]

Ce graphique nous montre que la simulation n'est pas stable mais que C se stabilise vers 0.3.

Il est aussi à noter que sur les images B est à 1.9 et que plus B tend vers 1.8, C se stabilise vers 0.4.

Pour un B supérieur à 2 On observe la simulation suivante au bout de 400 tours:

[[Fichier:Screen B 2 10%.PNG]]

On observe que les traîtres occupent quasiment tout l'espace et que les croyants sont regroupés en îlots qui s'étendent et se rétrécissent périodiquement.

Le graphique de l'évolution de C est le suivant:

[[Fichier:Screen Graph B 2 10%.PNG]]

Ce graphique nous montre que la simulation est très stable et que C tend vers 0.02.

== Améliorations à apporter ==

Nous n’avons pas exploré toutes les possibilités de notre modèle nous discuterons ici des améliorations à apporter à notre modèle.

La première des améliorations que nous pourrions apporter pourrait être l’introduction de comportements avec un historique des actions passées de leurs voisins. Cela nous permettrait d’avoir des stratégies plus complexes à étudier.

La deuxième amélioration que nous pourrions apporter serait une amélioration au niveau du code. On proposerait de faire en sorte d’avoir un objet Stratégie qui se passerait de prisonnier en prisonnier et grâce à la programmation objet on pourrait créer des Stratégies variées avec peu de changements dans la structure du programme.

== Sources ==

[http://cormas.cirad.fr/fr/applica/dps.htm Lien vers le site du cormas]

[https://www.researchgate.net/publication/216634494_Evolutionary_Games_and_Spatial_Chaos Lien vers l'article original]

Génération et résolution de labyrinthes II

2019-05-19T21:09:30Z

Theodet :

Génération et résolution de labyrinthes II

2019-05-19T21:08:02Z

Theodet : /* Kruskal */

__FORCETOC__[[Fichier:labyrinthe_photo.png|vignette|300px|Labyrinthe généré avec Kruskal et résolu avec le parcours en profondeur. En route foncé, l'entrée. En vert, la sortie. En bleu, le chemin. En rouge clair, les cellules visitées lors de la résolution.|alt="Labyrinthe"]]

On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Et comment trouver la sortie quand on est perdu dans le labyrinthe ?

== Représentation ==

=== Propriétés ===

Un labyrinthe est une grille de cellules reliées, ou non, entre elles.

Deux cellules sont reliées entre elles par une '''porte''', ou séparées par un '''mur'''.

Tout labyrinthe a '''une entrée''' et '''une sortie''', et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est '''unique'''.

=== Modélisation en graphe ===

En théorie des graphes, un graphe est un ensemble de '''points''' (ou nœuds ou sommets) reliés ensemble par des '''lignes''' (ou liens ou arêtes).

[[Fichier:graphe_cyclique.png|vignette|left|300px|Exemple de graphe connexe cyclique non orienté|alt=Graphe cyclique]]

Un graphe peut être '''connexe''' (en un seul morceau) ou '''non connexe''' (en plusieurs morceaux).

Un graphe peut aussi être '''cyclique''' si les points sont reliés en formant une boucle ou '''acyclique'''.

Enfin, un graphe peut être '''orienté''' (si les arêtes sont à sens unique) ou '''non orienté'''.

[[Fichier:Arbre.PNG|vignette|left|300px|Exemple d'arbre|alt=Arbre]]

Un '''arbre''' est un graphe connexe, acyclique et non orienté.

En plaçant un point sur chaque cellule de notre labyrinthe, et en reliant deux cellules séparées par une porte, on peut dessiner un arbre à partir de n'importe quel labyrinthe.

[[Fichier:labyrinthe_avec_arbre.png|vignette|centre|300px|Exemple de labyrinthe avec son arbre. Pour plus de simplicité, on attribue à chaque nœud une position.|alt=Labyrinthe avec arbre]]

== Génération ==

Un labyrinthe rectangulaire de largeur <math> L </math> et de hauteur <math> H </math> contient exactement <math>L \times H - 1</math> portes.

Du point de vue du graphe, il y a donc <math>L \times H - 1</math> arêtes.

Maintenant, comment répartir toutes ces portes de façon à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?

De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal.
Chaque algorithme est différent et produit des labyrinthes visuellement différents.

En effet, si nous comparons un labyrinthe généré avec l'algorithme du parcours en profondeur à un labyrinthe généré avec l'algorithme de Kruskal, bien qu'ils aient tous les deux une solution unique, ils apparaissent néanmoins différents visuellement.

[[Fichier:recursive_backtracker_comparaison.png|vignette|left|500px|Parcours en profondeur. On remarque des chemins proprement dessinés.|alt=Parcours en profondeur]]
[[Fichier:kruskal_comparaison.png|vignette|right|500px|Algorithme de Kruskal. On remarque des murs de 1 de longueur çà et là.|alt=Kruskal]]

=== Parcours en profondeur ===

[[Fichier:recursive_backtracker.gif|vignette|left|500px|Illustration du parcours en profondeur|alt=Parcours en profondeur]]

Dans l'algorithme du parcours en profondeur ("recursive backtracker" en anglais), on commence sur une cellule aléatoire dans le labyrinthe.

On se dirige dans une direction aléatoire et on casse le mur en face, tout en marquant la cellule précédente comme visitée.

Lorsque aucune direction n'est disponible, on remonte à la position précédente.

[[Fichier:pile.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

Pour sauvegarder l'historique des positions, on peut utiliser une '''pile'''.

Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.

Une pile contient 2 méthodes :
* push(elem) : ajoute elem à la pile
* pop() -> elem : retourne le dernier élément de la pile (elem dans notre cas)

Dans mon implémentation de la pile, une erreur est levée si l'on appelle la méthode pop sur une pile vide.

=== Kruskal ===

[[Fichier:kruskal.gif|vignette|left|500px|Illustration de l'algorithme de Kruskal.|alt=Kruskal]]

Alors que pour le parcours en profondeur on partait des cellules, l'algorithme de Kruskal s'applique sur des murs.

On attribue à chaque cellule un identifiant unique.

On choisit un mur aléatoire. Si les cellules séparées par ce mur ont des identifiants différents, on leur associe le même identifiant et on casse le mur.

Sinon, on passe à un autre mur.

[[Fichier:union_find.png|vignette|300px|Représentation d'une structure Union-Find avec find(a,b) et find(b,c).|alt=Union-Find]]

Pour mettre en œuvre cet algorithme, on utilise une structure de données appelée '''Union-Find''', qui permet de mettre en relation des éléments partageant un même représentant (ou un même identifiant).

Il existe plusieurs variantes d'Union-Find, dont notamment la compression de chemin, qui permet de n'avoir qu'un ou deux éléments à parcourir pour obtenir le représentant d'un élément.

Union-Find fonctionne comme un arbre. <math>a</math> a un représentant <math>A</math>, etc..., qui lui même a un représentant <math>\alpha</math>, qui est son propre représentant.

Union-Find est composé de deux méthodes :
* union(a, b) : associe à <math>a</math> et <math>b</math> le même représentant, par exemple <math>A</math> le représentant de <math>a</math>
* find(a) -> <math>\alpha</math> : tant que l'élément n'est pas son propre représentant, on applique find au représentant de l'élément. On commence donc par find(a), puis find(A) (si <math>A</math> est le représentant de <math>a</math>), etc... La méthode de la compression de chemin permet d'éviter trop de récursivité en écrivant : représentant de <math>a</math> := <math>\alpha</math>

=== Labyrinthes cycliques ===

Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.

Cependant, certains algorithmes de résolution n'adopteront pas le même comportement.

== Résolution ==

Il existe là encore de nombreux algorithmes de résolution de labyrinthes, plus ou moins efficaces, et surtout ne fonctionnant pas tous dans les mêmes conditions.

=== Parcours en profondeur ===

Cet algorithme est quasiment identique à celui du parcours en profondeur pour la génération.

Il est très efficace et trouvera une solution en minimisant le nombre de cases visitées.

Il s'adapte aux labyrinthes cycliques. En cas de boucle, il ne fera pas la boucle vu que l'intersection a déjà été visitées, il reviendra sur ses pas.

Il s'adapte aux labyrinthes sans solution. En effet, s'il n'y a pas de sortie, il va revenir à sa position de départ sans position précédente (pile vide) et en ayant parcouru toutes les cases.

=== Mur droit ===

Cet algorithme va suivre de la main droite le mur de droite.

Il est relativement inefficace, et va visiter un grand nombre de cases.

Il s'adapte assez mal aux labyrinthes cycliques. En effet, si la sortie n'est pas dans la même boucle que l'entrée, il ne la trouvera jamais.

Il ne s'adapte pas aux labyrinthes sans solution, et fera le tour de la grille à l'infini.

[[Fichier:labyrinthe_exp_exhaust.png|vignette|left|500px|Labyrinthe résolu en utilisant le parcours en profondeur. 660 cellules visitées, 1179 déplacements, chemin de 142 cellules.|alt=Parcours en profondeur]]
[[Fichier:labyrinthe_right_hand.png|vignette|right|500px|Labyrinthe résolu en utilisant le mur droit. 1068 cellules visitées, 1995 déplacements, chemin de 142 cellules.|alt=Mur droit]]

== Affichage ==

tkinter

[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive tkinter]

== Code ==

Mon projet total contenant plusieurs milliers de lignes de code réparties dans une dizaine de fichiers, je ne peux évidemment pas l'insérer directement dans cette page.

Le code source est disponible sur Github à [https://github.com/Rominos111/Labyrinthe_VISI201 cette adresse]

== Sources ==

Génération
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li>
</ul>

Résolution
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li>
</ul>

Structures de données
<ul>
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li>
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li>
</ul>

Python
<ul>
<li> [https://docs.python.org/3.6/reference/datamodel.html Classes et types de variables personnalisés (en)] </li>
<li> [http://effbot.org/tkinterbook/canvas.htm Canvas Tkinter (en)] </li>
</ul>

Fichier:Union find.png

2019-05-19T20:25:40Z

Theodet :

Génération et résolution de labyrinthes II

2019-05-19T20:20:52Z

Theodet :

__FORCETOC__[[Fichier:labyrinthe_photo.png|vignette|300px|Labyrinthe généré avec Kruskal et résolu avec le parcours en profondeur. En route foncé, l'entrée. En vert, la sortie. En bleu, le chemin. En rouge clair, les cellules visitées lors de la résolution.|alt="Labyrinthe"]]

On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Et comment trouver la sortie quand on est perdu dans le labyrinthe ?

== Représentation ==

=== Propriétés ===

Un labyrinthe est une grille de cellules reliées, ou non, entre elles.

Deux cellules sont reliées entre elles par une '''porte''', ou séparées par un '''mur'''.

Tout labyrinthe a '''une entrée''' et '''une sortie''', et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est '''unique'''.

=== Modélisation en graphe ===

En théorie des graphes, un graphe est un ensemble de '''points''' (ou nœuds ou sommets) reliés ensemble par des '''lignes''' (ou liens ou arêtes).

[[Fichier:graphe_cyclique.png|vignette|left|300px|Exemple de graphe connexe cyclique non orienté|alt=Graphe cyclique]]

Un graphe peut être '''connexe''' (en un seul morceau) ou '''non connexe''' (en plusieurs morceaux).

Un graphe peut aussi être '''cyclique''' si les points sont reliés en formant une boucle ou '''acyclique'''.

Enfin, un graphe peut être '''orienté''' (si les arêtes sont à sens unique) ou '''non orienté'''.

[[Fichier:Arbre.PNG|vignette|left|300px|Exemple d'arbre|alt=Arbre]]

Un '''arbre''' est un graphe connexe, acyclique et non orienté.

En plaçant un point sur chaque cellule de notre labyrinthe, et en reliant deux cellules séparées par une porte, on peut dessiner un arbre à partir de n'importe quel labyrinthe.

[[Fichier:labyrinthe_avec_arbre.png|vignette|centre|300px|Exemple de labyrinthe avec son arbre. Pour plus de simplicité, on attribue à chaque nœud une position.|alt=Labyrinthe avec arbre]]

== Génération ==

Un labyrinthe rectangulaire de largeur <math> L </math> et de hauteur <math> H </math> contient exactement <math>L \times H - 1</math> portes.

Du point de vue du graphe, il y a donc <math>L \times H - 1</math> arêtes.

Maintenant, comment répartir toutes ces portes de façon à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?

De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal.
Chaque algorithme est différent et produit des labyrinthes visuellement différents.

En effet, si nous comparons un labyrinthe généré avec l'algorithme du parcours en profondeur à un labyrinthe généré avec l'algorithme de Kruskal, bien qu'ils aient tous les deux une solution unique, ils apparaissent néanmoins différents visuellement.

[[Fichier:recursive_backtracker_comparaison.png|vignette|left|500px|Parcours en profondeur. On remarque des chemins proprement dessinés.|alt=Parcours en profondeur]]
[[Fichier:kruskal_comparaison.png|vignette|right|500px|Algorithme de Kruskal. On remarque des murs de 1 de longueur çà et là.|alt=Kruskal]]

=== Parcours en profondeur ===

[[Fichier:recursive_backtracker.gif|vignette|left|500px|Illustration du parcours en profondeur|alt=Parcours en profondeur]]

Dans l'algorithme du parcours en profondeur ("recursive backtracker" en anglais), on commence sur une cellule aléatoire dans le labyrinthe.

On se dirige dans une direction aléatoire et on casse le mur en face, tout en marquant la cellule précédente comme visitée.

Lorsque aucune direction n'est disponible, on remonte à la position précédente.

[[Fichier:pile.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

Pour sauvegarder l'historique des positions, on peut utiliser une '''pile'''.

Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.

Une pile contient 2 méthodes :
* push(elem) : ajoute elem à la pile
* pop() -> elem : retourne le dernier élément de la pile (elem dans notre cas)

Dans mon implémentation de la pile, une erreur est levée si l'on appelle la méthode pop sur une pile vide.

=== Kruskal ===

[[Fichier:kruskal.gif|vignette|left|500px|Illustration de l'algorithme de Kruskal|alt=Kruskal]]

Alors que pour le parcours en profondeur on partait des cellules, l'algorithme de Kruskal s'applique sur des murs.

On attribue à chaque cellule un identifiant unique.

On choisit un mur aléatoire. Si les cellules séparées par ce mur ont des identifiants différents, on leur associe le même identifiant et on casse le mur.

[[Fichier:union_find.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

=== Labyrinthes cycliques ===

Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.

Cependant, certains algorithmes de résolution n'adopteront pas le même comportement.

== Résolution ==

Il existe là encore de nombreux algorithmes de résolution de labyrinthes, plus ou moins efficaces, et surtout ne fonctionnant pas tous dans les mêmes conditions.

=== Parcours en profondeur ===

Cet algorithme est quasiment identique à celui du parcours en profondeur pour la génération.

Il est très efficace et trouvera une solution en minimisant le nombre de cases visitées.

Il s'adapte aux labyrinthes cycliques. En cas de boucle, il ne fera pas la boucle vu que l'intersection a déjà été visitées, il reviendra sur ses pas.

Il s'adapte aux labyrinthes sans solution. En effet, s'il n'y a pas de sortie, il va revenir à sa position de départ sans position précédente (pile vide) et en ayant parcouru toutes les cases.

=== Mur droit ===

Cet algorithme va suivre de la main droite le mur de droite.

Il est relativement inefficace, et va visiter un grand nombre de cases.

Il s'adapte assez mal aux labyrinthes cycliques. En effet, si la sortie n'est pas dans la même boucle que l'entrée, il ne la trouvera jamais.

Il ne s'adapte pas aux labyrinthes sans solution, et fera le tour de la grille à l'infini.

[[Fichier:labyrinthe_exp_exhaust.png|vignette|left|500px|Labyrinthe résolu en utilisant le parcours en profondeur. 660 cellules visitées, 1179 déplacements, chemin de 142 cellules.|alt=Parcours en profondeur]]
[[Fichier:labyrinthe_right_hand.png|vignette|right|500px|Labyrinthe résolu en utilisant le mur droit. 1068 cellules visitées, 1995 déplacements, chemin de 142 cellules.|alt=Mur droit]]

== Affichage ==

tkinter

[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive tkinter]

== Code ==

Mon projet total contenant plusieurs milliers de lignes de code réparties dans une dizaine de fichiers, je ne peux évidemment pas l'insérer directement dans cette page.

Le code source est disponible sur Github à [https://github.com/Rominos111/Labyrinthe_VISI201 cette adresse]

== Sources ==

Génération
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li>
</ul>

Résolution
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li>
</ul>

Structures de données
<ul>
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li>
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li>
</ul>

Python
<ul>
<li> [https://docs.python.org/3.6/reference/datamodel.html Classes et types de variables personnalisés (en)] </li>
<li> [http://effbot.org/tkinterbook/canvas.htm Canvas Tkinter (en)] </li>
</ul>

Rest & Pub-Sub : protocole hybride pour l'IoT

2019-05-19T19:28:49Z

Theodet : /* Introduction */

== Introduction ==

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

== MQTT ==
MQTT, Message Queuing Telemetry Transport, est un protocole publish/subscribe se basant sur le protocole TCP/IP.
Il a été créé par Andy Stanford-Clark et Arlen Nipper.

De façon concrète, MQTT permet à des appareils de publier des informations sur un sujet donné sur un broker (un serveur qui fonctionne comme un coursier) qui va les retransmettre aux appareils abonnés à ce sujet.

[[Fichier:Fonctionnement broker mqtt.png|600px]]

MQTT gère aussi la qualité de service (d'une qualité 0 à une qualité 2):

Qualité 0: le client qui publie une donnée ne reçoit aucune information par rapport à la confirmation de son arrivé.

Qualité 1: le client qui publie reçoit la confirmation ou non que la donnée publier à été reçu par le broker.

Qualité 2: le client qui publie reçoit la confirmation ou non que la donnée publier à été reçu par le broker ainsi qu'un message lui indiquant que le client qui s'abonne à reçu la donnée.
===Mosquitto===
Mosquitto est un broker open-source qui se sert du protocole MQTT. Il permet une fois installé de se familiarisé avec MQTT et le "publish/subscribe".

nous nous en somme servit ici en publiant en localhost:

[[Fichier:Mosquitto exemple.png]]

sur un premier terminal on s'abonne à un topic "température" et sur un deuxième terminal, on publie ensuite sur ce même topic des nombres (qui s'apparentent à des température). Au fur et à mesure que nous publions ces informations, nous les recevons sur le premier terminal.
Mosquitto remplit bien ici son rôle de broker.

===Pub/Sub avec Python===

Nous avons ensuite développer un client ''publisher'' et un client ''subscriber'' en python grâce à la librairie paho-mqtt.
Pour plus de simplicité et éviter des problèmes de timing, nous avons tout regrouper en un seul programme:

import paho.mqtt.client as mqtt
import time

broker="test.mosquitto.org"

def envoi_message(client, QoS, message):
print("message reçu :", str(message.payload.decode("utf-8")))

client= mqtt.Client("client_test")
client.on_message=envoi_message

client.connect(broker)
print("connection")
client.loop_start()
client.subscribe("Cafetière/temperature_cafe")
print("Abonnement...")
time.sleep(1)
pub= input("entrez une température (un nombre):")
print("Publication...")
time.sleep(1)
client.publish("Cafetière/temperature_cafe",pub +"°C")
time.sleep(1)
client.disconnect()
print("deconnection")
client.loop_stop()
Comme broker, nous nous somme servit ici d'un broker mit en libre service par mosquitto.

==REST==
REST (Representational State Transfer) aussi appeler restful est une architecture logiciel inventer par Roy Fielding qui se sert des verbes HTTP comme identifiant des opérations et des réponses HTTP comme représentation des ressources.

Une architecture REST est définit par 5 règles/contraintes :

- Client–serveur

- Sans état

- Avec mise en cache

- En couches

- Interface uniforme

===Service pub/sub avec REST===
On peut réaliser un équivalent de service pub/sub avec REST avec des GET et des POST:

Génération et résolution de labyrinthes II

2019-05-17T13:33:47Z

Theodet : /* Génération */

__FORCETOC__[[Fichier:labyrinthe_photo.png|vignette|300px|Labyrinthe généré avec Kruskal et résolu avec le parcours en profondeur. En route foncé, l'entrée. En vert, la sortie. En bleu, le chemin. En rouge clair, les cellules visitées lors de la résolution.|alt="Labyrinthe"]]

On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Et comment trouver la sortie quand on est perdu dans le labyrinthe ?

== Représentation ==

=== Propriétés ===

Un labyrinthe est une grille de cellules reliées, ou non, entre elles.

Deux cellules sont reliées entre elles par une '''porte''', ou séparées par un '''mur'''.

Tout labyrinthe a '''une entrée''' et '''une sortie''', et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est '''unique'''.

=== Modélisation en graphe ===

En théorie des graphes, un graphe est un ensemble de '''points''' (ou nœuds ou sommets) reliés ensemble par des '''lignes''' (ou liens ou arêtes).

[[Fichier:graphe_cyclique.png|vignette|left|300px|Exemple de graphe connexe cyclique non orienté|alt=Graphe cyclique]]

Un graphe peut être '''connexe''' (en un seul morceau) ou '''non connexe''' (en plusieurs morceaux).

Un graphe peut aussi être '''cyclique''' si les points sont reliés en formant une boucle ou '''acyclique'''.

Enfin, un graphe peut être '''orienté''' (si les arêtes sont à sens unique) ou '''non orienté'''.

[[Fichier:Arbre.PNG|vignette|left|300px|Exemple d'arbre|alt=Arbre]]

Un '''arbre''' est un graphe connexe, acyclique et non orienté.

En plaçant un point sur chaque cellule de notre labyrinthe, et en reliant deux cellules séparées par une porte, on peut dessiner un arbre à partir de n'importe quel labyrinthe.

[[Fichier:labyrinthe_avec_arbre.png|vignette|centre|300px|Exemple de labyrinthe avec son arbre. Pour plus de simplicité, on attribue à chaque nœud une position.|alt=Labyrinthe avec arbre]]

== Génération ==

Un labyrinthe rectangulaire de largeur <math> L </math> et de hauteur <math> H </math> contient exactement <math>L \times H - 1</math> portes.

Du point de vue du graphe, il y a donc <math>L \times H - 1</math> arêtes.

Maintenant, comment répartir toutes ces portes de façon à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?

De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal.
Chaque algorithme est différent et produit des labyrinthes visuellement différents.

En effet, si nous comparons un labyrinthe généré avec l'algorithme du parcours en profondeur à un labyrinthe généré avec l'algorithme de Kruskal, bien qu'ils aient tous les deux une solution unique, ils apparaissent néanmoins différents visuellement.

[[Fichier:recursive_backtracker_comparaison.png|vignette|left|500px|Parcours en profondeur. On remarque des chemins proprement dessinés.|alt=Parcours en profondeur]]
[[Fichier:kruskal_comparaison.png|vignette|right|500px|Algorithme de Kruskal. On remarque des murs de 1 de longueur çà et là.|alt=Kruskal]]

=== Parcours en profondeur ===

[[Fichier:recursive_backtracker.gif|vignette|left|500px|Illustration du parcours en profondeur|alt=Parcours en profondeur]]

Dans l'algorithme du parcours en profondeur ("recursive backtracker" en anglais), on commence sur une cellule aléatoire dans le labyrinthe.

On se dirige dans une direction aléatoire et on casse le mur en face, tout en marquant la cellule précédente comme visitée.

Lorsque aucune direction n'est disponible, on remonte à la position précédente.

[[Fichier:pile.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

Pour sauvegarder l'historique des positions, on peut utiliser une '''pile'''.

Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.

Une pile contient 2 méthodes :
* push(elem) : ajoute elem à la pile
* pop() -> elem : retourne le dernier élément de la pile (elem dans notre cas)

Dans mon implémentation de la pile, une erreur est levée si l'on appelle la méthode pop sur une pile vide.

=== Kruskal ===

[[Fichier:kruskal.gif|vignette|left|500px|Illustration de l'algorithme de Kruskal|alt=Kruskal]]

Alors que pour le parcours en profondeur on partait des cellules, l'algorithme de Kruskal s'applique sur des murs.

On attribue à chaque cellule un identifiant unique.

On choisit un mur aléatoire. Si les cellules séparées par ce mur ont des identifiants différents, on leur associe le même identifiant et on casse le mur.

[[Fichier:union_find.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

=== Labyrinthes cycliques ===

Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.

Cependant, certains algorithmes de résolution n'adopteront pas le même comportement.

== Résolution ==

Il existe là encore de nombreux algorithmes de résolution de labyrinthes, plus ou moins efficaces, et surtout ne fonctionnant pas tous dans les mêmes conditions.

=== Parcours en profondeur ===

Cet algorithme est quasiment identique à celui du parcours en profondeur pour la génération.

Il est très efficace et trouvera une solution en minimisant le nombre de cases visitées.

Il s'adapte aux labyrinthes cycliques. En cas de boucle, il ne fera pas la boucle vu que l'intersection a déjà été visitées, il reviendra sur ses pas.

Il s'adapte aux labyrinthes sans solution. En effet, s'il n'y a pas de sortie, il va revenir à sa position de départ sans position précédente (pile vide) et en ayant parcouru toutes les cases.

=== Mur droit ===

Cet algorithme va suivre de la main droite le mur de droite.

Il est relativement inefficace, et va visiter un grand nombre de cases.

Il s'adapte assez mal aux labyrinthes cycliques. En effet, si la sortie n'est pas dans la même boucle que l'entrée, il ne la trouvera jamais.

Il ne s'adapte pas aux labyrinthes sans solution, et fera le tour de la grille à l'infini.

[[Fichier:labyrinthe_exp_exhaust.png|vignette|left|500px|Labyrinthe résolu en utilisant le parcours en profondeur. 660 cellules visitées, 1179 déplacements, chemin de 142 cellules.|alt=Parcours en profondeur]]
[[Fichier:labyrinthe_right_hand.png|vignette|right|500px|Labyrinthe résolu en utilisant le mur droit. 1068 cellules visitées, 1995 déplacements, chemin de 142 cellules.|alt=Mur droit]]

== Affichage ==

tkinter

[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive tkinter]

== Code ==

Mon projet total contenant plusieurs milliers de lignes de code réparties dans une dizaine de fichiers, je ne peux évidemment pas l'insérer directement dans cette page.

Le code source est disponible sur Github à [https://github.com/Rominos111/Labyrinthe_VISI201 cette adresse]

== Sources ==

Génération
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li>
</ul>

Résolution
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li>
</ul>

Structures de données
<ul>
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li>
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li>
</ul>

Python
<ul>
<li> [https://docs.python.org/3.6/reference/datamodel.html Classes et types de variables personnalisés (en)] </li>
<li> [http://effbot.org/tkinterbook/canvas.htm Canvas Tkinter (en)] </li>
</ul>

Fichier:Kruskal.gif

2019-05-17T13:28:56Z

Theodet :

Fichier:Kruskal comparaison.png

2019-05-17T13:25:55Z

Theodet :

Fichier:Recursive backtracker comparaison.png

2019-05-17T13:25:40Z

Theodet :

Génération et résolution de labyrinthes II

2019-05-17T13:21:25Z

Theodet :

__FORCETOC__[[Fichier:labyrinthe_photo.png|vignette|300px|Labyrinthe généré avec Kruskal et résolu avec le parcours en profondeur. En route foncé, l'entrée. En vert, la sortie. En bleu, le chemin. En rouge clair, les cellules visitées lors de la résolution.|alt="Labyrinthe"]]

On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Et comment trouver la sortie quand on est perdu dans le labyrinthe ?

== Représentation ==

=== Propriétés ===

Un labyrinthe est une grille de cellules reliées, ou non, entre elles.

Deux cellules sont reliées entre elles par une '''porte''', ou séparées par un '''mur'''.

Tout labyrinthe a '''une entrée''' et '''une sortie''', et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est '''unique'''.

=== Modélisation en graphe ===

En théorie des graphes, un graphe est un ensemble de '''points''' (ou nœuds ou sommets) reliés ensemble par des '''lignes''' (ou liens ou arêtes).

[[Fichier:graphe_cyclique.png|vignette|left|300px|Exemple de graphe connexe cyclique non orienté|alt=Graphe cyclique]]

Un graphe peut être '''connexe''' (en un seul morceau) ou '''non connexe''' (en plusieurs morceaux).

Un graphe peut aussi être '''cyclique''' si les points sont reliés en formant une boucle ou '''acyclique'''.

Enfin, un graphe peut être '''orienté''' (si les arêtes sont à sens unique) ou '''non orienté'''.

[[Fichier:Arbre.PNG|vignette|left|300px|Exemple d'arbre|alt=Arbre]]

Un '''arbre''' est un graphe connexe, acyclique et non orienté.

En plaçant un point sur chaque cellule de notre labyrinthe, et en reliant deux cellules séparées par une porte, on peut dessiner un arbre à partir de n'importe quel labyrinthe.

[[Fichier:labyrinthe_avec_arbre.png|vignette|centre|300px|Exemple de labyrinthe avec son arbre. Pour plus de simplicité, on attribue à chaque nœud une position.|alt=Labyrinthe avec arbre]]

== Génération ==

Un labyrinthe rectangulaire de largeur <math> L </math> et de hauteur <math> H </math> contient exactement <math>L \times H - 1</math> portes.

Du point de vue du graphe, il y a donc <math>L \times H - 1</math> arêtes.

Maintenant, comment répartir toutes ces portes de façon à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?

De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal.
Chaque algorithme est différent et produit des labyrinthes visuellement différents.

=== Parcours en profondeur ===

[[Fichier:recursive_backtracker.gif|vignette|left|500px|Illustration du parcours en profondeur|alt=Parcours en profondeur]]

Dans l'algorithme du parcours en profondeur ("recursive backtracker" en anglais), on commence sur une cellule aléatoire dans le labyrinthe.

On se dirige dans une direction aléatoire et on casse le mur en face, tout en marquant la cellule précédente comme visitée.

Lorsque aucune direction n'est disponible, on remonte à la position précédente.

[[Fichier:pile.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

Pour sauvegarder l'historique des positions, on peut utiliser une '''pile'''.

Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.

Une pile contient 2 méthodes :
* push(elem) : ajoute elem à la pile
* pop() -> elem : retourne le dernier élément de la pile (elem dans notre cas)

Dans mon implémentation de la pile, une erreur est levée si l'on appelle la méthode pop sur une pile vide.

=== Kruskal ===

Alors que pour le parcours en profondeur on partait des cellules, l'algorithme de Kruskal s'applique sur des murs.

On attribue à chaque cellule un identifiant unique.

On choisit

=== Labyrinthes cycliques ===

Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.

Cependant, certains algorithmes de résolution n'adopteront pas le même comportement.

== Résolution ==

Il existe là encore de nombreux algorithmes de résolution de labyrinthes, plus ou moins efficaces, et surtout ne fonctionnant pas tous dans les mêmes conditions.

=== Parcours en profondeur ===

Cet algorithme est quasiment identique à celui du parcours en profondeur pour la génération.

Il est très efficace et trouvera une solution en minimisant le nombre de cases visitées.

Il s'adapte aux labyrinthes cycliques. En cas de boucle, il ne fera pas la boucle vu que l'intersection a déjà été visitées, il reviendra sur ses pas.

Il s'adapte aux labyrinthes sans solution. En effet, s'il n'y a pas de sortie, il va revenir à sa position de départ sans position précédente (pile vide) et en ayant parcouru toutes les cases.

=== Mur droit ===

Cet algorithme va suivre de la main droite le mur de droite.

Il est relativement inefficace, et va visiter un grand nombre de cases.

Il s'adapte assez mal aux labyrinthes cycliques. En effet, si la sortie n'est pas dans la même boucle que l'entrée, il ne la trouvera jamais.

Il ne s'adapte pas aux labyrinthes sans solution, et fera le tour de la grille à l'infini.

[[Fichier:labyrinthe_exp_exhaust.png|vignette|left|500px|Labyrinthe résolu en utilisant le parcours en profondeur. 660 cellules visitées, 1179 déplacements, chemin de 142 cellules.|alt=Parcours en profondeur]]
[[Fichier:labyrinthe_right_hand.png|vignette|right|500px|Labyrinthe résolu en utilisant le mur droit. 1068 cellules visitées, 1995 déplacements, chemin de 142 cellules.|alt=Mur droit]]

== Affichage ==

tkinter

[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive tkinter]

== Code ==

Mon projet total contenant plusieurs milliers de lignes de code réparties dans une dizaine de fichiers, je ne peux évidemment pas l'insérer directement dans cette page.

Le code source est disponible sur Github à [https://github.com/Rominos111/Labyrinthe_VISI201 cette adresse]

== Sources ==

Génération
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li>
</ul>

Résolution
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li>
</ul>

Structures de données
<ul>
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li>
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li>
</ul>

Python
<ul>
<li> [https://docs.python.org/3.6/reference/datamodel.html Classes et types de variables personnalisés (en)] </li>
<li> [http://effbot.org/tkinterbook/canvas.htm Canvas Tkinter (en)] </li>
</ul>

Génération et résolution de labyrinthes II

2019-05-17T12:16:00Z

Theodet : /* Labyrinthes cycliques */

__FORCETOC__[[Fichier:labyrinthe_photo.png|vignette|300px|Labyrinthe généré avec Kruskal et résolu avec le parcours en profondeur. En route foncé, l'entrée. En vert, la sortie. En bleu, le chemin. En rouge clair, les cellules visitées lors de la résolution.|alt="Labyrinthe"]]

Lorem ipsum

== Représentation ==

=== Propriétés ===

Un labyrinthe est une grille de cellules reliées, ou non, entre elles.

Deux cellules sont reliées entre elles par une '''porte''', ou séparées par un '''mur'''.

Tout labyrinthe a '''une entrée''' et '''une sortie''', et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est '''unique'''.

=== Modélisation en graphe ===

En théorie des graphes, un graphe est un ensemble de '''points''' (ou nœuds ou sommets) reliés ensemble par des '''lignes''' (ou liens ou arêtes).

[[Fichier:graphe_cyclique.png|vignette|left|300px|Exemple de graphe connexe cyclique non orienté|alt=Graphe cyclique]]

Un graphe peut être '''connexe''' (en un seul morceau) ou '''non connexe''' (en plusieurs morceaux).

Un graphe peut aussi être '''cyclique''' si les points sont reliés en formant une boucle ou '''acyclique'''.

Enfin, un graphe peut être '''orienté''' (si les arêtes sont à sens unique) ou '''non orienté'''.

[[Fichier:Arbre.PNG|vignette|left|300px|Exemple d'arbre|alt=Arbre]]

Un '''arbre''' est un graphe connexe, acyclique et non orienté.

En plaçant un point sur chaque cellule de notre labyrinthe, et en reliant deux cellules séparées par une porte, on peut dessiner un arbre à partir de n'importe quel labyrinthe.

[[Fichier:labyrinthe_avec_arbre.png|vignette|centre|300px|Exemple de labyrinthe avec son arbre. Pour plus de simplicité, on attribue à chaque nœud une position.|alt=Labyrinthe avec arbre]]

== Génération ==

Un labyrinthe rectangulaire de largeur <math> L </math> et de hauteur <math> H </math> contient exactement <math>L \times H - 1</math> portes.

Du point de vue du graphe, il y a donc <math>L \times H - 1</math> arêtes.

Maintenant, comment répartir toutes ces portes de façon à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?

De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal.
Chaque algorithme est différent et produit des labyrinthes visuellement différents.

=== Parcours en profondeur ===

[[Fichier:recursive_backtracker.gif|vignette|left|500px|Illustration du parcours en profondeur|alt=Parcours en profondeur]]

Dans l'algorithme du parcours en profondeur ("recursive backtracker" en anglais), on commence sur une cellule aléatoire dans le labyrinthe.

On se dirige dans une direction aléatoire et on casse le mur en face, tout en marquant la cellule précédente comme visitée.

Lorsque aucune direction n'est disponible, on remonte à la position précédente.

[[Fichier:pile.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

Pour sauvegarder l'historique des positions, on peut utiliser une '''pile'''.

Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.

Une pile contient 2 méthodes :
* push(elem) : ajoute elem à la pile
* pop() -> elem : retourne le dernier élément de la pile (elem dans notre cas)

Dans mon implémentation de la pile, une erreur est levée si l'on appelle la méthode pop sur une pile vide.

=== Kruskal ===

Alors que pour le parcours en profondeur on partait des cellules, l'algorithme de Kruskal s'applique sur des murs.

On attribue à chaque cellule un identifiant unique.

On choisit

=== Labyrinthes cycliques ===

Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.

Cependant, certains algorithmes de résolution n'adopteront pas le même comportement.

== Résolution ==

Il existe là encore de nombreux algorithmes de résolution de labyrinthes, plus ou moins efficaces, et surtout ne fonctionnant pas tous dans les mêmes conditions.

=== Parcours en profondeur ===

Cet algorithme est quasiment identique à celui du parcours en profondeur pour la génération.

Il est très efficace et trouvera une solution en minimisant le nombre de cases visitées.

Il s'adapte aux labyrinthes cycliques. En cas de boucle, il ne fera pas la boucle vu que l'intersection a déjà été visitées, il reviendra sur ses pas.

Il s'adapte aux labyrinthes sans solution. En effet, s'il n'y a pas de sortie, il va revenir à sa position de départ sans position précédente (pile vide) et en ayant parcouru toutes les cases.

=== Mur droit ===

Cet algorithme va suivre de la main droite le mur de droite.

Il est relativement inefficace, et va visiter un grand nombre de cases.

Il s'adapte assez mal aux labyrinthes cycliques. En effet, si la sortie n'est pas dans la même boucle que l'entrée, il ne la trouvera jamais.

Il ne s'adapte pas aux labyrinthes sans solution, et fera le tour de la grille à l'infini.

[[Fichier:labyrinthe_exp_exhaust.png|vignette|left|500px|Labyrinthe résolu en utilisant le parcours en profondeur. 660 cellules visitées, 1179 déplacements, chemin de 142 cellules.|alt=Parcours en profondeur]]
[[Fichier:labyrinthe_right_hand.png|vignette|right|500px|Labyrinthe résolu en utilisant le mur droit. 1068 cellules visitées, 1995 déplacements, chemin de 142 cellules.|alt=Mur droit]]

== Affichage ==

tkinter

[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive tkinter]

== Code ==

Mon projet total contenant plusieurs milliers de lignes de code réparties dans une dizaine de fichiers, je ne peux évidemment pas l'insérer directement dans cette page.

Le code source est disponible sur Github à [https://github.com/Rominos111/Labyrinthe_VISI201 cette adresse]

== Sources ==

Génération
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li>
</ul>

Résolution
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li>
</ul>

Structures de données
<ul>
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li>
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li>
</ul>

Python
<ul>
<li> [https://docs.python.org/3.6/reference/datamodel.html Classes et types de variables personnalisés (en)] </li>
<li> [http://effbot.org/tkinterbook/canvas.htm Canvas Tkinter (en)] </li>
</ul>

Génération et résolution de labyrinthes II

2019-05-17T12:15:20Z

Theodet :

__FORCETOC__[[Fichier:labyrinthe_photo.png|vignette|300px|Labyrinthe généré avec Kruskal et résolu avec le parcours en profondeur. En route foncé, l'entrée. En vert, la sortie. En bleu, le chemin. En rouge clair, les cellules visitées lors de la résolution.|alt="Labyrinthe"]]

Lorem ipsum

== Représentation ==

=== Propriétés ===

Un labyrinthe est une grille de cellules reliées, ou non, entre elles.

Deux cellules sont reliées entre elles par une '''porte''', ou séparées par un '''mur'''.

Tout labyrinthe a '''une entrée''' et '''une sortie''', et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est '''unique'''.

=== Modélisation en graphe ===

En théorie des graphes, un graphe est un ensemble de '''points''' (ou nœuds ou sommets) reliés ensemble par des '''lignes''' (ou liens ou arêtes).

[[Fichier:graphe_cyclique.png|vignette|left|300px|Exemple de graphe connexe cyclique non orienté|alt=Graphe cyclique]]

Un graphe peut être '''connexe''' (en un seul morceau) ou '''non connexe''' (en plusieurs morceaux).

Un graphe peut aussi être '''cyclique''' si les points sont reliés en formant une boucle ou '''acyclique'''.

Enfin, un graphe peut être '''orienté''' (si les arêtes sont à sens unique) ou '''non orienté'''.

[[Fichier:Arbre.PNG|vignette|left|300px|Exemple d'arbre|alt=Arbre]]

Un '''arbre''' est un graphe connexe, acyclique et non orienté.

En plaçant un point sur chaque cellule de notre labyrinthe, et en reliant deux cellules séparées par une porte, on peut dessiner un arbre à partir de n'importe quel labyrinthe.

[[Fichier:labyrinthe_avec_arbre.png|vignette|centre|300px|Exemple de labyrinthe avec son arbre. Pour plus de simplicité, on attribue à chaque nœud une position.|alt=Labyrinthe avec arbre]]

== Génération ==

Un labyrinthe rectangulaire de largeur <math> L </math> et de hauteur <math> H </math> contient exactement <math>L \times H - 1</math> portes.

Du point de vue du graphe, il y a donc <math>L \times H - 1</math> arêtes.

Maintenant, comment répartir toutes ces portes de façon à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?

De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal.
Chaque algorithme est différent et produit des labyrinthes visuellement différents.

=== Parcours en profondeur ===

[[Fichier:recursive_backtracker.gif|vignette|left|500px|Illustration du parcours en profondeur|alt=Parcours en profondeur]]

Dans l'algorithme du parcours en profondeur ("recursive backtracker" en anglais), on commence sur une cellule aléatoire dans le labyrinthe.

On se dirige dans une direction aléatoire et on casse le mur en face, tout en marquant la cellule précédente comme visitée.

Lorsque aucune direction n'est disponible, on remonte à la position précédente.

[[Fichier:pile.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

Pour sauvegarder l'historique des positions, on peut utiliser une '''pile'''.

Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.

Une pile contient 2 méthodes :
* push(elem) : ajoute elem à la pile
* pop() -> elem : retourne le dernier élément de la pile (elem dans notre cas)

Dans mon implémentation de la pile, une erreur est levée si l'on appelle la méthode pop sur une pile vide.

=== Kruskal ===

Alors que pour le parcours en profondeur on partait des cellules, l'algorithme de Kruskal s'applique sur des murs.

On attribue à chaque cellule un identifiant unique.

On choisit

=== Labyrinthes cycliques ===

Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.

Cependant, certains algorithmes de résolution n'auront pas le même comportement.

== Résolution ==

Il existe là encore de nombreux algorithmes de résolution de labyrinthes, plus ou moins efficaces, et surtout ne fonctionnant pas tous dans les mêmes conditions.

=== Parcours en profondeur ===

Cet algorithme est quasiment identique à celui du parcours en profondeur pour la génération.

Il est très efficace et trouvera une solution en minimisant le nombre de cases visitées.

Il s'adapte aux labyrinthes cycliques. En cas de boucle, il ne fera pas la boucle vu que l'intersection a déjà été visitées, il reviendra sur ses pas.

Il s'adapte aux labyrinthes sans solution. En effet, s'il n'y a pas de sortie, il va revenir à sa position de départ sans position précédente (pile vide) et en ayant parcouru toutes les cases.

=== Mur droit ===

Cet algorithme va suivre de la main droite le mur de droite.

Il est relativement inefficace, et va visiter un grand nombre de cases.

Il s'adapte assez mal aux labyrinthes cycliques. En effet, si la sortie n'est pas dans la même boucle que l'entrée, il ne la trouvera jamais.

Il ne s'adapte pas aux labyrinthes sans solution, et fera le tour de la grille à l'infini.

[[Fichier:labyrinthe_exp_exhaust.png|vignette|left|500px|Labyrinthe résolu en utilisant le parcours en profondeur. 660 cellules visitées, 1179 déplacements, chemin de 142 cellules.|alt=Parcours en profondeur]]
[[Fichier:labyrinthe_right_hand.png|vignette|right|500px|Labyrinthe résolu en utilisant le mur droit. 1068 cellules visitées, 1995 déplacements, chemin de 142 cellules.|alt=Mur droit]]

== Affichage ==

tkinter

[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive tkinter]

== Code ==

Mon projet total contenant plusieurs milliers de lignes de code réparties dans une dizaine de fichiers, je ne peux évidemment pas l'insérer directement dans cette page.

Le code source est disponible sur Github à [https://github.com/Rominos111/Labyrinthe_VISI201 cette adresse]

== Sources ==

Génération
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li>
</ul>

Résolution
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li>
</ul>

Structures de données
<ul>
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li>
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li>
</ul>

Python
<ul>
<li> [https://docs.python.org/3.6/reference/datamodel.html Classes et types de variables personnalisés (en)] </li>
<li> [http://effbot.org/tkinterbook/canvas.htm Canvas Tkinter (en)] </li>
</ul>

Génération et résolution de labyrinthes II

2019-05-17T12:14:14Z

Theodet : /* Résolution */

__FORCETOC__[[Fichier:labyrinthe_photo.png|vignette|300px|Labyrinthe généré avec Kruskal et résolu avec le parcours en profondeur. En route foncé, l'entrée. En vert, la sortie. En bleu, le chemin. En rouge clair, les cellules visitées lors de la résolution.|alt="Labyrinthe"]]

Lorem ipsum

== Représentation ==

=== Propriétés ===

Un labyrinthe est une grille de cellules reliées, ou non, entre elles.

Deux cellules sont reliées entre elles par une '''porte''', ou séparées par un '''mur'''.

Tout labyrinthe a '''une entrée''' et '''une sortie''', et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est '''unique'''.

=== Modélisation en graphe ===

En théorie des graphes, un graphe est un ensemble de '''points''' (ou nœuds ou sommets) reliés ensemble par des '''lignes''' (ou liens ou arêtes).

[[Fichier:graphe_cyclique.png|vignette|left|300px|Exemple de graphe connexe cyclique non orienté|alt=Graphe cyclique]]

Un graphe peut être '''connexe''' (en un seul morceau) ou '''non connexe''' (en plusieurs morceaux).

Un graphe peut aussi être '''cyclique''' si les points sont reliés en formant une boucle ou '''acyclique'''.

Enfin, un graphe peut être '''orienté''' (si les arêtes sont à sens unique) ou '''non orienté'''.

[[Fichier:Arbre.PNG|vignette|left|300px|Exemple d'arbre|alt=Arbre]]

Un '''arbre''' est un graphe connexe, acyclique et non orienté.

En plaçant un point sur chaque cellule de notre labyrinthe, et en reliant deux cellules séparées par une porte, on peut dessiner un arbre à partir de n'importe quel labyrinthe.

[[Fichier:labyrinthe_avec_arbre.png|vignette|centre|300px|Exemple de labyrinthe avec son arbre. Pour plus de simplicité, on attribue à chaque nœud une position.|alt=Labyrinthe avec arbre]]

== Génération ==

Un labyrinthe rectangulaire de largeur <math> L </math> et de hauteur <math> H </math> contient exactement <math>L \times H - 1</math> portes.

Du point de vue du graphe, il y a donc <math>L \times H - 1</math> arêtes.

Maintenant, comment répartir toutes ces portes de façon à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?

De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal.
Chaque algorithme est différent et produit des labyrinthes visuellement différents.

=== Parcours en profondeur ===

[[Fichier:recursive_backtracker.gif|vignette|left|500px|Illustration du parcours en profondeur|alt=Parcours en profondeur]]

Dans l'algorithme du parcours en profondeur ("recursive backtracker" en anglais), on commence sur une cellule aléatoire dans le labyrinthe.

On se dirige dans une direction aléatoire et on casse le mur en face, tout en marquant la cellule précédente comme visitée.

Lorsque aucune direction n'est disponible, on remonte à la position précédente.

[[Fichier:pile.png|vignette|300px|Représentation d'une pile de positions|alt=Pile]]

Pour sauvegarder l'historique des positions, on peut utiliser une '''pile'''.

Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.

Une pile contient 2 méthodes :
* push(elem) : ajoute elem à la pile
* pop() -> elem : retourne le dernier élément de la pile (elem dans notre cas)

Dans mon implémentation de la pile, une erreur est levée si l'on appelle la méthode pop sur une pile vide.

=== Kruskal ===

Alors que pour le parcours en profondeur on partait des cellules, l'algorithme de Kruskal s'applique sur des murs.

On attribue à chaque cellule un identifiant unique.

On choisit

=== Labyrinthes cycliques ===

Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.

Cependant, certains algorithmes de résolution n'auront pas le même comportement.

== Résolution ==

Il existe là encore de nombreux algorithmes de résolution de labyrinthes, plus ou moins efficaces, et surtout ne fonctionnant pas tous dans les mêmes conditions.

=== Parcours en profondeur ===

Cet algorithme est quasiment identique à celui du parcours en profondeur pour la génération.

Il est très efficace et trouvera une solution en minimisant le nombre de cases visitées.

Il s'adapte aux labyrinthes cycliques. En cas de boucle, il ne fera pas la boucle vu que l'intersection a déjà été visitées, il reviendra sur ses pas.

Il s'adapte aux labyrinthes sans solution. En effet, s'il n'y a pas de sortie, il va revenir à sa position de départ sans position précédente (pile vide) et en ayant parcouru toutes les cases.

=== Mur droit ===

Cet algorithme va suivre de la main droite le mur de droite.

Il est relativement inefficace, et va visiter un grand nombre de cases.

Il s'adapte assez mal aux labyrinthes cycliques. En effet, si la sortie n'est pas dans la même boucle que l'entrée, il ne la trouvera jamais.

Il ne s'adapte pas aux labyrinthes sans solution, et fera le tour de la grille à l'infini.

[[Fichier:labyrinthe_exp_exhaust.png|vignette|left|500px|Labyrinthe résolu en utilisant le parcours en profondeur. 660 cellules visitées, 1179 déplacements, chemin de 142 cellules.|alt=Parcours en profondeur]]
[[Fichier:labyrinthe_right_hand.png|vignette|right|500px|Labyrinthe résolu en utilisant le mur droit. 1068 cellules visitées, 1995 déplacements, chemin de 142 cellules.|alt=Mur droit]]

== Affichage ==

tkinter

[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive tkinter]

== Code ==

Mon projet total contenant plusieurs milliers de lignes de code réparties dans une dizaine de fichiers, je ne peux évidemment pas l'insérer directement dans cette page.

Le code source est disponible sur Github à [https://github.com/Rominos111/Labyrinthe_VISI201 cette adresse]

== Sources ==

Génération
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li>
</ul>

Résolution
<ul>
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li>
</ul>

Structures de données
<ul>
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li>
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li>
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li>
</ul>

Python
<ul>
<li> [https://docs.python.org/3.6/reference/datamodel.html Classes et types de variables personnalisés (en)] </li>
<li> [http://effbot.org/tkinterbook/canvas.htm Canvas Tkinter (en)] </li>
</ul>

Fichier:Labyrinthe right hand.png

2019-05-17T12:11:56Z

Theodet :

Fichier:Labyrinthe exp exhaust.png

2019-05-17T12:11:12Z

Theodet :

Génération et résolution de labyrinthes II

2019-05-17T11:35:02Z

Theodet : /* Code */

Génération et résolution de labyrinthes II

2019-05-17T11:33:28Z

Theodet : /* Sources */

Génération et résolution de labyrinthes II

2019-05-17T11:30:01Z

Theodet : /* Code */

Génération et résolution de labyrinthes II

2019-05-17T10:18:25Z

Theodet : /* Sources */

Génération et résolution de labyrinthes II

2019-05-17T10:04:43Z

Theodet : /* Sources */

Génération et résolution de labyrinthes II

2019-05-17T10:02:43Z

Theodet :

Génération et résolution de labyrinthes II

2019-05-17T09:44:28Z

Theodet : /* Génération */

Génération et résolution de labyrinthes II

2019-05-17T09:40:56Z

Theodet : /* Parcours en profondeur */

Génération et résolution de labyrinthes II

2019-05-17T09:39:38Z

Theodet : /* Modélisation en graphe */

Génération et résolution de labyrinthes II

2019-05-17T09:36:27Z

Theodet : /* Modélisation en graphe */

Génération et résolution de labyrinthes II

2019-05-17T09:35:46Z

Theodet : /* Parcours en profondeur */

Génération et résolution de labyrinthes II

2019-05-17T09:34:55Z

Theodet : /* Kruskal */

Fichier:Pile.png

2019-05-17T09:34:52Z

Theodet :

Génération et résolution de labyrinthes II

2019-05-17T09:31:18Z

Theodet : /* Prim */

Génération et résolution de labyrinthes II

2019-05-17T09:29:36Z

Theodet : /* Code */

Génération et résolution de labyrinthes II

2019-05-17T09:29:28Z

Theodet : /* Code */

Génération et résolution de labyrinthes II

2019-05-17T09:29:16Z

Theodet : /* Code */

Génération et résolution de labyrinthes II

2019-05-17T09:28:04Z

Theodet : /* Code */

Génération et résolution de labyrinthes II

2019-05-17T09:25:30Z

Theodet : /* Parcours en profondeur */

Génération et résolution de labyrinthes II

2019-05-17T09:24:26Z

Theodet : /* Prim */

Génération et résolution de labyrinthes II

2019-05-17T09:19:22Z

Theodet : /* Génération */

Génération et résolution de labyrinthes II

2019-05-17T09:19:01Z

Theodet : /* Génération */

Génération et résolution de labyrinthes II

2019-05-17T09:17:43Z

Theodet : /* Parcours en profondeur */

Génération et résolution de labyrinthes II

2019-05-17T09:14:06Z

Theodet : /* Parcours en profondeur */

Fichier:Recursive backtracker.gif

2019-05-17T09:13:07Z

Theodet :

Génération et résolution de labyrinthes II

2019-05-17T09:09:56Z

Theodet : /* Définition */