The goal is to generate a 2D maze. To accomplish this you will need two classes,

Question

The goal is to generate a 2D maze. To accomplish this you will need two classes, Maze and Cell. The Cell class should be implemented as a private class inside the Maze class. That way you can directly access its attributes without the need for get and set methods The Cell class represents a single cell in the maze. It should have the following attributes: 1. north 2. east 3. south 4. west 5. visited 6. row 7. column The first 4 attributes are boolean and indicate if there is a wall between the current cell and one of its neighbors. For example if north is false that means that there is no wall between the current cell and its north neighbor. If south is true it means there is a wall between the current cell and its south neighbor. The attribute visited is used to mark whether a neighbor was visited or not. Row and column refer to the cell's location in the maze (the 2D array of cells mentioned below). The Maze class will have the following attributes: 1. 2D array of Cells representing the maze 2. nrRows-the number of rows 3. nrCols the number of columns It will also have the following methods: 1. A constructor that accepts as input the number of rows and columns 2. generateMaze(int startRow, int startCol)-that generates a random maze using the algorithm described below. 3. toString0 method that will print the maze To generate a maze you will use the following algorithm (known as Recursive Backtracker): Mark maze start as visited; create a stack with elements of type Cell using Java API. Push start onto the stack; while stack is not empty do Pop current cell off stack; if current cell has unvisited neighbors then Choose a random unvisited neighbor; Remove wall with neighbor Mark neighbor as visited;

Explanation / Answer

import java.util.*;
import static java.util.stream.Collectors.toList;

class Maze {
  
private Cell[][] maze;
private int nrRows;
private int nrCols;
  
public Maze(int rows, int columns){
this.nrRows = rows;
this.nrCols = columns;
this.maze = new Cell[rows][columns];
  
// This code will initialize Maze
for(int i=0; i<=nrRows-1;i++){
for(int j=0; j<=nrCols-1; j++){
maze[i][j] = new Cell(i,j);
}
}
}
  
public String toString(){
  
for(int i=1;i<=nrCols;i++)
System.out.print("_");
System.out.println();

for(int i=0; i<= nrRows-1 ;i++){
for(int j=0; j<=nrCols-1; j++){
Cell currentCell = maze[i][j];
if(currentCell.west == true)
System.out.print("|");
}
System.out.print("|");
System.out.println();

for(int j=0; j<=nrCols-1; j++){
Cell currentCell = maze[i][j];
if(currentCell.south == true)
System.out.print("_");


}
System.out.println();  
}

return "";
}
  
public void generateMaze(int startRow, int startCol){
// Mark Maze Start as visited
Cell startCell = maze[startRow][startCol];
startCell.visited = true;
  
Stack<Cell> cells = new Stack<>();
cells.push(startCell);
  
while (!cells.empty()){
Cell currentCell = cells.pop();
  
List<Cell> unvisitedNeighbourers = findUnvisitedNeighbourers(currentCell);
  
if(!unvisitedNeighbourers.isEmpty()){
int size = unvisitedNeighbourers.size();
  
Random r = new Random();
int Low = 0;
int High = size;
int randomNumber = r.nextInt(High-Low) + Low;
  
Cell randomUnvisitedNeigbourer = unvisitedNeighbourers.get(randomNumber);
  
removeWallBetweenNeighbourers(currentCell,randomUnvisitedNeigbourer);
randomUnvisitedNeigbourer.visited = true;
  
cells.push(currentCell);
cells.push(randomUnvisitedNeigbourer);

}
}
}
  
private List<Cell> findUnvisitedNeighbourers(Cell currentCell){
List<Cell> unvisitedNeighbourers = new ArrayList<>();
// North Neighbourer Cell
int northNeighbourerCell_row = currentCell.row-1;
int northNeighbourerCell_column = currentCell.column;
  
  
// South Neighbourer Cell
int southNeighbourerCell_row = currentCell.row + 1;
int southNeighbourerCell_column = currentCell.column;
  
  
// East Neighbourer Cell
int eastNeighbourerCell_row = currentCell.row;
int eastNeighbourerCell_column = currentCell.column-1;
  
// West Neigbourer Cell
int westNeighbourerCell_row = currentCell.row-1;
int westNeighbourerCell_column = currentCell.column+1;
  
unvisitedNeighbourers.add(isCellUnvisited(northNeighbourerCell_row,northNeighbourerCell_column));
unvisitedNeighbourers.add(isCellUnvisited(southNeighbourerCell_row,southNeighbourerCell_column));
unvisitedNeighbourers.add(isCellUnvisited(eastNeighbourerCell_row,eastNeighbourerCell_column));
unvisitedNeighbourers.add(isCellUnvisited(westNeighbourerCell_row,westNeighbourerCell_column));
  
// Remove Nulls from Unvisited Neighbourers
unvisitedNeighbourers.removeIf(Objects::isNull);
  
return unvisitedNeighbourers;
}
  
private void removeWallBetweenNeighbourers(Cell a, Cell b){
  
// Find Spatial Relationship between a and b
int a_x = a.row;
int a_y = a.column;
int b_x = b.row;
int b_y = b.column;
  
if(a_x == b_x) {
  
if(a_y > b_y) {
a.west = false;
b.east = false;
}
  
if(a_y < b_y) {
a.east = false;
b.west = false;
}
}
  
if(a_y == b_y) {
if(a_x > b_x) {
a.north = false;
b.south = false;
}
  
if(a_x < b_x){
a.south = false;
b.north = false;
}
}
}

private Cell isCellUnvisited(int row, int col){
if(isCellValid(row,col)){
Cell cell = maze[row][col];
if(cell.visited == false)
return cell;
}
return null;
}
private boolean isCellValid(int row, int col){
if(row >= 0 && row < nrRows && col >=0 && col < nrCols )
return true;
return false;
}
  
public static void main(String[] args) {
  
Maze maze = new Maze(3,4);
maze.generateMaze(0,2);
System.out.println(maze);
  
}
  
private class Cell {
boolean north = true; // Indicates wall between this cell and north cell
boolean south = true;
boolean east = true ;
boolean west = true;
  
boolean visited;
  
int row,column;
  
public Cell(int row,int column){
this.row = row;
this.column = column;
this.visited = false;
}
  
}
  
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.