This article has been updated since its original posting on February 19, 2017.
This tutorial will teach you how to make a random maze generator using a depth-first search (DFS) algorithm in GameMaker: Studio. With minor syntax changes, you’ll be able to get it working with GMS2. Maze generation is a fairly simple concept to grasp, and can serve as a solid introduction to data systems like grids and stacks.
As always, the source code can be found at the end of this tutorial via a GitHub link.
What is Depth-First Search?
Before we jump into the coding, I should shine some light on DFS, the backbone of this generator. DFS is an algorithm largely used when writing a program that will need to traverse through a tree data structure, reaching each and every node in all connecting branches. When a dead-end is reached - defined by no adjacent nodes that have not yet been visited - the algorithm traverses backwards until it is able to penetrate new territory.
Our two-dimensional maze may not appear to be a tree with branches upon first glance, but take a closer look at the generation animation at the beginning of this tutorial. Each square is considered a cell. Dark gray cells are unvisited, meaning that they have not been carved out by the green, active cell yet. Blue squares are the opposite - they are officially a hallway in the maze. When the active cell is adjacent to an unvisited cell, it will go to it. In the event there are multiple unvisited, adjacent cells, the active cell will randomly select one to visit. In the event there are no unvisited neighbors, the active cell will begin backtracking through its route until it meets a new, unvisited neighbor. As a result of this backwards movement, the active cell will make its way back to its starting position when its job generating the maze is completed.
There are multiple ways to structure a DFS, some more computationally efficient than others. For the sake of simplicity in an inherently "easy" task of generating a random maze, this tutorial will present DFS in its most raw form, with (sometimes) excessive backtracking. Assuming you are not generating enormous mazes, lag spikes and slowdowns should not be a problem with this code.
Overview of The Depth-First Search Maze Generator
Unless you want foresight into how this project will be structured and what resources we will need to create, you can skip over this section of the tutorial.
Our maze generator will consist of only two objects, oMaze and oCell. The former is the control object which oversees the entire maze, used to execute commands on each of the cells, oCell. oMaze will utilize the Create Event and Step Event. oCell will utilize the Create Event and Draw Event. We are not using any sprites in this tutorial, and anything rendered is being drawn using built-in GM:S functions, most notably draw_line() and draw_rectangle().
We will be writing three custom scripts, index(), checkNeighbors(), and removeWalls(). I will explain what these scripts do when we get to them. There will also be one room.
Remember that you can name your resources however you would like (e.g. obj_maze instead of oMaze), though be sure you modify their references in the code to suit your preferences.
Let's get started!
Preparing the Maze
We should begin development in the Create Event of object oMaze. Here, we are initializing variables and generating cells which will soon become the corridors of the maze. Using basic algebra, we are able to figure out how many cells we are able to fit inside our defined area, the current room size (320, 240) in this example. Further, we define the starting location of the maze generator at (0, 0). Be sure to create the room and place object oMaze in it.
Creating the Maze Cells
If you run the code now without creating oCell, you will receive an error indicating that no such object exists. To fix this, let's go ahead and create the oCell object. The Create Event is much less lengthy than oMaze's. We are merely defining the four walls the cell possess and stating that it has not yet been visited - it is not a cooridore of the maze yet.
Drawing the Maze Cells
You can run the project now and not get an error, but all you will see is an empty room. We already have a lot of code written but not much to show for it. I like seeing progress, and I am sure you do as well, so next let's draw the cells to at least have something! The next block of code will go in the Draw Event of object oCell. For this tutorial, I have each cell start out dark gray, become blue once visited, and green when it is the current, active cell. This code draws the colored cell and its four walls.
Generating the Maze
Now when running the game, you should be presented with a static, grid-like pattern. Sweet! It's not much, but it shows that we are able to properly position and size our cells across the room.
The next thing we should do is transition over to the Step Event of object oMaze where will finally start writing the maze generation using DFS.
The upcoming chunk of code is intimidating to look at, especially now that we're introducing the custom scripts, but it's much more comprehensive once we break it down. You'll notice the code is wrapped around a do... until() loop. This means that all the code inside of the do will be executed until a condition is met. In our case, the condition is that there are no unvisited cells on the board. This means that the entire maze will be generated in one game step - wow! If your game is running at 30 steps per second (room_speed), don't always expect the maze to generate in 1/30 of a second, especially if the maze you want to generate is large. The bigger the maze, the longer the hang-time. If you want to see the maze generate cell by cell, simply remove the do and until-related lines of code.
We mark the active cell as visited and set our destination cell, a neighboring cell, to undefined. The generator has not yet made up its mind on what adjacent cell it wants to move to next. The (unwritten) checkNeighbors() script will return us an unvisited, neighboring cell assuming one exists. If not, our destination cell will remain undefined.
Each time the generator moves the active cell to an unvisited neighbor, we add its position to a stack. A stack is a data structure that is comparable to a deck of playing cards. Each time you want to pull something from a stack, you take the top card off. The first elements (cards) in the stack are the last ones to leave. The last elements (cards) in the stack are on the top and the first to leave. This is commonly referred to LIFO: last-in, first-out. If there are no unvisited neighbors, we begin backtracking through the maze until we encounter one, going through the stack, removing the elements until it is empty - until there are no cards left. We can simulate a stack function by storing elements in a ds_list and removing the latest element from it. In a ds_list, each new element is appended to the end of the list, meaning that if we wanted the newest item in the list, we would have to pull from the end of it. We can use ds_list_size() to get the number of elements in a list. Using this, we know the desired index of the element we want to pull. Once pulled, we simply remove it from the list.
EDIT: Due to an oversight, I forgot GM:S comes with a built-in stack data structure, ds_stack, which can be used in lieu of our ds_list workaround.
If the currently active cell can move to an unvisited neighboring cell, we mark the neighboring cell as visited in anticipation of the move, add our position to the stack, and remove the walls between the two neighboring cells. Finally, we update the currently active cell to the neighbor. The neighbor now has control and will go through the entire process we just covered.
Checking for Neighbors
Most of the logic is in the game now! If you run the program, you'll get an error because we haven't written the custom scripts checkNeighbors(), removeWalls(), and index() yet. Let's do just that right now.
The first script we'll be writing is checkNeighbors(). This script will return a random, unvisited neighboring cell if one should exist. If not, it will return undefined. To randomize which neighbor the active cell should visit next, all neighbors are placed into a list which is shuffled. We reference another script, index(), which we'll look at afterwards. This script simplifies both the math and edge cases when referencing adjacent cells.
Clock-wise (above, right, below, left), we check for neighbors and add them to the list if unvisited.
Convenient Cell Referencing
Script index() accepts two arguments, an x-coordinate and a y-coordinate. It will return the cell at those coordinates if one should exist. Otherwise, it will return undefined. This script serves as more of an aid to cut down on repeating logic statements in checkNeighbors(). The edges of the maze do not have adjacent cells in all directions and we would get an "index out of bounds" error if we tried to reference one without the boundary checks.
Bringing it All Together: Removing Walls
Finally, the last code we need to write - the code which actually makes the maze look like a maze! Here, we remove the walls between visited, neighboring cells. Script removeWalls() is simple, though repetitive. There are ways to condense it, but this is passable. This script accepts two arguments, both of which are cells. First, we determine what direction the maze was just carved - what adjacent cell was visited. Then, we remove the walls. There are two walls to remove, one from each cell. If we translated to the right, we would remove cell A's right wall and cell B's left wall. The walls overlap, so both must be removed for it to visually make a difference.
Whew! We're done! Run the program and you should get a random maze on the fly. Press R to generate a new one. If something's not working or you just want to get your hands on the source, click here for the GitHub repo.
Thanks for reading this tutorial! Again, I would like to give a huge shout-out to the wonderful Daniel Shiffman for the original code I've ported over to GM:S. If you have any comments, questions or critiques, feel free to leave them below.
If you use any of this code in projects of your own, I ask for no credit whatsoever. However, all animations in this post were created by me and I would appreciate attribution if used anywhere.