Maze generation is a fascinating concept. When I first stumbled upon it I had no clue how to get started. I did some research and landed upon a few excellent articles. I'll link them for any interested people to check out. I'll get a few things out of the way before getting into the actual algorithms. First of all, all of the algorithms I included are used to generate perfect mazes. By that I mean mazes that have exactly one path between any two cells and no loops. What's cool about the concept of generating mazes is that it is very relevant to graph theory. A lot of the algorithms are just minimum spanning tree or graph traversal algorithms with a little bit of randomness mixed in. Now that I've mentioned it I'll clear up a few basic graph terms. A spanning tree is just a tree that contains every node in a graph. Every perfect maze is just one of the possible spanning trees that can be formed in a grid. There are two types of maze creators: passage carvers and walls creators, which are fairly evident of what they mean. Well, I think that clears a good amount of the vocabulary for this so let's move onto the actual algorithms.
How this one works is that it essentially just does a depth first traversal of graph. It starts by putting a random node onto a stack. And then on each cycle it pops a node off of the stack and randomly adds one of its neighbors that hasn't yet been visited. If all the neighbors have been visited then the node isn't aded back to the stack. So basically it will form a long path until it dead-ends itself. Once it dead-ends then it will essentially pop nodes off of the stack until one with unvisited children is found. This continues until all nodes have been visited and the stack is empty.
This one is just a bit of graph theory. It's an interesting implementation of Prim's algorithm which I'll explain in minmal detail. The purpose of Prim's algorithm is to build a minimum spanning tree of a graph, which is basically just a tree that contains all edges of the graph but has the smallest possible sum of edge weights. The difference in this implementation is that there aren't really varying edge weights between nodes because they all are spaced evenly. One way we could simulate this is to randomly assign weights to all of the edges and then choose edges to add to the spanning tree based on that, but I found that it is much simpler to just add a random neighbor from a node. This accurately simulates this idea. Now with relation to how to generate maze. We start off by not having any nodes displayed/visited. Each time that we add a neighbor from a node we carve a path and mark it as visited. This pattern continues until all of the nodes have been visited. This isn't really my favorite algo mostly because of how the mazes end up looking. It's cool to watch them be generated but not that great in the end because they end up being very obviously generated by this algorithm in my opinion. You can kind of see how they branch out from the starting point.
I'm actually quite a fan of this one. Once again it's taken straight from graph theory. Kruskal's algorithm is also used for generating a minimum spanning tree but it does it in a very different way. Instead of branching out from what has been visited and adding nodes it works on the basis of adding edges to the tree. Each time that it adds an edge it has to check to make sure that it doesn't cause a loop in the tree. It repeats adding edges until there aren't any remaining to add which also implies that all the nodes have been visited. We can implement this thing by just putting all of the edges into a list and shuffling it. At each iteration we check the first edge and if it doesn't cause a loop then we add it to the current graph and mark those nodes as visited. Once again just repeat this until all of the nodes/edges have been visited.
Eller's algorithm may be my favorite of them all for a few reasons. First it generates mazes that to me are quite attractive/random looking. Next is maybe the coolest, it can generate a maze with space proportional to the width of the maze. This means that it can theoretically generate infinitely large mazes only requiring space for the width of the maze, you only ever need to know the data from the last row to generate a new one. Okay, now onto actually implementing it. It's a little bit more complicated than the others implement. We'll start off by observing just the first row of the maze. We want to start by creating a unique set for each of the nodes in this row. Next we'll iterate through and randomly decide whether or not to join it with the next cell. If the two cells are already in the same set then you can't connect them. When you connect two cells merge their sets together. This means that each set represents all cells that are connected together which will become more useful as more rows are added. After we finish connecting adjacent cells we move on to looking at the next row down, kind of. Now we still are using the sets from the previous row but we are randomly adding connections downward and adding those to the set. Each set must have at least one downward connection. Now we can finally move onto the next row. Add any cell that wasn't added by a downward connection to it's own unique set. We can repeat the first step with merging the adjacent cells just now using the cells from the last row. Repeat this for as long as you want but when you want to to stop there is one last step. We iterate through the last row and add a connection between any two cells that are not in the same set. This ensures that there is a path between every cell. I hope that was at least close to a decent explanation. It can be a confusing algorithm but I found that going through it on paper helped it to make a lot more sense to me.
This is an algorithm that is extremely simple but also generates very good looking mazes. What's nice is that it is one of the few algorithms that is bias free. The other ones have consistent biases and characteristics that show up in every graph, like long winding paths or really short dead-ends. But this one can truly randomly generate a maze out of all possible mazes that could be generated. The algorithm is very simple which is also nice. It goes like this. We start, like most of the others it starts at a randomly location in the graph. Now we randomly visit one of the neighbors of this node. If it is unvisited then we carve a passage between them and mark it as visited. This continues repeatedly until all of the nodes have been visited. If you haven't noticed, this is very inefficient because it can visit a cell any number of times without reaching one that hasn't been visited.
The way that this one works is kind of cool and especially cool to watch. All of the previous algorithms have worked by adding connections between cells. This one instead adds walls. It does it in a recursive manner by adding a wall randomly inside of a section and recursively doing the same to either side of that newly added wall. This continues until it gets to the required detail level. It could continue to have an infinite amount of detail as well which is kind of cool. Unfortunately, this one has very obvious biases with both long unbroken passages and long unbroken walls.
This one is similar to the Aldous Broder algorithm in that it is free of baises. It starts, who could have guessed, at a random cell and does a loop erased random walk from it. That means that it does a basic random walk but each time that the walk crosses on itself it removes all the nodes in the loop and continues from where they crossed. It also picks an intial target cell and when the random walk reaches the cell it marks all of the cells in the path as visited. This initial step can take a very long time but one it after that it finishes much faster than Aldous Broder.
This one is very similar to the backtracker. It does the same basic logic for carving paths but when it encounters a dead-end it simply starts again from the first unvisited cell in the maze, starting from the top left counting left to right in each column. This results once again in long winding passages but they are mostly directed towards the bottom rather than branching from one path. There really isn't much more to be said about this algorithm.
This one is similar to Eller's in the way that it operates row by row. It actually is able to use less storage then Eller's, however. It only needs to keep track of one set. How it works is it iterates through each cell and chooses whether or not to add it to the set. If it decides not to then it adds 1 random path up from the current set, clears the set, and adds the current cell to the set. If it chooses to add the cell to the set then it just, well, adds the cell and draws the passage. Due to the nature of carving paths upword it we first need to draw the entire first row so that all the later rows will be guaranteed to be connected. And that's it, it forms a perfect maze by doing this.
This algorithm is cool in that it is more general than the others. It can be configured to behave in different manners. It's basic functionality is this: you have a set that starts out empty and then you add a random cell to start from. At each iteration you take a cell from that set and carve a passage to one of the cells unvisited neighbors, adding that neighbor to the set as well. If the selected cell didn't have any unvisited neighbors then the cell is removed from the set. It may sound pretty basic but the behavior of the algorithm is changed drastically depending on how the cells are selected from the set. It behaves the same as Prim's when the cells are selected at random and the same as the backtracker when the cell selected is the one most recently added to the set. These behaviors can be mixed for interesting results.
Last and sort of least we have the binary tree algorithm. It works how you may assume it to work and is kind of cool in that it actually works on just a cell by cell basis. It carves a passage one of two directions depending on which corner you start from. If you are starting from the top left then you either carve a passage down or right. If the cell is along the left or bottom wall then it only has one option to carve so it creates large passages along those sides. And this ends up creating a perfect maze which is kind of cool, no additional memory necessary.