Debugging Part 1

After the conversion to the framework and the modules, the code has been slightly more buggy than it was at the Milestone 2 presentation. That is why last week was spent not only on the conversion process, but also a lot on the subtle art of debugging code. This post will cover the major bugs and issues encountered.

World Space Issues
SkewedResults

The above issue was caused by having several different methods of representing something in world space in various modules. The worst module in this respect was the grid conversion module, which added a predetermined padding on each side in order to avoid overflows and out-of-bounds array fetches. While very useful at first, it only added more issues then it solved and it was eventually removed in favor for more sanity checks when working with the grid.

Graph Reduction Issues

When writing the node graph modules, I decided that all data was to be represented as pointers for simplicity’s sake when working between the different modules. But I forgot to implement a basic copy constructor, which meant that all graphs now where working on a single set of graph data, instead of having their own to work with. This of course only happens when the graph modules where used together with each other and not if they were to be used separately.

Post Milestone 2 – Progress Report

Milestone 2 Presentation

Last Friday(6/2/2015) we had our milestone 2 presentation, where we showcased our prototypes and any relevant documentation and changes we had made to our original plan. After that, we got some feedback and were told to revise our documentation until all the feedback we were given was resolved. I delivered a short presentation where I discussed the research I had done and showcased the current prototype, which thankfully did not crash and worked like intended. Demo and presentation can be found here http://svn.gscept.com/ip15/ip16/public/MS2/
Now we are fully committed to our projects and we may change little to nothing in our plans and time schedules.

Chop code into pieces

This will be mostly be comprised of creating the basic framework and modules for the dungeon generator. In order to do this, the code written for the prototype needs to be chop into smaller, more manageable, modular classes.
NewClasses

Step by step generation

Next, I would like to explore the possibility to preform step-by-step generation, meaning each step of the generation process is done over a number of frames. This will allow for easier debugging and more impressive visual representation of how the generation process works in the future demo.

External Config For Fast Prototyping

Quick update on external config files.
In order to speed up the testing and debugging, I opted to implement an automatic config system early.
This is a very basic system that allows the user to change various settings of the generator without the need to recompile the software over and over again. Another benefit is that the user does not need to restart the software or press any buttons to apply the changes made to the settings file. The software itself keeps an eye on the file and reloads it if the change date is altered. Crude, but functional.

Performance And Bottlenecks

I have been working on this project for just over a week now, trying and testing various algorithms and methods useful to generating a dungeon level. Some of them are faster and more effective than others. This topic meant to discuss the current performance and how it could be improved. This does not mean I have the intention of improving it just yet, that is for a later stage of development. Below are a few pictures taken of a basic performance measuring tool I wrote for the generator. All tests were run using Relative Neighborhood Graphs and making the generator create the most compact dungeon it can by setting room spacing to 1(will be discussed in a later topic).

50 rooms – 47 ms total
Preformance_50rooms

150 rooms – 0.36 seconds total
Preformance_150rooms

450 rooms – 5.1 seconds total
Preformance_450rooms

1000 rooms – 1 minute 3.6 seconds total
Preformance_1000rooms

Finally, a test to generate 10000 rooms was started, but after 2 hours it had yet to finish the first phase of creating the rooms and the layout.
Looking at the results of the measurements and looking at the algorithms I have implemented, I could draw a few conclusions as to what was consuming so much time:

  1. The room layout generator and its random placement nature. The risk of continuously picking rooms that are surrounded by other rooms when generating large amounts of rooms is large. This can be solved using increased room spacing or by improving the random room picking
  2. The Relative Neighborhood Graph algorithm looks at all nodes, instead of just the closest ones that are relevant, thus consuming more than than needed. Sorting rooms by x and y axis could solve this
  3. Minimum Spanning Trees is a greedy algorithm, could look into alternative MST algorithms that are less greedy

Generating Corridors

Next to tackle is generating a set of corridors from the node graph. It was decided that at least two different algorithms are going to be used to do this, the first being a simple L-shape from two points, and the other being the Bresenham’s Line algorithm. Both will generate a set of lists with cells that are considered corridors in the generator. Pictured below is the L-shape method
Corridors_Tech1

At this moment, only the L-shape method has been implemented, and this is because I noticed an immediate issue with the corridor generation. It originates from the center of the room, as all the node graphs do when they are computed. The issue is that the corridor then starts in the middle of a room and ends in the middle of another room. Highly undesirable and can even cause issues at later stages of the generation process. My solution to this problem, is to add portal/corridor anchors to each room, right at the edge where the walls later will be. These anchors will then be used to connect the rooms to each other. Each side of the room will have at least one anchor.

General update on previous posts!

All posts now have some links at the end of them for additional reading on the subjects.

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

Room Placing and Spacing

One issue with the generation process was how to determine where to place the newly generated rooms. Up until now, all rooms where placed randomly, which caused all sorts of problems with overlapping or rooms being to far away from each other. My first idea on how to fix this was from reading this (http://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/). His solution was to generate all rooms very tightly, so that they overlap each other. Then he solved the overlapping with a steering behavior similar to those found in Artificial Intelligence. But I felt it was overly complex. Instead, I wrote my own algorithm, which produces a room layout which is pictured below.
Room_Tech8

The algorithm works like this:

  1. First room that is generated is randomly placed in the world space, does not matter where
  2. When a new room is generated, pick another random room that already exists and is placed in the world
  3. Pick a random angle from this room, and set the distance to the radius of both rooms(old and new)
  4. If no other room occupies the space, the room is placed, otherwise return to step 2
  5. Repeat until all rooms are placed

It has been working well thus far, but it has a few issues which will be fixed in the future and it is poorly optimized for larger sets of rooms(100+).

Cont. Delaunay Triangulation

DelaunayTriangulation2
The Delaunay Triangulation algorithm used in the dungeon generator preforms well in most circumstances, but there are a few exceptions and issues that requires attention. One issue can be seen highlighted in the picture above, where a very shallow triangle has been formed between three exterior points. This is a very undesirable behavior and the triangle is mostly useless. This is a very easy fix, simply check the radius of the circle formed. If the circle’s radius is larger than a predetermined threshold, ignore the triangle without even checking for points.
Another solution, which would be a lot more flexible, would be to look at the average circle radius. When the generation is finished, the algorithm looks for anomalies in the average and removes them, thus avoiding the issues outlined.

DelaunayTriangulation3
Another issue that sometimes occur, though quite rare, is edge overlapping as seen in the picture above. A fix for this is to check every edge for collisions with each other and simply remove one of the two in the case of a collision, but it would be quite expensive to do. More time is needed later on to look into this issue, but so far it will not cause any major issues with the dungeon generator.

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.