Résolution d'un labyrinthe
Un algorithme peut aussi trouver la sortie d'un labyrinthe
Résolution d'un labyrinthe
Un labyrinthe est un tracé sinueux, muni ou non d'embranchements, d'impasses et de fausses pistes, destiné à perdre ou à ralentir celui qui cherche à s'y déplacer.
Lors de ma seconde année de DUT Informatique, en 2014, nous devions réaliser un projet informatique dans le cadre des modélisations mathématiques. Mes partenaires et moi avions choisi de réaliser un algorithme qui pourrait résoudre la plupart des labyrinthes.
En se documentant, nous nous sommes rendu compte que beaucoup d'algorithmes existaient pour sortir d'un labyrinthe (et même si on y est plongé dans le noir !). Cette curiosité de la représentation d'un labyrinthe en mathématiques et en informatique nous a donné envie d'approfondir notre travail. Nous avons ainsi rendu avec l'algorithme, une interface graphique représentant un labyrinthe et son chemin de sortie généré.
Mais alors comment avons-nous fait pour dessiner un labyrinthe et rendre son apparence dynamique avec la programmation informatique ? Et bien nous avons déduit qu'un labyrinthe est tout simplement une matrice constituée de cases où certaines sont des murs et où d'autres sont des chemins. Et en programmation informatique, une matrice est très simple à réaliser car c'est en fait un tableau à deux dimensions. Ensuite, pour distinguer les murs des chemins, nous nous sommes servis d'une numérotation binaire : 1 et 0. Le numéro 1 représente un mur et le numéro 0 un chemin. Au final nous avions donc un tableau qui ressemble à ceci dans le code :
grille = new int[][]{
{ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 1 },
{ 1, 1, 0, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 0, 1, 0, 1, 1, 1, 0, 1 },
{ 1, 0, 1, 1, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 0, 1, 1, 1, 0, 1 },
{ 1, 0, 1, 1, 0, 1, 0, 0, 0, 1 },
{ 1, 0, 0, 1, 0, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 0, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 0, 0 }
};
Enfin, pour le rendre visible à l'écran, nous avons remplacé les 1 par une image noire (pour représenter les murs) et les 0 par une image blanche (pour représenter les chemins). Le rendu est le suivant :
L'algorithme de résolution et son fonctionnement sont expliqués en détail dans le rapport du projet disponible en PDF ci-dessous.