Prefab Room Spacing Issue

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.

Todays subject: Portals

Portals where added as a way to simplify the process of generating corridors between rooms and it worked very well, as long as the rooms themselves had a portal on each side. This design flaw is now making itself very obvious and impedes the progress off creating interesting prefabricated rooms(more on this in a later post) with portals on only one side.
There are a few solutions to this:

  1. Changing the graph generation process to work with the room portals instead of the rooms themselves. This could create a more tightly controlled graph, with the added risk of overlapping rooms.
  2. Adding pathfinding based corridor generation. This would only be used for corridors which is known to overlap a room and would be run after the grid has been created. It would create some new interesting corridors, but at the cost of time. Pathfinding is not cheap.
  3. Adding sanity checks when preforming the graph, or simply having special rules for the graph generation of prefab rooms. A possibility would be to force the creation of a room in conjunction with the prefab room portals.

(P = portal, # = void, F = room)
To the left: a room layout with portals on each side
To the right: a room layout with only portals at the bottom

This image perfectly outlines the current issue with portals. The left room is trying to connect with the prefab room “End”, which only have one portal posibility, which in this case unfortunately is to the right. The end result is a corridor which runs straight through the room and causes mayhem.

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

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.

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

150 rooms – 0.36 seconds total

450 rooms – 5.1 seconds total

1000 rooms – 1 minute 3.6 seconds total

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

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.

Cont. Delaunay Triangulation

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.

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.