JavaScript: Random Maze Generator
Following many requests we've ported our PHP maze generating class to JavaScript and are making it publicly available.
This is a basic version which will create a maze of the specified dimensions, with an entrance, exit, and a cunningly placed key to be retrieved en route. You can find a more advanced version linked below.
Working Demonstration
Below you should see a randomly generated maze with 16 columns and 12 rows. This maze is not interactive, but can be made so by subsequently applying our Maze Game code presented earlier. There are also no monsters or treasure.
Unlike our earlier examples which used PHP, this maze is generated entirely in your browser, so you can (re-)generate mazes to your heart's content:
MazeBuilder Source Code
class MazeBuilder {
// Original JavaScript code by Chirp Internet: www.chirpinternet.eu
// Please acknowledge use of this code by including this header.
constructor(width, height) {
this.width = width;
this.height = height;
this.cols = 2 * this.width + 1;
this.rows = 2 * this.height + 1;
this.maze = this.initArray([]);
/* place initial walls */
this.maze.forEach((row, r) => {
row.forEach((cell, c) => {
switch(r)
{
case 0:
case this.rows - 1:
this.maze[r][c] = ["wall"];
break;
default:
if((r % 2) == 1) {
if((c == 0) || (c == this.cols - 1)) {
this.maze[r][c] = ["wall"];
}
} else if(c % 2 == 0) {
this.maze[r][c] = ["wall"];
}
}
});
if(r == 0) {
/* place exit in top row */
let doorPos = this.posToSpace(this.rand(1, this.width));
this.maze[r][doorPos] = ["door", "exit"];
}
if(r == this.rows - 1) {
/* place entrance in bottom row */
let doorPos = this.posToSpace(this.rand(1, this.width));
this.maze[r][doorPos] = ["door", "entrance"];
}
});
/* start partitioning */
this.partition(1, this.height - 1, 1, this.width - 1);
}
initArray(value) {
return new Array(this.rows).fill().map(() => new Array(this.cols).fill(value));
}
rand(min, max) {
return min + Math.floor(Math.random() * (1 + max - min));
}
posToSpace(x) {
return 2 * (x-1) + 1;
}
posToWall(x) {
return 2 * x;
}
inBounds(r, c) {
if((typeof this.maze[r] == "undefined") || (typeof this.maze[r][c] == "undefined")) {
return false; /* out of bounds */
}
return true;
}
shuffle(array) {
/* sauce: https://stackoverflow.com/a/12646864 */
for(let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
return array;
}
partition(r1, r2, c1, c2) {
/* create partition walls
ref: https://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_division_method */
let horiz, vert, x, y, start, end;
if((r2 < r1) || (c2 < c1)) {
return false;
}
if(r1 == r2) {
horiz = r1;
} else {
x = r1+1;
y = r2-1;
start = Math.round(x + (y-x) / 4);
end = Math.round(x + 3*(y-x) / 4);
horiz = this.rand(start, end);
}
if(c1 == c2) {
vert = c1;
} else {
x = c1 + 1;
y = c2 - 1;
start = Math.round(x + (y - x) / 3);
end = Math.round(x + 2 * (y - x) / 3);
vert = this.rand(start, end);
}
for(let i = this.posToWall(r1)-1; i <= this.posToWall(r2)+1; i++) {
for(let j = this.posToWall(c1)-1; j <= this.posToWall(c2)+1; j++) {
if((i == this.posToWall(horiz)) || (j == this.posToWall(vert))) {
this.maze[i][j] = ["wall"];
}
}
}
let gaps = this.shuffle([true, true, true, false]);
/* create gaps in partition walls */
if(gaps[0]) {
let gapPosition = this.rand(c1, vert);
this.maze[this.posToWall(horiz)][this.posToSpace(gapPosition)] = [];
}
if(gaps[1]) {
let gapPosition = this.rand(vert+1, c2+1);
this.maze[this.posToWall(horiz)][this.posToSpace(gapPosition)] = [];
}
if(gaps[2]) {
let gapPosition = this.rand(r1, horiz);
this.maze[this.posToSpace(gapPosition)][this.posToWall(vert)] = [];
}
if(gaps[3]) {
let gapPosition = this.rand(horiz+1, r2+1);
this.maze[this.posToSpace(gapPosition)][this.posToWall(vert)] = [];
}
/* recursively partition newly created chambers */
this.partition(r1, horiz-1, c1, vert-1);
this.partition(horiz+1, r2, c1, vert-1);
this.partition(r1, horiz-1, vert+1, c2);
this.partition(horiz+1, r2, vert+1, c2);
}
isGap(...cells) {
return cells.every((array) => {
let row, col;
[row, col] = array;
if(this.maze[row][col].length > 0) {
if(!this.maze[row][col].includes("door")) {
return false;
}
}
return true;
});
}
countSteps(array, r, c, val, stop) {
if(!this.inBounds(r, c)) {
return false; /* out of bounds */
}
if(array[r][c] <= val) {
return false; /* shorter route already mapped */
}
if(!this.isGap([r, c])) {
return false; /* not traversable */
}
array[r][c] = val;
if(this.maze[r][c].includes(stop)) {
return true; /* reached destination */
}
this.countSteps(array, r-1, c, val+1, stop);
this.countSteps(array, r, c+1, val+1, stop);
this.countSteps(array, r+1, c, val+1, stop);
this.countSteps(array, r, c-1, val+1, stop);
}
getKeyLocation() {
let fromEntrance = this.initArray();
let fromExit = this.initArray();
this.totalSteps = -1;
for(let j = 1; j < this.cols-1; j++) {
if(this.maze[this.rows-1][j].includes("entrance")) {
this.countSteps(fromEntrance, this.rows-1, j, 0, "exit");
}
if(this.maze[0][j].includes("exit")) {
this.countSteps(fromExit, 0, j, 0, "entrance");
}
}
let fc = -1, fr = -1;
this.maze.forEach((row, r) => {
row.forEach((cell, c) => {
if(typeof fromEntrance[r][c] == "undefined") {
return;
}
let stepCount = fromEntrance[r][c] + fromExit[r][c];
if(stepCount > this.totalSteps) {
fr = r;
fc = c;
this.totalSteps = stepCount;
}
});
});
return [fr, fc];
}
placeKey() {
let fr, fc;
[fr, fc] = this.getKeyLocation();
this.maze[fr][fc] = ["key"];
}
display(id) {
this.parentDiv = document.getElementById(id);
if(!this.parentDiv) {
alert("Cannot initialise maze - no element found with id \"" + id + "\"");
return false;
}
while(this.parentDiv.firstChild) {
this.parentDiv.removeChild(this.parentDiv.firstChild);
}
const container = document.createElement("div");
container.id = "maze";
container.dataset.steps = this.totalSteps;
this.maze.forEach((row) => {
let rowDiv = document.createElement("div");
row.forEach((cell) => {
let cellDiv = document.createElement("div");
if(cell) {
cellDiv.className = cell.join(" ");
}
rowDiv.appendChild(cellDiv);
});
container.appendChild(rowDiv);
});
this.parentDiv.appendChild(container);
return true;
}
}
Please note that we've written the MazeBuilder class using ES6 class notation, meaning that it may not work in some older browsers.
How does it work?
The constructor() creates an empty matrix which is then walled (Figure 1) and partitioned (Figure 2) according to the recursive division algorithm which you can find details of under References below.
Placing the key with placeKey() is the most complicated part of the code as we first traverse the maze from both the start point and the end point with countSteps() and use that to calculate where the key should go to be as far away as possible from both those points (Figure 3).
Finally, the display() method generates and inserts the maze into the page using HTML with classes to indicate the position of walls and other elements.
You may notice that the isGap() method is way more complicated than necessary for the purpose used, but the reason for that will become evident in the more advanced version where we start finessing the maze layout. Similarly, the totalSteps value is only used when the maze becomes interactive (Figure 4).
Code for generating a maze
All you need now in order to start generating your own mazes is the following code, including a CSS file and the above JavaScript file:
<link rel="stylesheet" href="/mazing.css">
<div id="maze_container"><!-- --></div>
<script src="/maze-builder.js"></script>
<script>
let Maze = new MazeBuilder(16, 12);
Maze.placeKey();
Maze.display("maze_container");
</script>
You will need to copy these files to your own server and include them from there to avoid our hot-linking protection.
References
- Wikipedia: Maze generation algorithm - Recursive Division
- MDN: Javascript spread syntax (...)
- MDN: Array.prototype.every()
Related Articles - Games
- JavaScript Amazing Maze Game
- JavaScript Random Maze Generator
- JavaScript Playable Maze Game Generator
- JavaScript Twister Controller with Speech
- JavaScript Creating a Generator Function
- JavaScript Memory Card Game with Animation
- JavaScript Graphing Game