Decisions, Decisions, Decisions….

My original goal with the project was to eventually make a small, but functional demo game in Unity3D using the random dungeon generator. As it stands now, this will most likely not be the case. Time estimation for a project is a difficult task and takes quite a lot of practice to become adept at. Working with the project and getting the framework and all the base modules working properly with each other required far more time then was estimated at the start of the project.
The main focus was always to make a functional, modular and expandable dungeon generator framework, that later on could be usable in various other game projects. That has thus far been successful, even if the framework still needs a lot of work and polish. The project was, in the end, a very large undertaking and it would realistically have needed at least two more developers working on it to finish within a reasonable time frame.
To summarize:

  • No demo game
  • More focus on working framework
  • Time estimation is hard and requires practice

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.

Prefabricated rooms

Just a quick update on prefabricated rooms. A basic version is fully implemented and functioning, with support for the following:

  1. Layout controll, set distance to other rooms, placement modes and various other settings
  2. Predetermined room structure and layout, which can create for some very interesting rooms created by the developer

It has resulted in more varied dungeons that feel and look more dynamic. Screenshot below shows how one rooms has a very large room radius, which forces new rooms to be further away from it.
PrefabRooms

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.

RoomLayoutFile1RoomLayoutFile2
(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

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

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

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!
3D_Dungeon1
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.
OldBresenham
FixedBresenham

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.
CavesUsingCorridors
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.
RNG_Graphs
RNG_Graphs2

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