Maze generation given intersection tree

Question

Background Information: I'm building a 2D maze generator. I have tried Prim's algorithm, Wilson's algorithm, and a recursive backtracker algorithm for generating my maze, however was not satisfied with the difficulty of any. I have decided to create my own. I decided that two things make a maze hard. First, mazes can have lots of intersections and choices to make. Second, they can be disorienting and cause you to lose your way. I decided to create a tree to represent the intersections and dead ends in a maze and connect each node in the tree with a randomly generated path to disorient users.

The problem: If I begin to generate the cells in the maze for the tree, I may find that a node doesn't have the room it needs to connect to or create its children. How do I fix or avoid this problem?

My Thoughts: There seems like there might be a way to do this by dividing the maze into sections and subdividing them, but that still doesn't guarantee enough room at the end of the division. I could also try to start small and work my way up, sectioning off smaller areas and then creating connections between them, but that could still run into pathing issues with not having enough room to connect the sections together or even creating really long paths between sections.

I am using a hexagonal grid, but any solution you guys come up for rectangular grids should be easy to transfer to a hexagonal one.

I wasn't sure if this should be posted in the theoretical computer science section or here, and opted for the more general one.

Answer 1

There are many maze descriptions in the wikipedia article maze generation algorithm, but I'm going to describe one that works for any shape maze with any number of dimensions.

1. You start off giving each room room in the maze a distinct number.
2. You then find the set of all walls between the rooms that have different numbers on either side.
3. From this set, you select a random wall and remove it.
4. For the two rooms on either side, you change all rooms with the higher number value to the lower number value.
5. Repeat steps 2-4 until all rooms have the same (lowest) value.

This works for 2 or 3 dimensional mazes (never tried 4, but I see no reason why it wouldn't) and for rectangular and hexagonal mazes (but could also be irregular shapes too - nothing in there dictates the shape, number of adjacent walls, or even that each room is the same).

It will generate a maze that has a one path from any two points and only one path (there are no loops). Aesthetically, I like the mazes generated by it as I find some of the others lead to either long walls or long corridors.

---

An example of this maze generation on a 3x3 square maze:

+---+---+---+
|   +   +   |
| 0 a 1 b 2 |
|   +   +   |
++c+-+d+-+e++
|   +   +   |
| 3 f 4 g 5 |
|   +   +   |
++h+-+i+-+j++
|   +   +   |
| 6 k 7 l 9 |
|   +   +   |
+---+---+---+

At the start, the set of walls is abcdefghijkl. You pick a random wall, lets say 'd'. The maze then becomes:

+---+---+---+
|   +   +   |
| 0 a 1 b 2 |
|   +   +   |
++c++   ++e++
|   +   +   |
| 3 f 1 g 5 |
|   +   +   |
++h+-+i+-+j++
|   +   +   |
| 6 k 7 l 9 |
|   +   +   |
+---+---+---+

The set of walls is now abcefghijkl. After two more steps, for walls b and g, the maze is:

+---+-------+
|   +       |
| 0 a 1   1 |
|   +       |
++c++   ++e++
|   +       |
| 3 f 1   1 |
|   +       |
++h+-+i+++j++
|   +   +   |
| 6 k 7 l 9 |
|   +   +   |
+---+---+---+

Note that now, since e has a 1 on each side, it is no longer a candidate in the set of walls that can be removed.