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. É 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 geram labirintos idênticos e o de Kruskal corre 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 informático norte-americano. Descreveu o algoritmo pela primeira vez em 1956 no seu artigo "Sobre a subárvore de menor abrangência de um grafo e o problema do caixeiro viajante".

O algoritmo foi desenhado para encontrar a árvore geradora mínima (MST) de um grafo, garantindo que todos os vértices estão ligados com o menor peso total de arestas possível, evitando 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 células adjacentes como arestas potenciais.

Passo 2: Classifique as paredes

• Baralhe ou ordene as paredes aleatoriamente. Se implementar como um verdadeiro algoritmo de Kruskal, classifique as paredes numa ordem aleatória (uma vez que a geração de labirintos não requer pesos).

Etapa 3: Processar Paredes

• Repita através das paredes baralhadas.
• Se as duas células divididas pela parede pertencerem a conjuntos diferentes (ou seja, ainda não estiverem ligadas no labirinto), retire a parede e junte os conjuntos.
• Se já estiverem no mesmo conjunto, salta a parede (para evitar ciclos).

Passo 4: Continue até à conclusão

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

Como o algoritmo de Kruskal depende da fusão de conjuntos, pode ser otimizado utilizando o algoritmo Union-Find, que fornece uma forma eficiente de rastrear as células ligadas durante a geração do labirinto. Pode ver a minha implementação PHP do algoritmo Union-Find aqui: Conjunto Disjunto (Union-Find Algorithm) em PHP