Download the 8 Puzzle Unlimited App from Google Play.
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
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.
We will generate Mazes Using Depth-First Algorithm.
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.
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.
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.
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.
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.
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.
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).
In this tutorial, we have seen how to generate mazes using depth-first algorithm. There are many other better and more optimized algorithms that can be used to generate mazes. I will cover them in other tutorials.