Un algo pour sortir d’un labyrinthe

Sortir d’un labyrinthe semble complexe et aléatoire….

…il n’en est rien, une méthode infaillible pour sortir d’un labyrinthe consistera à suivre le mur « toujours du même côté ». Cette stratégie, même si elle n’est pas optimale (il y a souvent « plus rapide ») est cependant toujours gagnante.

J’en vois deux qui trichent…

Seul cas particulier , les labyrinthes « à îlots » (imaginez un gros poteau) : le risque est de tourner indéfiniment autour de lui…jusqu’à creuser sa tombe.

Exemple ci-contre : en mode « priorité » à droite« . Seul un capteur US supplémentaire est nécessaire.

Voici l’algorithme correspondant :

Cette méthode est d’ailleurs celle préconisée par les pompiers pour sortir d’un local sans visibilité (fumée…)

Un très bon site pour construire automatiquement des labyrinthes variés (avec ou sans sa solution) : mazegenerator.net (…in english but not difficult to understand)