Tutorial - Random Maze Generation Algorithm in Javascript

I recently began working on a mobile game, more info of which will be coming as it gets closer to a release date. One of the central points of the game requires generating random mazes in a variety of sizes. This is a fairly well known concept in computer science, and there are a number of different algorithms which can be used to provide the maze. However, in my research, I came across few good tutorials on what exactly these algorithms did. As any developer knows, understanding what an algorithm does step by step is important to utilizing it in your own programs. Merely copying and pasting a function from some other site will invariably lead to convoluted code surrounding that function in order to get the parameters you need from it, and can lead to many problems down the road when a problem arises with that function. And believe me, a problem will always arise.

I was able to work off of several different examples in a few languages in order to work through the algorithms I found, and to then rewrite the code in a manner that was suited to my purposes. For this particular purpose, I would be writing the code in Javascript. For anyone who would just like to jump ahead and see the finished code for themselves, you are free to visit the project at https://github.com/dstromberg2/maze-generator

There are a number of different common algorithms for generating a random maze, and each approach will yield differing characteristics for the completed maze. For this particular project, I decided upon a depth-first search algorithm, with recursive backtracking. This is probably the simplest approach to the problem, and ensures that every maze will be solvable, and that every cell of the maze will be accessible, ensuring no wasted space in the maze.

The first step in constructing the algorithm is determining what is needed for the return values. For my game, I decided that I wanted a nested array that defined each cell, consisting of arrays of cells (x values) nested in arrays of rows (y values). Each cell would then be defined by the presence of each of its four borders. I decided to construct the result in this manner to facilitate an easy process of laying out each cell in HTML, and then defining each of its borders using CSS. As such, the border definitions are presented in CSS order of [top, right, bottom, left]. Familiarity with HTML should make it apparent that defining rows as the first element of the array, with cells nested in rows, provides an easy way to loop through the array when drawing the final outcome. This may make it slightly confusing in that y values are stored before x values, but the alternative requires much more convoluted for loops than are really necessary. So the output of the function will be in the form of:

maze[y][x][borders]

And defining the first cell in the maze with all walls still intact would be:

maze[0][0][0,0,0,0]

Now knowing the return value of the function, we get in to actually writing the complete script. First off is defining the function, along with the input parameters of x and y values, and the defining each of the starting variables that we will be working with.

function newMaze(x, y) {

    var totalCells = x*y;

    var cells = new Array();

    var unvis = new Array();

The "totalCells" variable will be used later when we are looping through the arrays to make sure that we check every cell in the generated maze. "cells" is the main array, and will contain all of the values that will be used for the return. "unvis" keeps track of which specifc cells in the maze have not yet been checked. Since the algorithm will be moving through the maze in a random fashion, it is important to keep track of which cells are left to be checked.

Next up is looping through each of these arrays and establishing all of the nested arrays, as well as the default starting values for each. Considering the intended look of the final array, this should be fairly straightforward.

for (var i = 0; i < y; i++) {

    cells[i] = new Array();

    unvis[i] = new Array();

    for (var j = 0; j < x; j++) {

        cells[i][j] = [0,0,0,0];

        unvis[i][j] = true;

    }

}

In order to generate a more randomized maze, we pick a random place within the maze to start from. If the algorithm were to always start at the first cell, the resulting mazes would end up being too similar over time. By starting at a random cell and working out to the rest of the cells, the algorithm will end up drawing more unique mazes.

var currentCell = [Math.floor(Math.random()*y), Math.floor(Math.random()*x)];

With a starting point determined, we next establish that starting cell as being visited, and store it as the first cell in our algorithm's path. As we go through each other cell, the path along the way will continue to be stored. Whenever a dead end is reached, we will then be able to trace back the steps and start creating a new path in a different direction.

var path = [currentCell];

unvis[currentCell[0]][currentCell[1]] = false;

var visited = 1;

Now we get to the nitty gritty of the algorithm. Establish a while loop which will check whether all the cells in the maze have been visited yet.

while (visited < totalCells) {

With our starting cell in place, we define which other four cells are its potential neighbors which should be checked.

var potential = [[currentCell[0]-1, currentCell[1], 0, 2],      // top

        [currentCell[0], currentCell[1]+1, 1, 3],               // right

        [currentCell[0]+1, currentCell[1], 2, 0],               // bottom

        [currentCell[0], currentCell[1]-1, 3, 1]];              // left

var neighbors = new Array();

The array of potential neighbors defines the y and x coordinates of the neighbor (zero and first values), as well as which wall will be the border between the neighbor and the current cell. The second value defines the wall of the current cell which is adjoining, while the third value defines the wall of the neighboring cell which is adjoining. In case there is any confusion about my numbering of the values there, since this is being stored in an array, the first listed element is always zero in an array. It's a good habit to get in to thinking about array positions with zero as the starting point, rather than thinking that the first element will be referenced with a zero in your code. Although now I fear I have made that explanation more complicated than it may have been already.

With each of the potential neighbors defined, we check each of them against a series of conditions to see if they are eligible. We need to know whether each of the neighboring cells are valid points within the game grid, and whether the cell has already been checked.

for (var l = 0; l < 4; l++) {

    if (potential[l][0] > -1 &&     // Is the y value of the neighbor inside the maze?

        potential[l][0] < y &&      // Is the y value of the neighbor inside the maze?

        potential[l][1] > -1 &&     // Is the x value of the neighbor inside the maze?

        potential[l][1] < x &&      // Is the x value of the neighbor inside the maze?

    unvis[potential[l][0]][potential[l][1]]) // Has the neighbor already been visited?

             { neighbors.push(potential[l]); }

}

A quick for loop will check each of the neighbors for the conditions. I have broken out the if statement here in to multiple lines for readability, and provided a comment for each condition. This is not present in my final code, but is used here for explanation. If all of the conditions are met, the eligible neighboring cell is added to an array, which we will be using momentarily. After the for loop has checked each of the neighbor cells, the result will be an array containing each of the eligible neighbors.

Once we have determined which neighbors are available, we check to make sure we ended up with at least one. If there are no eligible neighboring cells, that means we have reached a dead end. As I had mentioned earlier in this tutorial, when a dead end is reached in the maze, we will go back up the path of cells we have already visited and try again. In Javascript, the pop() method of an array will remove the highest value from the array, which is the most recently stored, and store it in a new variable if one is defined. In our code, it will take the previously visited cell in our path, and make it the current cell, so that we can begin checking again.

if (neighbors.length) {

    // More stuff will be added here shortly

} else {

    currentCell = path.pop();

}

Within the if statement, where that comment is currently, defines what the algorithm will do if there are eligible neighbors that we need to check. We will begin by randomly choosing one of the eligible neighbors.

next = neighbors[Math.floor(Math.random()*neighbors.length)];

Having chosen one of the neighbors, the next step is to knock down the wall between that neighbor, and our current cell. Since each cell is defined by its borders, a wall actually consists of two definitions, one for each cell which borders the wall. In order to make sure our final array is correct for every cell, we have to remove the wall first of the current cell, and then of the selected neighbor cell. Since the position of the walls was defined earlier in the potential neighbors array, those values will be used as a reference to knock down the wall.

cells[currentCell[0]][currentCell[1]][next[2]] = 1;

cells[next[0]][next[1]][next[3]] = 1;

Here we select a cell from the result array using the determined x and y values, then select which border we are removing, and mark it as 1, signifying that no wall is present at that location. You can change those values to false, and the original cell definitions can use true, if you desire to have true boolean expressions. For my purposes, one and zero was easier. In fact, the values you choose to store here are completely up to you. The benefit of understanding what the algorithm is actually doing is that you can modify any of this to suit your exact needs, and this is a great example.

With the walls removed between the current cell and the neighbor, we need to move in to the neighboring cell, and set it as the current cell, so that we can repeat the process, and continue repeating it until we are done. First mark the neighboring cell as having been visited, and increment our counter.

unvis[next[0]][next[1]] = false;

visited++;

Then set the current cell equal to the values of the neighboring cell, and add it to our path that we are following through the maze.

currentCell = [next[0], next[1]];

path.push(currentCell);

Here I am only using the zero and first elements of the neighbor's array, since the other two values define the borders, and we will not be needing those anymore. It would do no harm to pass that entire array in to the current cell, but I always choose to keep my stored values to the minimum needed to avoid confusion down the road.

All of that will be contained within the while loop, so that the algorithm will continue tracing its path and knocking down walls until it has checked every cell in the maze. The only thing left from here is to close out our brackets and send the completed cells array as the return value for the function.

    }

    return cells;

}

That should do it! Again, to see the completed code, use the Github link at the top of this tutorial. You are welcome to clone and fork that repository for your own needs. Hopefully this tutorial will be helpful to anyone out there looking to get a better understanding of exactly how these types of algorithms work. If you ever come across code where you aren't sure what it does, take the time to dig in to it and understand what it is accomplishing, so that you can leverage it for your own purposes. It will always pay off in the long run.

There will likely be more information, and possibly some more tutorials, about my game in the coming weeks, so keep it tuned here to find out more!