Maze Generator à la Shiffman

Step 1

Create all necessary variables.

var cols, rows, current, button, gridSize;

var w = 20;
var grid = [];
var stack = [];
var createMaze = false;

Step 2

Setup the canvas and grid (Please note: grid is a one-dimensional array). Populate the grid with “cells” and set the first cell in our grid to current.

function setup() {
  createCanvas(401,401);
  textAlign(CENTER);
  cols = floor(400/w);
  rows = floor(400/w);
  
  for (var j = 0; j < rows; j++) {
    for (var i = 0; i < cols; i++) {
      var cell = new Cell(i,j);
      grid.push(cell);
    }
  }
  
  current = grid[0];
}

Step 3

This is the code for our Cell objects that we have stored in our grid. Each Cell has 4 walls (top, right, bottom, left - in that order) which are represented by an array of booleans of length 4, e.g. this.walls = [true, true, true, true]. Each Cell also has the following functions:

• show: makes the cell visible to us by drawing lines and indicates whether the cell has been visited or not by colouring it.
• highlight: highlights the cell that has been set to current.
• checkNeighbours: checks whether a cell has any unvisited neighbours and if so, randomly selects one to move to.

function Cell(i, j) {
  this.i = i;
  this.j = j;
  this.walls = [true, true, true, true]; // Initially all 
  // walls are intact.
  this.visited = false;
  
  this.checkNeighbours = function() {
    var neighbours = [];
    
    var top = grid[index(i, j - 1)];
    var right = grid[index(i + 1, j)];
    var bottom = grid[index(i, j + 1)];
    var left = grid[index(i - 1, j)];

    if (top && !top.visited) {
      neighbours.push(top);
    }

    if (right && !right.visited) {
      neighbours.push(right);
    }
    
    if (bottom && !bottom.visited) {
      neighbours.push(bottom);
    }
    
    if (left && !left.visited) {
      neighbours.push(left);
    }
    
    if (neighbours.length > 0) {
      var r = floor(random(0, neighbours.length));
      return neighbours[r];
    } else {
      return undefined;
    }
  }
  
  this.highlight = function() {
    var x = this.i * w;
    var y = this.j * w;
    noStroke();
    fill(0,255,0,100);
    rect(x,y,w,w);
  }
  
  this.show = function() {
    var x = this.i * w;
    var y = this.j * w;
    
    stroke(255);
    
    if (this.walls[0]) {
      line(x,y,x+w,y);
    }
    if (this.walls[1]) {
      line(x+w,y,x+w,y+w);
    }
    if (this.walls[2]) {
      line(x+w,y+w,x,y+w);
    }
    if (this.walls[3]) {
      line(x,y+w,x,y);
    }
    
    if (this.visited) {
      noStroke();
      fill(0, 102, 255, 100);
      rect(x,y,w,w);
    }
  }
}

Step 4

You may have noticed the index function in Step 3. Indexing or identifying the location of a cell in our one-dimensional grid is such a common operation that it made sense to create a separate function for it.

function index(i, j) {
  
  if (i < 0 || j < 0 || i > cols-1 || j > rows - 1) {
    return -1;
  }
  return i + j * cols;
}

Step 5

Create a little start screen for your sketch.

function startScreen() {
  background(51);
  textSize(32);
  fill(255);
  text("Maze Generator", width/2, height/2 - 32);
  textSize(16);
  text("A depth-first, recursive approach", width/2, height/2);
    text("inspired by Dan Shiffman.", width/2, height/2 + 16);
  
  button = createButton('Start');
  button.position((width - button.width)/2, height/2 + 32);
  button.mousePressed(generateMaze);
  
}

Step 6

generateMaze tells our little app that we want some action and the maze generated. It is triggered when the button in the start screen is pressed.

function generateMaze() {
  createMaze = true;
  removeElements();
}

Step 7

Unsurprisingly, run is where a large part of the algorithm is implemented and a lot of the individual parts are put to work.

function run() {
  background(51);
  for (var i = 0; i < grid.length; i++) {
    grid[i].show();
  }
  
  current.visited = true;
  current.highlight();
  
  var next = current.checkNeighbours();
  if (next) {
    next.visited = true;
    
    stack.push(current);
    
    removeWalls(current, next);
    
    current = next;
  } else if (stack.length > 0) {
    current = stack.pop();
  }
    
    addEntranceExit();
}

Step 8

Our essential draw function entails a simple switch statement which quite literally switches on our maze generator.

function draw() {
  switch (createMaze) {
    case true: 
      this.run();
      break;
    case false:
      this.startScreen();
      break;
  }
}

Step 9

The function that removes the walls of the cells as we navigate through the maze.

function removeWalls(a, b) {
  var x = a.i - b.i;
  if (x == 1) {
    a.walls[3] = false;
    b.walls[1] = false;
  } else if (x == -1) {
    a.walls[1] = false;
    b.walls[3] = false;
  }
  
  var y = a.j - b.j;
  if (y == 1) {
    a.walls[0] = false;
    b.walls[2] = false;
  } else if (y == -1) {
    a.walls[2] = false;
    b.walls[0] = false;
  }

}

Step 10

A maze wouldn’t be much fun without an entrance and an exit so here we add those.

function addEntranceExit() {
    grid[0].walls[0] = false;
    grid[grid.length -1].walls[2] = false;
}

Putting it all together

If you are familiar with p5.js you probably won’t need to read this bit, however, if you are new to p5.js I would strongly recommend to read the official Get Started guide.

In short, what you have to do is put all the code chunks above in one file and save it with the file extension .js, so for example sketch.js.

In your HTML document, you need to make sure that p5.js is included in the <head> tags using:

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.7.1/p5.js"></script>

You also must include your actual sketch/script by using <script src="filepath/sketch.js"></script>.

An example HTML may end up looking like this:

<html>
  <head>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.7.1/p5.js"></script>
    <script src="filepath/sketch.js"></script>
  </head>
  <body>
  </body>
</html>

Now all that’s left to do is to open the aforementioned HTML document in your browser of your choice - et voilà.