Question

Need assistance with small piece of larger assignment writing a recursive division algorithm (Java).

The assignment is to write a recursive division algorithm to build a maze in a 2D array.

I have code that will randomly generate vertical and horizontal walls and randomly place doorways in the walls.

Requirements:

The maze should be broken into sub-regions on each recursive method call until the sub-region is no less than 3x3.

My recursive calls only seem to work on the top left sub-region of each call and I can't seem to get it to work on every sub-region in the entire maze board.

Outline of my code:

1) BASE CASE - If the width of sub region is less than 3 and height of a sub-region is less than 3 (smaller than 3x3), do not run recursive method again. {

(below code is inside base case if statement)

variable X = randomly select a x value for vertical wall in the range of left boundary to right boundary

variable Y = randomly select a y value for horizontal wall in range of top boundary to bottom boundary

for loop to build vertical wall

randomly place passage somewhere along vertical wall

for loop to build horizontal wall

randomly place passage on horizontal wall LEFT of vertical wall

randomly place passage on horizontal wall RIGHT of vertical wall

run recursive method

}

Thoughts:

Should one recursive method call go inside of the base case if statement, then another call outside of it? How can I ensure EVERY sub-region greater than 3x3 is being divided to the base case.

Answer 1

Dear Learner,

The solution is in the question itself. The outline of the code says that IF the width of sub region is less than 3 and height of a sub-region is less than 3 (smaller than 3x3), do not run recursive method again. We can use this to stop our recursive calls.

This can be done in the following manner -

Passing the dimension and coordinates as parameters

You can pass the dimensions of the region during the function call and reduce it everytime.

begin

{

m = width of board //to set the dimensions of the region (we will keep on reducing this during our recursive calls)

n = height of board

while x<=number of columns and y<=number of rows

{ //this part will help us to traverse through all the regions

if (x==number of columns)

CreateMaze(1,y++,m,n) //go to next row first column

else

CreateMaze(x++,y,m,n) //shift left

}

}

------------------------------------------

CreateMaze(int x, int y,int m,int n) //assuming the base case is m*n dimension with its top left coordinate as x,y

{

if(m==3 && n ==3) //this will be the base condition

{

variable X = randomly select a x value for vertical wall in the range of left boundary to right boundary

variable Y = randomly select a y value for horizontal wall in range of top boundary to bottom boundary

for loop to build vertical wall

randomly place passage somewhere along vertical wall

for loop to build horizontal wall

randomly place passage on horizontal wall LEFT of vertical wall

randomly place passage on horizontal wall RIGHT of vertical wall

return;

}

else CreateMaze(x,y,m-1,n-1)) //this will ensure that you call every subregions

}

This should perform the way you are expecting.

I hope I have answered the question the way you were expecting. If you still have any doubts or any other questions regarding this, feel free to ask us in the comment section.

Please leave a like if this was helpful.

Thanks

Happy Studying