Generator labirintov in igra

Kako uporabljati generator labirintov

1. Nastavi Širino (stolpci) in Višino (vrstice), vsako od 4 do 60 celic, ter izberi Algoritem. Klikni Nov labirint.
2. Tvoj položaj je pika v zelenem vhodu zgoraj levo. Pridi do rdečega izhoda spodaj desno.
3. Premikaj se s smernimi tipkami ali WASD. S tipko Shift in smerno tipko tečeš vzdolž hodnika do naslednjega križišča. Na telefonu ali tablici podrsaj po labirintu, da tečeš v to smer, ali tapni gumbe s puščicami pod njim za posamezne korake.
4. Časovnik se zažene ob prvem premiku in se ustavi pri izhodu. Za teboj se riše sled; če se vrneš po njej, se izbriše, zato vedno kaže pot, na kateri si.
5. Si obtičal? Pokaži rešitev nariše najkrajšo pot od mesta, kjer stojiš, do izhoda. Nazaj na začetek te postavi nazaj na vhod, časovnik pa se ponastavi.
6. Če želiš igrati na papirju, klikni Natisni ali Prenesi PDF. Prej obkljukaj Dodaj stran z rešitvijo, če želiš odgovor na drugi strani.

Deli labirint s kodo

Vsak labirint ima Kodo labirinta, na primer b20x15-k3j9x2: črko algoritma (b, p ali k), širino × višino in naključno seme. Ista koda na kateri koli napravi vedno zgradi popolnoma enak labirint, zato lahko prijatelja izzoveš, naj na isti postavitvi premaga tvoj čas. Vnesi ali prilepi kodo in klikni Uporabi kodo ali uporabi Kopiraj povezavo, da deliš spletni naslov, ki neposredno odpre ta labirint.

Trije algoritmi za ustvarjanje

Vsi trije zgradijo popoln labirint: do vsake celice je mogoče priti in med katerima koli dvema celicama obstaja natanko ena pot, zato ni zank in zaprtih območij. Razlikujejo se po videzu labirinta:

• Rekurzivno vračanje (dolgi hodniki) se naključno sprehaja od celice do celice, podira stene in se vrne, ko pride do slepe ulice. Ustvari dolge vijugaste prehode z malo razvejanji: rešitev je običajno dolga in te vodi čez večino mreže.
• Prim (veliko kratkih slepih ulic) raste navzven iz naključne celice in vsakič doda naključno mejno celico. Dobiš veliko kratkih stranskih vej, zaradi katerih je labirint videti natrpan, glavna pot pa je lažje opazna.
• Kruskal (enakomerno, razvejano) odstranjuje naključno izbrane stene med celicami, ki še niso povezane (sledi se s strukturo union-find). Rezultat je povsod enakomerno razvejan, brez vidne izhodiščne točke.

Vrstica nad labirintom prikazuje velikost, dolžino najkrajše poti in število slepih ulic, tako da lahko algoritme primerjaš na prvi pogled.

Kako se najde rešitev

Rešitev uporablja iskanje v širino (BFS): izhajajoč iz tvoje celice preišče vse sosede za en korak, nato za dva koraka in tako naprej, dokler ne doseže izhoda. Ker je vsak korak enako drag, BFS vedno najde najkrajšo pot. V popolnem labirintu je ta pot tudi edina brez vračanja. Če je bila rešitev prikazana med igro, tvoj končni čas ni shranjen kot najboljši čas.

Nasveti za tiskanje

Natisnjena različica in PDF narišeta čiste črne stene na belem, s kodo labirinta v naslovu, da lahko isti labirint najdeš znova. Velikosti okoli 15 × 15 so primerne za majhne otroke; 30 × 30 in več je trdna uganka za odrasle. Zelo veliki labirinti (50 × 60) imajo na listu A4 ozke hodnike, zato jih natisni v polni velikosti strani.