Mazes

In this article I’m going to take a look at one of the many algorithms that can be used to generate mazes. The technique I am going to describe uses a depth first search strategy. It is also given the name of a recursive backtracking algorithm. Both of these names should give you clues as to how the technique works.

A maze is a complex structure of interconnected passageways. There should be (at least) one way to get from a designated start location to a designated end. Typically the path is convoluted and branched (these branches can also be branched, and often leading to dead-ends) making it not obvious to the naked eye the correct path to take (even when exposed to a God’s eye view from above with all information exposed).Mazes are even more challenging to solve when you are inside one and are only exposed to the information you can immediately see!

Mazes are even more challenging to solve when you are inside one and are only exposed to the information you can immediately see!

Generating Mazes

|Different algorithms for generating mazes work in different ways. Some start with a ‘solid’ block and ‘carve’ out passages as they progress. Others start with an ‘empty’ space and ‘build’ walls. The back track recursive algorithm is a carving algorithm: It starts out as a complete grid with all boundaries and walls set and removes walls to generate the labyrinth.In this article I’m using a 2D rectangular grid but the technique can be generalized to any tessellating shapes in any number of dimensions.||

In this article I’m using a 2D rectangular grid but the technique can be generalized to any tessellating shapes in any number of dimensions.

First, however, let’s take a quick look at ways we can describe mazes:

Properties of mazes

Mazes have characteristics that describe them. A maze is classified as ‘perfect’ if it does not contain loops (as we will see later, the dual of a maze is a graph, and if this graph is a single tree with no cycles then it is a perfect maze. A perfect maze can also be described as a ‘simply connected’ maze.

If a maze is simply connected it is possible to solve it using a wall following algorithm. By always keeping you right hand (or left if you prefer!), against the maze wall and walking around you will walk a path that will eventually visit every location in the maze and return to the same location.

The maze on the left above is a simple maze. By selecting a wall and following it all the way around, each and every location in the maze is visited. Wherever the entrance and exit were, with a simple maze, following a wall will, eventually, take you past them. The maze on the right is not simple; it has a loop (island). Using a wall following algorithm you are not exposed to all locations. If the exit of this maze happend to be in the island, you would never find it using a simple wall follower.

More properties

Mazes are usually generated using random number generators and even running the same algorithm twice in a row (with different seeds for the random number generator) will produce different results. However, on average, different algorithms have different characteristics and properties. Here are some of these characteristics:

Simply connected/Complex - We’ve mentioned this already. Is it possible to visit every location by simply following one wall? If so, the maze is simply connected. A simply connected maze does not have any loops.
Number of dead-ends - It’s possible to make maze that has no wrong turns at all, it’s just a convoluted loop! This would not be a very challenging maze! The number of dead ends in a maze is the measure of the number of locations in the maze that have only one way in. A maze that has only a few dead-ends, and long pathways in-between, might be quite frustrating as you’d have to go a long distance before finding out you’d gone the wrong way!
Length of longest path - This is often measured as percentage. First you find the shortest (optimal) path through the maze, then measure the ratio of the number of cells on this path to all the cells in the maze. A high percentage indicates a fair amount of convolution and twisting of the solution (taking lots of turns in order to get to the destination, and visiting a good measure of the maze before exiting).
Convolution - Either measured as twistiness, or its inverse straightness, and is some metric to measure how often in the maze that the path exits a cell on the opposite side of the way it came in, and how often it turns a corner in a cell. The human brain has an easier job following paths that are straight (if you see a long line a cells in a straight line you instantly know that there is a clear path to the end of this section. However, if the path is twisted, you can’t immediately see to the end and have to trace it to find out).
Distribution of Valency - Dead ends cells have a valency of one (There is only one way in and out of that cell). Crossroads have a valency of four (in a rectangular grid maze); there are four possible directions to go from this cell. Unbranched corridors have a valency of two, and T-junctions have a valency of three. Different maze algorithms generate different distributions of valencies. An algorithm with a high percentage of T-junctions and crossroads exposes the solver to lots of options. One with a high percentage of corridors (valence two cells), takes the user on long ‘rides’.
Complexity - Related to all the above, this is a measure of the average number of ‘decisions’ a solver will have make to get from the start to the end. What is the average number of junctions you’ll encounter when solving a maze?

Mazes can also be described as having biases; these are patterns baked into the maze by the algorithm (typically by modifications to the random number generator). For instance, instead of selecting entirely at random, an algorithm could be programmed to give a much higher probability of turning clockwise when exiting any cell (making obvious twists), or alternatively, configured to have a much higher probability of exiting a cell opposite the way that it came in (making a maze that has a bias for long runs of straight corridors).

Both of the above mazes are perfect mazes. The one on the right has a strong vertical bias. It also has a high concentration of two valence cells, and high straightness.

Graph Theory

Below are two mazes. The one of the left is a perfect maze, the one on the right has loops. There is an alternate way of thinking about a maze. Instead of thinking about the walls, we can think about the paths between cells. Mathematicians call this a dual network.

The pathways form a graph (sometimes called a tree). The graph for each maze is shown below in red. We can see now that if there is more than one graph the maze is not solvable (if the start and exit are in different trees); this is because there would be no path between the seperate trees.

Where the maze has (redundant) loops - representing alternative ways to get to the same location we can see the graph also has loops.

Spanning Tree

||From this we can see that to generate a perfect maze what we need to do is create a random spanning tree that connects all the cells in the maze.The various ways of generating spanning trees form the basics of various maze generating algorithms. The one we’re going to look at is a recursive backtracking algorithm.|

The various ways of generating spanning trees form the basics of various maze generating algorithms. The one we’re going to look at is a recursive backtracking algorithm.

Recursive Backtracker

||The basics of a recursive bactracking algorithm is that we start somewhere on the maze (it does not matter where), and step in a random direction onto a new square. The constraint is that we can’t step onto a square that we’ve already trodden on. When travelling to this new square we remove the wall to the new square and this is what carves out the maze. We keep a track of which squares we’ve visited and which we have not.We keep repeating this algorithm: Examining all the neigbours of the current square and selecting (at random) any of the unvisited squares, moving into it, then mark this new location as also visited.This is all well and good but sooner or later we’ll find that we’ve painted ourself into a dead end and there will be no neigbouring unvisted squares. What the algorithm does then, is take a step backwards to see if there are any unvisted neigbours from the last visited square, if so carrying on from there, if not, it takes another step further back and looks from there, etc …This keeps going on (moving forward into unvisted squares), or backing up until a square with unvisted neighbours is found, until all squares have been visited. It is called a depth first search because the algorithm plows as far forward as it can before backing up.|

We keep repeating this algorithm: Examining all the neigbours of the current square and selecting (at random) any of the unvisited squares, moving into it, then mark this new location as also visited.

This keeps going on (moving forward into unvisted squares), or backing up until a square with unvisted neighbours is found, until all squares have been visited. It is called a depth first search because the algorithm plows as far forward as it can before backing up. |A common way to implement this is through the use of a stack (First In Last Out). As we visit each square for the first time, we push this location onto a stack which keeps track of the order we’ve visited them (a stack is like a stack of plates; it’s a list but with strict rules about how we can access them), we keep adding plates to the top (pushing the current location onto the stack) for every forward move we make until we can’t make any more moves. When we get stuck, we pop off the top item from the stack (the last visited square), and carry on from there. If the previous location popped off the stack is also blocked, we pop off the next item from the stack (the previous, previous visited location), and so on …The stack dynamically changes in length as the algorithm progresses.||

The stack dynamically changes in length as the algorithm progresses.

Let’s see this in action …

We’ll demonstrate this with a small (5x5) maze. ||We’ll demonstrate this with a small (5x5) maze.The cells are numbered as seen on the left. RED squares are cells that have been visited.The stack is currently empty.All the walls are are currently present between all locations in the grid.|

RED squares are cells that have been visited.

All the walls are are currently present between all locations in the grid. | | ||Next we select a location to start.This can be random, but let’s chose #1.This location is pushed onto the stack.We’ve visited our first location.STACK: 1||

This can be random, but let’s chose #1.

We’ve visited our first location. | | ||We’re currently at grid location #1.Next we enumerate all possible destinations from here.We find out all possible (non-visited) locations that are adjacent to the current location. We’ll show these in YELLOW The possible locations are #2 and #6.We’ll select one of these at random.|

Next we enumerate all possible destinations from here.

The possible locations are #2 and #6. | | ||We’ve selected #2.This location is now pushed onto the stack.We now carve a path between #1 and #2.We do this by removing the wall seperating these two locations. The image on the right shows the maze as it is developing. The Magenta locations have been visited.STACK: 1 2||