Language: C++, random maze generation program (using recursive division)

I get stuck with this assignment, and I really need some help.

The assignment is about recursive maze generation. The method is similiar to recursive division method.

Here is the direction:

Implement the following recursive algorithm to randomly generate a maze. In the example below I have made the maze 10x10 to save space but your maze should be 40x40. Start with a 2D array of char and assign walls to the borders.

Call the recursive function with parameters that specify the blank area in the middle, in this case, highlighted by yellow below. You could do this a couple of ways, for example, pass in the coordinates of the upper left and lower right corner, or pass in the coordinate of the upper left corner plus the width and height of the area.

If the width of the yellow area is

By avoiding the top and bottom row of the yellow area, we prevent ourselves from drawing a wall that might box ourselves in by covering up a passageway. In the green area, randomly select a vertical position (in this case from y=2 to y=7) and draw a horizontal wall all the way across the green. In this example, I randomly selected y=3:

Next, check if the ends of the line we just drew are next to a blank. If so, make the end wall a blank. This is to allow passage through the blank instead of blocking it. In this example, check if (0,3) is a blank. If it is, then make (1,3) a blank. Also check if (9,3) is a blank. If it is then make (8,3) a blank. There is no blank to add in this case.

Next, randomly select one of the cells in the wall that was added and turn it into a blank. This adds a hole to allow passage between the two halves of the maze separated by the new wall. In this example, I randomly picked x=3 and turned cell (3,3) into a blank.

Next, recursively repeat the process in area above the wall we just drew, and below the wall we just drew. Here would be the recursive call for the area above the wall, highlighted in yellow:

This area has a height that is

Next, here is the recursive call for the area below the wall, with the area highlighted in yellow:

This area has a large enough width and height to continue. In this case the width is greater than the height so instead of a horizontal wall we draw a vertical wall, using the same idea as before. First we pick a random x coordinate in the green area to draw a vertical line. As before we skip the edges as candidates to draw a wall to avoid blocking passages:

The random x coordinate for this wall could be anywhere from x=2 to x=7. Lets say we happen to pick x=3. This results in a vertical wall at x=3.

Check the ends of the wall we just made to make sure there arent any blanks we are blocking. In this case we check (3,3) and it is a blank! So we turn (3,4) into a blank so we dont block the passage. We would also check (3,9) for a blank. Its not but if it was we would turn (3,8) into a blank.

Next we randomly select one of the cells we turned into a wall and make it into a blank, to poke a hole in the wall and allow passage between our wall. Lets say we randomly pick the cell at (3,8):

Now we make a recursive call to the area to the left of the wall we just made.

This area has a width that is too small, so it just exits.

We would also make a recursive call to the area on the right of the previous wall we made.

The width is greater than the height so we draw a vertical wall somewhere in this green area:

Say that we randomly pick x=6. We check the ends and poke a hole in a random spot in the wall, say at y=8:

We make recursive calls on the area to the left of the wall we just made but it is too small so it exits.

Finally, we make a recursive call on the area to the right of the wall we made but it is also too small and exits.

This is the final maze!

TO DO: Write a program that randomly generates 40x40 mazes using the algorithm described here.

-------------------End of Instruction-------------------

I tried so many times to do this program but it still not works...Can anyone help me with this assignment?

Thanks for all the help!!

0123456789 0123456789