There are many algorithms which procedurally create human styled architecture and layouts. They generally operate on a cartesian grid and produce rooms, hallways, walls, and doors which align with the four cardinal directions. While these provide realistic human styled architecture, they quickly become predictable and boring in a video game setting. This blog post will describe an algorithm to create an interesting floor plan. “Interesting” for this exercise will be defined as non-cardinal, non-orthogonal, and semi-unpredictable.
This video is provided for reader visualization: https://www.youtube.com/watch?v=60fbtJmqvNo
Some additional Screenshots showcasing different parameterizations: http://imgur.com/a/sELIk
We start with a set of points on a grid; the example video uses an 11x23 grid. We add variance to the location of the points. “Variance” in our implementation is a value between 0 and 1 where 0 indicates the points are perfectly aligned to a grid and 1 indicates they have moved as much as possible without leaving their initial grid square. The demonstration video animates the variance of the grid from a value of 0 to a value of 0.8.
Next, we generate a Voronoi Mesh between the points. We modified this implementation to return the room indices for the walls that are generated. Constructing the rooms involved some work as there is no information about external walls, and no order to the walls constructed. Additionally, the implementation has small floating point discrepancies between joints which would ideally be an exact match. Once those are taken into account, you can build a list of rooms with solid perimeters.
Using the list of rooms from the previous step, we calculate the area of each room. Small rooms are joined into larger rooms by removing walls between adjacent rooms. A “Room Join Target” parameter is used to measure when rooms are sufficient size. This value is the approximate minimum number of rooms that will be combined when larger rooms are formed. In the example video, the Room Join Target is 6 so 6-10 small rooms tend to get joined into each large room, though the exact number could be smaller or larger. To implement this, we take the average room size and multiply it by the Room Join Target parameter to get a “Target Room Size”. Rooms smaller than Target Room Size can be combined with adjacent rooms as long as they don’t exceed 4x the Target Room Size. Choosing the smallest rooms first we evaluate neighboring rooms. We choose neighbors using a score based system which attempts to maximize walls removed while also trying to select smaller neighbors.
Combining several small rooms can result in very complex geometry with many small walls. The next step combines several smaller walls into fewer longer walls. Longer walls make it easier to place doors in the following step. Reducing wall count also simplifies spacial logic at runtime (e.g. which room is the player currently standing in?)
In this step we simply iterate over all wall joints. If a joint has exactly two walls attached, it is considered for removal. It is reduced if either of two conditions are met, the angle between the joined walls is close to 180° or the joined walls are shorter than the wall join threshold.
Once the walls are simplified, we add doors by iterating the adjacency graph between the rooms. If you use a depth-first search to add doors, you’ll wind up with longer more linear levels. If you use a breadth-first search the starting room will become the hub for the level with adjacent rooms leading to many shallow paths. We dubbed our method a “Random-First Search” due to the fact that it works just like the first two, but the next room to be visited is selected by a random number generator rather than by insertion order. Additionally, there is a “Connectivity” parameter which allows a random chance to open a door to a neighbor which has already been visited -- being careful however, that it is not requeued for visiting again. The “connectivity” used in the example video is 20%. This provides a porous floor plan which the player can navigate with minimal backtracking.
Conclusion: if you're interested in constructing nontraditional floor plans, manipulation of a Voronoi graph is a great place to experiment.