Major Progress Update

Wall generation issues

One issue that continually impedes the progress of the dungeon generator is the problem of generating walls. There are a lot of ways to do wall generation, but most of them use some form a grid format that is a huge time and memory sink, especially at larger dungeon sizes. This type of generation does not scale well and is not very flexible. A solution to this major issue should be researched and tested.

Step by step generation video

Rooms – Design, Layouts and Randomization

The room system thus far has been very basic and not very flexible. It only supports square rooms, with a portal on each side which is randomly placed. It works for debugging purposes, but now that most of the basic systems are functional and stable, it isn’t good enough. It needs an upgrade!

Here is a flowchart of the newly designed system to be implemented.

The room generation process simply handles the sub modules, which each handle the actual room generation and placement. There are 3 different types of rooms:

  1. Prefabricated (or prefab for short) rooms that have the exact same size, layout and design every time it is created. Very useful for spawn locations, or important rooms to the game plot.
  2. Ruleset rooms. These rooms are created out of a set of rules, which is defined by the sub module itself. These room have a semi random nature, where the room can look similar, but never identical. Layout, placement and size can differ.
  3. Random rooms. These rooms are completely random and have no real rules that define what they are supposed to be or what they should look like. They are usually empty and mostly used as junctions in the dungeon landscape. Oh, and usually filled with enemies!

This new system is estimated to be finished by Wednesday next week, with decor being the next target to tackle.

3D Dungeons And Fixed Corridors

Today has been spent trying to visualize the dungeon generation in 3D space. It is still very rough and only meant to get a peak at what the dungeons would look like further down the road. It will also make it easier to work on room decor and other similar systems that needs to be implemented. Disregard any and all graphical artifacts!
A few remarks where made when viewing the dungeon in 3D:

  1. Corridors with a width of 2 look out of place, unless only really large rooms are used
  2. A good way of determining what the game should render is a good idea. This will probably be some sort of algorithm where it renders 1 or 2 rooms away in the graph, including any connecting corridors.
  3. A wall generation process that creates internal walls between rooms and corridors, otherwise portals are useless

Another issue that was worked upon today was that when using a corridor width of 1, the corridors created using Bresenham’s line algorithm are disconnected and creates corridors that are incomplete. To sort this out, it protrudes the last added cell so that it actually connects with the newly added cell. The difference can be seen in the screenshots below.

Generating Caves By Accident?

The interesting aspect of creating highly modular, adaptive code is that you can mess around with different settings and setups to create something that was not intended. Here is a perfect example of this, generating caves by simply tweeking some settings in the generation process. In this case, the corridor width was set to a very high number, which caused what you see in the screenshot below.
How this is used is then up to the developer, by adding specific room modules that are more oriented to cave designs (e.g. that the rooms most likely won’t have any walls).

Relative Neighborhood Graphs And Corridors

The Relative Neighborhood Graph algorithm has proven itself to create some very interesting and useful graphs for the corridor algorithm to use. The graph is highly usable, even without the use of a Minimum Spanning Tree to reduce the amount of edges. Below are some screenshots of what the graph has resulted in. The final version will most likely use this graph, as it is fast and creates credible corridors in the dungeon.

A new type of corridor generation was also implemented, Bresenham’s line plotting algorithm. This one allows for more straight path corridors, as is outlined by the screenshot below. A combination of both Bresenham’s and L-shapes is now used to created even more varied corridors.

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.

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
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.

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

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.