Miklix

Gerador de labirintos do algoritmo de Eller

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

Gerador de labirintos utilizando o algoritmo de Eller para criar um labirinto perfeito. Este algoritmo é interessante porque requer manter apenas a linha atual (não o labirinto inteiro) na memória, pelo que pode ser utilizado para criar labirintos muito, muito grandes, mesmo em sistemas muito limitados.

Esta página foi traduzida automaticamente do inglês para a tornar acessível ao maior número possível de pessoas. Infelizmente, a tradução automática ainda não é uma tecnologia aperfeiçoada, pelo que podem ocorrer erros. Se preferir, pode ver 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 (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.


Gerar novo labirinto








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.

Partilhar no BlueskyPartilhar no FacebookPartilhar no LinkedInPartilhar no TumblrPartilhar em XPartilhar no LinkedInFixar no Pinterest

Mikkel Bang Christensen

Sobre o autor

Mikkel Bang Christensen
Mikkel é o criador e proprietário do miklix.com. Tem mais de 20 anos de experiência como programador informático/desenvolvedor de software profissional e trabalha atualmente a tempo inteiro para uma grande empresa europeia de TI. Quando não está a escrever no blogue, dedica o seu tempo livre a um vasto leque de interesses, passatempos e actividades, que podem, em certa medida, refletir-se na variedade de tópicos abordados neste sítio Web.