How to Generate Mazes Using Depth-First Algorithm

In this tutorial, we will learn how to generate mazes using depth-first algorithm. To do this firstly, I will define the problem, then I will explain the algorithm and finally demonstrate the implementation in Javascript. We will use P5js to demonstrate the working of the maze generation.

Read Also: Solving the 8 puzzle problem using A* (star) algorithm

Introduction to Maze Generation

A maze is a path or collection of paths, typically from an entrance to a goal. Maze generation is the process of designing the layout of passages and walls within a maze by using a computer program. In this tutorial, we will concentrate only on the generation of the maze and not on solving how to traverse a maze.

Before continuing with the tutorial take a look at the final implementation below using P5js. (Note: Although I have used pre tag, yet the formatting is not retained. Not sure how to solve the formatting issue). Click on the Play button to see the maze generation in action.

Read Also: What Are C# Delegates And How To Use Them

How to Generate Mazes

The goal is to create a layout of passages and walls within a maze using Javascript.

Before we can solve the problem we will need to model the problem. But what is meant by Modelling the Problem?

In generic terms, modelling a problem is the art of formulating the problem at hand in terms of precisely described, well-understood building blocks and logic to reach a solution. In computer science, proper modelling is the key to applying algorithmic design techniques to any real-world problems. Real-world applications involve real-world problems.

You might be working on a system that simulates air traffic in and around an airport, you might be working on optimizing the dispatch of delivery vans for an e-commerce application, or you might be working to search through patterns in a large image set. To solve such problems you will use some sort of modelling techniques to reduce the problem in terms of rigorously defined abstract structures such as graphs, trees, permutations, sets and so on.

Depth-First Algorithm

We will use the depth-first search algorithm to solve our problem of maze generation.

We will implement the depth-first algorithm with a stack. This approach is one of the simplest ways to generate a maze using a computer program. To do this we will first create a grid of cells to represent the room structure. For our problem we will only have 4 sided cells, each cell starting with four walls.

The program will start from a random cell, then selects a random neighbour cell that has not yet been visited. The program then removes the wall between the two cells and marks the new cell as visited. It also adds it to the stack to facilitate backtracking. When a cell is found to have no unvisited neighbours the program backtracks through the path by popping cells from the stack until it reaches a cell that has an unvisited neighbour. This process continues until every cell has been visited, causing the program to backtrack all the way back to the starting cell.

Implementation of Maze Generation Using Javascript

I will demonstrate the implementation of the above algorithm P5 Javascript API. The reason to choose P5 is convenience and experimentation of ideas with Javascript.

First of all, let’s define a few variables that are global in nature. These will be used for drawing of the grid and finally the maze.

The array Directions refer to sort of enumeration of the wall direction for a cell. CELL_WIDTH and CELL_HEIGHT are the width and height of each cell in terms of pixels. OFFSET is an offset from the top left corner of the canvas to start drawing the grid.

Cell

A cell is an independent unit of a grid. For our problem, we will model the cell with 4 walls.

Each cell comprises of an x, y position, a boolean flag to indicate whether or not the cell has been visited and 4 boolean flags to indicate which walls need to be drawn. The cell is constructed with an x and y coordinate.

Utility function to set the colour of the wall lines using P5 API.

Utility function to draw the 4 walls of the cell based on the flag values of which walls are present for the given cell. A value of true for the boolean type means wall exists and a value of false means the wall is taken down by the algorithm as the cell was visited.

Mouse

The mouse is the red colour block that moves while searching. This is just for visual purposes. With every visit to a cell, the mouse moves to the location of that cell. This shows the movement of the search visually.

Maze

The Maze class comprises the list of cells as a 2d array. Besides, a few utility functions, there are two main functions to the Maze class. They are getNeighbours and removeCellWall.

Get Neighbours

The getNeighbours function returns a list of cells that are neighbours to a given cell and have not been visited.

Remove Cell Wall

The removeCellWall function removes a wall of the current cell based on the direction from where it came and the wall of the neighbour cell from where it came.

Other Utility functions of Maze

The other utility functions include setting the line colours of the walls, getting a specific cell given its coordinates and drawing of the maze. These functions are simple and self-explanatory.

Maze Generator

The MazeGenerator class handles the generation of the mesh using the generateNext function. This function handles the exploring of the neighbours, adding them to the stack, marking them visited and popping from the stack if no neighbours are found.

The Main App

The main app called MyApp just encapsulates MazeGenerator, Maze and the Mouse into a simple class (for convenience).