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.