In this code challenge, you will write a Maze Generator. The problem is to determine how to remove walls in a grid to form a proper maze. A proper maze should have:

1. Reachability: Allow a wanderer to start at any cell in the grid, and reach any other cell in the grid - without walking through any walls.
2. No Loops: There should be exactly one path between any two cells in the grid (not counting back-tracking). Note that a grid with this property will have N - 1 walls removed if it has N cells.

You can watch a sample solution, by pressing the Run button, below. When you are ready to try writing your own solution, open this CodePen Template.

Note the API reference at the bottom of this page.

Your solution should be defined in the form of a JavaScript generator function. You're not required to be familiar with that. Only to know that your function name should have an "*" in front of it, and that you should use the yield statement in the inner loop of your solution. This will allow the grid visualization to display the workings of your program and for you to control the execution speed with the buttons beneath the grid.

• grid.cell(row, col) - Call this function to retrieve an individual Cell in the Grid. The elements of the Grid start at (0, 0) for the upper left cell, and increase to the right and down. The lower right cell of a 10 by 10 Grid is at at (9, 9).
• cell.mark - This boolean property can be used to keep track of cells you have visited. When set to true they will appear highlighted in the grid.
• cell.testWall(dir) - Test to see if there is a wall currently present next to the cell. The direction argument is a number from 0 to 3.
  • 0 - up
  • 1 - right
  • 2 - down
  • 3 - left
• cell.removeWall(dir) - Remove the wall of the cell in the direction given. Note that there is only one wall between any two cells (you don't have to remove the up wall of a cell, as well as the down wall of the cell above it).

The sample generator shown in this demo works by starting with the center cell of the maze. It "marks" it as being included in the set of cells reachable from the center cell.

It then picks a random cell and a direction. If the cell, and it's neighbor in that direction are on opposite sides of a wall with one cell being "marked" and the other cell being "unmarked", then it can remove the wall and increase the number of reachable cells from the center. It then marks the previously unmarked cell, and chooses another random cell in the grid.

The algorithm returns when N - 1 walls have been removed (for a grid with N cells in it), since, by that criteria, all cells will be reachable from the center (as well as every other cell).

There is an entire Wikipedia article on Maze Generation.

If you'd like to see how the Grid visual simulator was implemented - you can find the source code on our Github repo.