Generador de laberintos del algoritmo de Kruskal

El algoritmo de Kruskal es un algoritmo de árbol de expansión mínimo que se puede adaptar para la generación de laberintos. Es particularmente eficaz para crear laberintos perfectos. Una alternativa al algoritmo de Kruskal es el algoritmo de Prim, que también es un algoritmo de árbol de expansión mínimo, pero como ambos generan laberintos idénticos y el de Kruskal se ejecuta más rápido, no me he molestado en implementar el de Prim.

Un laberinto perfecto es un laberinto en el que hay exactamente un camino desde cualquier punto del laberinto a cualquier otro punto. Eso significa que no puedes acabar dando vueltas en círculo, pero a menudo te encontrarás con callejones sin salida que te obligarán a dar media vuelta y volver atrás.

Los mapas de laberintos generados aquí incluyen una versión por defecto sin posiciones de inicio y final, para que puedas decidirlas por ti mismo: habrá una solución desde cualquier punto del laberinto a cualquier otro punto. Si quieres inspirarte, puedes activar una posición inicial y final sugeridas, e incluso ver la solución entre ambas.

Acerca del algoritmo de Kruskal

El algoritmo de Kruskal fue creado por Joseph Bernard Kruskal, Jr., matemático, estadístico y científico informático estadounidense. Describió el algoritmo por primera vez en 1956 en su artículo "Sobre el subárbol de expansión más corto de un gráfico y el problema del viajante".

El algoritmo está diseñado para encontrar el árbol de expansión mínimo (MST) de un gráfico, garantizando que todos los vértices estén conectados con el mínimo peso total de borde posible y evitando ciclos.

Cómo funciona el algoritmo de Kruskal para la generación de laberintos

Paso 1: Inicializar

• Trate cada celda del laberinto como un conjunto separado (un componente único).
• Enumere todas las paredes entre celdas adyacentes como bordes potenciales.

Paso 2: Ordenar las paredes

• Mezclar u ordenar aleatoriamente las paredes. Si se implementa como un verdadero algoritmo de Kruskal, ordenar las paredes en un orden aleatorio (ya que la generación del laberinto no requiere pesos).

Paso 3: Procesar las paredes

• Iterar a través de las paredes revueltas.
• Si las dos celdas divididas por la pared pertenecen a conjuntos diferentes (es decir, aún no están conectadas en el laberinto), elimine la pared y fusione los conjuntos.
• Si ya están en el mismo conjunto, salta el muro (para evitar ciclos).

Paso 4: Continuar hasta completar

• Repita este proceso hasta que todas las celdas estén conectadas, formando un único árbol de expansión.
• Al final, cada célula está conectada con las demás sin bucles ni secciones aisladas.

Dado que el algoritmo de Kruskal se basa en la fusión de conjuntos, se puede optimizar mediante el algoritmo Union-Find, que proporciona una forma eficiente de rastrear celdas conectadas durante la generación del laberinto. Puede ver mi implementación en PHP del algoritmo Union-Find aquí: Conjunto disjunto (algoritmo de búsqueda de unión) en PHP