Simplificação de caminho LSRB para robôs de labirinto de linhas

Um robô de labirinto de linhas que siga apenas a regra da mão esquerda sempre chegará ao destino, mas fará uma rota absurda para chegar lá — entrando em cada beco sem saída, saindo dele novamente e percorrendo ramos que não levavam a lugar nenhum. O LSRB é o truque que transforma essa primeira execução desajeitada em uma segunda execução ótima, usando quase nenhuma memória e nenhum mapa.

Ele precisa apenas de um vetor de caracteres. Essa é toda a estrutura de dados.

Quatro símbolos

Toda vez que o robô deixa uma interseção, acrescenta um caractere que descreve o que fez:

• L — virou à esquerda
• S — seguiu em frente
• R — virou à direita
• B — voltou, o que acontece somente em um beco sem saída

Após a execução de exploração, essa sequência é o caminho percorrido. Ela também contém, escondida em seu interior, o caminho que deveria ter sido percorrido. Em outras palavras, a sequência funciona como a memória da rota.

A única ideia

Cada B na sequência marca um erro: o robô entrou em um ramo que não levava a lugar nenhum e precisou dar ré para sair. O movimento antes do B e o movimento depois dele faziam parte desse desvio desperdiçado.

Portanto, observe cada B junto com seus vizinhos — uma janela de três caracteres como L B L. Esses três giros levaram o robô a um beco sem saída e de volta, deixando-o orientado para alguma direção. Sempre existe um único giro que produziria o mesmo resultado sem o desvio. Substitua o trio por esse giro e o beco sem saída desaparece da rota.

Siga o exemplo. O robô chega à interseção central com orientação para leste e pega o ramo à esquerda (L), que aponta para o norte. Ele encontra um beco sem saída e dá ré (B). De volta à interseção, com orientação para o sul, pega novamente o ramo à esquerda (L), que agora aponta para o leste. Efeito líquido: entrou com orientação para leste e saiu com orientação para leste. Isso é S — seguir em frente.

As seis substituições

Existem apenas seis janelas possíveis, porque o caractere central é sempre B e um B nunca aparece ao lado de outro B:

Você pode obter cada linha somando os ângulos de giro, contando esquerda como −90°, frente como 0°, direita como +90° e retorno como 180°. L B L é −90 + 180 − 90 = 0°, que corresponde a S. S B S é 0 + 180 + 0 = 180°, que corresponde a B. A tabela não precisa ser memorizada — ela decorre da aritmética.

Aplique até estabilizar

Uma passagem não basta. Reduzir um desvio pode unir dois movimentos que agora formam uma nova janela redutível; portanto, examine repetidamente até que uma passagem completa não produza nenhuma alteração:

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

Um ramo longo que sai do corredor principal é reduzido uma interseção por vez, passagem após passagem, até não restar nada dele. Quando o laço termina, a sequência não contém nenhum B — o que prova que a simplificação acabou, pois qualquer desvio restante em direção a um beco sem saída ainda mostraria um.

Executando a rota otimizada

A segunda execução é muito mais simples que a primeira. Não restam decisões: o robô segue a linha e, em cada interseção, consome o próximo caractere da sequência simplificada e gira de acordo. A classificação da interseção continua importante — o robô precisa saber que chegou a uma interseção — mas a escolha do ramo agora significa apenas ler o próximo símbolo.

É por isso que robôs de labirinto parecem muito mais rápidos na segunda execução. Não é apenas porque a rota é mais curta; é porque o robô não precisa mais desacelerar, observar e decidir em cada cruzamento. Você pode aumentar a velocidade de base durante a segunda execução porque cada movimento já é conhecido com antecedência.

O que o LSRB não pode fazer

O LSRB funciona em um labirinto perfeito — um labirinto sem ciclos e com exatamente um caminho entre quaisquer dois pontos. Se houver um ciclo, a regra da mão esquerda pode percorrê-lo indefinidamente, e as regras de substituição não terão um desvio de beco sem saída para reduzir.

Assim que os ciclos forem possíveis, você precisará de um mapa real e de uma busca em grafos. Esse é o domínio do preenchimento por inundação, que constrói um campo de distância em todo o labirinto e o percorre em direção aos valores menores, e que o Simulador de Labirintos executa após a fase de exploração. O LSRB é a ferramenta certa quando o labirinto é uma árvore — o que os labirintos de linhas com fita quase sempre são — e consome algumas dezenas de bytes, enquanto o preenchimento por inundação precisa de uma grade inteira.