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:
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!!!?
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! :)
Esta aplicacion permite escalar una imagen desde java sin perder las proporciones de la misma, utiliza SCALE_AREA_AVERAG...
Servicio Web Un servicio web (en inglés, Web Service o Web services) es una tecnología que utiliza un conjunto de protoc...
Completa agenda para organizar tu vida personal y/o profesional, si te olvidas de acontecimientos familiares, citas de t...
Los smartphone al no tener los típicos botones de los celulares, su pantalla es sensible al movimiento, esto se llama «t...
Si quieres cambiar el nombre de tus atributos sin tener que reescribir código java por X o Y razón, GSON te permite reno...
Las matemáticas son fundamentales para la vida y aparte de las actividades clásicas de enseñanza desarrolladas en el aul...
Si trabajas con redes sociales (RRSS) a continuación te muestro tres herramintas gratuitas que te ayudaran a la hora de...
Por lo general se usan transacciones a nivel base de datos y posteriormente se llaman estos a través de procedimientos a...
En este post, aprenderemos como conectar Visual Basic 6 con SQL Server, abrir una tabla, leer su contenido y mostrar est...
Lo que veremos en este post es la configuración del driver para PHP de SQL Server que ha creado Microsoft el cual permit...