Gerador de labirinto de algoritmo de Eller

O algoritmo de Eller é um algoritmo de geração de labirintos que produz labirintos perfeitos (labirintos sem laços e com um único caminho entre quaisquer dois pontos) de forma eficiente, utilizando 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 com recursos limitados e para geração procedural de conteúdo.

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

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

Algoritmo de Eller processa uma linha de cada vez, mantendo e modificando conjuntos de células conectadas. Ele garante a conectividade, evitando loops, e estende o labirinto para baixo de forma eficiente.

Teoricamente, pode ser usado para gerar labirintos infinitos; no entanto, para garantir que o labirinto gerado seja realmente solucionável, é necessário mudar para a lógica da "linha final" em algum ponto para finalizar o labirinto.

Passo 1: Inicialize a primeira linha

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

Passo 2: Una algumas células adjacentes horizontalmente

• Mescle aleatoriamente células adjacentes atribuindo a elas o mesmo ID de conjunto. Isso garante a existência de passagens horizontais.

Passo 3: Crie conexões verticais com a próxima linha.

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

Passo 4: Mova para a próxima linha

• Prossiga 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.

Passo 5: Repita os passos 2 a 4 até chegar à última linha.

• Continue o processamento linha por linha.

Etapa 6: Processar a linha final

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

Leitura adicional

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

• Gerador de labirintos de backtracker recursivo
• Gerador de labirintos do algoritmo de Wilson
• Gerador de Labirinto Caçar e Matar