blog.hirnschall.net

In this weeks challenge we'll take a look at maze generation with javascript. But why would you do that?

As always the intent of this challenge is to learn something new in an interesting way. This week we focus on getting more comfortable with classes and object oriented programming.

How Maze Generation Works

There are several different ways to generate a maze. Some more complicated than others. As this is our second challenge we'll use a simple algorithm which gets even easier as it is related to Challenge #1: Random walker.

Lets start with a square checker board. To generate the maze we will trace the path the random walker takes until it reaches the end point. For this to result in a maze we have to change the walker in several ways:

• it has to visit every cell
• it is not allowed to revisit cells if there is an alternative
• if all adjacent cells have been visited it has to go back until a unvisited cell becomes available

Getting Started With p5js

We'll use p5.js, a great javascript library for drawing and animation.

The Cells

To make things easier each cell should be its own object and keep track of the following:

• its location (x,y)
• if it has been visited
• which way the walker was going (for drawing walls)

We are also using a global variable called "w" for the cells width/height. Using global variable is generally not a good Idea, but it is ok for smaller projects like this one.

function Cell(x, y) {
this.x = x;
this.y = y;
this.wall = [1, 1, 1, 1];
this.visited = 0;


As you can see, member variables are always named with a starting "this.".

To draw a cell it also needs a "show" function. Sometimes also called "display" or something similar. It is called each frame to display or update the cell. It has to:

• draw a square at the correct position if the cell has been visited
• draw walls on each side the walker was not going through

I also want the start at the top left and the finish at the bottom right to have a different color.(green and red)

this.show = function () {
var x = this.x * w;
var y = this.y * w;
if (this.visited) {
if(!this.x && !this.y)
fill(50,200,50);
else if(this.x == cols-1 && this.y == rows-1)
fill(200,50,50);
else
fill(150);
} else {
noFill();
}
noStroke();
rect(x, y, w, w);

stroke(255);
if (this.wall[0]) //h line
{
line(x, y, x + w, y);
}
if (this.wall[1]) //h line
{
line(x + w, y, x + w, y + w);
}
if (this.wall[2]) //h line
{
line(x, y + w, x + w, y + w);
}
if (this.wall[3]) //h line
{
line(x, y, x, y + w);
}
}
}


We first check if the cell has been visited, if it is the start cell with position x=0 and y=0 or if it is the finish cell with position x=cols-1 and y=rows-1. We can then draw a rectangle with the correct color and check which walls should be painted using the "line" function.

The Walker

We store all cells in a matrix "grid[x][y]". We will take a closer look at how to initialize this array in the next section.

As we are only using a singe walker I have decided to build it right into the main draw loop. Each frame it will do the following:

• check if all adjacent cells have been visited
• if not choose one at random
• otherwise go the the cell it has been before
• update the walls array of adjacent cells

We start by checking if all adjacent cells have been visited. If we find one that has not we store it in a new array called "next".

var next = [];
if (currentCell.x > 0 && !grid[currentCell.x - 1][currentCell.y].visited) {
next.push(grid[currentCell.x - 1][currentCell.y]);
}
if (currentCell.y > 0 && !grid[currentCell.x][currentCell.y - 1].visited) {
next.push(grid[currentCell.x][currentCell.y - 1]);
}
if (currentCell.x < cols - 1 && !grid[currentCell.x + 1][currentCell.y].visited) {
next.push(grid[currentCell.x + 1][currentCell.y]);
}
if (currentCell.y < rows - 1 && !grid[currentCell.x][currentCell.y + 1].visited) {
next.push(grid[currentCell.x][currentCell.y + 1]);
}


We can now check the length of "next" to see if there are cells available for the walker to move on. In case you wonder where currentCell.x and currentCell.y in the listing above comes from, you can see how we update it at the end of the next listing.

If there are cells available, we push the current position in an array called "stack". The walker then generates a random number between 0 and next.length. As the random function generates a real number we use the floor function to round it to the next integer.

if (next.length) //if there are cells available
{
stack.push(currentCell); //push to stack
++stackc;

var nextIndex = random(next.length);
if (nextIndex == next.length)
nextIndex -= 1;

var nextCell = next[floor(nextIndex)];

if (nextCell.x > current[0] && nextCell.y == current[1]) {
nextCell.wall[3] = 0;
currentCell.wall[1] = 0;
} else if (nextCell.x < current[0] && nextCell.y == current[1]) {
nextCell.wall[1] = 0;
currentCell.wall[3] = 0;
} else if (nextCell.x == current[0] && nextCell.y > current[1]) {
nextCell.wall[0] = 0;
currentCell.wall[2] = 0;
} else if (nextCell.x == current[0] && nextCell.y < current[1]) {
nextCell.wall[2] = 0;
currentCell.wall[0] = 0;
}

current[0] = nextCell.x;
current[1] = nextCell.y;
}


If no cells are available we check "stack" to find the previous position. If "stack" has length 0 we are done!

else { //no unvisited cells reachable
if (stack.length) {
current[0] = stack[stackc - 1].x;
current[1] = stack[stackc - 1].y;
stack.splice(stackc - 1, 1);
--stackc;
} else {
return;
}
}


Initialization

You can see how we initialize the grid array down below:

current = [0, 0];

cols = floor(canvasWidth / w);
rows = floor(canvasHeight / w);

for (var x = 0; x < cols; ++x) {
grid[x] = new Array(rows); // add 2d array
for (var y = 0; y < rows; ++y) {
var cell = new Cell(x, y);
grid[x][y] = cell;
//grid[x][y].show();
}
}


Further Ideas

You could try to:

• experiment with different colors
• make the walker its own class
• use multiple walkers with different starting points to create a more complex  maze. (Hint: be careful with initialization and end condition)
• use if(mouseIsPressed){ line(pmouseX, pmouseY, mouseX, mouseY); } to solve the maze after generating it.