Gerador de labirintos e jogo

Como usar o gerador de labirintos

1. Define a Largura (colunas) e a Altura (linhas), de 4 a 60 células cada, e escolhe um Algoritmo. Clica em Novo labirinto.
2. A tua posição é o ponto na entrada verde, em cima à esquerda. Chega à saída vermelha, em baixo à direita.
3. Desloca-te com as setas ou com WASD (ZQSD num teclado francês). Mantém Shift premido com uma seta para correr ao longo de um corredor até ao próximo cruzamento. Num telemóvel ou tablet, desliza o dedo no labirinto para correr nessa direção, ou toca nos botões de seta por baixo dele para avançar uma casa de cada vez.
4. O cronómetro arranca com o teu primeiro movimento e para na saída. O teu rasto é desenhado atrás de ti; voltar para trás por cima dele apaga-o, por isso mostra sempre o caminho em que estás.
5. Encalhaste? Mostrar solução desenha o caminho mais curto desde onde estás até à saída. Voltar ao início põe-te de novo na entrada, com o cronómetro a zeros.
6. Para jogar em papel, clica em Imprimir ou Transferir PDF. Marca antes Juntar página com a solução se quiseres a resposta numa segunda página.

Partilhar um labirinto com o seu código

Cada labirinto tem um Código do labirinto, como b20x15-k3j9x2: a letra do algoritmo (b, p ou k), a largura × altura e uma semente aleatória. O mesmo código reconstrói sempre exatamente o mesmo labirinto em qualquer dispositivo, por isso podes desafiar um amigo a bater o teu tempo no mesmo percurso. Escreve ou cola um código e clica em Carregar código, ou usa Copiar ligação para partilhar um endereço que abre diretamente esse labirinto.

Os três algoritmos de geração

Os três constroem um labirinto perfeito: todas as células são alcançáveis e existe exatamente um caminho entre quaisquer duas células, sem ciclos nem zonas fechadas. Diferem na textura do labirinto:

• Retrocesso recursivo (corredores longos) avança ao acaso de célula em célula, derrubando paredes, e recua quando chega a um beco sem saída. Produz passagens longas e sinuosas com poucas ramificações: a solução costuma ser longa e atravessa a maior parte da grelha.
• Prim (muitos becos curtos) faz crescer o labirinto a partir de uma célula aleatória, acrescentando de cada vez uma célula aleatória da fronteira. Obténs muitas ramificações laterais curtas, o que torna o labirinto visualmente carregado, mas o caminho principal mais fácil de ver.
• Kruskal (uniforme, ramificado) remove paredes escolhidas ao acaso entre células que ainda não estão ligadas (controladas com uma estrutura union-find). O resultado é ramificado de forma uniforme em toda a parte, sem um ponto de partida visível.

A linha por cima do labirinto indica o tamanho, o comprimento do caminho mais curto e o número de becos sem saída, para poderes comparar os algoritmos num relance.

Como é encontrada a solução

A solução usa uma pesquisa em largura (BFS): a partir da tua célula, explora todos os vizinhos a um passo, depois a dois passos, e assim por diante, até chegar à saída. Como todos os passos custam o mesmo, a BFS encontra sempre o caminho mais curto. Num labirinto perfeito, esse caminho é também o único sem voltar atrás. Se a solução foi mostrada durante uma partida, o teu tempo final não é guardado como melhor tempo.

Dicas para imprimir

As versões impressa e em PDF desenham paredes pretas nítidas sobre fundo branco, com o código do labirinto no título para o voltares a encontrar. Tamanhos à volta de 15 × 15 são adequados a crianças pequenas; 30 × 30 ou mais dão um bom desafio para adultos. Labirintos muito grandes (50 × 60) têm corredores finos numa folha A4, por isso imprime-os a página inteira.