Maze is a fun game for everyone. Rather than waiting for a new maze from other people, you can have your own unlimited number of mazes. Yes, in this blog, we are going to focus on how to make a randomly generated maze in your web browser with D3.js.
I hope you have heard D3.js before because this is a very famous JavaScript library. Quote: a JavaScript library for manipulating documents based on data(
https://d3js.org). I am gonna start from a very beginning to build a random maze generator. In this small project, AngularJS is used as a application framework, which makes this blog more like an web application, and encapsulates the maze related JavaScript codes and SVG elements into a HTML element.
A Simple Maze Algorithm
There are several maze generating algorithms available already. So, we will go with a easy one and I call it Knocking Down Method. Of course, there is official name for the algorithm. But I will describe the algorithm in an understandable way and get rid of some unnecessary details. OK, let us assume that the maze we will generate is a square based, which means the maze is a two dimensions array, like a grid. It could be 5x5, 10x10 or 19x19. Here is the steps:
- Take every grid cell as a room and every room has four walls to seal the room.
- Randomly find a room in grid;
- mark this room as visited;
- Randomly select one of the walls of the room;
- Detect if there is a room next to the wall: true then go to 6; false then go to 7;
- Knock the walls (one wall from this room and another wall from the next room) down and visit the new room if there is a room available next to the wall and this new room is not visited before: true then go back to 3; false then go to 7;
- Find another wall of the room and go back to 5.
The whole process will stop when all the rooms in the grid have been visited. And every room will lose at least one wall. Then you can see the maze has been generated. Just like a magic, right? In fact, according to this algorithm, any two rooms in this grid have and only have one way to connect each other. So you can easily indicate the start and finish points of the maze.
Because we randomly pick up the starting room and randomly knock down the walls, the maze is totally different with others after every time you refresh your web page.
Source Code with D3.js
We has several functions defined in JavsScript to achieve the maze generation:
initAttrs();
initSvg();
initMaze();
genRandomMaze();
renderMaze();
Let us go through them one by one.
- initAttrs(): some attributes need to be prepared for maze generation. row and col define the two dimension array. startX, startY, endX and endY is the entry and exit of the maze.
// get attributes values from this directive.
var row = attrs.row;
var col = attrs.col;
var startX = attrs.startX;
var startY = attrs.startY;
var endX = attrs.endX;
var endY = attrs.endY;
var roomWidth = 10;
var roomHeight = 10;
var mazeBackground = attrs.mazeBackground;
var roomBackground = attrs.roomBackground;
var wallColour = attrs.wallColour;
var wallWidth = 1;
// define maze related variables.
var matrix = [];
var svg = null;
var stack = [];
// Make sure all the initial parameters have the correct values.
var initAttrs = function(){
if(row == null || row == undefined || row < 3){
row = 20;
}
if(col == null || col == undefined || col < 3){
col = 20;
}
if(startX == null || startX == undefined || startX < 1 || startX > col){
startX = 1;
}
if(startY == null || startY == undefined || startY < 1 || startY > row){
startX = 1;
}
if(endX == null || endX == undefined || endX < 1 || endX > col){
endX = col;
}
if(endY == null || endY == undefined || endY < 1 || endY > row){
endY = row;
}
if(mazeBackground == null || mazeBackground == undefined){
mazeBackground = "lightgray";
}
if(roomBackground == null || roomBackground == undefined){
roomBackground = "lightgray";
}
if(wallColour == null || wallColour == undefined){
wallColour = "black";
}
}
- initSvg(): Using D3.js, it is very easy to insert a SVG element into your web page and start to all kinds of shapes into the SVG panel.
// generate a SVG element as a core part of this directive.
var initSvg = function(){
// generate root svg element with responsive CSS.
svg = d3.select(elements[0])
.append("svg").attr("width", 400)
.attr("height",400);
}
- initMaze(): At the beginning, every room in the maze has four walls, we need to prepare all the room objects and put them into the two dimensions array.
// make sure we knock down walls in a room randomly.
var disorder = function(directions) {
var i, pos, temp;
// randomly pick up two elements and move them to the end of the array to generate a random list.
for (i = 0; i < 2; i++) {
pos = Math.floor(Math.random() * directions.length);
temp = directions[pos];
directions.splice(pos, 1);
directions.push(temp);
}
return directions;
}
// initialize all the rooms in the maze and every room has four walls at the beginning.
var initMaze = function(){
var svgWidth = 400;
var svgHeight = 400;
// width of room should be between 10 and 50.
if(Math.floor(svgWidth / col) > 50 || Math.floor(svgWidth / col) < 10){
roomWidth = 50;
}else{
roomWidth = Math.floor(svgWidth / col) - 1;
}
// Height of room should be between 5 and 10.
if(Math.floor(svgHeight / row) > 50 || Math.floor(svgHeight / row) < 10){
roomHeight = 50;
}else{
roomHeight = Math.floor(svgHeight / row) - 1;
}
// generate all the rooms with all the walls.
var x = 1;
var y = 1;
for(var i = 1; i <= row; i++){
var rooms = [];
for(var j = 1; j <= col; j++){
var room = {};
room.top = wallWidth;
room.bottom = wallWidth;
room.left = wallWidth;
room.right = wallWidth;
room.xPos = x;
room.yPos = y;
room.row = i;
room.col = j;
room.visited = false;
//generate a random neighbour rooms visiting list: 0 - left, 1 - right, 2 - top, 3 bottom.
room.directions = disorder([0, 1, 2, 3]);
rooms.push(room);
x += roomWidth;
}
x = 1;
y += roomHeight;
matrix.push(rooms);
}
}
- genRandomMaze(): Visiting a room and find next room to visit is the core part of the maze generation algorithm.
// Need to check the availability of the neighbour room. Not all the room have an available neighbour in any direction.
var getNeighbourRoom = function(room, direction){
var offsetX = 0;
var offsetY = 0;
switch(direction){
case 0:
offsetX -= 1;
break;
case 1:
offsetX += 1;
break;
case 2:
offsetY -= 1;
break;
case 3:
offsetY += 1;
break;
default:
}
var newX = room.col + offsetX;
var newY = room.row + offsetY;
console.log("Neighbour Row - Col: " + newY + " - " + newX);
if(newX < 1 || newX > col || newY < 1 || newY > row){
return null;
}else{
return matrix[newY - 1][newX - 1];
}
}
// We need to record the room we have visited before we knock down a wall and move to next room.
var visitRoom = function(){
while(stack.length > 0){
var room = stack.pop();
if(room.visited && room.directions.length == 0){
continue;
}
// record current room and ready to knock down a random wall.
stack.push(room);
room.visited = true;
var tmp = null;
switch(room.directions[0]){
case 0:
tmp = getNeighbourRoom(room, 0);
if(tmp != null && tmp != undefined && !tmp.visited){
room.left = 0;
tmp.right = 0;
stack.push(tmp);
}
break;
case 1:
tmp = getNeighbourRoom(room, 1);
if(tmp != null && tmp != undefined && !tmp.visited){
room.right = 0;
stack.push(tmp);
tmp.left = 0;
}
break;
case 2:
tmp = getNeighbourRoom(room, 2);
if(tmp != null && tmp != undefined && !tmp.visited){
room.top = 0;
stack.push(tmp);
tmp.bottom = 0;
}
break;
case 3:
tmp = getNeighbourRoom(room, 3);
if(tmp != null && tmp != undefined && !tmp.visited){
room.bottom = 0;
stack.push(tmp);
tmp.top = 0;
}
break;
default:
}
// Wall knocked down need to be removed.
room.directions.splice(0,1);
}
}
// By visiting the room, we can go to next room until all the rooms have been visited.
var genRandomMaze = function(){
var firstX = Math.floor(Math.random() * row);
var firstY = Math.floor(Math.random() * col);
console.log("First room to start Row - Col: " + firstY + " - " + firstX);
var room = matrix[firstY][firstX];
stack.push(room);
visitRoom();
}
- renderMaze(): This part is finished with D3.js. D3 bind our two dimensions array with room shapes. Every room is combined with one rectangle (as background) and four lines (as walls).
var renderMaze = function(){
// this is data binding for first layer of array.
var row = svg.selectAll(".row")
.data(matrix)
.enter().append("g")
.attr("class", "row");
// this is data binding for second layer of array. Every room is a group for multi-shapes.
var column = row.selectAll(".square")
.data(function(d) { return d; })
.enter().append("g").attr("class", function(d) { return d.xPos + "_" + d.yPos; });
// append rect as room background.
column.append("rect")
.attr("class","square")
.attr("x", function(d) { return d.xPos; })
.attr("y", function(d) { return d.yPos; })
.attr("width", roomWidth)
.attr("height", roomHeight)
.style("fill", roomBackground);
// append left wall;
column.append("line")
.attr("x1", function(d) { return d.xPos; })
.attr("y1", function(d) { return d.yPos; })
.attr("x2", function(d) { return d.xPos;})
.attr("y2", function(d) { return d.yPos + roomHeight;})
.attr("stroke-width", function(d) { return d.left; })
.style("stroke", wallColour);
// append right wall;
column.append("line")
.attr("x1", function(d) { return d.xPos + roomWidth; })
.attr("y1", function(d) { return d.yPos; })
.attr("x2", function(d) { return d.xPos + roomWidth;})
.attr("y2", function(d) { return d.yPos + roomHeight;})
.attr("stroke-width", function(d) { return d.right; })
.style("stroke", wallColour);
// append top wall;
column.append("line")
.attr("x1", function(d) { return d.xPos; })
.attr("y1", function(d) { return d.yPos; })
.attr("x2", function(d) { return d.xPos + roomWidth;})
.attr("y2", function(d) { return d.yPos;})
.attr("stroke-width", function(d) { return d.top; })
.style("stroke", wallColour);
// append bottom wall;
column.append("line")
.attr("x1", function(d) { return d.xPos; })
.attr("y1", function(d) { return d.yPos + roomHeight; })
.attr("x2", function(d) { return d.xPos + roomWidth;})
.attr("y2", function(d) { return d.yPos + roomHeight;})
.attr("stroke-width", function(d) { return d.bottom; })
.style("stroke", wallColour);
}
If you press F12, you can see all the JavaScript source code and it is not difficult to understand. There is one thing I need to mention that we can use recursive process to achieve the maze generation as well. But here we are using our own stack to make it work because a heavy recursive process is not healthy enough for JavaScript in your web browser.
Next time, we will make this maze a little bit more fun. Because we are not using recursive way to generate the maze, it would be easy for us to show the generation process in an animation way. Let me know if you like it!
