Generator labirinta i igra

Kako koristiti generator labirinta

1. Postavi Širina (stupci) i Visina (retci), od 4 do 60 polja svaki, i odaberi Algoritam. Klikni Novi labirint.
2. Tvoj položaj je točka u zelenom ulazu gore lijevo. Dođi do crvenog izlaza dolje desno.
3. Kreći se strelicama ili tipkama WASD (ZQSD na francuskoj tipkovnici). Drži Shift uz strelicu da potrčiš hodnikom do sljedećeg raskrižja. Na mobitelu ili tabletu povuci prstom po labirintu da potrčiš u tom smjeru ili dodiruj gumbe sa strelicama ispod njega za pojedinačne korake.
4. Mjerač vremena počinje tvojim prvim potezom, a staje na izlazu. Za tobom se crta trag; ako se vratiš preko njega, briše se, pa uvijek pokazuje put kojim trenutačno ideš.
5. Zapeo si? Prikaži rješenje crta najkraći put od mjesta na kojem stojiš do izlaza. Natrag na početak vraća te na ulaz s ponovno postavljenim vremenom.
6. Za igru na papiru klikni Ispis ili Preuzmi PDF. Prije toga označi Dodaj stranicu s rješenjem ako želiš odgovor na drugoj stranici.

Podijeli labirint pomoću kôda

Svaki labirint ima Kôd labirinta poput b20x15-k3j9x2: slovo algoritma (b, p ili k), širina × visina i nasumični seed. Isti kôd uvijek iznova gradi potpuno isti labirint na bilo kojem uređaju, pa možeš izazvati prijatelja da pobijedi tvoje vrijeme na istom rasporedu. Upiši ili zalijepi kôd i klikni Učitaj kôd, ili koristi Kopiraj poveznicu za dijeljenje web-adrese koja izravno otvara taj labirint.

Tri algoritma generiranja

Sva tri grade savršen labirint: do svakog polja može se doći i između svaka dva polja postoji točno jedan put, pa nema petlji ni zatvorenih područja. Razlikuju se po izgledu labirinta:

• Rekurzivno vraćanje (dugi hodnici) nasumično hoda od polja do polja rušeći zidove i vraća se kad stigne do slijepe ulice. Daje duge vijugave prolaze s malo grananja: rješenje je obično dugo i vodi te preko većeg dijela mreže.
• Prim (mnogo kratkih slijepih ulica) širi labirint prema van od nasumičnog polja, svaki put dodajući nasumično rubno polje. Dobivaš mnogo kratkih sporednih grana, zbog čega labirint djeluje prometno, a glavni put je lakše uočiti.
• Kruskal (ravnomjerno, granato) uklanja nasumično odabrane zidove između polja koja još nisu povezana (to prati struktura union-find). Rezultat je ravnomjerno granat labirint svugdje, bez vidljive polazne točke.

Redak iznad labirinta prikazuje veličinu, duljinu najkraćeg puta i broj slijepih ulica, pa algoritme možeš usporediti jednim pogledom.

Kako se pronalazi rješenje

Rješenje koristi pretraživanje u širinu (BFS): polazeći od tvog polja, istražuje sve susjede udaljene jedan korak, zatim dva koraka i tako dalje dok ne stigne do izlaza. Budući da svaki korak košta jednako, BFS uvijek pronalazi najkraći put. U savršenom labirintu taj je put ujedno jedini bez vraćanja. Ako je rješenje bilo prikazano tijekom igre, tvoje završno vrijeme ne sprema se kao najbolje vrijeme.

Savjeti za ispis

Ispisane i PDF verzije crtaju čiste crne zidove na bijeloj podlozi, s kôdom labirinta u naslovu kako bi isti labirint mogao ponovno pronaći. Veličine oko 15 × 15 prikladne su za malu djecu; 30 × 30 i više čine solidnu zagonetku za odrasle. Vrlo veliki labirinti (50 × 60) imaju tanke hodnike na stranici A4, pa ih ispiši u punoj veličini stranice.