Semplificazione del percorso LSRB per robot che seguono linee

Un robot che percorre un labirinto di linee seguendo soltanto la regola della mano sinistra raggiungerà sempre l’arrivo, ma lo farà sempre con un percorso assurdo: scenderà in ogni vicolo cieco, tornerà indietro e si perderà in diramazioni che non portano da nessuna parte. LSRB è il trucco che trasforma questa prima esplorazione goffa in una seconda ottima, usando quasi nessuna memoria e nessuna mappa.

Serve un solo array di caratteri. Questa è l’intera struttura dati.

Quattro simboli

Ogni volta che il robot lascia un incrocio, aggiunge un carattere che descrive cosa ha fatto:

• L — ha girato a sinistra
• S — è andato dritto
• R — ha girato a destra
• B — ha invertito la marcia, cosa che accade solo in un vicolo cieco

Al termine dell’esplorazione, quella stringa è il percorso effettuato. Contiene anche, nascosto al suo interno, il percorso che avrebbero dovuto percorrere.

L’unica intuizione

Ogni B nella stringa segnala un errore: il robot è entrato in una diramazione che non portava da nessuna parte e ha dovuto invertire la marcia. La svolta prima di B e quella dopo facevano entrambe parte di questa deviazione sprecata.

Osserva quindi ogni B insieme ai suoi vicini: una finestra di tre caratteri come L B L. Queste tre mosse hanno portato il robot dentro un vicolo cieco e fuori, lasciandolo rivolto in una certa direzione. Esiste sempre una singola svolta che avrebbe prodotto lo stesso risultato senza la deviazione. Sostituisci la terna con quella svolta e il vicolo cieco scompare dal percorso.

Segui l’esempio. Il robot arriva all’incrocio centrale direzione est e prende il ramo sinistro (L), cioè la diramazione secondaria che va verso nord. Raggiunge un vicolo cieco e inverte la marcia (B). Tornato all’incrocio in direzione sud, prende di nuovo il ramo sinistro (L), che ora punta verso est. Effetto netto: è entrato in direzione est ed è uscito in direzione est. È S, cioè è andato dritto.

Le sei sostituzioni

Esistono soltanto sei finestre possibili, perché il carattere centrale è sempre B e un B non compare mai accanto a un altro B:

Puoi ricavare ogni riga sommando gli angoli delle svolte, contando sinistra come −90°, dritto come 0°, destra come +90° e inversione come 180°. L B L è −90 + 180 − 90 = 0°, cioè S. S B S è 0 + 180 + 0 = 180°, cioè B. La tabella non è qualcosa da memorizzare: nasce dall’aritmetica.

Applica la regola finché non si stabilizza

Una passata non basta. L’eliminazione di una deviazione può accostare due svolte che ora formano una nuova finestra riducibile, quindi esegui scansioni ripetute finché un passaggio completo non modifica più nulla:

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;
    }
  }
}

Una diramazione lunga che si stacca dal corridoio principale viene eliminata un incrocio alla volta, passata dopo passata, finché non ne resta nulla. Quando il ciclo termina, la stringa non contiene più alcun B: questa è la prova che ha finito, perché ogni deviazione residua in vicolo cieco mostrerebbe ancora un B.

Esegui il percorso ottimizzato

La seconda esecuzione è molto più semplice della prima. Non restano decisioni: il robot segue la linea e, a ogni incrocio, consuma il carattere successivo della stringa semplificata e gira di conseguenza. La classificazione dell’incrocio conta ancora—serve a sapere che è stato raggiunto un incrocio—ma la scelta dell’incrocio ora consiste soltanto nel leggere il simbolo successivo.

Ecco perché i robot da labirinto sembrano molto più veloci alla seconda esecuzione. Non è solo perché il percorso è più breve: è che il robot non deve più rallentare, guardare e pensare a ogni incrocio. Puoi aumentare la velocità base per la riproduzione perché ogni svolta è già nota in anticipo.

Che cosa non può fare LSRB

LSRB funziona su un labirinto perfetto, privo di anelli e con esattamente un percorso fra due punti qualsiasi. Se il labirinto contiene un ciclo, la regola della mano sinistra può girare per sempre e le regole di sostituzione non hanno alcun vicolo cieco da eliminare.

Quando sono possibili anelli servono una mappa reale e una ricerca nel grafo. È il territorio del flood fill, che costruisce un campo di distanze sull’intero labirinto e lo segue in discesa, e che il simulatore di risoluzione dei labirinti esegue dopo la fase di esplorazione. LSRB è lo strumento giusto quando il labirinto è un albero—che è quasi sempre il caso dei labirinti lineari a nastro—e costa poche decine di byte, mentre il flood fill costa un’intera griglia.