Labyrintgenerator og labyrintspill

Slik bruker du labyrintgeneratoren

1. Sett Bredde (kolonner) og Høyde (rader), fra 4 til 60 ruter hver, og velg en Algoritme. Klikk på Ny labyrint.
2. Posisjonen din er prikken i den grønne inngangen øverst til venstre. Kom deg til den røde utgangen nederst til høyre.
3. Flytt deg med piltastene eller WASD. Hold Shift sammen med en piltast for å løpe langs en korridor til neste kryss. På mobil eller nettbrett sveiper du på labyrinten for å løpe i den retningen, eller trykker på pilknappene under den for enkeltskritt.
4. Tidtakeren starter med det første trekket ditt og stopper ved utgangen. Sporet ditt tegnes bak deg; hvis du går tilbake over det, viskes det ut, så det alltid viser ruten du er på nå.
5. Står du fast? Vis løsning tegner den korteste veien fra der du står til utgangen. Tilbake til start setter deg ved inngangen igjen med nullstilt tid.
6. Vil du spille på papir, klikker du på Skriv ut eller Last ned PDF. Huk først av for Legg til en løsningsside hvis du vil ha svaret på en egen side.

Del en labyrint med koden

Hver labyrint har en Labyrintkode som b20x15-k3j9x2: algoritmebokstaven (b, p eller k), bredde × høyde og en tilfeldig seed-verdi. Den samme koden bygger alltid nøyaktig den samme labyrinten på alle enheter, så du kan utfordre en venn til å slå tiden din på samme oppsett. Skriv inn eller lim inn en kode og klikk på Last inn kode, eller bruk Kopier lenke for å dele en nettadresse som åpner labyrinten direkte.

De tre algoritmene

Alle tre bygger en perfekt labyrint: alle ruter kan nås, og det finnes nøyaktig én vei mellom to vilkårlige ruter, så det er ingen sløyfer og ingen avstengte områder. De skiller seg i labyrintens preg:

• Rekursiv tilbakesporing (lange korridorer) går tilfeldig fra rute til rute og river vegger, og går tilbake når den møter en blindvei. Den lager lange, slyngede ganger med få forgreninger: løsningen er vanligvis lang og tar deg over det meste av rutenettet.
• Prim (mange korte blindveier) vokser utover fra en tilfeldig rute og legger til en tilfeldig grenserute hver gang. Du får mange korte sidegrener, som gjør at labyrinten ser travel ut, men at hovedveien er lettere å se.
• Kruskal (jevn, forgrenet) fjerner tilfeldig valgte vegger mellom ruter som ikke allerede henger sammen (holdt styr på med en union-find-struktur). Resultatet er jevnt forgrenet overalt, uten noe synlig startpunkt.

Linjen over labyrinten viser størrelsen, lengden på den korteste veien og antall blindveier, så du kan sammenligne algoritmene med et blikk.

Slik finnes løsningen

Løsningen bruker bredde-først-søk (BFS): fra ruten din utforsker den alle naboer ett skritt unna, så to skritt, og så videre, til den når utgangen. Fordi hvert skritt koster det samme, finner BFS alltid den korteste veien. I en perfekt labyrint er den veien også den eneste uten å gå tilbake. Hvis løsningen ble vist under en runde, lagres ikke sluttiden din som beste tid.

Tips for utskrift

Utskriften og PDF-versjonen tegner rene svarte vegger på hvit bunn, med labyrintkoden i tittelen så du kan finne den samme labyrinten igjen. Størrelser rundt 15 × 15 passer for små barn; 30 × 30 og større er en solid utfordring for voksne. Svært store labyrinter (50 × 60) får tynne korridorer på en A4-side, så skriv dem ut i full sidestørrelse.