Generatore di labirinti e gioco

Come usare il generatore di labirinti

1. Imposta Larghezza (colonne) e Altezza (righe), da 4 a 60 celle ciascuna, e scegli un Algoritmo. Clicca su Nuovo labirinto.
2. La tua posizione è il pallino nell’ingresso verde in alto a sinistra. Devi raggiungere l’uscita rossa in basso a destra.
3. Muoviti con le frecce o con WASD (ZQSD su una tastiera francese). Tieni premuto Maiusc insieme a una freccia per correre lungo un corridoio fino al prossimo incrocio. Su telefono o tablet, scorri sul labirinto per correre in quella direzione, oppure tocca i pulsanti freccia sotto il labirinto per fare un passo alla volta.
4. Il cronometro parte con la prima mossa e si ferma all’uscita. Dietro di te si disegna una scia; se torni sui tuoi passi la scia si cancella, così mostra sempre il percorso che stai seguendo.
5. Bloccato? Mostra soluzione disegna il percorso più breve dal punto in cui ti trovi fino all’uscita. Torna all’inizio ti riporta all’ingresso e azzera il cronometro.
6. Per giocare su carta, clicca su Stampa o Scarica PDF. Spunta prima Aggiungi una pagina con la soluzione se vuoi la risposta su una seconda pagina.

Condividi un labirinto con il suo codice

Ogni labirinto ha un Codice labirinto come b20x15-k3j9x2: la lettera dell’algoritmo (b, p o k), larghezza × altezza e un seme casuale. Lo stesso codice ricrea sempre esattamente lo stesso labirinto su qualsiasi dispositivo, così puoi sfidare un amico a battere il tuo tempo sullo stesso percorso. Scrivi o incolla un codice e clicca su Carica codice, oppure usa Copia link per condividere un indirizzo web che apre direttamente quel labirinto.

I tre algoritmi di generazione

Tutti e tre costruiscono un labirinto perfetto: ogni cella è raggiungibile e tra due celle qualsiasi esiste un solo percorso, quindi non ci sono anelli né zone chiuse. Cambia invece la «trama» del labirinto:

• Backtracking ricorsivo (corridoi lunghi) avanza a caso da una cella all’altra abbattendo i muri, e torna indietro quando arriva in un vicolo cieco. Produce lunghi passaggi tortuosi con poche diramazioni: la soluzione di solito è lunga e attraversa gran parte della griglia.
• Prim (tanti vicoli ciechi corti) fa crescere il labirinto a partire da una cella casuale, aggiungendo ogni volta una cella di frontiera scelta a caso. Ottieni tante brevi diramazioni laterali: il labirinto sembra intricato, ma il percorso principale si individua più facilmente.
• Kruskal (uniforme, ramificato) rimuove muri scelti a caso tra celle non ancora collegate (tenute sotto controllo con una struttura union-find). Il risultato è ramificato in modo uniforme ovunque, senza un punto di partenza riconoscibile.

La riga sopra il labirinto indica la dimensione, la lunghezza del percorso più breve e il numero di vicoli ciechi, così puoi confrontare gli algoritmi a colpo d’occhio.

Come viene trovata la soluzione

La soluzione usa una ricerca in ampiezza (BFS): partendo dalla tua cella, esplora tutte le celle vicine a un passo, poi a due passi e così via, finché non raggiunge l’uscita. Poiché ogni passo ha lo stesso costo, la BFS trova sempre il percorso più breve. In un labirinto perfetto quel percorso è anche l’unico senza ritorni indietro. Se durante una partita hai mostrato la soluzione, il tuo tempo finale non viene salvato come tempo migliore.

Consigli per la stampa

Le versioni stampata e PDF disegnano muri neri e netti su fondo bianco, con il codice del labirinto nel titolo per ritrovare lo stesso labirinto in seguito. Dimensioni intorno a 15 × 15 vanno bene per i bambini piccoli; da 30 × 30 in su diventa un rompicapo serio anche per gli adulti. I labirinti molto grandi (50 × 60) hanno corridoi sottili su un foglio A4, quindi stampali a pagina intera.