Gerador de labirintos do algoritmo de Eller

O algoritmo de Eller é um algoritmo de geração de labirintos que produz eficientemente labirintos perfeitos (labirintos sem laços e com um único caminho entre quaisquer dois pontos) usando uma abordagem linha a linha. Produz labirintos semelhantes ao algoritmo de Kruskal, mas faz-no gerando apenas uma linha de cada vez, sem necessidade de armazenar todo o labirinto na memória. Isso torna-o útil para gerar labirintos muito grandes em sistemas muito limitados e para geração procedural de conteúdo.

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 destaca-se pela sua abordagem eficiente linha a linha na geração de labirintos, tornando-o ideal para labirintos infinitos ou labirintos gerados em tempo real. É frequentemente citado em literatura sobre geração procedural de conteúdo e geração de labirintos, mas não consegui encontrar fontes primárias que detalhem 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 eficientemente o labirinto para baixo.

Teoricamente, pode ser usado para gerar labirintos infinitos, mas para garantir que o labirinto gerado é realmente solucionável, é necessário mudar para a lógica da "última linha" em algum momento para terminar o labirinto.

Passo 1: Inicializar a Primeira Fila

• Atribuir a cada célula da linha um ID de conjunto único.

Passo 2: Juntar algumas células adjacentes horizontalmente

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

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

• Para cada conjunto que aparece na linha, pelo menos uma célula tem de se ligar para baixo (para garantir a conectividade).
• Escolhe aleatoriamente uma ou mais células de cada conjunto para ligar à próxima linha.

Passo 4: Passar para a Próxima Fila

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

Passo 5: Repita os passos 2–4 até chegar à última fila

• Continue a processar linha a linha.

Passo 6: Processar a Última Fila

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

Leitura adicional

Se gostou deste post, também pode gostar destas sugestões:

• Gerador de labirintos com algoritmo de árvore em crescimento
• Gerador de labirintos de backtracker recursivo
• Gerador de labirintos de caça e matança