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.