Prefab Room Spacing Issue

LayoutIssue
An issue with the new prefab room system is clearly seen in the screenshot above. The two prefab rooms have a connected relation, where one is placed at a predetermined distance from the other using a random angle. While it works really well in most cases to create dungeons with consistent start/end rooms (or similar layouts), it also causes some issues sometimes, where there is a lack of rooms between them due to the random nature of the algorithms used.
I came up with the following solutions to combat this problem:

  1. Placing a few rooms along a straight line between the two rooms and adding a slight deviation so the rooms do not line up perfectly. Since the distance between the two rooms is constant, a set amount of rooms can be created and spaced roughly equally along said line.
  2. Placing a few rooms within a circle (or even better, an ellipsoid) that is based upon the two rooms. Same as above, the distance is constant, thus a set amount of rooms can be created.

As a side note, long diagonal corridors look really ugly and would probably appear as confusing to the player, especially in first person perspective. Long corridors should probably use L-shapes or even insert a new room somewhere along it to break up the length.

Alternate Graph Generators

After some research and testing, I found two new graph generating algorithms that now have been implemented and added to Yggdrasil. They all work in a similar manner, yet still produce vastly different results. Below is a description of the two new algorithms and some comparison screenshots.

Gabriel Graphs

Graph_Gabriel
A Gabriel graph is constructed in a similar manner to Delaunay Triangulation, yet more scaled down. It only uses two points to calculate a circle and uses that information in exactly same way as Delaunay Triangulation does to determine if a triangle works or not. Only, in this case it only results in a single edge, instead of a triangle. This seems to reduce the risk of overlapping edges and creates some interesting connections, as can be seen in the picture above.

Relative Neighborhood Graphs (RNG)

Graph_RelativeNeighborhood
A Relative Neighborhood Graph also works in a similar fashion to Delaunay Triangulation and like the Gabriel graph, it simply uses two points instead of three. The main difference between a Gabriel graph and a RNG is how they determine if a point is invalid. The RNG method ensures that the two points are closer to each other than any other point. From testing, this always results in a complete dungeon, without any risk of segmentation (unlike the two above, but the risk is still very low). It also generates a graph that barely requires the Minimum Spanning Tree algorithm and can be used directly after it finishes. When generating 100 rooms, only 25% of the edges are removed by the MST on average. Compare this too 50% of all edges on average from a Gabriel Graph and almost 70% of all edges on average from Delaunay Triangulation.

All of these methods are equally useful and can serve their own purpose and have their own use cases. Depending on what is required by the game creator, any one of them could be used.

http://en.wikipedia.org/wiki/Gabriel_graph
http://en.wikipedia.org/wiki/Relative_neighborhood_graph

Take 2 – New design, Gaussian Distribution and Delaunay Triangulation

After much thought and consideration, it was decided that the current design for the procedural generation system was not good enough, nor was it flexible enough to fit the requirements outlined by the project plan and design. Here is a very rough overview of how the new system will function. The flowchart is still a work in progress and will most likely change during the progress of the project, but the core is finished. It also omits steps such as decor for practical reasons, but they are included.
NewIdeaFlow

To achieve this new design, a more robust and predictable random number generator was needed. After some research, it landed upon a variation of Normal Distribution (also called Gaussian Distribution). A random uniform number between [-1, 1] is generated and feed into the algorithm and a distributed random number is returned. See the images down below for some examples of what the results can look like when this is repeated a few thousands of times. The “Marsaglia polar” method is used to preform a Normal Distribution computationally.
GaussianRandom1
GaussianRandom2
GaussianRandom3

The data generated from the Gaussian Distribution can then be used to more uniformly generate rooms of various sizes. For example, the curve could be divided into sections, where each section represent a predetermined size for the room. Thus, there could be a larger chance to create a small room, and a smaller chance to generate a larger room. This could have been done using normal random number generation as well, but the results would not be near as predictable as this method.
IntervalRandom1
IntervalRandom2

Now that the rooms have been generated using Gaussian Distribution, they need to be connected to each other in order to create a node graph. This node graph will later be used to generate corridors to connect these rooms. There are a few requirements that need to be meet for the rooms to be connected properly:

  1. The node graph segments cannot cross each other
  2. All rooms must have at least 1 neighbor in the graph

To achieve this, a algorithm called Delaunay Triangulation is used. There are quite a few variations of the algorithm, but it was decided upon a fairly simple to implement method. A circle is formed by choosing three different points and preforming some basic geometry calculations. Then a check is preformed to see if any of the other points is within the circle. If no points are found, a triangle is formed between the three points and they are connected to each other in a graph. If a point is found, it skips and tries three new points. This is done until all points have been tested. The results can be seen in the picture below. This method is however not without flaws. Certain issues can arise that will generated overlapping edges. The most probable reason for this is imprecision in the checks.
DelaunayTriangulation

http://en.wikipedia.org/wiki/Normal_distribution
http://en.wikipedia.org/wiki/Delaunay_triangulation

Layout and graph generation

The goal for this week is to be able to generate a dungeon, with rooms and corridors, that has a sensible layout.

Firstly, I tried to generate a layout using Binary Space Partitioning(BSP). It creates a large cell, and splits this cell down into a tree-like structure, until a specific condition is met. In this case, the condition is cell size. If a cell is to small to be split, it stops. Eventually, this condition is met in all cells and the splitting stops in the entire tree, thus marking the end of the layout generation. The results is a layout with many smaller rooms, but a general lack of larger ones. This can be seen in the picture below. This isn’t a very good way of generating interesting layouts for the dungeon, so alterations are in order.
Layout tech test 1

Adding some additional conditions in the decision between vertical and horizontal splitting does improve the layout slightly, but it still feels out of place. Another issue that I have started to notice, is a clear pattern or repetition in the layouts. This can clearly be seen in the picture below. While the layout does not represent the final rooms that will be generated, I still feel the need to look into it. Optionally, I could go for another approach to generating the layout.
Layout tech test 2

Secondly, after the layout has been generated, we need to connect the individual layout cells to each other in order to create corridors. The are several ways to do this, the easiest being to use the existing structure of the BSP tree that was generated. The drawback to this is that the resulting node graph will be non-looping, meaning no matter what direction you take, you will find an end. It could be used directly to generate corridors, but it would not allow for further generation options.
Another option is to preform a polygonal edge-edge test between all the node cells. This will create large node graph of neighbors for each cell. This is however, a very CPU intensive algorithm, and does not scale well with larger amounts of cells. This due to the fact that all cells need to check all other cells. We could take advantage of the fact that the layout still has the BSP tree structure, but that is a future topic.
The resulting node graph from the edge testing is still not very usable to generate corridors. It would more or less connect all the rooms to each other, allowing the player easily traverse the map(see the picture below for a visual representation). The node graph needs to be trimmed into something more usable. Prim’s Algorithm is perfect for this, as it is a Minimum Spanning Tree(MST) algorithm. A MST is the graph that connects all the nodes with the lowest edge weights in a larger node graph(for more information, see http://en.wikipedia.org/wiki/Minimum_spanning_tree). The difference can be seen in the picture below. This new graph could now be used to generate corridors to connect the rooms and it would look OK.
Layout Tech Test 2

As you might have noticed in the picture above, the edge testing is not perfect. It is very picky that the edges must be a perfect match in order to be considered connecting. While not a problem due to the nature of the BSP tree generation, it does cause some unwanted behavior. A fix for this will be updated at a later time.