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.
No comments:
Post a Comment