How to create a maze algorithm with JavaScript
This is a simple guide that will help you to develop an algorithm in JavaScript to create a maze.
Motivation
Back in the days I stumbled over this BASIC one-liner which is supposed to create a random maze. I tried to reproduce this with JavaScript (source code). It works pretty well, is fast and pretty compact. But if you look closer you will see, that this will never work as a maze.
It’s just some randome lines with no possible solution. So I asked myself: How difficult could it be to create a maze algorithm.
There are in fact a couple ways of maze creation. This article describes the steps I took from the first idea to the final maze and I think it’s a good excercise on how to create an algorithm. It’s no rocket science, but it documents my prefered way of developing algorithms: Starting with a simple, rough solution and improve it.
Preparation
From my point of view the simplest approach is to create an area with x times y cells where every cell has four walls (actually it’s two walls, but we keep that for later). The goal is to plow through every wall until we hit the exit.
As we want to achieve this in JavaScript and HTML, we need to start with a table, rows and columns. I am using a pretty straight forward loop for that:
mazeWidth = 10;
mazeHeight = 10;function createBlankMaze() {
var rowIndex, colIndex;
var table = document.createElement("table");
var tbody = document.createElement("tbody");
for (rowIndex = 1; rowIndex <= mazeHeight; rowIndex++) {
var row = document.createElement("tr");
for (colIndex = 1; colIndex <= mazeWidth; colIndex++) {
var col = document.createElement("td");
if (rowIndex == 1 && colIndex == 1 ) {
col.style.backgroundColor = "rgb(244,0,0)";
col.setAttribute("type", "start");
} else if (rowIndex == mazeHeight && colIndex == mazeWidth) {
col.style.backgroundColor = "rgb(0,244,0)";
col.setAttribute("type", "finish");
} else {
col.style.backgroundColor = "rgb(255,255,255)";
}
col.setAttribute("id", "cell_" + rowIndex + "_" + colIndex);
row.appendChild(col);
}
tbody.appendChild(row);
}
table.appendChild(tbody);
document.getElementById("maze_container").appendChild(table);
}
This loop creates a table with ten rows and ten colums. The walls are “build”with CSS:
table td {
border: 1px #000000 solid;
}The starting point always is on the top left position (row = 1, column= 1), the first cell has the background color red. The exit cell always is on the bottom right position (row = maze width, col= maze height), cell color is green.
We are now going to move from cell to cell, remove walls and ultimately reach the exit. Because our solution path will not go touch every existing cell, we also need to remove some random walls and create detours.
Lets go.
Step 1: One simple path
For starters we want to understand how to create a solution path. The walls will be removed later, then comes the chaos. Promise.
To create basic loop, lets start with a really simple path from the starting cell to the exit. We achieve that by moving nine cells to the right and nine cells to the bottom. Why nine times? Because as soon as we reach the last cell, we’re done:
Lets put those commands into an array. I named this array exits instead of direction, because actually we are creating exits by removing walls:
var exits = ["right", "right", "right", "right", "right", "right", "right", "right", "right", "bottom", "bottom", "bottom", "bottom", "bottom", "bottom", "bottom", "bottom", "bottom"];Now lets loop through those instructions. Based on the instruction, right or bottom, we increment the row or column index to get to a new cell. And this cell is being colored red:
var currentCell;
var rowIndex = 1;
var colIndex = 1;
for (exitIndex = 0; exitIndex < exits.length; exitIndex++) {
switch(exits[exitIndex]) {
case "right":
colIndex = colIndex + 1;
break;
case "bottom":
rowIndex = rowIndex + 1;
break;
}
currentCell = document.getElementById("cell_" + rowIndex + "_" + colIndex);
currentCell.style.backgroundColor = "#f00000";
}Please ignore the walls (borders) for now. At this point we try to understand how to create a solution path. This is the result (live demo):
Step 2: Add some variety
This was not too difficult. What about some variety? Lets alternate the instruction array:
var exits = [];
for (exit = 1; exit <= mazeWidth - 1; exit++) {
exits.push("right");
exits.push("bottom");
}This is no big deal. The ouput does not reveal any surprises (live demo):
Step 3 Removing walls
As we are going to add real chaos to the path soon, we need a clear view. So now is a good point to remove the walls aka borders. To achieve that, we just remove the border to the right or bottom, depending on where the exit is.
Before the actual loop start, we adress the first cell (1/1):
var currentCell = document.getElementById("cell_1_1");In the loop, right after we get the next instruction, we remove the border of the current cell.
currentCell.style["border-"+exit] = "none";And now you see why we use “right” and “bottom” as instructions: It makes removing walls easier. We may move down, but “bottom” makes addressing the CSS border attribute easier.
As there are four walls around every cell, we also need to remove the opposite wall of the next cell. We do that right after we moved to it:
currentCell = document.getElementById(“cell_” + rowIndex + “_” + colIndex);
switch(exit) { case "right": currentCell.style["border-left"] = "none";
break; case "bottom": currentCell.style["border-top"] = "none";
break;}
And that’s the result (live demo). Pretty convincing, isn’t it?
Step 4 Add more variety
The next step is obvious: Randomize the instruction list!
First we need to adapt the loop condition. We are not iterating through all available exits anymore. Lets give the iteration variable a more general name: loop.
for (loop = 0; loop < (mazeWidth + mazeHeight — 2); loop++) {
[...]}
Also the loop is now limited by mazeWidth and mazeHeight, because the exit array will not work as a valid loop condition anymore. We have to modify it: Everytime we take a step to the right, the remaining amounts of step to the right is being decremented by one. Same for the bottom-instruction.
We realize this by just removing (splice) the particular instruction from the exits array after it was applied. This will also create kind of a weight when randomly selecting the next instruction. The exitIndex now comes from a simple random function:
exitIndex = Math.floor(Math.random() * exits.length);exit = exits[exitIndex];exits.splice(exitIndex, 1);
Everything else remains the same. And this is how it looks like (live demo):
You may wonder: Wouldn’t it work without removing the latest instruction? Do we really need the weight? It’s not only about the wheight, it’s also about the iterations. We could keep the exit array, but then probably would never reach the final cell. This is how it would look like:
The amount of allowed exits to the right or bottom also is the amount of required exits (we will come to that in the next step). If we ignore this, we must use an infinite loop that we only exit, as we reach the final cell. Our solution is way faster!
Step 5: Add more mobilty
Right now we only move to the right and the bottom. What about left and up? You may think that we can just add those directions to the instructions array. But this will not work. Ask yourself: How many exits to the left are possible in the first iteration? Zero. Because you are on the left border of the maze. Same for the upper exit.
But for every exit you taken to the right you can add one exit to the left. Which also means: You must add one exit to the right, to finally reach the destination.
To achieve this we adapt our first switch-clause. We just need to push the opposite exit to the exits array, based on the current exit:
switch(exit) { case "right":
colIndex = colIndex + 1;
exits.push("left");
break; case "bottom":
rowIndex = rowIndex + 1;
exits.push("top");
break; case "left":
colIndex = colIndex - 1;
exits.push("right");
break; case "top":
rowIndex = rowIndex - 1;
exits.push("bottom");
break;
}
The second switch condition needs to be extended, too. We just need to add the “wall-removal” for the two additional directions, e.g. “left”:
[...]
case “left”:
currentCell.style[“border-right”] = “none”;
break;
[...]Also we need to change the loop condition. Again. Theoretically we could now visit every cell. Currently that’s 100 minus 1 (because as soon as we reach the last cell, we’re done). So the upper limit of the loop is now a product like that:
while (loop < ((mazeWidth * mazeHeight) - 2)) {
[...]
}There you go (live demo):
Looks strange, doesn’t it? We are facing two problems right now. Let’s start with the first:
Step 6: Do not visit the same cell twice
Currently we are just randomly moving through the maze, totally ignoring if we are crossing our own path. To fix that, we are just going to check the surrounding cells if they are already occupied right before we randomly decide where to go next.
First we need to add some new variables. ValidExits is a simple static list (aka array) defining our exits:
var validExits = ["right", "bottom", "left", "top"];RemainingExits is our counting list that holds the amount of required / allowed exits. Remember: We need nine exits on the right and nine bottom exits to reach the final cell.
var remainingExits = {
"right": mazeWidth - 1,
"bottom": mazeHeight - 1,
"left": 0,
"top": 0};And finally nextExits. An array that contains valid exits for every iteration:
var nextExits = [];Now, before we randomly get the next exit, we need to define, what exit is actually possible:
That’s how it looks like in JavaScript:
nextExits = [];for (i = 0; i < validExits.length; i++) {switch(validExits[i]) {
case "right":
nextPossibleCell = document.getElementById("cell_" + rowIndex + "_" + (colIndex + 1));
break; case "left":
nextPossibleCell = document.getElementById("cell_" + rowIndex + "_" + (colIndex - 1));
break; case "bottom":
nextPossibleCell = document.getElementById("cell_" + (rowIndex + 1) + "_" + colIndex);
break; case "top":
nextPossibleCell = document.getElementById("cell_" + (rowIndex - 1) + "_" + colIndex);
break;} // switchif (nextPossibleCell != null && nextPossibleCell.style.backgroundColor != "rgb(240, 0, 0)") {
for (t = 0; t < remainingExits[validExits[i]]; t++) {
nextExits.push(validExits[i]);
}
} // if} // for-to
What do we do? We just loop through every possible direction. And we check, if the cell in this direction is “occupied” (it’s background color is red). The last for-to-loop is important: Based on the amount of required exits, we push the currently tested and hopefully valid exit to our list of nextExits. This list now contains a couple of rights and tops and maybe lefts, depending on where we are:
nextExits = ["right", "right", "top", "left", "left", "left", "left"];This way we add a weighting factor to our random selection.
But we are not done yet. We also need to keep our counting list up to date. For this we have to change our first switch-condition:
switch(exit) {
case "right":
colIndex = colIndex + 1;
remainingExits.left++;
remainingExits.right--;
break; case "bottom":
rowIndex = rowIndex + 1;
remainingExits.top++;
remainingExits.bottom--;
break; case "left":
colIndex = colIndex - 1;
remainingExits.left--;
remainingExits.right++;
break; case "top":
rowIndex = rowIndex - 1;
remainingExits.top--;
remainingExits.bottom++;
break;
}
That should be clear. If the next exit is to the right, we decrease the value for right exits in our counting list. At the same time we increase the amount of possible exits to the left. Same for all other directions. That’s the result (live demo):
Although the path looks pretty clear now, we are not reaching the final cell. That’s the second problem we need to take care of: The dead end.
Step 7 Escape the dead end
When our loop reaches a cell that has no valid exits, it will just iterate until it hits the loop limit:
As soon as we hit one of those dead ends, we need to pull back to the previous cell, test for valid exits again and chose another one. So what we need is a list that holds all cells from the current path:
var lastCells = [];Besides that we need to change our loop logic. When we hit a dead end and move back, the iteration does not count. So we need a loop that we can control from inside:
var loop = 0;
var loop = 0;
var maxLoops = 1000;while (loop < ((mazeWidth * mazeHeight) - 1)) {
loopFuse++;
if (loopFuse >= maxLoops) {break;}
[...]
loop++;
}
When I control a loop from inside, I always prefer adding a loop-fuse. This is an additional counter that has an upper limit. If this limit is reached, we break the loop. This way we prevent ending up in an infinite loop (I agree, that there are better solutions, but for now let’s focus on creating a solution path).
This his how we detect a dead end. If we found one, we remove the last entry from the path history (which is the cell we are currently in) and we set pointer the second-last entry, which represents the previous cell:
if (nextExits.length == 0) {
lastCells.splice(lastCells.length - 1, 1);
rowIndex = lastCells[lastCells.length - 1][0];
colIndex = lastCells[lastCells.length - 1][1];
currentCell = document.getElementById("cell_" + rowIndex + "_" + colIndex);
continue;
}Finally we skip this iteration of the loop with continue. After we successfully moved to a new cell, we also need to add this cell to the path history:
lastCells.push([rowIndex, colIndex]);But we also need to check, if we already reached the final cell. This is required, because we are now skipping the loop from inside. Means: We could reach the final cell before we reached the loop limit. Finally we increment the loop counter:
if (rowIndex == mazeHeight && colIndex == mazeWidth) {
break;
}loop++;
And how does it look like? I would say: Perfect! (live demo)
Step 8, Final step: Add wrong tracks
Although this is the final step, we are going to change a lot in our code. I will not post the complete code here, but only the most important changes. First we need to move the part that creates the route to a new function addRoute(). We don’t need to change a lot here. This function now expects four parameters:
- startAtRow / startAtCol: coordinates where to start painting a path
- createDetour: if true, this will create a path until it hit’s a dead end, otherwise it will go back in the history and try new path’s until it reaches the final cell
- backgroundColorRoute: this is only for documentation purposes, to differentiate the routes
Besides that we now use a pseudo HTML attribute called “occupied” to mark a cell as visited. It makes more sense than coloring the solution path in red. Which was good for showing the progress, but not in a real maze.
Now the paint()-function first creates the solution path:
startAtRow = 1;
startAtCol = 1;
addRoute(startAtRow, startAtCol, false, “rgb(240, 0, 0)”);As you can see, we start at the first cell, top left of the maze. After that we just go through every cell. If this cell is part of the solution path, we will use this as the starting point for detours:
for (n = 1; n < (mazeWidth * mazeHeight) - 1; n++) {
var currentCell = document.getElementById("cell_" + startAtRow + "_" + startAtCol);
if (currentCell.getAttribute("occupied") == "true") {
addRoute(startAtRow, startAtCol, true, "rgb(240, 120, 0)");
} if (startAtCol == mazeWidth) {
startAtRow++;
startAtCol = 1;
} else {
startAtCol++;
}}
And that’s it. This is how it looks like (live demo):
This a maze with 100 rows and columns (live demo).
Conclusion
Congratulations. We just “discovered” the “recursive backtracker algorithm”. Of course there is a lot of potential for optimisation. We can clean up the code and make the script faster or even add more interactivity:
- We could adress the cells by an incrementing integer (eg. from 1 to 100) instead by coordinate (row/col). This makes iterating easier.
- We could limit movements to the left or top to decrease complexity. As you can see from the 100x100-example, the path sometimes looks sheer endless.
- We could work with two walls only (to the right and bottom). Because the right wall always is the left wall of the next cell in the row. Same for bottom / top. This would slim down the code.
- …?
I put all this logic into a little game (d.i.p. — development in progress) which offers some additional features. If you like it or have some input to optimize the algorithm, feel free to drop me a comment.
You may find the source code and all examples on github. If you’re looking for a German translation of this text (which is not as detailled as this one), you can find it here.
