The MaZe BaSe

The recursive division algorithm divides a field into 4 zones and then connects these zones with 3 doors, thereby creating a very basic maze. This process is then repeated recursively to make the maze more detailed.

The advantage of this algorithm is that it's easy to implement and highly efficient: it requires a minimum amount of steps to attain a completed maze. The downside is that it does not make the most interesting maze. The first few (big) zones can easily be recogized.

step by step

1. Create an array to store the zones to be divided. The first zone to divide is the entire field, so add this to the array.
2. Pick a zone from the array to divide. Remove this zone from the array.
3. Randomly divide the selected zone into 4 new zones. You can do this by finding a random point withinin the zone: this is the intersection of your 2 dividing walls.
4. Place 3 random doors to connect the 4 new zones.
5. Check the size of the each new zone: if it has not reached minimum size, add it to the zones array.
6. Check the zones array. If not empty, there are still zones to be divided, so restart the process at step 2.

Prim's algorithm grows a maze organically from its starting point. It does this by selecting a random cell to add to the maze, and then saving valid neighbours as 'frontier'. Next it selects a random cell from the frontier and repeats the process.

Fun to see growing and easy to build, Prim's algorithm is a joy to work with. On the other hand, it tends to generate short hallways in the maze, giving it a less interesting result.

step by step

1. Create an array to act as frontier and add a random starting cell to it.
2. Pick a random cell from the frontier. Make it part of the maze and remove it from the frontier.
3. Check neighbouring cells: if a cell is found that is already part of the maze, bridge to it.
4. Add all unvisited neighbours to the frontier.
5. Check size of the frontier: if not empty, restart process at step 2.

The recursive backtracker is a classic among maze generation algorithms: it randomly tunnels its way through the field until it corners itself. At that point, it retraces its steps until it finds an opportunity to start a new path, thus starting the process again.

Not as efficient as Prim's or Recursive Division, the algorithm creates long winding hallways that are interesting to look at. You can be absorbed by watching it retrace its steps and feeling out its way through every cell of the maze. If applied correctly, the last cell to be touched will always be the same as the first.

step by step

1. Create an array to store the path the algorithm has followed. Add a random cell to the path to give it a starting point.
2. Select the last cell from the path array. If not part of the maze yet, add it now.
3. Inspect the neighbours of this cell: if there are unvisited neighbours, choose one at random. If not, remove the cell from the path array and skip to step 5.
4. Open wall to selected neighbour and add it to the end of the path array.
5. Check path array: if not empty, restart process at step 2.

The same recursive backtracker, but this time in the shape of an octagon. This is done by applying a simple mask to the starting field to remove the corner cells from the maze. The algorithm ignores these cells when building the maze.

You will also see a small change in how the walls of the maze are rendered: previously every cell was defined as either wall or path, but now there is no longer any dictinction. Rather, every cell now logs internally which of its sides need to be walled. This is a much more robust way of working that gives us a lot more options to draw mazes. Among other things, it makes it easier to apply masks to a maze.

Unlike the previous algorithms which always showed a bias towards a certain result, the Aldous-Broder Algorithm (also known as a random walk algorithm) generates a truly random maze. As the term indicates, the algorithm simply randomly walks through the maze: if it encounters an unvisited cell, it makes this cell a part of the maze. It continues walking until it has randomly visited every cell.

While easy to code and giving a very nice result, the algorithm is not a very smart one. Due to its random nature, it can theoretically take an infinite number of steps for it to reach every cell. Don't get frustrated watching it walk past the last unvisited cell again and again!

step by step

1. Select a random starting point. Mark this as your current cell.
2. If the cell is unvisited, mark it as visited and build its walls. Check if there was a previous cell: if so, open the wall to this cell.
3. Choose a random neighbour to jump to. Mark this neighbour as your current cell.
4. Count the number of unvisited cells in the maze. If higher than 0, restart process at step 2.

This algorithm is a variation on the backtracker: like the backtracker, it starts tunneling in a random direction until it reaches a dead end. However, at that point it doesn't retrace its steps, but selects a new unvisited cell to start over. The algorithm ends when it can't find any unvisited cells anymore.

Requiring a lot more code, this is not the most elegant algorithm. Still, it does add to the texture of the maze. It leans more towards medium length hallways than the backtracker does.

step by step

1. Select a random starting point. Mark this as your current cell.
2. Mark the current cell as visited and build its walls. Check if there was a previous cell: if so, open the wall to this cell.
3. Evaluate neighbouring cells: if there are unvisited neighbours, pick one at random, mark as current cell and return to step 2.
4. Evaluate the field: are there unvisited cells neighbouring visited cells? If so, pick one at random, mark as current cell and return to step 2.

While we're playing around with shapes, let's try making a circular labyrinth! This can be achieved by switching to polar instead of cartesian coordinates: our x-axis is redefined as an angle on a circle (from 0° to 360°), while the y-axis becomes the distance from the center of the circle.

The labyrinth above isn't perfect yet: we simply took the standard backtracker algorithm and changed the way it's drawn to make it look polar. In reality, the maze is still generated with cartesian coordinates in mind. This results in a few problems:

1. The further away from the center, the wider cells become. In a proper maze, all cells should be around the same size.
2. If we were to split the wider cells, we end up with a grid where cells can border more than 4 other cells: an impossibility in our current grid system.
3. We have to leave the center of the circle empty to avoid mashed up, unusable hallways.

We'll resolve these issues by rethinking our coordinate system for the next labyrinth!

In order to resolve the issues of the previous maze, we have now implemented a new grid and coordinate system (or rather: we have done away with a coordinate system)!

While we previously relied on a grid to determine where a cell was and who it neighboured, every cell now stores a reference to its neighbours on its own. This means that cells can now have as many neighbours as they want, with the added advantage of greatly reducing the amount of logic need for the maze generation algorithm. We also store the shape of the cell for when we have to draw it on the canvas.

Other than that, we added some new logic to the field:

1. The central cell is the first one to be created.
2. Next we create a ring of new cells around the central cells. The amount of cells in this first ring is calculated automatically (to make them about as wide as they are heigh).
3. We continue adding rings (in function of the radius of the circle). If we detect that cells are becoming too wide, we split them in half.
4. While adding rings (and creating cells), we link the cells to their neighbours.

While we're at it, let's explore what else we can do now that we've moved so much logic from the grid into the individual cells.

This is a maze where every cell has only 3 neighbours. As before, who these neighbours are and how they relate to each other is all stored locally. Every cell carries the DNA of its neighbours. Other than that, every cell also remembers its orientiation. This has allow a grid where every cell is a triangle. We masked the extremeities (top left, top right and bottom cells) for visual reasons.

Such a novel shape!