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

Migrar proyecto Netbeans a Eclipse

Migrar proyecto Netbeans a Eclipse

En ocasiones por motivos cualesquiera que sea queremos pasar proyectos hechos en netbeans a Eclipse, Netbeans cuenta con...

Primeros pasos en Jaspersoft Studio

Primeros pasos en Jaspersoft Studio

¿Que es Jaspersoft Studio? Jaspersoft Studio es el nuevo diseñador de informes basado en Eclipse para JasperReports y Ja...

Obteniendo coordenadas XY con Touch Event

Obteniendo coordenadas XY con Touch Event

Los smartphone al no tener los típicos botones de los celulares, su pantalla es sensible al movimiento, esto se llama...

Libreria swing BlackTabbedPane

Libreria swing BlackTabbedPane

Continuación del tutorial [Personalizar JTabbedPane con Netbeans]. La clase BlackTabbedPaneUI que extendemos de BasicTab...

Pon a prueba tus conocimientos sobre comandos Linux

Pon a prueba tus conocimientos sobre comandos Linux

Como dice un viejo dicho, “La practica hace al maestro” y en el mundo de la programación no es diferente, po...

Modificar las pestañas de JTabbedPane

Modificar las pestañas de JTabbedPane

En este tutorial veremos lo fácil que es personalizar las pestañas de un JTabbedPane con unas cuantas lineas de código y...

Comparte lo que sabes

Categorias

Últimas entradas

Netbeans es uno de los entornos de desarrollo integrado (Integrated Development Environment – IDE)  más conocidos...

Geany es un editor de texto para Sistemas Operativos Linux, windows y MAC que utiliza el kit de herramientas GTK+ con ca...

En este post te hablaremos sobre una interesante herramienta para le lectura y edición de metadatos que no te debe de fa...

Java cuenta con la clase java.lang.Math  la cual contiene métodos para realizar operaciones numéricas básicas como las f...

Android Bolivia

MAUS