Gerador de labirintos do algoritmo de Kruskal

O algoritmo de Kruskal é um algoritmo de árvore geradora mínima que pode ser adaptado para a geração de labirintos. Ele é particularmente eficaz na criação de labirintos perfeitos. Uma alternativa ao algoritmo de Kruskal é o algoritmo de Prim, que também é um algoritmo de árvore geradora mínima, mas como ambos geram labirintos idênticos e o de Kruskal é executado mais rapidamente, não me preocupei 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.

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 "Sobre a Subárvore Geradora Mais Curta de um Grafo e o Problema do Caixeiro Viajante".

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

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

Passo 1: Inicializar

• Considere cada célula do labirinto como um conjunto separado (um componente único).
• Liste todas as paredes entre células adjacentes como possíveis arestas.

Etapa 2: Classificar paredes

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

Etapa 3: Processar paredes

• Percorra as paredes embaralhadas.
• Se as duas células separadas pela parede pertencerem a conjuntos diferentes (ou seja, ainda não estiverem conectadas no labirinto), remova a parede e junte os conjuntos.
• Se já estiverem no mesmo conjunto, ignore 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 geradora.
• No final, cada célula está conectada às outras sem laços ou seções isoladas.

Como o algoritmo de Kruskal se baseia na fusão de conjuntos, ele pode ser otimizado usando o algoritmo Union-Find, que oferece 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: Link

Leitura adicional

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

• Algoritmo de Árvore Crescente Gerador de Labirinto
• Gerador de labirinto de algoritmo de Eller
• Gerador de labirintos de backtracker recursivo