Introducing Maze Generator [Java]
Tags: showdev, java, maze
Published: 2018-01-04 02:03:24

---
cover_image: https://thepracticaldev.s3.amazonaws.com/i/9vj2bll4b6c31dqfqfdb.jpg
title: Introducing Maze Generator [Java]
published: true
description: A program that generates random mazes.
tags: #showdev #java #maze
---

*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](http://weblog.jamisbuck.org/2011/1/17/maze-generation-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](http://weblog.jamisbuck.org/2011/1/17/maze-generation-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](http://weblog.jamisbuck.org/2011/1/17/maze-generation-aldous-broder-algorithm).

###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](https://thepracticaldev.s3.amazonaws.com/i/ata031a8s4tjlbpxzdw2.jpg)

Save that position to *starts*

Step 2 (randomly selecting a neighbor cell)

![step-two](https://thepracticaldev.s3.amazonaws.com/i/ltjvgetcucmh0epl9qoe.jpg)

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](https://thepracticaldev.s3.amazonaws.com/i/m5vcd9yhmfoyqm9fkcao.jpg)

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](https://thepracticaldev.s3.amazonaws.com/i/cr2e4h6su0go6up5kmxa.jpg)  

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

![five](https://thepracticaldev.s3.amazonaws.com/i/03p97n71emp0z3sxj0q2.jpg)

That's more like it.

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

```java
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](https://thepracticaldev.s3.amazonaws.com/i/hsvqzoo7r1dtnrmooglf.JPG)

###20x20
![20x20](https://thepracticaldev.s3.amazonaws.com/i/l2btabtdx3tla9iteak0.JPG)

###50x50
![50x50](https://thepracticaldev.s3.amazonaws.com/i/ise18lha261xcm3do7pd.JPG)

###100x100
![100x100](https://thepracticaldev.s3.amazonaws.com/i/nzkv5f0poz1elcbd05gg.JPG)

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*