How can I generate mazes that often have multiple "forks" or choices?

Question

The basic algorithm for procedurally generating mazes goes something like this:

1. Choose a random available direction from the current square.
2. If there is one, go there and repeat from step 1.
3. Otherwise, backtrack to the previous square and repeat from step 1.

This is a fairly good algorithm, but the problem is that it typically generates easy mazes. They usually only have one option or path, and alternate paths don't appear very often and reach dead-ends quickly.

How could I alter the algorithm (or change it entirely) to create more branching?

Answer 1

The algorithm you've mentioned is called depth-first generation, and actually, it's quite easy to intuitively demonstrate a way to do this.

If you have a maze generated via a depth-first algorithm, there is one and only one way to each square. DFS generates a "perfect" maze - one without any closed loops, without inaccessible areas, and is simply connected. There is one and only one path from any point to any other point. Thus, the maze has exactly one solution.

Now take adjacent - but walled - points A and B. There exists a path from the entrance to point A, and there exists a path from point B to the exit. However, because there is a wall between points A and B, there also exists a path which does not go through both A and B that leads to the exit. By removing the wall between A and B, you create a new (second) path through both A and B that leads to the exit, thus creating an alternate path.

Thus, if you remove any wall in the maze, you create another path, or multiple valid paths.

Note that this makes your maze imperfect by definition, as there are now two paths from the start to the exit.

Answer 2

First I want to question your premise a bit. Your goal is to create harder mazes, but you suggest that the method is to increase the branching factor.

You are right up to a point; more branches is often associated with higher difficulty, but if you go too far you run into the problem that Joe Z. hinted at - you'll have lots of very short dead-ends, which to a human is very easy to spot.

For the ultimate maze/labyrinth creation resource, I often go to Think Labyrinth by Walter D. Pullen. On his Maze Classification page, he lists a relevant metric for you, river:

River: The "river" characteristic means that when creating the Maze, the algorithm will look for and clear out nearby cells (or walls) to the current one being created, i.e. it will flow (hence the term "river") into uncreated portions of the Maze like water. A perfect Maze with less "river" will tend to have many short dead ends, while a Maze with more river will have fewer but longer dead ends.

I think what you want is a moderate amount of "river"; lots of branches but not so many that will cause the dead ends to be too small and easy to spot.

Compare the following mazes generated by different algorithms:

Recursive backtracker (very high river)

Eller's Algorithm (moderate river)

Prim's Algorithm (very low river)

Note that your algorithm is pretty much the recursive backtracker. Try a different algorithm!

Answer 3

Ok - you want your Algorithm to create more challenging mazes? Change it to a BFS - You start with your normal algorithm, but you always pick random where you continue and not just after you have reached the goal...

1. Initialize path-list with one active square at the starting location.
2. Pick a random active squares: Referred to as 'current square'
3. Pick a random free square around the current square (if there are non skip to 5)
4. Connect the chosen free square to the current square and mark it NOT free and
   add it to the list of active squares.
5. If the current square has no empty squares around remove it from the list
6. If the new Square is next to the Goal, connect it to the goal
7. Goto 2 until there are no more active paths left.

This will give you a labyrinth with a single path to the goal, but many paths which look just as promising. This should be pretty hard. If you want more than a single path to the goal, you can add a switch in step 3, which can also chose an occupied square and open up a connection to it (but doesn't add it to the list of active squares)

Then you will get a labyrinth with round-trips and (possibly) multiple ways to the goal

Answer 4

There are multiple maze generation algorithms. The one you describe the basic DFS algorithm. I'm aware of two other maze algorithms, both of which produce a lot more branching: Prim's algorithm and Kruskal's algorithm. Both of these algorithms are actually algorithms to find the minimum spanning tree of an undirected weighted graph.

Suppose you have a grid of points, which are connected horizontally and vertically to their direct neighbours. Then, assign each edge a random weight, and run Prim's algorithm to find the minimum spanning tree of this grid. Ta-dah, you have a randomly generated maze.

Now, the problem with mazes like this, from testing and experience, is that they branch a little too much. Most of the branches are one-square to three-square ordeals, and it's really easy to determine which branches lead to dead ends most of the time. You want somebody to be able to follow the maze for a little while before reaching dead ends.

So what you can do is to tweak the algorithm a little bit. One of the easiest alternate algorithms you can make is a "bounded DFS", in which you only go a certain distance inward on your search for a path before forcing a backtrack and branching again. This will create mazes with nice long stray paths most of the time.

As for modifying Prim and Kruskal, I don't know enough about graph theory to ascertain whether this method will actually work, but consider making it so that when generating the random graph at the start, the weights of edges touching the same point have to be within a certain distance of each other.

---

You can read more about maze generation algorithms on Wikipedia.