Mazes: Height Map Weighting of Logical Graphs

The wait is over. As an apology for making you wait so long for this post, I am going to put the results first.

Let us say that you have generated the following physical graph to serve as the basis for your maze. I have left out the logical graph; you should hopefully be able to imagine what it would look like by now:

Using the technique I am about to show you to apply edge weights for the logical graph, you can generate results that look like this:

Or, like these:

Or even like these:

The secret turns out to be very straightforward. Start by generating a height map that covers the range of the logical vertices: a function that assigns to each [x,y] point in the range some height value z. Each logical vertex will thus have an associated height value. Then, assign to each edge in the logical graph the absolute value of the difference in height between the two endpoint vertices.

It is worth emphasizing this point: the weight of an edge is not dependent on the height function, but on the difference between two height function values. We are computing a minimum spanning tree, and so edges with lower weights are more likely to be chosen for the spanning tree. The edge weights are lowest when the two endpoints have identical heights. This is NOT the same as the two points being close together: two points that are very far away may have identical height map values.

As an example, consider the first result above. This was created by using the simple height map h(x,y) = x. Note that the edges chosen for the logical graph's minimum spanning tree are mostly vertical, leading to long vertical corridors with very short horizontal steps. This is because, for this height map, an edge's weight is simply the distance in X between the endpoints. Vertical logical edges thus have weights very close to zero.

The second example used the height map h(x,y) = y. Consequently, the 'best' logical edges are those with the change in y being close to zero. The third example uses h(x,y) = x + y, and the fourth uses h(x,y) = x - y. Each graph has a very visible 'grain' to it, which corresponds to the direction in which the derivative of the height function is zero.

The last two results are slightly more interesting. The fifth result uses a height map of the Euclidean distance between that point and the center of the graph. If you were to look at the height map directly, it would look like an inverted cone. The sixth result uses a height map of the Manhattan distance between that point and the center of the graph: this height map would look like an inverted square pyramid. The two resulting mazes look very similar, although the left result is more round in shape as compared to the square result on the right.

Another way to think about this process is to imagine a lazy person, such as myself. I prefer to walk along level surfaces. It is tiring to try and climb a hill, and I might fall and hurt myself if I walk down a hill. The height map will thus determine which corridors are chosen for the maze by preferring those edges which minimize the amount of climbing or falling I would have to do. The best lines (the lines with zero weight) are those with identical heights at either end. Cartographers would refer to these lines as 'contour lines'.

You can also get some interesting results by taking the negation of the absolute value of the height difference. This flips everything on its head, making contour lines the worst choice for the minimum spanning tree. For an example, compare the Euclidean height map example above (left), with the negated weighting result (right):

It is a bit hard to see in these results because they are not very large, but on the left, the edges with the smallest weight travel in circles around the central point, whereas on the right, edges with the smallest weight extend radially outwards from the central point.

The use of a height map can be combined with the eariler technique of splitting logical vertices into 'regions', and greatly increasing the weights of edges that connect two regions, as in this example:

I have highlighted the region boundaries, since they are much more difficult to see in a random graph as opposed to a lattice graph.

You can also freely intermingle the two techniques. For example, select a bunch of regions and assign huge weights to edges between them, but for each region, use the height map technique with a different height map for each region. The sky is the limit.

I seem to recall previously taking a blog holiday because of the amount of labour involved in producing all of the required images. Thankfully all of these images are computer-generated.

Mazes: Irregular Physical Graphs

I lied in the last post: I have one more interlude post before we can dig into the details of weighting the maze logical graph.

So far, we have been using a square lattice for our physical graph, which gives rise to another square lattice for its logical graph. This works well for showing off the theory of finding a spanning tree of the logical graph, but it provides very little interesting detail for assigning edge weights to the logical graph, such as varying-length logical edges and varying number of edges incident to each logical vertex.

What we would like is to generate a random graph, compute its dual, and use this as the input to our mazes. How would we do this, programatically? One way is to run Fortune's algorithm on a set of random points. Recall that the output Voronoi diagram and Delaunay Triangulation are duals, so we can pick one to use as the physical graph and the other as the logical graph. I happen to like using the Voronoi diagram as the physical graph, as the Delaunay triangulation is composed of triangles (by definition), making for very jagged wall layouts if used as the physical graph.

There is one problem to solve with this approach: recall that due to the 179 degree problem, the Voronoi diagram of an input point set can extend far beyond the range of the initial points. For example, consider the following Voronoi diagram (purple) and Delaunay triangulation (green). The green graph spans a range of only 100 units, while the Voronoi diagram is over 50,000 units tall! As a matter of fact, the Delaunay triangulation is so small it doesn't even appear in the image.

In another post, I explored how to constrain a random point set so that its Voronoi diagram would be bounded. In playing with this result, I found it unsatisfactory, since the Voronoi cells along the boundary of the diagram regularly came out far larger than the interior cells.

To solve this, I came up with a better approach, which is to take the original output above, and simply throw out the Voronoi cells which extend outside the input data range. To be specific, you can follow these steps:

• Generate a Voronoi diagram and Delaunay Triangulation of a random point set.
• Determine the faces of these graphs (identify which vertices in the physical graph are part of edges of each face corresponding to a logical vertex, and vice versa).
• Throw out all logical vertices whose face has at least one physical vertex that is outside of bounds.
• Throw out all physical vertices whose face is made up entirely of logical vertices that were removed by the previous step.

If you apply this result to the graph above, you get this graph, which looks much better as a source for a maze:

This technique is very general. It only requires each physical vertex to be classifiable as 'in bounds' or 'out of bounds'. For example, with a suitable selection of classification, you can make a ring shape:

Tune in next time, where I will FINALLY assign some interesting weights to these logical graphs and show off the results.

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.

Mazes: Weighting The Logical Graph

Last time, we saw how to use the spanning tree of the logical graph to select which physical edges to use for our mazes. We also saw that not all spanning trees give good results.

As mentioned in the last post, Prim's algorithm and Kruskal's algorithm can be used to find a spanning tree for a graph, but if we apply it to our lattice grids, we get a very un-mazelike result:

What is happening here? These algorithms find a specific spanning tree: the minimum spanning tree. That is, of all possible spanning trees, they will select one of the ones with the lowest possible edge weight sum^[1]. For our lattice grid, each edge has the same length, and thus, the output of the algorithm turns out to depend only on the initial vertex selected and the order that edges are added to and removed from a priority queue maintained by the algorithm.

The weight of an edge is not required to be its Euclidean length, however. We can immediately get better results if we simply assign a random value as the weight of each edge. The resulting minimum spanning tree will give us a much more winding result:

We can achieve a lot of interesting effects with clever selection of logical edge weights; more than a single blog post can contain. As one example, start by assigning a random weight between zero and nine inclusive to each edge of a lattice grid. Then, take two lines that split the square lattice in half horizontally and vertically. Any logical edge that crosses one of these two splitting lines has its weight increased by ten.

The result looks like this:

We have created a maze where each 'component' of the original lattice (based on the splitting lines) is self-contained, and only connected to the others by the minimum number of edges required to ensure that the logical graph is spanned. One immediate video game application of this technique is to make each component its own 'biome', for example, each component might be a swamp, a forest, a desert, a mountain, or an ocean, and players can only cross between biomes at a single location, where your maze generator would place boss monsters.

Tune in next time where we look at more advanced strategies for assigning weights to our logical graphs.

---

[1] It is worth noting that there may be multiple spanning trees for a given graph with a minimal edge weighting.

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.

Mazes: Preliminary Theory

The first step to generating a maze is to define it. What is a maze? I personally conceptualize a maze as a collection of rooms, with passageways between them, as in the following image:

Under such a concept, we can generate a maze by first generating a collection of unconnected rooms, and then generating passageways between them. Generating a set of rooms is straightforward. You can use any planar graph, such as the following regular lattice, and then every face^[1] will serve as a room:

We will refer to such a planar graph the 'physical' graph, for reasons that will soon become apparent. In the physical graph, each face is a room, and each edge is a wall.

Now that we have the rooms, how can we decide how to connect the rooms together?

Students of graph theory know that any planar graph has what is known as a dual graph, which is another graph containing a vertex for every face in the original graph. Each of the dual vertices is connected by an edge if the corresponding faces in the original graph share a common edge. This turns out to result in each vertex of the original graph to correspond to a face of its dual graph.

A picture is worth a thousand words, so here is the dual graph of the lattice above:

We will refer to the dual of the physical graph as the 'logical' graph. In the logical graph, each vertex is a room, and each edge will be referred to as a corridor. Note that for physical-logical dual graphs, each physical room is paired with a logical room, and each edge in the physical graph has a twin in the logical graph^[2].

There is a natural tension between the phycial and logical graphs. If there is a corridor connecting two rooms in the logical graph, then a player can navigate between the two rooms. However, if there is an wall between two rooms in the physical graph, then a player cannot navigate between the two rooms^[3]. By the Law of Excluded Middle, a player either can or cannot directly navigate between the two rooms. Consequently, a physical wall and its logical corridor cannot both exist simultaneously, and one must be removed.

The application of this strategy is to select among the physical/logical dual edges, keeping some as walls, and others as corridors. If you choose wisely, the resulting physical graph will form a maze:

In the next post, we will look at the wisdom behind the choice of wall or corridor.

---

[1] Pedants of graph theory will note that I have ignored the 'unbounded' face of the graph. This blog series will only be concerned with the bounded faces of the planar graph.

[2] Except, per note [1], that the physical edges of the unbounded face do not have duals in the logical graph, because the logical graph does not contain a vertex corresponding to the unbounded face.

[3] They cannot navigate directly. They should be able to find some path between the two rooms by passing through other intermediate rooms.

Mazes: Introduction

After a long hiatus for summer, I have another blog series for you. This one shall cover programmatic generation of random mazes. These mazes would be suitable for printing and solving by hand, or as the terrain for some dungeon-crawling top-down loot-em-up.

Some readers have complained that my posts tend to be a bit difficult to follow, as I leave the pay-off to the end. To get around this, I will start out by showing the results we will eventually be able to get to. In the image below, find the path between the four corners.

Stay tuned to find out how to generate such an image in code.