Labyrintgenerator och spel

Så använder du labyrintgeneratorn

1. Ställ in Bredd (kolumner) och Höjd (rader), från 4 till 60 rutor vardera, och välj en Algoritm. Klicka på Ny labyrint.
2. Din position är pricken i den gröna ingången uppe till vänster. Ta dig till den röda utgången nere till höger.
3. Flytta dig med piltangenterna eller WASD (ZQSD på ett franskt tangentbord). Håll ner Skift tillsammans med en piltangent för att springa längs en korridor till nästa korsning. På mobil eller platta kan du svepa på labyrinten för att springa åt det hållet, eller trycka på pilknapparna under den för enstaka steg.
4. Tidtagningen startar vid ditt första drag och stannar vid utgången. Ditt spår ritas bakom dig. Om du går tillbaka över det suddas det ut, så det visar alltid vägen du är på.
5. Fastnat? Visa lösning ritar den kortaste vägen från där du står till utgången. Tillbaka till start placerar dig vid ingången igen med nollställd tid.
6. Vill du spela på papper klickar du på Skriv ut eller Ladda ner pdf. Kryssa först i Lägg till en lösningssida om du vill ha svaret på en andra sida.

Dela en labyrint med dess kod

Varje labyrint har en Labyrintkod, till exempel b20x15-k3j9x2: algoritmbokstaven (b, p eller k), bredd × höjd och ett slumpmässigt frö. Samma kod bygger alltid upp exakt samma labyrint på vilken enhet som helst, så du kan utmana en vän att slå din tid på samma layout. Skriv eller klistra in en kod och klicka på Ladda kod, eller använd Kopiera länk för att dela en webbadress som öppnar just den labyrinten.

De tre algoritmerna

Alla tre bygger en perfekt labyrint: varje ruta går att nå och det finns exakt en väg mellan två rutor, så det finns inga slingor och inga avstängda områden. De skiljer sig i labyrintens karaktär:

• Rekursiv backtracker (långa korridorer) går slumpmässigt från ruta till ruta och river väggar, och backar när den kommer till en återvändsgränd. Den ger långa, slingrande gångar med få förgreningar: lösningen är oftast lång och tar dig över större delen av rutnätet.
• Prim (många korta återvändsgränder) låter labyrinten växa utåt från en slumpmässig ruta och lägger varje gång till en slumpmässig gränsruta. Du får många korta sidogrenar, vilket gör labyrinten rörig men huvudvägen lättare att se.
• Kruskal (jämn, förgrenad) tar bort slumpmässigt valda väggar mellan rutor som ännu inte är förbundna (med hjälp av en union-find-struktur). Resultatet är jämnt förgrenat överallt, utan någon synlig startpunkt.

Raden ovanför labyrinten anger storleken, längden på den kortaste vägen och antalet återvändsgränder, så att du lätt kan jämföra algoritmerna.

Så hittas lösningen

Lösningen använder en bredden först-sökning (BFS): från din ruta undersöker den alla grannar ett steg bort, sedan två steg bort och så vidare tills den når utgången. Eftersom varje steg kostar lika mycket hittar BFS alltid den kortaste vägen. I en perfekt labyrint är den vägen också den enda utan backning. Om lösningen visades under en omgång sparas inte din sluttid som bästa tid.

Tips för utskrift

De utskrivna versionerna och pdf-versionerna ritar rena svarta väggar på vitt, med labyrintkoden i rubriken så att du kan hitta samma labyrint igen. Storlekar kring 15 × 15 passar små barn, och 30 × 30 och uppåt är ett rejält pussel för vuxna. Mycket stora labyrinter (50 × 60) har smala korridorer på ett A4-ark, så skriv ut dem i full sidstorlek.