Learning to Get Lost: Maze Algorithms and Game Development | The Software Guild

This month we feature the ninth installment in our new series of blog posts for 2019 — exploring topics from that interest and inspire our expert instructors. Subscribe to our blog to read analysis, programming tips and overall thoughts, straight from our instructors. This month, Kyle Rudy, Software Guild Java Instructor, explains how maze algorithms are used in game development and procedural development projects.

As I was growing up, I knew I wanted to work with computers as a profession because I loved computer games. Even though I never worked directly for a gaming company, I’ve still written computer games independently. Coming at game development from the perspective of a programmer-the idea of procedural generation, using code to generate aspects of the game world algorithmically rather than manually-has always fascinated me. One part of game development that ties into procedural development nicely is maze generation, using an algorithm to generate the dungeon or caves or labyrinth our players must explore and conquer.

In this post I’m going to explore one maze generation algorithm that does an excellent job of generating random mazes. Although it may seem complicated at first, it turns out to be relatively easy to understand. All the code snippets will be written in Java and I’ll use a game development framework called libGDX to display results. A link to a GitHub repository with the full codebase will be provided.

Wilson’s Algorithm

We’ll start by looking at Wilson’s Algorithm, also known as a loop-erased random walk. The algorithm works as follows:

1. Pick a position in the maze to be the initial cell included in the maze.
2. Pick a second position in the maze and start a path using a random walk from that cell, choosing a new random direction to go in every step.
3. If the path intersects with itself, forming a loop, erase the loop and continue from the intersection point.
4. If the path intersects a cell included in the maze, add the entire path to the maze.
5. While there are positions not in the maze, restart at step 2

To start the algorithm, we need to pick our initial point and initialize all the unused points. Due to the random nature of the paths we pick in this algorithm, any starting point is valid, so we often use point 0,0 as our initial maze point. We then add all other points to the unused list:

//Set initial maze point 
Cell initial = new Cell(0,0); 
maze.add(initial);
//Initialize the grid 
for(int x = 0;x<width;x++) { 
        for(int y = 0;y<height;y++) { 
                unused.add(new Cell(x, y)); 
        }
 }
//Remove initial maze point
unused.remove(initial);

Next, we must write code to determine what we do at each step of generating the maze. The easiest situation to deal with is if we haven’t yet started a new path or just finished a path, we can pull the first cell from the unused list and make that the beginning of a new path:

//When empty, choose a new starting point to draw from that's not in the maze 
if(path.isEmpty()) { 
        Cell newStart = unused.remove(0); 
        path.add(newStart);
 }

If we have a new path started, we must get the last cell added to the path so we can determine a random direction to travel from it:

//Get the top of the stack
 Cell lastCell = path.peek();

Once we have the cell, we can pick a direction, but we have to consider several things when picking a direction. First, if we are on the edge of the maze, certain directions are not valid, we can’t go north from the north edge of the map, or south from the south and so on. Second, if the direction we go runs back into the path, we go that way, but we eliminate the loop we created. Only when we can travel in a direction without hitting the path do we add that new cell to the path. There is a lot of similar code in this section so I’m only going to show the code for traveling north:

dir = (int) (Math.random()*4); 
if(dir == 0 && lastCell.y != 0) { 
        //North 
       nextCell = new Cell(lastCell.x, lastCell.y-1); if(!path.contains(nextCell)) {//The next cell is not in the path              
                valid = true; 
                lastCell.north = true;
                nextCell.south = true; 
                path.push(nextCell); 
} else { 
       while(!path.peek().equals(nextCell)) { 
              fixPathways();
              path.pop(); 
       }
 lastCell = path.peek();
 } 
}

We use random to get our direction (0 = north, 1 = south, 2 = west, 3 = east) and immediately check to verify we aren’t on the edge of the maze that prevents us from traveling that direction. Next, we create the cell with our new position and check to see if it is in the path or not. If it’s not in the path, we have a valid direction and can update the hallway variables to indicate we have a hallway between the two cells and then push the cell onto the path.

When the path does already contain the cell, we need to remove the loop that’s been created. We start working backwards through the path until we hit the cell we’re looking at again. Along the way, the fixPathways method will remove the hallways between cells.

The code for each direction looks the same, just adjusted to target the correct next cell and create the appropriate hallways.

Once we a valid next destination in the path, we have to do one last thing to finish this step, check if we are intersecting an existing section of the maze:

if(maze.contains(nextCell)) { 
         final Cell finalNextCell = nextCell;
         //Modify that cell in the maze so the connections are valid
         maze.stream()
         .filter((c) -> c.equals(finalNextCell))
         .forEach((c) -> { 
                  c.east = c.east || finalNextCell.east;
                  c.west = c.west || finalNextCell.west;
                  c.north = c.north || finalNextCell.north;
                  c.south = c.south || finalNextCell.south;
         });
         path.pop();//Remove the last cell from the stack
         maze.addAll(path);//Add all the entries in the path to the
         maze unused.removeAll(path); 
         path.clear();
}ene

We start by checking if the cell we traveled to is already in the maze, if so, we have intersected the maze. We first need to verify the final cell has valid hallways. Basically it needs to keep its own existing connections but also add any gained from the path. Once we’ve done that, we can remove that cell from the path by popping it off the top. Since it’s already in the maze we don’t want to add it twice. We then add all cells in the path to the maze, remove all cells in the path from the unused list and clear out the path so we can start over.

We continue this process until all cells are included in the maze. Here is what it looks like at 20×20:

After watching it in motion something you might notice is that the early paths often take the longest to generate. With so much open space and so few included cells in the maze, it’s easy for the random walk to wander for a long time. On the other hand, once we have a few paths it runs quicker. This also means that the larger the maze we are generating the longer it will take-almost exponentially longer.

There are much faster algorithms than this one, but the benefit of Wilson’s algorithm is how random the maze is. Other algorithms end up being biased towards short paths or long hallways or grid-like structure, whereas the mazes generating by Wilson’s algorithm don’t lean in any specific direction. All features can appear, or none can appear.

Maze algorithms are be a fun way to dive into procedural generation. If you want to develop games yourself, they can be an invaluable tool. You can find the code for this example at: https://github.com/kdrudy/WilsonsAlgorithm. Feel free to download and run it yourself. Tweak the code to see what other results you can generate.

Originally published at https://www.thesoftwareguild.com on September 12, 2019.