Sigueme en Facebook Sigueme en Twitter Sigueme en Instagram Sigueme en Youtube
JC Mouse Bolivia
Index / Java / Generación de laberintos: Algoritmo de Aldous-Broder

Generación de laberintos: Algoritmo de Aldous-Broder

Autor jc mouse martes, octubre 23, 2018

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

maze 3

Se elige «al azar» una casilla

aletaorio

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

casilla adyacente

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

laberinto tunel

Y se repite nuevamente buscando otra casilla hasta cubrirlas todas

casilla siguiente

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!!!?

Tags

Si te ha gustado podrías compartirlo o dejar un comentario. ¡Muchas gracias!
Autor: JC Mouse

Yo soy yo :) JC Mouse, Soy orgullosamente boliviano soy fundador y CEO de la web jc-Mouse.net uno de las pocas web en emprendimiento y tecnología en Bolivia.

Toda la información que encuentres en este sitio es y sera completamente gratis siempre, puedes copiar, descargar y re-publicar si así lo deseas en otros blogs o sitios web, solo te pido a cambio que dejes una referencia a esta web. Esto nos ayuda a crecer y seguir aportando. Bye

Enjoy! :)

También Te Podría Interesar

Potigol: Lenguaje de programación en portugues

Potigol: Lenguaje de programación en portugues

Oi galera, en esta oportunidad les traigo una curiosidad que encontré por casualidad perdiendo el tiempo en Internet, se...

Crear un plugin wordpress «Banned Word»

Crear un plugin wordpress «Banned Word»

En este post, escribiremos un sencillo plugin para wordpress el cual consistirá en reemplazar palabras en los comentario...

THE LAST JEDI: El Salar de Uyuni forma parte del universo Star Wars

THE LAST JEDI: El Salar de Uyuni forma parte del universo Star Wars

Así es, el Salar de Uyuni ubicado en el suroeste de Bolivia con una extensión de 10582 Km2 y a una altitud 3663 mts sobr...

Crea App multilenguaje con Android Studio

Crea App multilenguaje con Android Studio

En este post aprenderemos los pasos básicos para construir una aplicación android con soporte multilenguaje, utilizaremo...

Guardar reporte PDF directamente con Jasperreports

Guardar reporte PDF directamente con Jasperreports

Guardar un reporte PDF creado en iReport no es tan diferente de solo visualizarlo en pantalla. En este ejemplo se hace u...

Arrastrar y abrir archivo Excel

Arrastrar y abrir archivo Excel

En este post, crearemos una aplicación java que nos permita arrastrar un archivo excel hacia la aplicación, abrirlo y ca...

Comparte lo que sabes

Categorias

Últimas entradas

Las empresas GeoSystems e Inteligencia Geoespacial (Igeo) en coordinación con el Gobierno Nacional de Bolivia,  desarrol...

¿Sabia que por la pandemia que azota a la mayoría de los países de la Tierra, la mitad de la población estudiantil del m...

El gigante de la tecnología Microsoft ha lanzado un mapa interactivo para proporcionar información sobre la propagación...

El gigante de la informática Google, ante la reciente pandemia mundial declarada por la OMS (Organización Mundial de la...

Herramientas

Generador de Enlaces a Whatsapp