Gerador de labirintos do algoritmo de Kruskal

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.

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