Mazes: Logical Graphs and Spanning Trees

Last time, we introduced the physical and logical graphs of a maze, and showed how we can build one by taking dual pairs of edges in the graph, and removing one edge in each pair from its associated graph.

This time, we explore how to decide which edge in the pair to remove. To begin, we observe that there is a non-trivial amount of decision making required, as selecting each edge at random can lead to unsatisfactory results:

There are two problems with the maze above. First, the maze contains loops. (This may or may not be a problem for your application, but I personally prefer my mazes to be loop-free.) Second, and more importantly, the maze is not completely connected. There is a set of rooms on the right that cannot be reached from the rooms on the left.

The key to solving both of these problems lies in the logical graph. If there is an edge in this graph, it means that the corresponding maze rooms are connected. Going further, if there is a path in this graph, it means that the corresponding maze rooms at either end of the path can be reached from one another. Logically, this graph captures the traversability of the maze; hence its name.

The looping problem above occurs when there is more than one distinct path between two vertices in the logical graph. Hence, we want to enforce the requirement that there is at most one distinct path between any two logical vertices.

The disconnection problem above occurs when there is no path between two vertices in the logical graph. Hence, we want to enforce the requirement that there is at least one distinct path between any two logical vertices.

Combining these requirements means that we want to enforce the requirement that there is exactly one distinct path between any two vertices in the logical graph. In graph theory, such a graph is called a tree. For a graph that is not a tree, you can find a spanning tree: a subgraph which is a tree.

We therefore have a solution to our maze generating problem:

1. Produce a physical graph
2. Derive from it a logical graph
3. Find a spanning tree for the logical graph

We then keep the spanning tree edges in the logical graph (and remove their dual edges from the physical graph), and discard the remaining logical edges. The problem of finding a spanning tree of a graph is a well-studied problem in computer science, and there are several efficient algorithms to do so (the most famous being the algorithms of Kruskal and Prim).

The completed maze from the previous post was an example of a spanning-tree logical graph:

It turns out that this approach is not exactly what we are looking for, although it is a good first start. The problem is that 'require the logical graph to be a spanning tree' is too weak of a requirement; there are usually spanning trees of the logical graph which give poor results. To give an example of the problem, observe the following 'maze'. It has a correct spanning tree, but I would not call it a maze:

In the next post, we will look in greater depth at finding spanning trees for the logical graph that will give us better results.