Generador de laberints d'algoritmes de Kruskal

L'algoritme de Kruskal és un algorisme d'arbre d'abast mínim que es pot adaptar per a la generació de laberints. És especialment eficaç per crear laberints perfectes. Una alternativa a l'algoritme de Kruskal és l'algoritme de Prim, que també és un algorisme d'arbre d'abast mínim, però com que generen laberints idèntics i el de Kruskal s'executa més ràpid, no m'he molestat en implementar el de Prim.

Un laberint perfecte és un laberint en el qual hi ha exactament un camí des de qualsevol punt del laberint fins a qualsevol altre punt. Això vol dir que no pots acabar donant voltes, però sovint et trobaràs amb carrerons sense sortida, obligant-te a donar la volta i tornar enrere.

Els mapes de laberint generats aquí inclouen una versió predeterminada sense cap posició d'inici i d'arribada, de manera que les podeu decidir vosaltres mateixos: hi haurà una solució des de qualsevol punt del laberint fins a qualsevol altre punt. Si voleu inspiració, podeu activar una posició d'inici i d'arribada suggerida, i fins i tot veure la solució entre les dues.

Sobre l'algoritme de Kruskal

L'algorisme de Kruskal va ser creat per Joseph Bernard Kruskal, Jr., un matemàtic, estadístic i informàtic nord-americà. Va descriure per primera vegada l'algorisme l'any 1956 en el seu article "Sobre el subarbre d'abast més curt d'un gràfic i el problema del venedor ambulant".

L'algoritme està dissenyat per trobar l'arbre d'abast mínim (MST) d'un gràfic, assegurant que tots els vèrtexs estiguin connectats amb el pes total de vora mínim possible, evitant els cicles.

Com funciona l'algoritme de Kruskal per a la generació de laberints

Pas 1: inicialitzar

• Tracta cada cel·la del laberint com un conjunt separat (un component únic).
• Enumereu totes les parets entre cel·les adjacents com a vores potencials.

Pas 2: Ordena les parets

• Barrejar o ordenar aleatòriament les parets. Si ho implementeu com un veritable algorisme de Kruskal, ordena les parets en un ordre aleatori (ja que la generació de laberints no requereix pesos).

Pas 3: processar parets

• Itera a través de les parets remenades.
• Si les dues cel·les dividides per la paret pertanyen a conjunts diferents (és a dir, encara no estan connectades al laberint), traieu la paret i fusioneu els conjunts.
• Si ja estan en el mateix conjunt, saltar la paret (per evitar cicles).

Pas 4: Continueu fins a la finalització

• Repetiu aquest procés fins que totes les cel·les estiguin connectades, formant un únic arbre.
• Al final, cada cel·la està connectada amb les altres sense bucles ni seccions aïllades.

Com que l'algoritme de Kruskal es basa en la fusió de conjunts, es pot optimitzar mitjançant l'algorisme Union-Find, que proporciona una manera eficient de fer un seguiment de les cèl·lules connectades durant la generació del laberint. Podeu veure la meva implementació PHP de l'algorisme Union-Find aquí: Conjunt disjunt (algoritme Union-Find) en PHP