Miklix

Gerador de labirintos do algoritmo de Kruskal

Publicado: 16 de fevereiro de 2025 às 17:59:57 UTC

Gerador de labirintos usando o algoritmo de Kruskal para criar um labirinto perfeito. Este algoritmo tende a criar labirintos com corredores de comprimento médio e muitos becos sem saída, bem como uma solução bastante reta.

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:

Kruskal's Algorithm Maze Generator

O algoritmo de Kruskal é um algoritmo de árvore de abrangência mínima que pode ser adaptado para geração de labirintos. Ele é particularmente eficaz para criar labirintos perfeitos. Uma alternativa ao algoritmo de Kruskal é o algoritmo de Prim, que também é um algoritmo de árvore de abrangência mínima, mas como eles geram labirintos idênticos e o de Kruskal roda mais rápido, não me incomodei em implementar o de Prim.

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 Kruskal

O algoritmo de Kruskal foi criado por Joseph Bernard Kruskal, Jr., um matemático, estatístico e cientista da computação americano. Ele descreveu o algoritmo pela primeira vez em 1956 em seu artigo "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem".

O algoritmo foi projetado para encontrar a árvore geradora mínima (MST) de um gráfico, garantindo que todos os vértices estejam conectados com o menor peso total de arestas possível, evitando ciclos.

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

Etapa 1: Inicializar

  • Trate cada célula no labirinto como um conjunto separado (um componente único).
  • Liste todas as paredes entre células adjacentes como bordas potenciais.

Etapa 2: Classifique as paredes

  • Embaralhe ou ordene aleatoriamente as paredes. Se estiver implementando como um algoritmo de Kruskal verdadeiro, ordene as paredes em uma ordem aleatória (já que a geração de labirintos não requer pesos).

Etapa 3: Processar Paredes

  • Percorra as paredes embaralhadas.
  • Se as duas células divididas pela parede pertencerem a conjuntos diferentes (ou seja, ainda não estiverem conectadas no labirinto), remova a parede e mescle os conjuntos.
  • Se eles já estiverem no mesmo conjunto, pule a parede (para evitar ciclos).

Etapa 4: Continue até a conclusão

  • Repita esse processo até que todas as células estejam conectadas, formando uma única árvore de abrangência.
  • No final, cada célula é conectada às outras sem laços ou seções isoladas.

Como o algoritmo de Kruskal depende da fusão de conjuntos, ele pode ser otimizado usando o algoritmo Union-Find, que fornece uma maneira eficiente de rastrear células conectadas durante a geração do labirinto. Você pode ver minha implementação em PHP do algoritmo Union-Find aqui: Conjunto Disjunto (Algoritmo Union-Find) em PHP

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.