Étape 4: Résoudre le labyrinthe - la règle de la main gauche
Tel que discuté à l’introduction, la majorité des labyrinthes, toutefois complexe leur conception peut apparaître, étaient essentiellement formé d’un mur continu avec beaucoup de jonctions et de branches. Si le mur qui entoure l’objectif d’un labyrinthe est branché sur le périmètre du labyrinthe à l’entrée, le labyrinthe peut toujours être résolu en gardant une main en contact avec le mur, cependant de nombreux détours pouvant impliquer. Ces labyrinthes « simples » sont appelés correctement « Simplement connecté. »
La recherche sur Wikipedia, nous apprenons que «le suiveur de mur est la règle plus connue permettant de parcourir des labyrinthes. Il est également connu sous le nom de la règle gauche ou la droite règle. Si le labyrinthe est simplement connexe, c'est-à-dire tous ses murs sont connectés ensemble ou à la limite extérieure de la maze, puis en gardant une main en contact avec un mur du labyrinthe le solveur est garanti de ne pas se perdre et atteindra une sortie différente s’il y en a un ; Sinon, elle retourne à l’entrée ayant parcouru chaque corridor à côté qui reliait section des murs au moins une fois."
En bref, la règle de la main gauche peut être décrite comme :
- Placez votre main gauche sur le mur.
- Commencer à marcher vers l’avant
- À tous les carrefourset tout au long du labyrinthe, gardez votre main gauche touche le mur sur votre gauche.
- Finalement, vous arriverez à la fin du labyrinthe. Vous allez sans doute pas le moyen le plus court et plus direct, mais vous y arriverez.
Donc, la clé ici est d’identifier les intersections, définir quel cours à prendre selon les règles ci-dessus. Plus précisément dans notre genre de labyrinthe 2D, on retrouve 8 différents types d’intersections (voir la photo 1) :
En regardant la photo, nous pouvons réaliser que les actions possibles aux intersections sont :
- À une « croix »
- Aller à gauche
- Aller à droite
- Aller tout droit
- À un « T » :
- Aller à gauche
- Aller à droite
- À un droit uniquement :
- Aller à droite
- À gauche seulement :
- Aller à gauche
- À droite ou à gauche :
- Aller à gauche
- Aller tout droit
- À la droite ou vers la droite :
- Aller à droite
- Aller tout droit
- Dans une impasse :
- Aller retour ("U turn")
- À la fin du labyrinthe :
- Arrêter
Mais, en appliquant la « règle de la main gauche », les actions seront réduites à une seule option de chaque :
- À une « croix »: aller à gauche
- À un « T »: aller à gauche
- En un seul à droite : aller à droite
- À gauche seulement : aller à gauche
- À droite ou à gauche : aller à gauche
- À droite ou de droite : allez tout droit
- Dans une impasse : aller retour ("U turn")
- À la fin du labyrinthe : arrêter
Nous sommes presque là. Lorsque le robot atteint une impasse et à la fin d’un labyrinthe, il est facile de l’identifier car il n’existe pas des situations ambiguës (nous avons déjà mis en place ces actions sur le Robot suiveur de ligne). Le problème c’est quand le robot trouver une « ligne » par exemple, parce qu’une ligne peut être une « croix » (1) ou un "T" (2). Lorsqu’il atteint une « gauche ou droite tour », ceux qui peuvent également être les options d’aller directement ou un simple tour (options 3 ou 4) (5 ou 6). Pour découvrir exactement de quel type d’intersection, le robot est, il faut une étape supplémentaire : le robot doit exécuter un supplément « pouce » et voir ce qui est prévu (voir la photo 2 par exemple).
Donc, en termes de flux, que les actions possibles peuvent être maintenant décrire comme :
- Dans une impasse : aller retour ("U turn")
- Dans la ligne :
- Exécuter un supplément de pouce
- S’il y a une ligne : c’est une « croix » == > aller vers la gauche
- S’il n’y a pas de ligne : c’est un « T » == > aller vers la gauche
- S’il y a une autre ligne : c’est la fin du labyrinthe == > STOP
- À un virage à droite :
- Exécuter un supplément de pouce
- s’il y a une ligne : c’est une ligne droite ou droite == > aller directement
- S’il n’y a pas de ligne : c’est un droit que == > aller à droite
- À un virage à gauche :
- Exécuter un supplément de pouce
- s’il y a une ligne : c’est une ligne droite ou gauche == > aller gauche
- S’il n’y a pas de ligne : c’est une gauche seulement == > aller vers la gauche
Noter qu’en fait, dans le cas d’un « virage à gauche", vous pouvez passer le test, car vous prendrez gauche de toute façon. J’ai quitté l’explication plus générique uniquement par souci de clarté. Le code réel j’ignore cet essai.
(le diagramme 3, montre un labyrinthe très simple sur mon plancher de lab, que j’utilise à des fins de test) :
