Depth-first Search (DFS) Maze Generation in GameMaker: Studio

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.

In today's tutorial, I will be showing you how to make a random maze generator using a depth-first search (DFS) algorithm in GameMaker: Studio, which can be adapted with minor changes to work with GM:S2. This is a fairly simple concept to grasp, and can serve as a solid introduction into several 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 nor special, and that I'm essentially walking you through a GM:S 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. Further, if something in the code below does not make sense to you even with my - albeit brief - comments, be sure to check out Shiffman's video as he explains in-depth what the code he's writing does. However, remember that this tutorial is in GML and Shiffman's is in JavaScript, so using his code verbatim will not compile correctly in GM:S.

As always, the source code can be found at the end of this tutorial.


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 Project

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.

/// CREATE EVENT of object oMaze

random_set_seed(randomize()); // 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 = floor(width / w); // columns
rows = floor(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_create();

Creating the 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.

/// 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 Cell

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.

/// DRAW EVENT of object oCell

draw_set_color(make_color_rgb(42, 42, 42)); // set color to dark gray/black

if (visited) { // if the cell has been visited by the generator
    draw_set_color(make_color_rgb(0, 0, 255)); // set color to blue
    if (id == oMaze.current) { // set color to green if the cell is currently active
        draw_set_color(make_color_rgb(0, 255, 0));
    }
}
// draw rectangle over span of cell, colored based off the scenerios reached above
draw_rectangle(x, y, x + w, y + w, false);

// set the color to white to draw the walls
draw_set_color(c_white);

if (walls[0]) { // draw top wall
    draw_line(x, y, x + w, y);
}

if (walls[1]) { // draw right wall
    draw_line(x + w, y, x + w, y + w);
}

if (walls[2]) { // draw bottom wall
    draw_line(x + w, y + w, x, y + w);
}

if (walls[3]) { // draw left wall
    draw_line(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.

/// 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) {
        other.next = 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_add(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_empty(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_value(stack, ds_list_size(stack) - 1);
        ds_list_delete(stack, ds_list_size(stack) - 1); // remove the cell from the stack
    }
}
until(ds_list_empty(stack)); // the stack is empty; all cells have been visited

// reset the room by pressing the "R" key
if (keyboard_check_pressed(ord("R"))) {
    room_restart();
}

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.

///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_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_1d(n); c++) {
    if (n[c] != undefined) {
        if (!n[c].visited) {
            ds_list_add(neighbors, n[c]);
        }
    }
}

// check if we added any neighbors to our list (it's not empty)
if (!ds_list_empty(neighbors)) {
    ds_list_shuffle(neighbors); // shuffle the list of neighbors
    var n = ds_list_find_value(neighbors, 0); // grab the top neighbor
    ds_list_destroy(neighbors); // destroy the list of neighbors
    return n; // return the randomly-selected neighbor
} else {
    ds_list_destroy(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.

///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.

///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
}

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.

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.

GameMaker-related posts mailing list