Gerador de labirinto de algoritmo de Eller

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

Um labirinto perfeito é um labirinto em que há exatamente um caminho de qualquer ponto do labirinto para qualquer outro ponto. Isso significa que você não pode acabar andando em círculos, mas frequentemente encontrará becos sem saída, forçando-o a dar meia-volta e retornar.

Os mapas de labirinto gerados aqui incluem uma versão padrão sem posições de início e fim, para que você possa decidir por si mesmo: haverá uma solução de qualquer ponto do labirinto para qualquer outro ponto. Se quiser se inspirar, você pode ativar uma sugestão de posição inicial e final e até mesmo 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 por sua abordagem eficiente linha por linha para geração de labirintos, tornando-o ideal para labirintos infinitos ou labirintos gerados em tempo real. Ele é comumente citado na literatura sobre geração de conteúdo procedural e geração de labirintos, mas não consegui encontrar fontes primárias detalhando sua publicação original.

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

O algoritmo de Eller processa uma linha por vez, mantendo e modificando conjuntos de células conectadas. Ele garante a conectividade enquanto evita loops, e estende o labirinto para baixo de forma eficiente.

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

Etapa 1: Inicializar a primeira linha

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

Etapa 2: Junte algumas células adjacentes horizontalmente

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

Etapa 3: Crie conexões verticais para a próxima linha

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

Etapa 4: Mover para a próxima linha

• Continue as conexõ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.

Etapa 5: Repita as etapas 2 a 4 até que a última linha seja alcançada

• Continue processando linha por linha.

Etapa 6: Processe a linha final

• Garanta que todas as células na última linha pertençam ao mesmo conjunto mesclando quaisquer conjuntos separados restantes.