Il y a quantité d'algorithmes pour sortir de labyrinthes (l'un des plus célébres est celui de Dijkstra ) , nous décrirons une solution que nous éspérons assez simple et compréhensible. Nous l'avons essayée avec succés dans différents petits labyrinthes, ce qui ne veut pas dire qu'il n'y ait pas de cas ou elle échoue! On ne peux pas tester tout!.
Nous nous limiterons au cas simplifié ou le robot se déplace sur un quadrillage formé de cases carrées et n'a que 4 directions de déplacement: vers le nord (=N=le haut ) , vers l'est (=E=droite), vers le sud (=S=bas) , vers l'est (=E=gauche). Il pourra donc : avancer, reculer, tourner a droite (à 90 degrés) , tourner à gauche (à 90 degrés).
Ce labyrinthe peut représenter le plan d'une pièce de la maison avec ses murs et différents meubles qui l' encombrent et on veut que le robot s'y déplace sans accrochages!
On considérera que le labyrinthe a une seule sortie.
Le labyrinthe est constitué par les murs qui le délimitent à l' extérieur et des cloisons intérieures,. On les représente en décidant que le bord de la case correspondante est épais. Il est interdit au robot de traverser ces obstacles !
Ces cases sont numérotés en partant du coin de l' espace de déplacement ,en haut et a gauche (case[0,0] ) et stockées dans un tableau avec leur code de distance à la sortie.
Pour éviter de traverser les murs , on a dans deux tableaux les bordures verticales et horizontales des cases : quand leur épaisseur est à zéro on peut passer , sinon le passage est interdit.
On peut représenter ce labyrinthe sur un écran , en utilisant les fonctions graphiques du C# ( GDI) , on trace les obstacles en traits noirs épais et le robot est représenté par un simple carré rouge qui permet de suivre les déplacements du robot avant de commencer à commander un robot réel.
Dans ce cas simplifié on a attribué un code à chaque cellule en partant de la case de sortie (code = 1) et en augmentant le code à mesure qu'on s' éloigne de la sortie en suivant différents chemins . En partant d'une case du quadrillage ( attention le robot démarre toujours avec le nez dirigé vers le Nord) il suffit de suivre une série de cases dont les codes vont en décroissant pour arriver à la sortie (on s' arrête quand le code =1).
Lorsqu'on est en case[X,Y] , pour explorer les 4 cases voisines nous avons choisi de partir du Nord et de tourner dans le sens des aiguilles d'une montre (N, E ,S ,O) . La première case qui est accessible (pas de mur de son coté) et dont le code est inférieur au code actuel devient à son tour la case actuelle ,le robot se déplace sur cette case, et on recommence a explorer les cases autour.
Si on a bien codé les différentes cases tout se passe bien, mais il faut qu'un humain ait rempli la table des codes
Pour coder les cases on peut opérer comme suit (ce n'est sans doute pas la meilleure méthode mais ça marche et on comprend assez bien comment ) :
(le codage obtenu est moins efficace que celui <fait main> mais c'est plus confortable et plus rapide à adapter à un autre labyrinthe)
Même si le programme fonctionne correctement , le trajet d'un robot réel se décalera par rapport au parcours théorique .
Réguliérement on peut repérer avec 4 détecteurs infra rouge les distances aux murs du labyrinthe et réajuster la position.Pour cela il faut retenir que les détecteurs ont une zone de détection ou ils sont plus performants( entre 15 et 30 cm pour les Sharp que j'ai) et comme leur sensibilité est variable il faut etalonner ses détecteurs pour déterminer le seuil de signal qui fait modifier la trajectoire. Alors ,si on détecte un mur plus prés que prévu à droite on fait tourner le robot d'un petit angle vers la gauche.