Generador de laberints i joc

Com utilitzar el generador de laberints

1. Defineix l’Amplada (columnes) i l’Alçada (files), d’entre 4 i 60 cel·les cadascuna, i tria un Algorisme. Fes clic a Laberint nou.
2. La teva posició és el punt de l’entrada verda, a dalt a l’esquerra. Arriba a la sortida vermella, a baix a la dreta.
3. Mou-te amb les fletxes o amb WASD (ZQSD en un teclat francès). Mantén premuda Maj amb una fletxa per córrer per un passadís fins al creuament següent. En un telèfon mòbil o una tauleta, llisca pel laberint per córrer en aquella direcció, o toca els botons de fletxa de sota per fer passos d’un en un.
4. El cronòmetre s’engega amb el primer moviment i s’atura a la sortida. El teu rastre es dibuixa darrere teu; si hi tornes a passar per sobre, s’esborra, de manera que sempre mostra la ruta que segueixes.
5. T’has encallat? Mostra la solució dibuixa el camí més curt des d’on ets fins a la sortida. Torna a l’inici et posa de nou a l’entrada i reinicia el cronòmetre.
6. Per jugar en paper, fes clic a Imprimeix o a Baixa el PDF. Marca abans Afegeix una pàgina amb la solució si vols la resposta en una segona pàgina.

Comparteix un laberint amb el seu codi

Cada laberint té un Codi del laberint com b20x15-k3j9x2: la lletra de l’algorisme (b, p o k), l’amplada × alçada i una llavor aleatòria. El mateix codi reconstrueix sempre exactament el mateix laberint en qualsevol dispositiu, de manera que pots desafiar un amic a superar el teu temps en la mateixa distribució. Escriu o enganxa un codi i fes clic a Carrega el codi, o fes servir Copia l’enllaç per compartir una adreça web que obre directament aquell laberint.

Els tres algorismes de generació

Els tres construeixen un laberint perfecte: es pot arribar a totes les cel·les i hi ha exactament un camí entre dues cel·les qualssevol, de manera que no hi ha bucles ni zones tancades. Es diferencien en la textura del laberint:

• Cerca recursiva amb retrocés (passadissos llargs) va d’una cel·la a una altra a l’atzar, tirant parets avall, i retrocedeix quan arriba a un atzucac. Produeix passadissos llargs i sinuosos amb poques ramificacions: la solució sol ser llarga i et fa creuar gairebé tota la quadrícula.
• Prim (molts atzucacs curts) fa créixer el laberint cap enfora a partir d’una cel·la a l’atzar, afegint cada vegada una cel·la frontera a l’atzar. Obtens moltes branques laterals curtes, cosa que fa que el laberint sembli atapeït però que el camí principal es vegi més fàcilment.
• Kruskal (uniforme, ramificat) elimina parets triades a l’atzar entre cel·les que encara no estan connectades (ho gestiona una estructura d’unió-cerca). El resultat està ramificat de manera uniforme arreu, sense un punt de partida visible.

La línia sobre el laberint indica la mida, la longitud del camí més curt i el nombre d’atzucacs, de manera que pots comparar els algorismes d’un cop d’ull.

Com es troba la solució

La solució fa servir una cerca en amplada (BFS): a partir de la teva cel·la, explora tots els veïns a un pas de distància, després a dos passos, i així successivament fins que arriba a la sortida. Com que cada pas costa el mateix, la cerca en amplada sempre troba el camí més curt. En un laberint perfecte, aquest camí també és l’únic sense retrocedir. Quan s’ha mostrat la solució durant una partida, el temps d’arribada no es desa com a millor temps.

Consells per imprimir

Les versions impresa i en PDF dibuixen parets negres netes sobre fons blanc, amb el codi del laberint al títol perquè puguis tornar a trobar el mateix laberint. Les mides d’uns 15 × 15 van bé per als nens petits; 30 × 30 i més són un bon repte per als adults. Els laberints molt grans (50 × 60) tenen passadissos estrets en una pàgina A4, de manera que imprimeix-los a mida de pàgina completa.