Maze Generation With Depth-First Search and Recursive Backtracking

Part Three — Maze Generation

This is EXACTLY how our maze will look…👀

It’s time. You have made it to the final step of this three part series. I want to congratulate you on following Part 1 as we made our grid, Part 2 as we set ourselves up to have our cells find their neighbors, and now finally sticking around to implement all these parts to develop our maze generating algorithm.

To remind ourselves on what we need to complete the algorithm let’s turn to our trusty Wikipedia definition and go step by step!

Now, before we begin, there is a crucial part missing from this definition that we need. When I worked on this project, and I am realizing this just now, the information I was using from Wikipedia looked different. The information I have been writing about is correct, but an additional part that I used of this algorithm implementation has been moved and is described below.

What we want to take away from this Iterative Implementation is the idea of the stack. With the use of the stack we will be able to continue our recursive implementation so our maze generator won’t get stuck as it looks for unvisited cells. It’ll make much more sense as we move through the code, but I wanted to apologize that I overlooked this before. BUT DON’T WORRY, this is still gonna be sweet 😎.

Okay! Let’s do this.

Step 1 — Given a current cell as a parameter

SO, first things first, we need to create a parameter that is a current cell. I’m going to create a new file for our maze generator to keep us within the design principle of separation of concerns, and we will set our current cell as our cell within our grid at index of 0.

# /src/maze-generator.js
let current = grid[0];

Our maze generating algorithm will start at grid[0] . Boom. Done.

We are going to want to visualize the algorithm at work as the maze is generated. We have already given our divs a class of ‘cell’, so let’s grab all of those and set it to a variable. Let’s create a stack variable that is an empty array as well to make our lives easier later.

# /src/maze-generator.js
let current = grid[0];
let stack = [];
const cells = document.querySelectorAll('.cell');

Step 2 — Mark the current cell as visited

Okay, well, our current cell is grid[0] , and we know that our cell class objects start with this.visited = false . That means once the current cell has been defined we need to set that cell’s this.visited value to true. Now comes the fun part of building our maze generating function!

Let’s start with coloring in the current cell (div) we are on to begin our visualization and write our conditional in regards to this.visited. AND, taking a page out of our iterative implementation we will push our current cell into our stack variable.

# /src/maze-generator.js
// Variables above ^^
function MazeGenerator() {
  cells[current.row * columns + current.column].style.background = 'rgb(102, 179, 229)';
  if (!current.visited) {
    current.visited = true;
    stack.push(current);
  };

Step 3 — While the current cell has any unvisited neighbor cells…

Here’s where things get interesting. The first part of step three is…

While the current cell has any unvisited neighbor cells, choose one of those unvisited neighbors.

Now that we have taken our current cell and marked it as visited we need to check if the cell has any unvisited neighbors and then choose one of them. We can do this by creating another empty array to hold the neighbors of the current cell and then pushing unvisited neighbors into that array. We will then choose one of those neighbors from the unvisited array. I found a for…of loop was the best way of adding unvisited neighbors to our array.

# /src/maze-generator.js
// Variables above ^^
function MazeGenerator() {
// current.visited part of function
let unvisited = [];
for (let neighbor of current.neighbors) {
  if (!neighbor.visited) {
    unvisited.push(neighbor);
  }
}
if (unvisited.length > 0) {
  let random = Math.floor(Math.random() * unvisited.length);
  let next = unvisited[random];
// Conditional will continue with next part of Step 3

With our unvisited neighbor chosen randomly from our unvisited array, we are ready to move to the second part of step three, which is…

While the current cell has any unvisited neighbor cells, choose one of those unvisited neighbors; Remove the wall between the current cell and the chosen cell.

Each one of our cell objects has a constructor of this.walls which holds an array of 4 boolean statements set to true. Now we need to remove the wall between the current cell and the chosen neighbor cell by setting that wall value to false. In the Part 2 of this series we focused on the cell where it’s x & y coordinates equaled 1. Using that same cell as an example, how do we find the correct index from our walls array to switch to false?

It’s easier than you think. Using our cell where x = 1 & y = 1 (or this.row = 1 & this.column = 1), if we were to check the neighbor just above the coordinates would be x = 0& y = 1(or this.row = 0& this.column = 1). Now the wall to the top of our current cell is what needs to be removed and the wall to the bottom of our neighbor cell needs to be removed. If we subtract our neighbor cell’s x value from our current cell’s x value (since those numbers have changed and do not equal 0) we end up with 1 (1 — 0 = 1). SO, if current.row — next.row === 1we want to remove the current cell’s top wall, and the neighbor cell’s bottom wall by setting those values to false. Previously, we decided that the index of 0 in our walls array would be top, index of 1 would be right, index of 2 would be bottom, and index of 3 would be left. This leaves us with…

if (current.row - next.row === 1) {
  current.walls[0] = false;
  next.walls[2] = false;
}

And that’s basically it, except now we apply this to every different possibility when removing walls. This leads us to the code below.

# /src/maze-generator.js
// Variables above ^^
function MazeGenerator() {
// current.visited part of function
// unvisited array part of function
if (unvisited.length > 0) {
  let random = Math.floor(Math.random() * unvisited.length);
  let next = unvisited[random];
  let x = current.row - next.row;
  if (x === 1) {
    current.walls[0] = false;
    next.walls[2] = false;
  } else if (x === -1) {
    current.walls[2] = false;
    next.walls[0] = false;
  }
  let y = current.column - next.column;
  if (y === 1) {
    current.walls[3] = false;
    next.walls[1] = false;
  } else if (y === -1) {
    current.walls[1] = false;
    next.walls[3] = false;
  }
  current = next;
}
// Conditional will continue with next part of Step 3

We end this part of the conditional by setting the current cell to whatever the next cell was and then it runs through again and again…or does it?

Actually, it would eventually stop/get stuck. This is because it will probably find a cell that has already been visited and all of its neighbors have been visited as well, so it will stop running. THIS is why the stack is necessary. The stack is keeping track of every cell that’s been visited. As the algorithm visits the cells and checks for neighbors randomly we run into the problem of visiting all nearby cells already. That can leave our grid still intact with walls all the way around some cells. To avoid this possible outcome we add an else if statement to our conditional that will look to the stack array we’ve been adding to for help.

else if (stack.length > 0) {
  current = stack.pop();
}

While are stack has a length greater than 0 our algorithm will continue to run.

FINALLY, we are going to add some code so that you can visualize all of these steps before your very eyes. You’ll see the files below and this last part is a bit rushed, but I didn’t realize how large of an endeavor I was taking on when I started this series and this blog post is getting entirely too long as it is and I really should have broken this up into two posts, but I PROMISED we finish in this one and I don’t like to be a liar…so here we are.

In our maze-generator.js file screenshot you’ll notice that we now have a variable holding an invocation of the setInterval() method. We finish our MazeGenerator() function if else statement by clearing this interval. We also have a new function called animate() that uses our Cell’s class method show(), which is located in our cell.js file. This method applies CSS styling to our grid by removing borders if a value from our Cell’s this.walls constructor is false, allowing you to see the algorithm at work and watch the maze generation process.

Your four files should look something like this…

maze-generator.js

cell.js

app.css

index.html

Ain’t she a beaut?

And this concludes the Maze Generation With Depth-First Search and Recursive Backtracking series! Way to go! We did it!

Let me know if you have any questions and if this was helpful or, even better, let me see what cool maze games you come up with following this code!

In the end, Vincent Yang and I had a great time developing this project. You can check out our Github or watch this video of our Mod 3 project in action.

Now…