Generación de laberintos I.2. Algoritmo de Aldous-Broder.

El Algoritmo de Aldous-Broder es otro método para generar un laberinto aleatorio. Funcionamiento para la generación es el siguiente:

    1. Comenzar en un vértice aleatorio del grafo.
    2. Elegir un vecino aleatorio del vértice actual.
    3. Si el vecino no ha sido visitado, añadir la arista entre el vértice actual y el vecino al árbol de expansión.
    4. Moverse al vecino elegido (sea visitado o no).
    5. Repetir los pasos 2-4 hasta que todos los vértices hayan sido visitados.

Este algoritmo es simple pero ineficiente, especialmente para grafos grandes, ya que puede tomar mucho tiempo para visitar todos los vértices.

 

Código (AldousBroderMaze.java):

package aldousbrodermaze;

import java.util.*;

public class AldousBroderMaze {

    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private final int width;
    private final int height;
    private final boolean[][] maze;

    public AldousBroderMaze(int width, int height) {
        this.width = width;
        this.height = height;
        this.maze = new boolean[height * 2 + 1][width * 2 + 1];
    }

    public void generateMaze() {
        Random rand = new Random();
        int x = rand.nextInt(width) * 2 + 1;
        int y = rand.nextInt(height) * 2 + 1;
        int unvisited = width * height - 1;

        maze[y][x] = true;

        while (unvisited > 0) {
            int[] direction = DIRECTIONS[rand.nextInt(DIRECTIONS.length)];
            int newX = x + direction[0] * 2;
            int newY = y + direction[1] * 2;

            if (newX > 0 && newX < maze[0].length && newY > 0 && newY < maze.length) {
                if (!maze[newY][newX]) {
                    maze[newY][newX] = true;
                    maze[y + direction[1]][x + direction[0]] = true;
                    unvisited--;
                }
                x = newX;
                y = newY;
            }
        }
    }

    public void printMaze() {
        for (boolean[] row : maze) {
            for (boolean cell : row) {
                System.out.print(cell ? "  " : "██");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        AldousBroderMaze maze = new AldousBroderMaze(10, 10);
        maze.generateMaze();
        maze.printMaze();
    }
}


Resultado:

run:
██████████████████████████████████████████
██              ██  ██      ██          ██
██  ██████████████  ██████  ██  ██████████
██              ██      ██  ██      ██  ██
██  ██  ██████████████  ██  ██  ██████  ██
██  ██      ██          ██  ██          ██
██  ██████████████  ██████  ██  ██████  ██
██              ██  ██          ██  ██  ██
██  ██████████  ██  ██████  ██  ██  ██████
██  ██  ██              ██  ██      ██  ██
██  ██  ██████████████████  ██████  ██  ██
██          ██  ██      ██  ██          ██
██████████  ██  ██████  ██  ██  ██  ██████
██          ██  ██  ██      ██  ██      ██
██████████  ██  ██  ██████████  ██████████
██              ██      ██  ██      ██  ██
██████████████  ██  ██████  ██  ██████  ██
██                      ██  ██  ██      ██
██████████  ██  ██████  ██  ██  ██████  ██
██          ██  ██                      ██
██████████████████████████████████████████
BUILD SUCCESSFUL (total time: 0 seconds)