How to generate mazes in GameMaker Studio using depth-first search (DFS)

This article has been updated since its original posting on February 19, 2017.

The final result will generate the entire maze almost immediately, but to get a better sense of how DFS works (and for fun), this is the maze being carved out step-by-step.

The final result will generate the entire maze almost immediately, but to get a better sense of how DFS works (and for fun), this is the maze being carved out step-by-step.

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.

I feel it's important to preface the tutorial by stating that this particular maze generation technique is nothing new. I'm essentially walking you through a GameMaker port of Daniel Shiffman's JavaScript tutorial of the same topic. Shiffman is a wonderful personality and his Coding Train series on YouTube is engaging content for anyone who wants to learn about JavaScript (p5.js) and Java (Processing) through fun, digestible projects.

If something in this tutorial’s code doesn’t make sense to you even with my - albeit brief - comments, be sure to check out Shiffman's video. He explains in-depth what exactly the code he's writing does. Note that this tutorial is written in GML and Shiffman’s is written in JavaScript. If you want to learn how to make a random maze generator in Java or implement depth-first search in C++, then the verbatim code won’t correctly compile. With that said, even if you’re not using GameMaker, you’ll still be able to walk away from this tutorial with a strong understanding of depth-first search concepts.

As always, the source code can be found at the end of this tutorial via a GitHub link.

What is Depth-First Search?

This particular depth-first search prioritizes exploring to the left, gradually making its way to the right. How you choose to traverse is up to you.

This particular depth-first search prioritizes exploring to the left, gradually making its way to the right. How you choose to traverse is up to you.

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.

Neighbors (blue) are defined as adjacent cells to the right, left, top, and bottom of an active cell (green), not corner cells.

Neighbors (blue) are defined as adjacent cells to the right, left, top, and bottom of an active cell (green), not corner cells.

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

The expanded project resource tree.

The expanded project resource tree.

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.

GML Code Snippet
/// CREATE EVENT of object oMaze      
random_set_seedrandom_set_seed(seed)(randomizerandomize()()); // set a random seed to produce unique mazes every time      
width = room_width; // px horizontal span of the maze (width of room) (320)      
height = room_height; // px vertical span of the maze (height of room) (240)      
w = 10; // px width of each cell (applied to height also to produce square cells)      
// calculate the number of cells in rows and columns of the maze (total cells = columns * rows)      
cols = floorfloor(x)(width / w); // columns      
rows = floorfloor(x)(height / w); // rows      
// cycle through all columns and rows to fill the board will cells      
for (var i = 0; i < cols; i++) {     
    for (var j = 0; j < rows; j++) {     
        Create a cell at (i, j) and multiply the coordinates by      
        the cell size to properly position them in the room.      
        If your maze should not start at (0, 0), add an offset to the      
        x and y spawning position (be sure width and height vars take into      
        account this repositioning).      
        e.g. obj = instance_create(100 + (i * w), 100 + (j * w), oCell);      
        obj = instance_create(i * w, j * w, oCell);     
        // pass variables from the generator into the cell      
        obj.i = i; // pass horizontal index      
        obj.j = j; // pass vertical index      
        obj.w = w; // pass width of cell      
        obj.cols = cols; // pass number of columns      
        obj.rows = rows; // pass number of rows rows      
        grid[i, j] = obj; // set index of 2d array to the cell      
We've just filled a 2d array, spanning the entire room, with cells      
(room_width/w) * (room_height/w) = 32 * 24 = 768 cell objects      
// cell from which the maze begins generating. [0, 0] is top-left      
current = grid[0, 0];     
// create a stack to previously visited cells, used for DFS backtracking      
stack = ds_list_createds_list_create()();    

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.

GML Code Snippet
/// CREATE EVENT of object oCell      
var w, cols, rows, i, j; // define vars. Values are passed in through object oMaze when created      
Each cell has four walls associated with it      
    wall[0] = top wall, wall[1] = right side wall, wall[2] = bottom wall, wall[3] = left side wall      
All four walls drawn together will produce an outline of a square      
If wall[i] = false, the wall will not be drawn. By default, all four should be      
for (var i = 0; i < 4; i++) {     
    walls[i] = true;     
// whether or not the cell has been visited yet and is a part of the maze      
visited = false;    

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.

GML Code Snippet
/// DRAW EVENT of object oCell      
draw_set_colordraw_set_color(col)(make_color_rgbmake_color_rgb(red,green,blue)(42, 42, 42)); // set color to dark gray/black      
if (visited) { // if the cell has been visited by the generator      
    draw_set_colordraw_set_color(col)(make_color_rgbmake_color_rgb(red,green,blue)(0, 0, 255)); // set color to blue      
    if (id == oMaze.current) { // set color to green if the cell is currently active      
// draw rectangle over span of cell, colored based off the scenerios reached above      
draw_rectangledraw_rectangle(x1,y1,x2,y2,outline)(x, y, x + w, y + w, false);     
// set the color to white to draw the walls      
if (walls[0]) { // draw top wall      
    draw_linedraw_line(x1,y1,x2,y2)(x, y, x + w, y);     
if (walls[1]) { // draw right wall      
    draw_linedraw_line(x1,y1,x2,y2)(x + w, y, x + w, y + w);     
if (walls[2]) { // draw bottom wall      
    draw_linedraw_line(x1,y1,x2,y2)(x + w, y + w, x, y + w);     
if (walls[3]) { // draw left wall      
    draw_linedraw_line(x1,y1,x2,y2)(x, y + w, x, y);     

A grid of empty cells. Soon, they'll be a part of a maze!

A grid of empty cells. Soon, they'll be a part of a maze!

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.

A visual representation of a stack data structure

A visual representation of a stack data structure

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.

Neighboring walls are removed

Neighboring walls are removed

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.

GML Code Snippet
/// STEP EVENT of object oMaze      
// the statement within the brackets will be executed until the stack is empty (until)      
do {     
    current.visited = true; // the current, active cell has been visited      
    // the destination cell, where we head next, has yet to be determined      
    next = undefined;     
    // check the current cell's neighbors to determine if we can visit one      
    with(current) {     = checkNeighbors();     
    // if the cell can move adjacently; if we have an unvisited neighbor      
    if (next != undefined) {     
        next.visited = true; // mark our neighbor as visited in preparation of the move      
        ds_list_addds_list_add(id,value,.)(stack, current); // add the current, active cell to the stack      
        removeWalls(current, next); // remove the walls between us and our neighbor      
        current = next; // update active cell to the neighboring cell      
    } else if (!ds_list_emptyds_list_empty(id)(stack)) { // if we have no unvisited neighbors and the stack isn't empty      
        // pop a cell off the top of the stack and visit it      
        current = ds_list_find_valueds_list_find_value(id,pos)(stack, ds_list_sizeds_list_size(id)(stack) - 1);     
        ds_list_deleteds_list_delete(id,pos)(stack, ds_list_sizeds_list_size(id)(stack) - 1); // remove the cell from the stack      
until(ds_list_emptyds_list_empty(id)(stack)); // the stack is empty; all cells have been visited      
// reset the room by pressing the "R" key      

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.

GML Code Snippet
/// checkNeighbors();      
    This script is called by a cell to get reference to its      
    neighboring cells and whether or not they have been visited.      
    If possible, it will return a random unvisited, neighboring cell.      
var neighbors, n; // declare temp vars      
neighbors = ds_list_createds_list_create()(); // create a list to hold the cell's neighbors      
n[0] = index(i, j - 1); // get the neighbor above us      
n[1] = index(i + 1, j); // get the neighbor to the right of us      
n[2] = index(i, j + 1); // get the neighbor below us      
n[3] = index(i - 1, j); // get the neighbor to the left of us      
/* if there is a neighbor, n, and it has not been visited, add      
it to the list of avaliable neighbors. Repeat for right, left, above, below*/     
for (var c = 0; c < array_length_1darray_length_1d(variable)(n); c++) {     
    if (n[c] != undefined) {     
        if (!n[c].visited) {     
            ds_list_addds_list_add(id,value,.)(neighbors, n[c]);     
// check if we added any neighbors to our list (it's not empty)      
if (!ds_list_emptyds_list_empty(id)(neighbors)) {     
    ds_list_shuffleds_list_shuffle(id)(neighbors); // shuffle the list of neighbors      
    var n = ds_list_find_valueds_list_find_value(id,pos)(neighbors, 0); // grab the top neighbor      
    ds_list_destroyds_list_destroy(id)(neighbors); // destroy the list of neighbors      
    return n; // return the randomly-selected neighbor      
} else {     
    ds_list_destroyds_list_destroy(id)(neighbors); // destroy the list of neighbors      
    return undefined; // return undefined, we have no neighbors      

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.

GML Code Snippet
/// index(i,j);      
    This script allows us to pass in coordinates and access      
    the appropriate cell at the given index, if it exists      
var i, j; // declare temp vars      
i = argument0;     
j = argument1;     
// return undefined if the index is out of our array      
if (i < 0 || j < 0 || i > cols - 1 || j > rows - 1) {     
    return undefined;     
return oMaze.grid[i, j]; // otherwise, return the necessary cell     

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.

GML Code Snippet
/// removeWalls(a, b);      
    This script is used to remove walls between the currently      
    active cell and the neighboring cell about to be visited      
var a, b, _x, _y; // declare temp vars      
a = argument0;     
b = argument1;     
/* subtract cell A's horizontal position from B's to determine whether      
the active cell visited the left neighbor (-1), right neighbor (1),      
or is parallel (0) */     
_x = a.i - b.i;     
if (_x == 1) { // if the previously-actived cell visited a neighbor to the right      
    a.walls[3] = false; // remove left wall from cell A      
    b.walls[1] = false; // remove right wall from cell B      
} else if (_x == -1) { // if the previously-actived cell visited a neighbor to the left      
    a.walls[1] = false; // remove right wall from cell A      
    b.walls[3] = false; // remove left wall from cell B      
/* subtract cell A's vertical position from B's to determine whether      
the active cell visited the above neighbor (-1), below neighbor (1),      
or is parallel (0) */     
_y = a.j - b.j;     
if (_y == 1) { // if the previously-actived cell visited a neighbor above      
    a.walls[0] = false; // remove top wall from cell A      
    b.walls[2] = false; // remove bottom wall from cell B      
} else if (_y == -1) { // if the previously-actived cell visited a neighbor below      
    a.walls[2] = false; // remove bottom wall from cell A      
    b.walls[0] = false; // remove top wall from cell B      

In Closing

Maze generation with different dimensions

Maze generation with different dimensions

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.