Introducing Maze Generator [Java]

This is a project I made for the subject Data Structures at my university.

Its name describes it pretty much, it generates random labyrinths, and its main logical resource is the Aldous-Broder algorithm.

This algorithm is known for making decisions randomly, thus the time it takes to create a labyrinth (depending on its dimensions) can be unpredictable (100x100 labyrinths can take up to 45 seconds).

Aldous-Broder algorithm

The Aldous-Broder algorithm works exclusively for maze generation, it uses a matrix to create the paths. Made simple, this is the algorithm:

1.- Take any cell randomly and check it.
2.- Take any neighbor cell (not diagonal), if that cell hasn't been checked, check it.
3.- Repeat step 2 until all the cells are checked.

You can see a full explanation and real-time demonstration here.

Checking cells

We check every cell by establishing a point with its coordinates, we connect each point to create a route. To trace this route we must have a record of where we've been, so we create two 2D arrays (starts and ends).

Let's see a quick example:

Step 1 (randomly selecting a starting cell)

Save that position to starts

Step 2 (randomly selecting a neighbor cell)

For it was unchecked, check it and save that position to ends. See that for every end we must have a new start, which is the previously visited cell.

Step 3 (repeat step 2 until every cell is checked)

We also got rid of the grid (it was just for you to see the matrix).

We now have all the necessary data to draw the maze, we just have to connect every start and end point with a straight line.

Our maze is ready, but it doesn't look quite good, so I increase the stroke of the lines.

That's more like it.

This is the code that draws the maze, I'll just give you the JPanel:

package interfazgrafica;

import javax.swing.*;
import java.awt.*;

class MazeIterfacePanel extends JComponent{ // JPANEL

    private int dims, thickness, margin;

    public MazeInterfacePanel(int dims, int thickness, int margin){
        this.dims = dims;
        this.thickness = thickness;
        this.margin = margin;
    }

    public void paintComponent(Graphics g){

        super.paintComponent(g);

        Graphics2D g2 = (Graphics2D) g;
        BasicStroke stroke = new BasicStroke(thickness);
        g2.setStroke(stroke);
        int j = 0;

        for (int i = 0; i < dims*dims; i++) { 
            g2.drawLine(Labyrinth.starts[i][j] * (500/dims) + margin, 
                        Labyrinth.starts[i][j+1] * (500/dims) + margin, 
                        Labyrinth.ends[i][j] * (500/dims) + margin, 
                        Labyrinth.ends[i][j+1] * (500/dims) + margin);
        }
    }     
}

The drawing is made by the drawLine function from the java.awt.Graphics class, it takes four parameters: the first two are the starting point of the line, the others are the ending point. I position these points using pixels as unit, I use dims to reduce the 500 pixels translation factor: say the maze dimensions are 50x50, then dims = 50. Plus, the JPanel is created with a especial stroke and margin depending on the dimensions. All this is what makes our mazes occupy the same space, and remember our starts and ends arrays? This is where we use them.

The coordinates on the window are: the indexes of our arrays multiplied by a translation factor reduced according to the dimensions, with an added margin.

This is what some actual random mazes look like:

10x10

20x20

50x50

100x100

Maze Generator also saves every generated maze in text files, these contain the time they took to generate as well, their directory is specified at the start of the program.

Epilogue

When I was given this project I had no idea how to do it, just basic OOP knowledge and almost no Java experience, and it was by doing it that I learned so much, this is an advice for every beginner out there.

This is my first actual post, and all your observations are welcome in the comments.

Cover image from Dreamlandia