Gerador de labirintos do algoritmo de Eller

O algoritmo de Eller é um algoritmo de geração de labirintos que produz labirintos perfeitos (labirintos sem loops e um único caminho entre dois pontos) utilizando uma abordagem linha a linha. Produz labirintos semelhantes ao algoritmo de Kruskal, mas fá-lo gerando apenas uma linha de cada vez, sem necessidade de armazenar todo o labirinto na memória. Isto torna-o útil para gerar labirintos muito grandes em sistemas muito limitados e para a geração de conteúdos procedimentais.

Um labirinto perfeito é um labirinto em que existe exatamente um caminho de qualquer ponto do labirinto para qualquer outro ponto. Isto significa que não pode acabar por andar em círculos, mas encontrará frequentemente becos sem saída, obrigando-o a dar meia volta e regressar.

Os mapas de labirinto gerados aqui incluem uma versão predefinida sem posições de início e fim, para que possas decidir por ti próprio: haverá uma solução de qualquer ponto do labirinto para qualquer outro ponto. Se quiseres inspiração, podes ativar uma posição de início e de fim sugerida - e até ver a solução entre as duas.

Sobre o Algoritmo de Eller

O Algoritmo de Eller foi introduzido por David Eller.

O algoritmo é notável pela sua abordagem eficiente linha a linha para a geração de labirintos, tornando-o ideal para labirintos infinitos ou labirintos gerados em tempo real. É comummente citado na literatura sobre a geração de conteúdo procedimental e a geração de labirintos, mas não consegui encontrar fontes primárias que detalhassem a sua publicação original.

Como funciona o algoritmo de Eller para a geração de labirintos

O algoritmo de Eller processa uma linha de cada vez, mantendo e modificando conjuntos de células ligadas. Garante a conectividade, evitando loops e estende o labirinto para baixo de forma eficiente.

Teoricamente, pode ser utilizado para gerar labirintos infinitos, no entanto, para garantir que o labirinto gerado é realmente solucionável, é necessário mudar para a lógica de "linha final" em algum momento para terminar o labirinto.

Passo 1: inicializar a primeira linha

• Atribua a cada célula da linha um ID de conjunto exclusivo.

Passo 2: Junte algumas células adjacentes horizontalmente

• Mescle aleatoriamente células adjacentes definindo-as com o mesmo ID de conjunto. Isto garante que haja passagens horizontais.

Passo 3: Crie ligações verticais para a próxima linha

• Para cada conjunto que aparece na linha, pelo menos uma célula deve ligar-se para baixo (para garantir a conectividade).
• Escolha aleatoriamente uma ou mais células de cada conjunto para ligar à linha seguinte.

Passo 4: Mover para a próxima linha

• Continue as ligações verticais atribuindo o mesmo ID de conjunto às células correspondentes abaixo.
• Atribua novos IDs de conjunto a quaisquer células não atribuídas.

Passo 5: Repita os passos 2 a 4 até que a última linha seja alcançada

• Continue a processar linha a linha.

Passo 6: Processe a linha final

• Garanta que todas as células da última linha pertencem ao mesmo conjunto, fundindo quaisquer conjuntos separados restantes.