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 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).
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.
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:
- 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
- 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
- Minimum Spanning Trees is a greedy algorithm, could look into alternative MST algorithms that are less greedy
If you are a programmer like me, you most likely aren’t very good at working with 3D graphics and modelling. I have however found a solution that works great for making simple models in rapid prototyping purposes.
The software is called Qubicle 2 and is a type of voxelbased 3D modelling software. It is easy to use and makes usable block models fast, perfect for someone like me. Down below is a render of a test model, which took 10 minutes to make, including some poking around and testing.
And here is said model loaded into Unity3D.
Qubicle will be used to create various miscellaneous models, such as tables, doorways, items, pickups and so on.