Generador de laberints d'algoritmes de Kruskal

L'algoritme de Kruskal és un algorisme d'arbre d'expansió mínima que es pot adaptar per a la generació de laberints. És particularment 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'expansió mínima, però com que generen laberints idèntics i el de Kruskal funciona més ràpid, no m'he molestat a 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'algoritme de Kruskal va ser creat per Joseph Bernard Kruskal, Jr., un matemàtic, estadístic i informàtic estatunidenc. Va descriure l'algoritme per primera vegada el 1956 al seu article "Sobre el subarbre de distribució més curta d'un gràfic i el problema del viatjant de comerç".

L'algoritme està dissenyat per trobar l'arbre d'expansió mínim (MST) d'un graf, garantint que tots els vèrtexs estiguin connectats amb el pes total d'aresta mínim possible i 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).
• Enumera totes les parets entre cel·les adjacents com a possibles vores.

Pas 2: Ordenar les parets

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

Pas 3: Processar les parets

• Iterar 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), elimineu la paret i fusioneu els conjunts.
• Si ja són al mateix conjunt, salta la paret (per evitar cicles).

Pas 4: Continua fins a la finalització

• Repetiu aquest procés fins que totes les cel·les estiguin connectades, formant un únic arbre d'expansió.
• Al final, cada cel·la està connectada a 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'algoritme Union-Find, que proporciona una manera eficient de rastrejar cel·les connectades durant la generació de laberints. Podeu veure la meva implementació PHP de l'algoritme Union-Find aquí: Enllaç

Lectures addicionals

Si t'ha agradat aquesta publicació, també et poden agradar aquests suggeriments:

• Caça i mata generador de laberints
• Generador de laberints d'algoritmes d'Eller
• Generador de laberints d'algoritmes de Wilson