Procedurally Generated Maze in Javascript

A maze in Javascript

A friend asked me if I could create an auto-generated maze for use in a project down the road. “CAN I!?” I asked pretty much 100% sincerely.  So let’s find out.

Planning:
There’s always more than one way to skin a cat. The first thing I had decided was I’d make my maze in JS/Canvas. The main reason being that it’s always so easy to get up and running with Javascript. If you’re doing something in PHP, Python, Ruby, or any variation of C or Java, you’re going to need an interpreter or compiler minimum to get started.

With Javascript you can always just start plugging away at the code and run it in a web browser. It’s a no fuss solution to just getting something up and running. So this was my go-to for this project.

HTML:

In HTML make sure you just have something along the following lines:
<canvas id='maze' height="800" width="800"></canvas>

A quick aside about setting the height / width on the canvas. If you use the CSS height / width properties to set the dimensions for you canvas you’ll almost inevitably get scaling and stretching. If you set them inline in the <canvas> tag you’ll get the dimensions you’re looking for. Percentages also are not a good idea here as pixel precise functionality won’t work and the scaling would still be a problem.

First let’s start with initializing the canvas in JS. Put this somewhere else in your HTML page:

<script>
var ctx = document.getElementById('maze').getContext('2d');
ctx.width = 800; // Set the width of the 2d canvas
ctx.height = 800; // Set the height of the 2d canvas
</script>

In the example above ‘maze’ is the ID of your canvas, and the ‘ctx’ object/variable name can be anything you want. The 2d context is used to draw simple shapes to the canvas. You could also draw a bitmap or webgl context, but the 2d’s adequate for what I’m doing here.

The first thing I’d think is to setup a box or a square. This square will be a prototype of my maze ’tile’. So yo dawg, let’s put a square in our square and see what that looks like.

Add this inside your script tags:
ctx.fillStyle = ‘rgb(0,0,0)’; // Sets the color to black
ctx.strokeRect(0, 0, 16, 16); // Draws a box at coordinates (0, 0) on the canvas with a height and width of 16px.

step-1

You should now see a 16px by 16px box. This accomplishes what we’re looking for, but it can’t really be extended into the maze. You could make a grid using shapes like these. But our tiles need to have dead ends and corners. By definition we need to be able to not stroke certain lines of our box. For doing this the path / line methods make much more sense.


ctx.fillStyle = 'rgb(0,0,0)'; // Sets the color to black
ctx.beginPath();
ctx.moveTo(0,0);
ctx.lineTo(0,16);
ctx.lineTo(16,16);
ctx.stroke();

step-2

Here we’ve done something similar, except we’ve drawn two lines. One is down 16 pixels, and the other is right 16 more. This produces a ‘corner’ effect. Specifically a lower left corner.

Now here’s the tricky part. Believe it or not, in using the line tool here. We already have most of what we need to algorithmically create a maze. Hey, there’s no guarantee it will have openings in the correct place, or look like the greatest maze ever invented. But let’s see what we can do.

If we take each tile to have a line in between the next tile, as a ‘shared wall’, there’s no real need to draw this wall again. What this means is we can actually only draw TWO walls of our tiles, and basically get away with creating walls for multiple tiles. We can create a pretty gnarly maze by going through each ’tile’ and adding only an upper and left wall randomly and doing the same to the next tile. First let’s see what this looks like with no randomization. We should see a grid.


<script>
var ctx = document.getElementById('maze').getContext('2d');
ctx.width = 800;
ctx.height = 800;
var tileSize = 16;
ctx.fillStyle = 'rgb(0,0,0)'; // Sets the color to black
for( x = 0; x < ctx.width / tileSize; x++ ) { // for as many tileSize-length pixel lines it takes to get across the width
for( y = 0; y < ctx.height / tileSize; y++ ) { // for as many tileSize=length pixel lines it takes to get across the height
ctx.beginPath();
ctx.moveTo( x * tileSize , ( y + 1 ) * tileSize ); // Move line down by the length of our tile
ctx.lineTo( x * tileSize , y * tileSize ); // Draw a line up the length of the tile
ctx.lineTo( ( x + 1) * tileSize , y * tileSize ); // Draw a line right the length of the tile
ctx.stroke(); // Add the color from fillStyle
}
}
</script>

This gives us a grid, as expected. This code is essentially moving down 16px, drawing a line up by 16px, then, drawing a line right by 16px. THEN done for each tiled segment of the graph. Doing this will give us this grid effect.

Two for loops are required to achieve this effect. I’m aptly naming the variables of these loops ‘x’ and ‘y’. By comparing the x and y values to the value of the width divided by the tilesize variable. And also using that tilesize variable in all of our line operations, we’ve made it so not only do these operations automatically fill the canvas exactly, but also so that you can change the ’tile-size’ to any pixel length. You can also change the width/height the canvas in the same way. 16 and 800 are used intentionally as 800 is divisible by 16 evenly. But by only declaring the constant of the tileSize to 16 pixels ONCE we allow also to only change it in one place.

Now is the tricky part. Instead of drawing the upper and left lines all the time. What if we do it…randomly? Fortunately, Javascript has a built in function to allow us to produce a random number: Math.random().

Math.random() produces a random floating point value between 0 and 1. This allows us to produce some “50% of the time”-type behavior


<script>
var ctx = document.getElementById('maze').getContext('2d');
ctx.width = 800;
ctx.height = 800;
var tileSize = 16;

ctx.fillStyle = ‘rgb(0,0,0)’; // Sets the color to black

for( x = 0; x < ctx.width / tileSize; x++ ) {
for( y = 0; y < ctx.height / tileSize; y++ ) {
ctx.beginPath();
ctx.moveTo( x * tileSize , ( y + 1 ) * tileSize );

if( Math.random() > 0.5 ) {
ctx.lineTo( x * tileSize , y * tileSize ); // Only draw this line half the time
}
else {
ctx.moveTo( x * tileSize , y * tileSize ); // If we DON’T draw it, just move over the same amount of space
// If we don’t do this a diagonal line will be drawn from the previous point to the next
// Simulate the actual drawing, but DON’T draw it.
}

if( Math.random() > 0.5 ) {
ctx.lineTo( ( x + 1) * tileSize , y * tileSize ); // Again only half the time.
}
ctx.stroke();
}
}
</script>

What happens if you don’t use the moveTo in the else block:
step-3

If you do:
step-4

There you have it. A procedurally generated maze. This will change on every refresh. It’s not perfect, it probably has too many openings and several closed off spaces. But it’s starting to look like what you’d usually recognize as a maze. This is just part one. Part two to come soon.

Here’s a link to it in action. Save the source if you want a copy for yourself to tool around with:
A MAZE ING.