Gerador de labirintos do algoritmo de Kruskal

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

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.

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. Descreveu o algoritmo pela primeira vez em 1956, no seu artigo "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.

O algoritmo foi concebido para encontrar a árvore geradora mínima (MST) de um grafo, garantindo que todos os vértices estão ligados com o peso total mínimo possível das arestas enquanto se evitam ciclos.

Como Funciona o Algoritmo de Kruskal para a Geração de Labirintos

Passo 1: Inicializar

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

Passo 2: Ordenar Paredes

• Baralha ou ordena aleatoriamente as paredes. Se for implementado como um verdadeiro algoritmo de Kruskal, ordena as paredes por ordem aleatória (já que a geração de labirintos não requer pesos).

Passo 3: Processar Paredes

• Iterar pelas paredes embaralhadas.
• Se as duas células divididas pela parede pertencerem a conjuntos diferentes (ou seja, ainda não estão ligadas no labirinto), remova a parede e funda os conjuntos.
• Se já estiverem no mesmo conjunto, salta a parede (para evitar ciclos).

Passo 4: Continuar até à conclusão

• Repete-se este processo até que todas as células estejam conectadas, formando uma única árvore que se estende.
• No final, cada célula está ligada às outras sem laços ou secções isoladas.

Como o algoritmo de Kruskal depende da fusão de conjuntos, pode ser otimizado usando o algoritmo Union-Finding, que fornece uma forma eficiente de rastrear células ligadas durante a geração de labirintos. Pode ver a minha implementação PHP do algoritmo Union-Find aqui: Link

Leitura adicional

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

• Gerador de labirintos do algoritmo de Eller
• Gerador de labirintos do algoritmo de Wilson
• Gerador de labirintos com algoritmo de árvore em crescimento