Miklix

Gerador de labirinto de algoritmo de Eller

Publicado: 16 de fevereiro de 2025 às 20:00:35 UTC

Gerador de labirinto usando o algoritmo de Eller para criar um labirinto perfeito. Esse algoritmo é interessante, pois requer apenas manter a linha atual (não o labirinto inteiro) na memória, então ele pode ser usado para criar labirintos muito, muito grandes, mesmo em sistemas muito limitados.

Esta página foi traduzida automaticamente do inglês para torná-la acessível ao maior número possível de pessoas. Infelizmente, a tradução automática ainda não é uma tecnologia aperfeiçoada, portanto, podem ocorrer erros. Se preferir, você pode visualizar a versão original em inglês aqui:

Eller's Algorithm Maze Generator

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.


Gerar novo labirinto








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.

Compartilhe no BlueskyCompartilhe no FacebookCompartilhe no LinkedInCompartilhe no TumblrCompartilhar em XCompartilhe no LinkedInFixar no Pinterest

Mikkel Bang Christensen

Sobre o autor

Mikkel Bang Christensen
Mikkel é o criador e proprietário do miklix.com. Ele tem mais de 20 anos de experiência como programador de computador/desenvolvedor de software profissional e atualmente trabalha em tempo integral para uma grande empresa europeia de TI. Quando não está blogando, ele dedica seu tempo livre a uma grande variedade de interesses, hobbies e atividades, o que pode, até certo ponto, refletir-se na variedade de tópicos abordados neste site.