In this tutorial, we will build a Random Maze Generator in Java using Swing for the graphical user interface (GUI). The maze generation will use the Depth-First Search (DFS) algorithm with backtracking, which is a common and effective algorithm for generating mazes.
The maze will be displayed as a grid, where each cell represents either a wall or a path. The algorithm will carve out paths between cells to create a solvable maze.
Features:
The user can click a button to generate a new random maze.
The maze is generated using the Depth-First Search (DFS) algorithm with backtracking.
The app displays the maze in a grid layout using Swing components.
The maze includes walls and paths, where the paths can be traversed.
Algorithm Overview:
The Depth-First Search (DFS) maze generation algorithm works as follows:
Start at a random cell and mark it as visited.
Randomly choose a neighbor that has not been visited.
Remove the wall between the current cell and the chosen neighbor and mark the neighbor as visited.
Recursively repeat this process from the new cell.
If there are no unvisited neighbors, backtrack to the previous cell and continue.
Complete Code
import javax.swing.*; import java.awt.*; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.util.ArrayList; import java.util.Collections; import java.util.Random; public class MazeGeneratorApp extends JFrame { private static final int ROWS = 20; // Number of rows in the maze private static final int COLS = 20; // Number of columns in the maze private static final int CELL_SIZE = 25; // Size of each cell private Cell[][] grid; // The grid representing the maze private JPanel mazePanel; // Panel to display the maze private JButton generateButton; // Button to generate the maze private Random random; // Random number generator // Cell class to represent each cell in the maze private static class Cell { int row, col; boolean visited = false; boolean topWall = true; boolean bottomWall = true; boolean leftWall = true; boolean rightWall = true; public Cell(int row, int col) { this.row = row; this.col = col; } } // Constructor to set up the GUI public MazeGeneratorApp() { setTitle("Maze Generator"); setSize(COLS * CELL_SIZE + 50, ROWS * CELL_SIZE + 100); setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); setLocationRelativeTo(null); // Center the window on the screen random = new Random(); // Create a grid to represent the maze grid = new Cell[ROWS][COLS]; for (int row = 0; row < ROWS; row++) { for (int col = 0; col < COLS; col++) { grid[row][col] = new Cell(row, col); } } // Set up the maze panel mazePanel = new JPanel() { @Override protected void paintComponent(Graphics g) { super.paintComponent(g); drawMaze(g); } }; mazePanel.setPreferredSize(new Dimension(COLS * CELL_SIZE, ROWS * CELL_SIZE)); mazePanel.setBackground(Color.WHITE); // Set up the generate button generateButton = new JButton("Generate Maze"); generateButton.addActionListener(new ActionListener() { @Override public void actionPerformed(ActionEvent e) { generateMaze(); mazePanel.repaint(); } }); // Set up the layout setLayout(new BorderLayout()); add(mazePanel, BorderLayout.CENTER); add(generateButton, BorderLayout.SOUTH); setVisible(true); } // Method to draw the maze on the panel private void drawMaze(Graphics g) { g.setColor(Color.BLACK); for (int row = 0; row < ROWS; row++) { for (int col = 0; col < COLS; col++) { Cell cell = grid[row][col]; int x = col * CELL_SIZE; int y = row * CELL_SIZE; // Draw the walls of the cell if (cell.topWall) { g.drawLine(x, y, x + CELL_SIZE, y); // Top wall } if (cell.bottomWall) { g.drawLine(x, y + CELL_SIZE, x + CELL_SIZE, y + CELL_SIZE); // Bottom wall } if (cell.leftWall) { g.drawLine(x, y, x, y + CELL_SIZE); // Left wall } if (cell.rightWall) { g.drawLine(x + CELL_SIZE, y, x + CELL_SIZE, y + CELL_SIZE); // Right wall } } } } // Method to generate the maze using DFS with backtracking private void generateMaze() { // Reset all cells for (int row = 0; row < ROWS; row++) { for (int col = 0; col < COLS; col++) { grid[row][col].visited = false; grid[row][col].topWall = true; grid[row][col].bottomWall = true; grid[row][col].leftWall = true; grid[row][col].rightWall = true; } } // Start the maze generation from a random cell Cell startCell = grid[random.nextInt(ROWS)][random.nextInt(COLS)]; dfs(startCell); } // Depth-First Search (DFS) algorithm to generate the maze private void dfs(Cell cell) { cell.visited = true; ArrayList neighbors = getUnvisitedNeighbors(cell); while (!neighbors.isEmpty()) { Cell neighbor = neighbors.remove(0); // Get a random neighbor removeWalls(cell, neighbor); // Remove the wall between the current cell and the neighbor dfs(neighbor); // Recursively visit the neighbor neighbors = getUnvisitedNeighbors(cell); } } // Method to get the unvisited neighbors of a cell private ArrayList getUnvisitedNeighbors(Cell cell) { ArrayList neighbors = new ArrayList<>(); // Check top neighbor if (cell.row > 0 && !grid[cell.row - 1][cell.col].visited) { neighbors.add(grid[cell.row - 1][cell.col]); } // Check bottom neighbor if (cell.row < ROWS - 1 && !grid[cell.row + 1][cell.col].visited) { neighbors.add(grid[cell.row + 1][cell.col]); } // Check left neighbor if (cell.col > 0 && !grid[cell.row][cell.col - 1].visited) { neighbors.add(grid[cell.row][cell.col - 1]); } // Check right neighbor if (cell.col < COLS - 1 && !grid[cell.row][cell.col + 1].visited) { neighbors.add(grid[cell.row][cell.col + 1]); } // Shuffle the neighbors to ensure randomness Collections.shuffle(neighbors, random); return neighbors; } // Method to remove the walls between two adjacent cells private void removeWalls(Cell current, Cell next) { // Determine the relative position of the next cell int dx = current.col - next.col; int dy = current.row - next.row; // Remove the walls if (dx == 1) { // Next cell is to the left current.leftWall = false; next.rightWall = false; } else if (dx == -1) { // Next cell is to the right current.rightWall = false; next.leftWall = false; } else if (dy == 1) { // Next cell is above current.topWall = false; next.bottomWall = false; } else if (dy == -1) { // Next cell is below current.bottomWall = false; next.topWall = false; } } // Main method to run the app public static void main(String[] args) { SwingUtilities.invokeLater(() -> new MazeGeneratorApp()); } }
Explanation of the Code
1. Import Statements
import javax.swing.*; import java.awt.*; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.util.ArrayList; import java.util.Collections; import java.util.Random;
javax.swing.*: Provides Swing components like JFrame, JButton, and JPanel to create the graphical interface.
java.awt.*: Provides layout management and graphical utilities (BorderLayout, Graphics).
java.util.*: Provides utilities such as ArrayList, Random, and Collections for randomization and storing neighbors.
2. Class Declaration and Instance Variables
public class MazeGeneratorApp extends JFrame { private static final int ROWS = 20; private static final int COLS = 20; private static final int CELL_SIZE = 25; private Cell[][] grid; private JPanel mazePanel; private JButton generateButton; private Random random; }
ROWS and COLS: The number of rows and columns in the maze grid.
CELL_SIZE: The size of each cell in the maze.
grid: A 2D array to represent the maze as a grid of cells.
mazePanel: A panel to display the maze.
generateButton: A button to generate a new maze.
random: A Random object to generate random values.
3. Cell Class
private static class Cell { int row, col; boolean visited = false; boolean topWall = true; boolean bottomWall = true; boolean leftWall = true; boolean rightWall = true; public Cell(int row, int col) { this.row = row; this.col = col; } }
Cell: Represents each cell in the maze. Each cell has walls (topWall, bottomWall, leftWall, rightWall) and a visited flag to indicate whether the cell has been visited during the maze generation.
4. Constructor
public MazeGeneratorApp() { setTitle("Maze Generator"); setSize(COLS * CELL_SIZE + 50, ROWS * CELL_SIZE + 100); setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); setLocationRelativeTo(null); random = new Random(); grid = new Cell[ROWS][COLS]; for (int row = 0; row < ROWS; row++) { for (int col = 0; col < COLS; col++) { grid[row][col] = new Cell(row, col); } } mazePanel = new JPanel() { @Override protected void paintComponent(Graphics g) { super.paintComponent(g); drawMaze(g); } }; mazePanel.setPreferredSize(new Dimension(COLS * CELL_SIZE, ROWS * CELL_SIZE)); generateButton = new JButton("Generate Maze"); generateButton.addActionListener(new ActionListener() { @Override public void actionPerformed(ActionEvent e) { generateMaze(); mazePanel.repaint(); } }); setLayout(new BorderLayout()); add(mazePanel, BorderLayout.CENTER); add(generateButton, BorderLayout.SOUTH); setVisible(true); }
Frame Setup:
Sets the window title and size, and ensures that the app exits when the window is closed.
Initializes the grid with Cell objects and creates the mazePanel to display the maze.
Adds a button to trigger the maze generation and sets up the layout of the components.
5. drawMaze() Method
private void drawMaze(Graphics g) { g.setColor(Color.BLACK); for (int row = 0; row < ROWS; row++) { for (int col = 0; col < COLS; col++) { Cell cell = grid[row][col]; int x = col * CELL_SIZE; int y = row * CELL_SIZE; if (cell.topWall) { g.drawLine(x, y, x + CELL_SIZE, y); } if (cell.bottomWall) { g.drawLine(x, y + CELL_SIZE, x + CELL_SIZE, y + CELL_SIZE); } if (cell.leftWall) { g.drawLine(x, y, x, y + CELL_SIZE); } if (cell.rightWall) { g.drawLine(x + CELL_SIZE, y, x + CELL_SIZE, y + CELL_SIZE); } } } }
This method draws the maze by iterating through each cell and drawing its walls based on whether the topWall, bottomWall, leftWall, and rightWall flags are set.
6. generateMaze() Method
private void generateMaze() { for (int row = 0; row < ROWS; row++) { for (int col = 0; col < COLS; col++) { grid[row][col].visited = false; grid[row][col].topWall = true; grid[row][col].bottomWall = true; grid[row][col].leftWall = true; grid[row][col].rightWall = true; } } Cell startCell = grid[random.nextInt(ROWS)][random.nextInt(COLS)]; dfs(startCell); }
This method resets all cells and starts the maze generation from a random cell by calling the dfs() method.
7. dfs() Method (Depth-First Search)
private void dfs(Cell cell) { cell.visited = true; ArrayList neighbors = getUnvisitedNeighbors(cell); while (!neighbors.isEmpty()) { Cell neighbor = neighbors.remove(0); // Get a random neighbor removeWalls(cell, neighbor); // Remove the wall between the current cell and the neighbor dfs(neighbor); // Recursively visit the neighbor neighbors = getUnvisitedNeighbors(cell); } }
dfs(): Implements the Depth-First Search (DFS) algorithm. It recursively visits each cell, removes walls between the current cell and a random neighbor, and marks cells as visited.
8. getUnvisitedNeighbors() Method
private ArrayList getUnvisitedNeighbors(Cell cell) { ArrayList neighbors = new ArrayList<>(); if (cell.row > 0 && !grid[cell.row - 1][cell.col].visited) { neighbors.add(grid[cell.row - 1][cell.col]); } if (cell.row < ROWS - 1 && !grid[cell.row + 1][cell.col].visited) { neighbors.add(grid[cell.row + 1][cell.col]); } if (cell.col > 0 && !grid[cell.row][cell.col - 1].visited) { neighbors.add(grid[cell.row][cell.col - 1]); } if (cell.col < COLS - 1 && !grid[cell.row][cell.col + 1].visited) { neighbors.add(grid[cell.row][cell.col + 1]); } Collections.shuffle(neighbors, random); return neighbors; }
This method returns the unvisited neighbors of a given cell. It checks the top, bottom, left, and right neighbors and shuffles the list to ensure random maze generation.
9. removeWalls() Method
private void removeWalls(Cell current, Cell next) { int dx = current.col - next.col; int dy = current.row - next.row; if (dx == 1) { current.leftWall = false; next.rightWall = false; } else if (dx == -1) { current.rightWall = false; next.leftWall = false; } else if (dy == 1) { current.topWall = false; next.bottomWall = false; } else if (dy == -1) { current.bottomWall = false; next.topWall = false; } }
This method removes the walls between the current cell and the next cell based on their relative position.
Customization Ideas
1. Allow Different Maze Sizes
Add options for the user to select different maze sizes (e.g., 10×10, 20×20, or 30×30 grids).
2. Add Maze Solvers
Implement a maze-solving algorithm (e.g., BFS or A* search) to highlight the solution path from a start point to an end point.
3. Customize the Appearance
Add colors to distinguish walls and paths, or add animations for the maze generation process.
Conclusion
This Random Maze Generator in Java using Swing demonstrates how to create a maze using the Depth-First Search (DFS) algorithm with backtracking. The project covers:
Using Swing components to create a graphical interface.
Implementing maze generation algorithms with recursive DFS.
Handling user interaction with buttons to trigger maze generation.
Feel free to expand the project by adding new features or improving the appearance of the maze!