loading...
Cover image for Introducing Maze Generator [Java]

Introducing Maze Generator [Java]

marksasp95 profile image Marco Suárez Updated on ・3 min read

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)

step-one

Save that position to starts

Step 2 (randomly selecting a neighbor cell)

step-two

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)

step-three

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.

four

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

five

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

10x10

20x20

20x20

50x50

50x50

100x100

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

Posted on by:

marksasp95 profile

Marco Suárez

@marksasp95

I'm the most curious guy I know.

Discussion

markdown guide
 

A maze generator is currently the first piece of code I write when I learn a new language these days because it helps you practice data structures, loops and dynamic allocating.

It also helped me understand how random number generators worked since at first I always got the same maze but had accidentally used a set seed.

Great job on your first post !

 

Creating a 100x100 maze using this algorithm should not take more than one second.

Sample times:

Running de.amr.mazes.simple.test.LargeMazeTest
                Prim: 1.000.000 vertices, (1464 ms)
                 BFS: 1.000.000 vertices, (426 ms)
                 DFS: 1.000.000 vertices, (235 ms)
              Wilson: 1.000.000 vertices, (1744 ms)
  Recursive Division: 1.000.000 vertices, (145 ms)
       Aldous Broder: 10.000 vertices, (95 ms)
         Binary Tree: 1.000.000 vertices, (54 ms)
             Kruskal: 1.000.000 vertices, (2563 ms)
          Sidewinder: 1.000.000 vertices, (89 ms)
        Growing Tree: 1.000.000 vertices, (1378 ms)
Tests run: 10, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 15.52 sec

For many more maze algorithms see github.com/armin-reichert/mazes