LSRB-padvereenvoudiging voor lijnmazrobots

Een lijnmazrobot die alleen de linkervolgeregel volgt, komt altijd aan en neemt altijd een belachelijke route om daar te komen—elke doodlopende gang in, weer terug, door takken die nergens heen leidden. LSRB is de truc die die eerste onhandige ronde in een optimale tweede ronde verandert, met bijna geen geheugen en helemaal geen kaart.

Het heeft één rij van tekens nodig. Dat is de hele datastructuur.

Vier symbolen

Elke keer dat de robot een kruispunt verlaat, voegt hij één teken toe dat beschrijft wat hij deed:

• L — linksaf geslagen
• S — rechtdoor gegaan
• R — rechtsaf geslagen
• B — omgedraaid, wat alleen op een dood eind gebeurt

Na de verkenning is die string de afgelegde route. Er zit ook, diep erin verborgen, de route in die je had moeten nemen.

Het ene inzicht

Elke B in de string markeert een fout: de robot betrad een tak die nergens heen leidde en moest terugkeren. De bocht vóór de B en de bocht erna waren allebei onderdeel van die verspilde omweg.

Bekijk dus elke B samen met zijn buren—een venster van drie tekens zoals L B L. Die drie stappen voerden de robot een dood eind in en weer uit en lieten hem in een bepaalde richting staan. Er is altijd één bocht die hetzelfde resultaat had gegeven zonder de omweg. Vervang de drietal door die ene bocht en de doodlopende gang verdwijnt uit de route.

Volg het voorbeeld. De robot komt oostwaarts bij het middelste kruispunt en neemt de linkertak (L), de zijgang die noordwaarts loopt. Hij loopt dood en keert om (B). Terug bij het kruispunt, nu zuidwaarts, neemt hij opnieuw de linkertak (L), die nu oostwaarts wijst. Netto effect: hij ging erin oostwaarts en eruit oostwaarts. Dat is S—rechtdoor.

De zes vervangingen

Er zijn maar zes vensters mogelijk, want het middelste teken is altijd B en een B staat nooit naast een andere B:

Elke rij kun je afleiden door de bochthoeken op te tellen, met links als −90°, rechtdoor als 0°, rechts als +90° en omkeren als 180°. L B L is −90 + 180 − 90 = 0°, en dat is S. S B S is 0 + 180 + 0 = 180°, en dat is B. De tabel is niets om uit je hoofd te leren—hij valt er rekenkundig uit.

Toepassen tot het bezinkt

Eén doorloop is niet genoeg. Het inklappen van een omweg kan twee bochten tegen elkaar aan leggen die nu een nieuw reduceerbaar venster vormen, dus herhaal de scan tot een volledige doorloop niets meer verandert:

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

Een lange tak vanuit de hoofdgang klapt kruispunt voor kruispunt in, doorloop na doorloop, tot er niets van over is. Als de lus eindigt, bevat de string helemaal geen B meer—en dat is het bewijs dat hij klaar is, want elke overgebleven doodlopende omweg zou er nog één tonen.

De geoptimaliseerde route rijden

De tweede ronde is veel eenvoudiger dan de eerste. Er zijn geen keuzes meer: de robot volgt de lijn en neemt bij elk kruispunt het volgende teken uit de vereenvoudigde string en slaat dienovereenkomstig af. De classificatie van kruispunten is nog steeds van belang—hij moet weten dat hij een kruispunt bereikt heeft—maar de keuze is nu alleen nog het volgende symbool lezen.

Daarom lijken mazrobots op hun tweede ronde zo veel sneller. Het is niet alleen dat de route korter is; het is dat de robot niet meer bij elke kruising hoeft af te remmen, te kijken en te nadenken. Je kunt de basis-snelheid voor de herhaling omhoog tillen, want elke bocht is van tevoren bekend.

Wat LSRB niet kan

LSRB werkt op een perfecte maze—een zonder lussen, met precies één pad tussen elk willekeurig paar punten. Zit er een cyclus in de maze, dan kan de linkervolgeregel eeuwig blijven cirkelen en hebben de vervangingsregels geen dood eind om in te klappen.

Zodra lussen mogelijk zijn, heb je een echte kaart en een grafiekzoekactie nodig. Dat is het terrein van flood fill, dat een afstandsveld over de hele maze opbouwt en daarin afdaalt, en dat de Maze Solver Simulator na zijn verkenningsfase draait. LSRB is het juiste gereedschap wanneer de maze een boom is—en dat zijn met tape gelegde lijnmazes vrijwel altijd—en het kost een paar tientallen bytes waar flood fill een volledig raster kost.