Mazes: Removing Dead Ends

Before we dive deeper into the weight assignment for the logical graph, I wanted to take a post to examine the results we get from assigning random weights:

The results are somewhat displeasing, although it is at first difficult to pin down exactly why. I stared at this for a while before figuring it out: there are a lot of dead end rooms (a physical room with only a single logical corridor) which are adjacent to what I will call 'crossroad' rooms (a physical room with three or more logical corridors).

The task of a person solving a maze, in essence, is to start at the start, and progress through the maze until they get to a crossroad, and then, to choose the correct branch. They repeat this until they get to the end of the maze, wherever that may be. Having a dead end right next to its parent branch makes it very easy to rule out an incorrect crossroad choice. Therefore, to make the maze harder, it is desirable to move dead ends as far away from their nearest crossroad as possible.

To get a better sense of the problem, I annotated the above image by marking the dead ends in red, the crossroads in blue, and the rest of the rooms (which have exactly two logical corridors) with green:

After giving it some thought, I discovered that there is a solution to this problem that can be enacted on a local scale (that is, without considering the entire graph). It goes like this: Take two dead-end vertices in the logical graph's spanning tree. Check if they are connected in the logical graph. If they are, then disconnect one of the dead ends from its neighbour and connect it to the other dead end.

Now, there is one subtlety here: the dead end that you disconnect must start out adjacent to a crossroad, in order to guarantee that the algorithm eventually terminates. It is fairly easy to see why. If you disconnect a dead end from a room with two logical corridors, you create a room with one logical corridor; i.e. another dead end. There are some configurations of physical rooms for which this would never terminate: imagine a 2x2 lattice, with a single wall that continually rotates around the center vertex.

To put the rule in more colorful terms: you take a red room, connected to a blue room, disconnect it from its neighbour and connect it to an adjacent red room. The room being connected to turns from red to green, and the room being disconnected from turns from blue to green, or stays blue.

Armed with this restriction, every time you merge two dead ends in this way, you are reducing the number of dead ends by one. It usually takes a few passes before every possible merge is found and performed, but once they are, you get a result that looks like this:

I can then remove the annotations, and compare the original maze (left) with the merged result (right):

I find the merged result to be an improvement over the unmerged result. However, to get really good layouts, we must apply a little bit less randomness to the initial edge weights. We will take a look at that in the next post.