A maze made on an HTML5 canvas

How to generate a maze using JavaScript and HTML5 canvas and a Cellular Automaton algorithm?

Generating a random map on a canvas is fun. In this article you will learn how to generate a random map or maze on an HTML5 canvas. We will use a model called Cellular Automaton.

While there are many ways to create a maze (or a map), what I’d like to create is a map that looks more like a cave or a chasms network rather than a human-built labyrinth. The following codepen shows a live demo of the working algorithm. Just hit “Step forward” to see the algorithm iterating until you get a nice looking cave maze.

See the Pen Cellular Automaton by Yonatan Kra (@yonatankra) on CodePen.

What is the Cellular Automaton algorithm?

We will understand the algorithm by imagining our world as binary – either we are a wall or we are a path. The Cellular Automaton Algorithm works as follows:

  1. Generate a random noise matrix of 0’s and 1’s (0 – walls, 1 – paths).
  2. matrix -> originalMatrix
  3. For every cell:
    1. Calculate the number of paths and the number of walls directly around it (edge of canvas is calcaulted as a wall) in the original matrix.
    2. Set the current cell’s value as the value of most of its direct neighbors.
  4. Repeat step 3 until satisfied.

Let’s take a simple example of a matrix. The matrix in Figure 1 is a small 5×5 matrix with randomly assigned values to its cells (pixels).

Figure 1: A random noise matrix

The next step in our algorithm would be to take every cell or pixel and calculate its value according to its neighbors.

Let’s take the topmost left cell (coordinates 0,0). It is black, it has 3 white neighbors – (1,0), (1,0), (1,1) but 5 black neighbors (all out of bounds). This is why, in the next iteration it will be black.

If we take the last cell (4,4), we will see it has only 2 white neighbors and 6 black (1 black neighbor and 5 out of bound neighbors) – so it will turn black in the next iteration.

Cell (2,1) is black, but it is surrounded by 7 white cells and will become white in the next iteration.

Figure 2 shows the results for steps 2,3 and 4.

Figure 2: Steps 2,3 and 4 (left to right) for the matrix from Figure 1.

How to implement the Cellular Automaton algorithm?

After we understand that the algorithm is all about counting neighbors, let’s get to work.

Generate a random matrix

Creating the random noise matrix is pretty easy:

function generateWhiteNoise(size, whiteLevel = .5) {
return new Array(size).fill(0)
.map(() => Math.random() >= whiteLevel ? BLACK : WHITE);
}

This function returns an array of given size filled with random values. Using the `whiteLevel` argument, we can determine if the white/block ratio should be skewed towards one or the other. In our case, we assume we’d like total randomness.

Using the generateWhiteNoise function, we can generate our matrix like that:

const noise_matrix = new Array(MATRIX_DIMENSIONS.height).fill(0).map(() => {
return generateWhiteNoise(MATRIX_DIMENSIONS.width, WHITE_LEVEL);
});

We create an array that is the size of the matrix height (e.g. rows). We then map each row to an array of white noise. Each cell represents a pixel of either 0 or 1.

Calculate value according to neighbors

Now that we have the preliminary matrix, we can handle it according to the Cellular Automaton algorithm:

function cellularAutomaton(matrix) {
const tmpMatrix = copyMatrix(matrix);
tmpMatrix.forEach((row, rowIndex) => {
row.forEach((pixel, pixelIndex) => {
tmpMatrix[rowIndex][pixelIndex] = calculatePixelValueByNeighbors(rowIndex, pixelIndex, matrix);
});
});
return tmpMatrix;
}
function calculatePixelValueByNeighbors(rowIndex, pixelIndex, matrix) {
let sum = 0;
for (let y = -1; y < 2; y++) {
for (let x = -1; x < 2; x++) {
if (!matrix[rowIndex + y] || !matrix[rowIndex + y][pixelIndex + x]) {
sum -= 1;
} else {
sum += 1;
}
}
}
return sum > 0 ? WHITE : BLACK;
}
view raw cellularAutomaton.js hosted with ❤ by GitHub

The function cellulareAutomaton receives a matrix as a n input. It then copies it (deep copy) into tmpMatrix. For every cell, it calculates the value according to its neighbors in the original matrix and updates the new one (tmpMatrix). It then returns the new matrix (thus keeping this function pure as a bonus).

calculatePixelValueByNeighbors does exactly what we would expect: it runs over the neighbors of the cell in (rowIndex, pixelIndex) and if there are more whites than blacks sets its value to white and vice versa.

Iterate until completion

Now that we have the full algorithm parts, let’s put it all together:

const matrices = {
last: null,
current: null
};
matrices.current = new Array(MATRIX_DIMENSIONS.height).fill(0)
.map(() => {
return generateWhiteNoise(MATRIX_DIMENSIONS.width, WHITE_LEVEL);
});
while (areMatricesDifferent(matrices.current, matrices.last) || someCounter > someLimit) {
matrices.last = matrices.current;
matrices.current = cellularAutomaton(matrices.last);
}
view raw createAMaze.js hosted with ❤ by GitHub

The code above keeps two matrices: the one we are currently using and the last one used. It generates the random noise matrix into the current. It then iterates until a convergence occurs. A convergence is a state in which the current matrix is the same as the last (note that “same” doesn’t necessarily mean identical – similarity can have an error margin but this comment is here just to pacify the nerds in the crowd).

Another thing to note is the limit using someCounter as it is unwise to create a while loop without a deterministic stop signal (and in some cases, Cellular Automatons can be infinite – don’t get me started on this…).

Draw the results

While drawing the results is not part of the algorithm, it would not be cool to just leave our matrix to the world of arrays and variables. Let’s write a short function that draws the matrix:

function draw(matrix) {
const ctx = canvas.getContext('2d');
ctx.clearRect(0, 0, CANVAS_HEIGHT, CANVAS_WIDTH);
ctx.beginPath();
matrix.forEach((pixelsRow, rowIndex) => {
const y = rowIndex * PIXEL_RATIO;
pixelsRow.forEach((pixel, pixelIndex) => {
const x = pixelIndex * PIXEL_RATIO;
ctx.fillStyle = COLORS[pixel];
ctx.fillRect(x, y, PIXEL_RATIO, PIXEL_RATIO);
});
});
ctx.closePath();
}
view raw drawMaze.js hosted with ❤ by GitHub

The draw function receives the matrix as an input. It then gets a handle to our canvas 2d context and clears what’s currently displayed on screen. It starts a new path and for every pixel, fills a rectangle in the color according to the pixel’s value.

The full working code

You can find the full code of what we’ve built here.

You can also play around with a cellular automaton stepper app on codepen.

Summary

The Cellular Automaton algorithm is a handy tool when you want to create random maps, mazes or a Rorschach card. Its implementation is pretty straight forward and we’ve added some fireworks to it (well… drawing on a canvas – which is the quiet version of fireworks 🙂 ).

The usage of this algorithm can vary – as you can add more than the binary state and thus try to create new wonderful worlds (like mountains, rivers, seas, deserts, plains etc.). This algorithm might be too simple to create a rich and real-feel world, but it can be a good starting point.

If this article got you excited, I suggest you read about the Game of Life, which is working according to similar principle to create amazing Cellular Automatons.

I hope you enjoyed this article. I’d love to know if you found it useful or just plain fun to play with 🙂

Thanks a lot for Yuval Bar Levi and Amir Lellouche for their kind and thorough review.

Sign up to my newsletter to enjoy more content:

Leave a Reply

Your email address will not be published. Required fields are marked *