Maze.java

/* This file is neede to create the maze using Prims algorithm.
It takes care of the structure for maze generation and the grid
in its entirety

Maze.java
*/

import java.util.*;

public class Maze {
    // Initialize public variables that will be used in other classes or this class
    public final int rows, cols; // Number of rows and columns in the maze
    public final Cell[][] grid; //2D array for enitre maze grid
    public final List<List<Integer>> adj; // Adjacency list for maze
    public final boolean[][] openRight, openDown; // Wall status open or closed

    // Construcctor for Maze class that will give value to variables when instantiated
    public Maze(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        grid = new Cell[rows][cols];
        // Creates a 2D array of cell objects
        for (int rowLoop = 0; rowLoop < rows; rowLoop++) {
            for (int colLoop = 0; colLoop < cols; colLoop++) {
                grid[rowLoop][colLoop] = new Cell(rowLoop, colLoop); // Uses the new 'grid' variable
            }
        }    
        // Initialize the adjacent list
        adj = new ArrayList<>();
        for (int i = 0; i < rows * cols; i++) {
            adj.add(new ArrayList<>());
        } 
        // Initialize the openRight and openDown arrays
        openRight = new boolean[rows][cols];
        openDown = new boolean[rows][cols];
    }

    // Convert the 2D cell coordinates to a single location id
    public int location(int r, int c) {
        return r * cols + c;
    }

    // Check if the given row and column are valid in the boundaries
    private boolean valid(int r, int c) {
        return r >= 0 && r < rows && c >= 0 && c < cols;
    }

    // Connect two cells in the maze and make the physical wall in between open
    private void connectCells(int r1, int c1, int r2, int c2) {
        int location1 = location(r1, c1);
        int location2 = location(r2, c2);

        // Update the list of adjacent cells
        adj.get(location1).add(location2);
        adj.get(location2).add(location1);

        // Determines which wall array to update based on cell positions
        if (r1 == r2 && c2 == c1 + 1) {
            openRight[r1][c1] = true;
        } else if (r2 == r1 && c1 == c2 + 1) {
            openRight[r2][c2] = true;
        } else if (c1 == c2 && r2 == r1 + 1) {
            openDown[r1][c1] = true;
        } else if (c2 == c1 && r1 == r2 + 1) {
            openDown[r2][c2] = true;
        }
    }
    // Get the list of valid neighboring cells for a given cell
    // Returns a list of int arrays where each array contains the row and column of a neighbor
    private List<int[]> neighbors(int r, int c) {
        List<int[]> neigh = new ArrayList<>();

        int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};

        for (int i = 0; i < directions.length; i++) {
            int changeR = r + directions[i][0];
            int changeC = c + directions[i][1];
            if (valid(changeR, changeC)) {
                neigh.add(new int[]{changeR, changeC});
            }
        }
        return neigh;
    }

    // Generate the maze using Prim's algorithm with a random seed
    public void generateMazeRandomly(long seed) {
        Random rand = new Random(seed);
        boolean[][] inMaze = new boolean[rows][cols];
        List<int[]> frontier = new ArrayList<>();

        // Start process from a random cell
        int sr = rand.nextInt(rows), sc = rand.nextInt(cols);
        inMaze[sr][sc] = true;
        // Neighboring cells of the starting cell are added to the frontier
        List<int[]> startNeighbors = neighbors(sr, sc);
        for (int i = 0; i < startNeighbors.size(); i++) {
        frontier.add(startNeighbors.get(i));
        }
        // Goes through every cell until all cells are in the maze
        while (!frontier.isEmpty()) {
            int idx = rand.nextInt(frontier.size());
            int[] cell = frontier.remove(idx);
            int r = cell[0];
            int c = cell[1];
            if (inMaze[r][c]) {
                 continue;
            }

            // Find neighbors that are already in the maze
            List<int[]> inNeighbors = new ArrayList<>();
            List<int[]> curNeighbors = neighbors(r, c);
            for (int i = 0; i < curNeighbors.size(); i++) {
                int[] nb = curNeighbors.get(i);

                if (inMaze[nb[0]][nb[1]]) {
                    inNeighbors.add(nb);
                }
            }
            // If no neighbors are in the maze, skip this cell
            if (inNeighbors.isEmpty()) {
                continue;
            } 
            // Randomly choose one of the in-maze neighbors to connect
            int[] chosen = inNeighbors.get(rand.nextInt(inNeighbors.size()));
            connectCells(r, c, chosen[0], chosen[1]);
            // Make the cell part of the maze
            inMaze[r][c] = true;

            // Add its neighbors to the frontier if they are not already in the maze
            for (int i = 0; i < curNeighbors.size(); i++) {
                int[] nb = curNeighbors.get(i);
                int neighR = nb[0];
                int neighC = nb[1];
                
                // Check if neighbor is already in the maze
                if (!inMaze[neighR][neighC]) {
                    boolean exists = false;

                    // Check if neighbor is already in the frontier
                    for (int j = 0; j < frontier.size(); j++) {
                        int[] f = frontier.get(j);
                        if (f[0] == neighR && f[1] == neighC) {
                            exists = true;
                            break;
                        }
                    }
                    if (!exists) frontier.add(nb);
                }
            }
        }
    }
}