Simplification de trajectoire LSRB pour robots de labyrinthe

Un robot de labyrinthe suiveur de ligne qui applique uniquement la règle de la main gauche atteindra toujours l’arrivée, mais au prix d’un parcours absurde — chaque impasse explorée puis rebroussée, chaque branche qui ne menait nulle part. LSRB est l’astuce qui transforme ce premier passage maladroit en un second passage optimal, avec presque aucune mémoire et sans aucune carte.

Il faut un seul tableau de caractères. C’est toute la structure de données.

Quatre symboles

Chaque fois que le robot quitte une intersection, il ajoute un caractère décrivant son action :

• L — a tourné à gauche
• S — est allé tout droit
• R — a tourné à droite
• B — a fait demi-tour, ce qui n’arrive qu’en impasse

Après le parcours d’exploration, cette chaîne est le chemin parcouru. Elle contient aussi, enfoui à l’intérieur, le chemin qui aurait dû être suivi.

L’idée unique

Chaque B dans la chaîne marque une erreur : le robot est entré dans une branche sans issue et a dû en ressortir en marche arrière. Le virage avant le B et celui après faisaient tous deux partie de ce détour inutile.

Regardez donc chaque B avec ses voisins — une fenêtre de trois caractères comme L B L. Ces trois mouvements ont mené le robot dans une impasse puis l’en ont ressorti, en le laissant face à une certaine direction. Il existe toujours un virage unique qui aurait produit le même résultat sans le détour. Remplacez le triplet par ce virage unique et l’impasse disparaît de l’itinéraire.

Suivez l’exemple. Le robot arrive à l’intersection centrale vers l’est et prend la branche de gauche (L), qui est l’embranchement vers le nord. Il bute sur une impasse et fait demi-tour (B). De retour à l’intersection vers le sud, il prend de nouveau la branche de gauche (L), qui pointe désormais vers l’est. Effet net : entré vers l’est, ressorti vers l’est. C’est S — tout droit.

Les six substitutions

Il n’existe que six fenêtres possibles, car le caractère central est toujours B et un B ne touche jamais un autre B :

Vous pouvez retrouver chaque ligne en additionnant les angles de virage, en comptant gauche comme −90°, tout droit comme 0°, droite comme +90° et demi-tour comme 180°. L B L vaut −90 + 180 − 90 = 0°, soit S. S B S vaut 0 + 180 + 0 = 180°, soit B. Le tableau n’est pas à apprendre par cœur — il découle du calcul.

Appliquer jusqu’à stabilisation

Un seul passage ne suffit pas. Réduire un détour peut rapprocher deux virages qui forment alors une nouvelle fenêtre réductible, il faut donc balayer la chaîne jusqu’à ce qu’un passage complet ne change plus rien :

void simplify(String& path) {
  bool changed = true;
  while (changed) {                       // a collapse can expose another
    changed = false;
    for (int i = 0; i + 2 < path.length(); i++) {
      if (path[i + 1] != 'B') continue;   // only windows centred on a turn-back
      path = path.substring(0, i) + fold(path[i], path[i + 2])
                                   + path.substring(i + 3);
      changed = true;
      break;
    }
  }
}

Une longue branche partant du couloir principal se réduit intersection par intersection, passage après passage, jusqu’à ce qu’il n’en reste rien. Quand la boucle se termine, la chaîne ne contient plus aucun B — c’est la preuve qu’elle est terminée, car tout détour restant afficherait encore un B.

Exécuter l’itinéraire optimisé

Le second passage est bien plus simple que le premier. Il ne reste aucune décision : le robot suit la ligne, et à chaque intersection il consomme le caractère suivant de la chaîne simplifiée puis tourne en conséquence. La classification des intersections compte toujours — il doit savoir qu’il a atteint une intersection — mais le choix consiste désormais à lire le symbole suivant.

C’est pourquoi les robots de labyrinthe semblent tellement plus rapides au second passage. Ce n’est pas seulement que l’itinéraire est plus court ; c’est que le robot n’a plus besoin de ralentir, d’observer et de réfléchir à chaque croisement. Vous pouvez augmenter la vitesse de base pour la répétition, car chaque virage est connu à l’avance.

Ce que LSRB ne sait pas faire

LSRB fonctionne sur un labyrinthe parfait — sans boucles, avec exactement un chemin entre deux points quelconques. Si le labyrinthe contient un cycle, la règle de la main gauche peut tourner en rond indéfiniment et les règles de substitution n’ont aucune impasse à réduire.

Dès que des boucles sont possibles, il faut une vraie carte et une recherche de graphe. C’est le domaine du remplissage par diffusion, qui construit un champ de distances sur tout le labyrinthe puis le descend, et que le simulateur de résolution de labyrinthe exécute après sa phase d’exploration. LSRB est l’outil adapté quand le labyrinthe est un arbre — ce qui est presque toujours le cas des labyrinthes de ligne adhésive — et il coûte quelques dizaines d’octets là où le remplissage par diffusion exige une grille complète.