Home Discussions Write at Opengenus IQ
×

Search anything:

Maze Generator and Solver in Java

Binary Tree book by OpenGenus

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

In this article, we will develop a Java program that generates a Maze and solves it using Depth-First Search with help of Backtracking. This is a strong profile for SDE portfolio.

Introduction


A Maze is a complex network of paths or passages, with many branching points and dead ends.

  • Maze generation and solving algorithms have been a topic of interest in computer science and game development for decades.
  • The goal of a maze generator is to create a complex, yet solvable maze that can challenge the problem-solving skills of a user.
  • The maze solver, on the other hand, aims to find a path from the entrance to the exit of the maze.

One of the most popular maze generation algorithms is the depth-first search (DFS) algorithm.

  • The DFS algorithm works by creating a maze through a recursive process of choosing a random starting cell and carving out a path in a particular direction until it hits a dead end.
  • At this point, the algorithm backtracks to the last cell where it had multiple directions to choose from and continues carving out paths until the entire maze is created.

The path-finding algorithm can use different approaches such as depth-first search, breadth-first search, or A* algorithm.

  • The depth-first search algorithm is used to explore all the possible paths starting from the entrance until it reaches the exit.
  • It checks if a particular cell is visited or not and marks it as visited if not.
  • The algorithm backtracks if it reaches a dead end or a visited cell, and continues the exploration until it reaches the exit.

In this project, we will explore maze generation and solving algorithms and implement them using Java programming language. We will also visualize the generated mazes and the paths found by the solving algorithms using popular Java Packages such as Swing and Abstract Window Toolkit (AWT).

Backtracking


Backtracking is a general algorithmic technique that involves exploring all possible solutions to a problem by incrementally building candidates and abandoning a candidate as soon as it determines that the candidate cannot be completed to a valid solution.

  • This technique is often used to solve constraint satisfaction problems, such as generating and solving mazes, by systematically searching for a solution through trial and error.
  • Backtracking algorithms typically use recursion to explore the search space and backtrack when a dead end is reached, allowing them to efficiently find a solution without exploring every possible candidate.

Depth-First Search Algorithm


DFS (Depth-First Search) is a graph traversal algorithm that explores as far as possible along each branch before backtracking.

  • In DFS, the algorithm starts at the root node (or any arbitrary node) and explores as far as possible along each branch before backtracking.
  • This is accomplished by maintaining a stack of nodes to be visited. When a node is visited, all of its neighbors are added to the stack in a specific order, and the next node to be visited is then popped off the stack.
  • The algorithm continues until the stack is empty, at which point all nodes in the graph have been visited.

DFS is commonly used for solving problems that can be represented as a graph or tree, such as maze solving and pathfinding.

Code


Let's get into code

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

/**
 * Creates a random maze, then solves it by finding a path from the
 * upper left corner to the lower right corner. (After doing
 * one maze, it waits a while then starts over by creating a
 * new random maze.)
 */
public class Maze extends JPanel implements Runnable {

    // a main routine makes it possible to run this class as a program
    public static void main(String[] args) {
        // Code will be written here
    }

    int[][] maze; // Description of state of maze. The value of maze[i][j]
                  // is one of the constants wallCode, pathcode, emptyCode,
                  // or visitedCode. (Value can also be negative, temporarily,
                  // inside createMaze().)
                  // A maze is made up of walls and corridors. maze[i][j]
                  // is either part of a wall or part of a corridor. A cell
                  // cell that is part of a corridor is represented by pathCode
                  // if it is part of the current path through the maze, by
                  // visitedCode if it has already been explored without finding
                  // a solution, and by emptyCode if it has not yet been explored.

    final static int backgroundCode = 0;
    final static int wallCode = 1;
    final static int pathCode = 2;
    final static int emptyCode = 3;
    final static int visitedCode = 4;

    Color[] color; // colors associated with the preceding 5 constants;
    int rows = 41; // number of rows of cells in maze, including a wall around edges
    int columns = 51; // number of columns of cells in maze, including a wall around edges
    int border = 0; // minimum number of pixels between maze and edge of panel
    int sleepTime = 5000; // wait time after solving one maze before making another
    int speedSleep = 30; // short delay between steps in making and solving maze
    int blockSize = 12; // size of each cell

    int width = -1; // width of panel, to be set by checkSize()
    int height = -1; // height of panel, to be set by checkSize()

    int totalWidth; // width of panel, minus border area (set in checkSize())
    int totalHeight; // height of panel, minus border area (set in checkSize())
    int left; // left edge of maze, allowing for border (set in checkSize())
    int top; // top edge of maze, allowing for border (set in checkSize())

    boolean mazeExists = false; // set to true when maze[][] is valid; used in
                                // redrawMaze(); set to true in createMaze(), and
                                // reset to false in run()

    public Maze() {
        // Code will be written here
    }

    void checkSize() {
        // Code will be written here
    }

    synchronized protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        checkSize();
        redrawMaze(g);
    }

    void redrawMaze(Graphics g) {
        // Code will be written here
    }

    public void run() {
        // Code will be written here
    }

    void makeMaze() {
        // Code will be written here
    }

    synchronized void tearDown(int row, int col) {
        // Code will be written here
    }

    void fill(int row, int col, int replace, int replaceWith) {
        // Code will be written here
    }

    boolean solveMaze(int row, int col) {
        // Code will be written here
    }
}
  • The above class is the basic structure of our maze generator and solver in JAVA.
  • we have imported two packages namely AWT and Swing. These are :
    • AWT : The Abstract Window Toolkit (AWT) supports Graphical User Interface (GUI) programming. A set of native user interface components
    • Swing : Swing is a Java Foundation Classes [JFC] library and an extension of the Abstract Window Toolkit [AWT]. Swing offers much-improved functionality over AWT, new components, expanded components features, and excellent event handling with drag-and-drop support.
  • Above class contains required properties such as
    • [ backgroundCode, wallcode, pathcode , emptycode, visited code ] codes for different types of cells
    • [ rows, columns, border, sleeptime, speedtime, blocksize ] measurements and specs for our maze to visualize.
  • Methods are empty. Don't worry, we will code every method one by one and explain it.

main() method


public static void main(String[] args) {
        JFrame window = new JFrame("Maze Solver");
        window.setContentPane(new Maze());
        window.pack();
        window.setLocation(120, 80);
        window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        window.setVisible(true);
}

This code is a Java program that creates a window titled "Maze Solver" using the JFrame class.

  • The program sets the content pane of the window to a new instance of the Maze class, which is responsible for generating and displaying a maze.
  • The pack() method is used to resize the window to fit its contents.
  • The setLocation() method is used to set the position of the window on the screen.
  • The setDefaultCloseOperation() method is used to set what happens when the user closes the window (in this case, the program will exit).
  • Finally, the setVisible() method is used to make the window visible on the screen.

Maze() constructer


public Maze() {
    color = new Color[] {
            new Color(200, 0, 0),
            new Color(200, 0, 0),
            new Color(128, 128, 255),
            Color.WHITE,
            new Color(200, 200, 200)
    };
    setBackground(color[backgroundCode]);
    setPreferredSize(new Dimension(blockSize * columns, blockSize * rows));
    new Thread(this).start();
}

This code is the constructor for the Maze class.

  • It initializes the color array and sets the background color of the maze based on the value of backgroundCode.
  • It also sets the preferred size of the maze based on the number of rows and columns
  • It also starts a new thread by calling the run() method of the current object.

checksize() method


void checkSize() {
    // Called before drawing the maze, to set parameters used for drawing.
    if (getWidth() != width || getHeight() != height) {
        width = getWidth();
        height = getHeight();
        int w = (width - 2 * border) / columns;
        int h = (height - 2 * border) / rows;
        left = (width - w * columns) / 2;
        top = (height - h * rows) / 2;
        totalWidth = w * columns;
        totalHeight = h * rows;
    }
}
  • This method checks the size of the maze before drawing it and sets the parameters used for drawing.
  • If the current width and height of the maze are not equal to the stored values, the method updates the width, height, and other parameters such as the size of each block and the location of the maze.
  • This ensures that the maze is properly centered within the window and that each block is drawn with the correct size.

redraw() and paintComponent() methods


synchronized protected void paintComponent(Graphics g) {
    super.paintComponent(g);
    checkSize();
    redrawMaze(g);
}

void redrawMaze(Graphics g) {
    // draws the entire maze
    if (mazeExists) {
        int w = totalWidth / columns; // width of each cell
        int h = totalHeight / rows; // height of each cell
        for (int j = 0; j < columns; j++)
            for (int i = 0; i < rows; i++) {
                if (maze[i][j] < 0)
                    g.setColor(color[emptyCode]);
                else
                    g.setColor(color[maze[i][j]]);
                g.fillRect((j * w) + left, (i * h) + top, w, h);
            }
    }
}

This is the paintComponent method that gets called whenever the panel is being redrawn.

  • It first calls the checkSize method to ensure that the size and dimensions of the maze are correct.
  • Then, it calls the redrawMaze method to actually draw the maze on the graphics object passed in as an argument.

The redrawMaze method iterates over the 2D array maze and draws each cell as a rectangle with the appropriate color.

  • The size of each cell is calculated based on the size of the panel and the number of rows and columns in the maze.
  • If maze[i][j] is negative, the cell is considered empty and is drawn with the empty color.
  • Otherwise, the color corresponding to the value in maze[i][j] is used.

run() method


public void run() {
    // run method for thread repeatedly makes a maze and then solves it
    try {
        Thread.sleep(1000);
    } // wait a bit before starting
    catch (InterruptedException e) {
    }
    while (true) {
        makeMaze();
        solveMaze(1, 1);
        synchronized (this) {
            try {
                wait(sleepTime);
            } catch (InterruptedException e) {
            }
        }
        mazeExists = false;
        repaint();
    }
}

This code defines the run() method which is executed by the thread.

  • Firstly, it waits for a second before starting. Then it enters an infinite loop which continuously generates and solves a maze.
  • Inside the loop, makeMaze() method is called to generate a new maze and solveMaze() method is called to solve the maze starting from the position (1, 1).
  • After solving the maze, the thread is put to sleep for a specified duration of sleepTime. The mazeExists flag is set to false and the repaint() method is called to redraw the maze.
  • The process repeats in a loop until the program is stopped. The synchronization block ensures that the thread sleeps for the specified time before starting to generate a new maze.

makeMaze() method


    void makeMaze() {
    // Create a random maze. The strategy is to start with
    // a grid of disconnected "rooms" separated by walls.
    // then look at each of the separating walls, in a random
    // order. If tearing down a wall would not create a loop
    // in the maze, then tear it down. Otherwise, leave it in place.
    if (maze == null)
        maze = new int[rows][columns];
    int i, j;
    int emptyCt = 0; // number of rooms
    int wallCt = 0; // number of walls
    int[] wallrow = new int[(rows * columns) / 2]; // position of walls between rooms
    int[] wallcol = new int[(rows * columns) / 2];
    for (i = 0; i < rows; i++) // start with everything being a wall
        for (j = 0; j < columns; j++)
            maze[i][j] = wallCode;
    for (i = 1; i < rows - 1; i += 2) // make a grid of empty rooms
        for (j = 1; j < columns - 1; j += 2) {
            emptyCt++;
            maze[i][j] = -emptyCt; // each room is represented by a different negative number
            if (i < rows - 2) { // record info about wall below this room
                wallrow[wallCt] = i + 1;
                wallcol[wallCt] = j;
                wallCt++;
            }
            if (j < columns - 2) { // record info about wall to right of this room
                wallrow[wallCt] = i;
                wallcol[wallCt] = j + 1;
                wallCt++;
            }
        }
    mazeExists = true;
    repaint();
    int r;
    for (i = wallCt - 1; i > 0; i--) {
        r = (int) (Math.random() * i); // choose a wall randomly and maybe tear it down
        tearDown(wallrow[r], wallcol[r]);
        wallrow[r] = wallrow[i];
        wallcol[r] = wallcol[i];
    }
    for (i = 1; i < rows - 1; i++) // replace negative values in maze[][] with emptyCode
        for (j = 1; j < columns - 1; j++)
            if (maze[i][j] < 0)
                maze[i][j] = emptyCode;
}

This method generates a random maze using a strategy that creates a grid of disconnected rooms separated by walls, and then randomly tears down walls between rooms in such a way that it does not create a loop in the maze.

The makeMaze() method generates a random maze using the following steps:

  • Initialize the maze array to a grid of walls and initialize counters for the number of rooms and walls.
  • Create a grid of empty rooms with each room represented by a different negative number in the maze array.
  • Record information about the walls between the rooms in two arrays, wallrow and wallcol.
  • Randomly choose walls from the wallrow and wallcol arrays and remove the wall if it does not create a loop in the maze.
  • Replace negative values in the maze array with the emptyCode value to finalize the maze.

tearDown() method


synchronized void tearDown(int row, int col) {
    // Tear down a wall, unless doing so will form a loop. Tearing down a wall
    // joins two "rooms" into one "room". (Rooms begin to look like corridors
    // as they grow.) When a wall is torn down, the room codes on one side are
    // converted to match those on the other side, so all the cells in a room
    // have the same code. Note that if the room codes on both sides of a
    // wall already have the same code, then tearing down that wall would
    // create a loop, so the wall is left in place.
    if (row % 2 == 1 && maze[row][col - 1] != maze[row][col + 1]) {
        // row is odd; wall separates rooms horizontally
        fill(row, col - 1, maze[row][col - 1], maze[row][col + 1]);
        maze[row][col] = maze[row][col + 1];
        repaint();
        try {
            wait(speedSleep);
        } catch (InterruptedException e) {
        }
    } else if (row % 2 == 0 && maze[row - 1][col] != maze[row + 1][col]) {
        // row is even; wall separates rooms vertically
        fill(row - 1, col, maze[row - 1][col], maze[row + 1][col]);
        maze[row][col] = maze[row + 1][col];
        repaint();
        try {
            wait(speedSleep);
        } catch (InterruptedException e) {
        }
    }
}

  • This method tears down a wall between two adjacent rooms in the maze. The method takes two parameters: the row and column of the wall to be torn down. The method first checks whether the row number is odd or even, which indicates whether the wall separates rooms horizontally or vertically.

  • If the wall is horizontal and the rooms on either side of the wall have different room codes, the method fills in the room codes on both sides of the wall to the same code, tears down the wall, and updates the maze accordingly. The same process is followed for vertical walls.

  • If the room codes on both sides of the wall are already the same, tearing down the wall would create a loop in the maze, so the wall is left in place.

  • The method is synchronized to ensure that only one thread can execute the method at a time, preventing race conditions that might arise if multiple threads try to modify the maze at the same time. The method also includes a call to wait(), which pauses the execution of the thread for a short time to slow down the rate at which the maze is generated.

fill() method


void fill(int row, int col, int replace, int replaceWith) {
    // called by tearDown() to change "room codes".
    if (maze[row][col] == replace) {
        maze[row][col] = replaceWith;
        fill(row + 1, col, replace, replaceWith);
        fill(row - 1, col, replace, replaceWith);
        fill(row, col + 1, replace, replaceWith);
        fill(row, col - 1, replace, replaceWith);
    }
}

The fill() method is a recursive function that is called by the tearDown() method to change "room codes".

  • It takes four arguments: the row and column position in the maze, the value of replace, and the value of replaceWith.
  • The purpose of this method is to find all the cells in the maze that have the value of replace and replace it with the value of replaceWith.
  • It does this by checking if the current cell at the given position has the value of replace.
  • If it does, it changes the value of that cell to replaceWith and then recursively calls fill() on its four neighboring cells (up, down, left, right), passing the same replace and replaceWith arguments.

The recursive call to fill() ensures that all cells in the same "room" as the initial cell with the replace value will be replaced with the replaceWith value.

solveMaze() method


boolean solveMaze(int row, int col) {
    // Try to solve the maze by continuing current path from position
    // (row,col). Return true if a solution is found. The maze is
    // considered to be solved if the path reaches the lower right cell.
    if (maze[row][col] == emptyCode) {
        maze[row][col] = pathCode; // add this cell to the path
        repaint();
        if (row == rows - 2 && col == columns - 2)
            return true; // path has reached goal
        try {
            Thread.sleep(speedSleep);
        } catch (InterruptedException e) {
        }
        if (solveMaze(row - 1, col) || // try to solve maze by extending path
                solveMaze(row, col - 1) || // in each possible direction
                solveMaze(row + 1, col) ||
                solveMaze(row, col + 1))
            return true;
        // maze can't be solved from this cell, so backtrack out of the cell
        maze[row][col] = visitedCode; // mark cell as having been visited
        repaint();
        synchronized (this) {
            try {
                wait(speedSleep);
            } catch (InterruptedException e) {
            }
        }
    }
    return false;
}

This code is used to solve the maze by following a path from a given starting position (row, col).

  • It returns true if a solution is found, meaning the path has reached the lower right cell, and false otherwise.
  • First, it checks if the cell at (row, col) is empty, and if so, it adds it to the path by setting its value to pathCode.
  • It then checks if the path has reached the goal (lower right cell) and if so, it returns true.
  • If the goal has not been reached yet, it tries to extend the path by recursively calling solveMaze() on each of the neighboring cells in each possible direction (up, down, left, right).
  • If a solution is found by any of these recursive calls, it returns true.
  • If the maze can't be solved from this cell, it backtracks out of the cell by setting its value to visitedCode, marking it as having been visited.
  • It then waits for a short period of time, synchronized with the speedSleep variable, before returning false.

Output


Conclusion


In conclusion, the maze generator and solver in Java provide an interactive way of creating and solving mazes.

  • The generator uses a randomized depth-first search algorithm to generate a maze with a unique solution, while the solver uses a recursive backtracking algorithm to find the solution.
  • The program allows users to customize the size of the maze and the speed of the generation and solving processes.( change those in the java file )

Overall, this project demonstrates the power and versatility of Java in creating graphical user interfaces and implementing complex algorithms.

  • It also showcases the importance of algorithm design in problem-solving and highlights the potential of computer science to create engaging and interactive applications.
  • Whether for educational or entertainment purposes, the maze generator and solver in Java provide a fun and challenging experience for users of all ages and backgrounds.

With this article at OpenGenus, you must have the complete idea of how to develop Maze generator and solver project in Java.

—
Maze Generator and Solver in Java
Share this