Generación de laberintos: Algoritmo de Aldous-Broder

El Algoritmo de Aldous-Broder llamado así por dos matemáticos, David Aldous and A. Broder (quienes trabajaban en la investigación de arboles uniformes), es uno de los algoritmos para generar laberintos más sencillos que existen, pertenece a  la categoría de «cavar túneles», lo que quiere decir que dado una matriz nxn, se cava un camino a lo ancho y alto de la matriz hasta cubrirlo en su totalidad.

El algoritmo es el siguiente:

1. Especificar el tamaño del laberinto. Una matriz NxM.
2. Elegir al azar una casilla dentro del laberinto.
3. Desplazarse a una casilla vecina adyacente al azar (vertical u horizontalmente, no en diagonal) , cavar un túnel hacia la casilla anterior en el caso de que la nueva casilla no haya sido visitada.
4. Repetir el paso 3 hasta que todas las casillas hayan sido visitadas.
   Marcar la ubicación de la entrada o del punto inicial de la exploración y la ubicación de la salida.

Este algoritmo, si bien consigue su objetivo de trazar un laberinto, es ineficiente porque visita la misma casilla varias veces dado que se mueve al azar y a más grande el laberinto, más tiempo tardara en visitar todas y cada una de las casillas.

A continuación un ejemplo trivial del algoritmo:

Dado una matriz 3×3

Se elige «al azar» una casilla

A continuación se desplaza a una casilla vecina adyacente al azar (vertical u horizontalmente, no en diagonal)

Si la casilla no ha sido visitada aun, se cava un túnel entre ambas

Y se repite nuevamente buscando otra casilla hasta cubrirlas todas

El siguiente video muestra el anterior proceso para varios tamaños de laberintos, se puede apreciar como a mayor dimensión del laberinto, más tiempo consumirá recorrer cada casilla y por tanto el tiempo para generar el laberinto es cada vez mayor.

enjoy!!!?