Doolhofgenerator en -spel

Zo gebruik je de doolhofgenerator

1. Stel de Breedte (kolommen) en Hoogte (rijen) in, elk van 4 tot 60 vakken, en kies een Algoritme. Klik op Nieuw doolhof.
2. Jij bent de stip in de groene ingang linksboven. Bereik de rode uitgang rechtsonder.
3. Beweeg met de pijltjestoetsen of WASD (ZQSD op een AZERTY-toetsenbord, zoals in België, werkt ook). Houd Shift ingedrukt met een pijl om door een gang te rennen tot de volgende splitsing. Op een telefoon of tablet veeg je over het doolhof om in die richting te rennen, of tik je op de pijlknoppen eronder voor losse stappen.
4. De timer start bij je eerste stap en stopt bij de uitgang. Achter je wordt een spoor getekend; loop je erover terug, dan verdwijnt het weer, zodat het altijd de route toont waarop je zit.
5. Vast? Oplossing tonen tekent de kortste route van waar je staat naar de uitgang. Terug naar de start zet je weer bij de ingang en zet de timer terug.
6. Wil je op papier spelen, klik dan op Afdrukken of Pdf downloaden. Vink eerst Oplossingspagina toevoegen aan als je het antwoord op een tweede pagina wilt.

Een doolhof delen met zijn code

Elk doolhof heeft een Doolhofcode, zoals b20x15-k3j9x2: de letter van het algoritme (b, p of k), de breedte × hoogte en een willekeurige seed. Dezelfde code bouwt op elk apparaat precies hetzelfde doolhof op, dus je kunt een vriend uitdagen om jouw tijd op dezelfde plattegrond te verbeteren. Typ of plak een code en klik op Code laden, of gebruik Link kopiëren om een webadres te delen dat dat doolhof direct opent.

De drie algoritmes

Alle drie bouwen ze een perfect doolhof: elk vak is bereikbaar en tussen twee vakken bestaat precies één pad, dus er zijn geen lussen en geen afgesloten gebieden. Ze verschillen in de structuur van het doolhof:

• Recursive backtracker (lange gangen) loopt willekeurig van vak naar vak, breekt muren af en keert terug zodra hij op een doodlopend punt komt. Dat geeft lange, kronkelende gangen met weinig zijpaden: de oplossing is meestal lang en voert je door het grootste deel van het raster.
• Prim (veel korte doodlopende stukken) laat het doolhof vanuit een willekeurig vak naar buiten groeien en voegt telkens een willekeurig randvak toe. Je krijgt veel korte zijtakken, waardoor het doolhof druk oogt maar de hoofdroute makkelijker te zien is.
• Kruskal (gelijkmatig, vertakt) haalt willekeurig gekozen muren weg tussen vakken die nog niet met elkaar verbonden zijn (bijgehouden met een union-find-structuur). Het resultaat is overal even vertakt, zonder zichtbaar beginpunt.

De regel boven het doolhof geeft het formaat, de lengte van de kortste route en het aantal doodlopende stukken, zodat je de algoritmes in één oogopslag kunt vergelijken.

Hoe de oplossing wordt gevonden

De oplossing gebruikt breadth-first search (BFS), zoeken in de breedte: vanaf jouw vak bekijkt het algoritme eerst alle buren op één stap, dan op twee stappen, enzovoort, tot het de uitgang bereikt. Omdat elke stap evenveel kost, vindt BFS altijd de kortste route. In een perfect doolhof is dat ook de enige route zonder terug te lopen. Als de oplossing tijdens een poging getoond werd, wordt je eindtijd niet als beste tijd opgeslagen.

Tips voor het afdrukken

De afgedrukte versie en de pdf tonen strakke zwarte muren op wit, met de doolhofcode in de titel zodat je hetzelfde doolhof later terugvindt. Formaten rond 15 × 15 zijn geschikt voor jonge kinderen; vanaf 30 × 30 heb je een stevige puzzel voor volwassenen. Zeer grote doolhoven (50 × 60) hebben smalle gangen op een A4’tje, dus druk ze af op volle paginagrootte.