Simplificacion de rutas LSRB para robots de laberintos de linea

Un robot de laberinto de lineas que solo sigue la regla de la mano izquierda siempre llegara a la meta, y siempre lo hara por una ruta ridicula: bajando por cada callejon sin salida, saliendo otra vez, vagando por ramas que no llevaban a ninguna parte. LSRB es el truco que convierte esa primera pasada torpe en una segunda pasada optima, usando casi nada de memoria y ningun mapa en absoluto.

Necesita un array de caracteres. Esa es toda la estructura de datos.

Cuatro simbolos

Cada vez que el robot sale de un cruce, anade un caracter que describe lo que hizo:

• L: giro a la izquierda
• S: siguio recto
• R: giro a la derecha
• B: dio media vuelta, lo que solo ocurre en un callejon sin salida

Despues de la pasada de exploracion, esa cadena es la ruta recorrida. Tambien es, enterrada dentro de ella, la ruta que se deberia haber recorrido.

La unica idea clave

Cada B de la cadena marca un error: el robot entro en una rama que no llevaba a ninguna parte y tuvo que salir marcha atras. El giro anterior al B y el giro posterior formaron parte ambos de ese desvio desperdiciado.

Asi que mira cada B junto con sus vecinos: una ventana de tres caracteres como L B L. Esos tres movimientos metieron al robot en un callejon sin salida y lo sacaron de el, dejandolo mirando en cierta direccion. Siempre existe un unico giro que habria producido el mismo resultado sin el desvio. Sustituye el trio por ese unico giro y el callejon sin salida desaparece de la ruta.

Sigue el ejemplo. El robot llega al cruce central rumbo al este y toma la rama izquierda (L), que es el ramal que va hacia el norte. Se topa con un callejon sin salida y da media vuelta (B). De vuelta en el cruce rumbo al sur, vuelve a tomar la rama izquierda (L), que ahora apunta al este. Efecto neto: entro rumbo al este y salio rumbo al este. Eso es S: recto.

Las seis sustituciones

Solo hay seis ventanas que pueden aparecer, porque el caracter central siempre es B y un B nunca aparece junto a otro B:

Puedes deducir cada fila sumando angulos de giro, contando la izquierda como -90°, el recto como 0°, la derecha como +90° y la media vuelta como 180°. L B L es -90 + 180 - 90 = 0°, que es S. S B S es 0 + 180 + 0 = 180°, que es B. La tabla no es algo que memorizar: sale de la aritmetica.

Aplicarlo hasta que se estabilice

Una pasada no basta. Compactar un desvio puede juntar dos giros que ahora forman una nueva ventana reducible, asi que recorres la cadena repetidamente hasta que una pasada completa no cambie nada:

void simplify(String& path) {
  bool changed = true;
  while (changed) {                       // un compactado puede destapar otro
    changed = false;
    for (int i = 0; i + 2 < path.length(); i++) {
      if (path[i + 1] != 'B') continue;   // solo ventanas centradas en una media vuelta
      path = path.substring(0, i) + fold(path[i], path[i + 2])
                                   + path.substring(i + 3);
      changed = true;
      break;
    }
  }
}

Una rama larga que sale del pasillo principal se compacta cruce a cruce, pasada tras pasada, hasta que no queda nada de ella. Cuando el bucle termina, la cadena no contiene ningun B, lo que es la prueba de que ha terminado, ya que cualquier desvio por callejon sin salida que quedara mostraria todavia uno.

Recorrer la ruta optimizada

La segunda pasada es mucho mas sencilla que la primera. Ya no quedan decisiones: el robot sigue la linea, y en cada cruce consume el siguiente caracter de la cadena simplificada y gira en consecuencia. La clasificacion de cruces sigue importando (necesita saber que ha llegado a un cruce), pero la eleccion de rama ahora es solo leer el siguiente simbolo.

Por eso los robots de laberinto parecen mucho mas rapidos en su segunda pasada. No es solo que la ruta sea mas corta; es que el robot ya no tiene que frenar, mirar y pensar en cada interseccion. Puedes subir la velocidad base para la repeticion porque cada giro se conoce de antemano.

Lo que LSRB no puede hacer

LSRB funciona en un laberinto perfecto: uno sin bucles, con exactamente un camino entre dos puntos cualesquiera. Si el laberinto contiene un ciclo, la regla de la mano izquierda puede dar vueltas para siempre y las reglas de sustitucion no tienen ningun callejon sin salida que compactar.

Cuando hay bucles posibles necesitas un mapa de verdad y una busqueda en grafo. Ese es el terreno del flood fill, que construye un campo de distancias sobre todo el laberinto y desciende por el, y que el simulador de resolucion de laberintos ejecuta despues de su fase de exploracion. LSRB es la herramienta adecuada cuando el laberinto es un arbol (que es lo que casi siempre son los laberintos de cinta) y cuesta unas pocas decenas de bytes donde el flood fill cuesta una rejilla completa.