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:
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.
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.
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:
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.
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.
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.
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.
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:
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.
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.
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.
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:
Corridors with a width of 2 look out of place, unless only really large rooms are used
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.
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.
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.
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.
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.
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.
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.