Hi! My name is Tom Liebmann, I'm living in Bitterfeld (Germany) and study computer science (master degree) in Leipzig (surprisingly also in Germany). In my freetime I like to program mostly in C++ and therefore I use IndieDB to share some of my experiences in game-development.
In the last couple of weeks I did not do much development stuff for the game. I just fixed some bugs, improved my compilation process and switched from SDL1.2 to SDL2, which still needs some further adjustment.
Two things I also did were some improvements to dungeon generation and first attempts to render items.
There are also a lot of things I already did which I never mentioned here in the blog. The reason for that is that I plan to do bigger posts about each of the topics, but this takes a lot of effort which I currently can't put into the blog. Some of these topics are:
To break the silence of my blog I decided to just run the current game and take a simple screenshot, no matter how boring and senseless the scene looks.
I may come up with a more precise and detailed post about the current state later on.
In my last post about the topic of randomly generated dungeons I wrote about my first approach to reach the goal of nice looking levels. These levels contained rooms connected by a set of corridors using a perfect maze.
Main disadvantages of this method were the strong constrains on the shape of the rooms, big gaps between rooms and therefore long corridors and the unbounded calculation time. To overcome these issues I've revamped the whole generation process.
To provide a huge amount of flexibility and to not limit the shape of the rooms to anything I've divided the room placement step into two phases.
In the first phase the properties of all rooms of the dungeon get calculated. At the current state only one starting and one end room along with a couple of simple rectangular empty rooms are present but I plan to add a lot of different room types with different events (e.g. bossfights) to the game.
All these rooms are then put into the same location on a map.
Putting all the rooms into one place of course results in a huge amount of overlapping parts. To resolve this the algorithm in the second phase slightly moves every room iteratively a bit in the direction, in which the most intersections get solved. After a definitively finite amount of time all room-to-room collisions get resolved and I have a good disjunct room placement.
The space between rooms can even be specified by simply creating an imaginary border around the walls so that the virtual room size in the moving process is bigger than the actual room itself.
There are still some problems with this approach which still persist and need to be solved. One big issue is the so called granular convection which results in small rooms staying in the center while bigger rooms tend to move to the outer regions of the map. I have some ideas how to solve this but I still need to verify these and try things out.
For corridor creation I've come up with an algorithm which is a mixture of some sort of flood filling paired with randomness. After placing every room on a map, there are a couple of points corridors can attach to. Starting at one of those points, the underlying map grid gets filled remembering the source direction. Everytime the filling process reaches another attachment point, a corridor along the traveled path gets created.
To provide some kind of randomness and to not create only perfect short corridors, I use some weights to negatively manipulate the traversal.
Of course there are a lot more details in this algorithm but I don't know, whether you are interested in this. I don't want to bore you with that fine-grained stuff. Instead I'll show you some pictures of the resulting dungeons I took some months ago.
As always I am still not that happy with the generation. For now I think the quality of the resulting dungeons is good enough but I am pretty sure that I will rebuild the whole generator sometime. I still want more control over the corridors. I want to create loops, deadends and branching corridors and the current generator is not really capable of doing those things.
I already have an idea how to further improve the system and maybe there will be a "Dungeon generation #03" soon.
About 5 months ago I posted my last entry but I am still working on the project more than ever before.
The lack of blog posts was/is due to different reasons mainly including problems to find the right words to explain different aspects of the development stages I were in.
In this short post I only want to show that I did not quit this and plan to give new information in the near future.
Topics will then be among others:
Thank you for reading!
My last blog-post is more than one week ago and that's way too long! This period is caused by me being busy fixing bugs and tweaking some details of the following topic.
When I first thought about random dungeon generation I had no idea how complicated it will be figuring out an appropriate algorithm to meet my requirements.
The first question is: What does a typically dungeon consist of?
All my approaches use the idea that a dungeon is simply a set of rooms of different sizes and shapes which are connected by corridors. Therefore the big problem of dungeon-generation splits into the two essential parts of room-placement and connecting these rooms in a natural and plausible manner.
To solve the problem of room-placement I decided to use a very simple approach at first. So I took an empty map with fixed width and height and threw a room with random size at it (of course this is meant metaphoric... I can't throw rooms, especially not of random size). After placing a second room randomly I simply check, whether it intersects the first one and if it does, I simply redo the placement.
This process got repeatet until there were enough rooms.
To connect the existing rooms I then generated a perfect maze.
A perfect maze is called perfect because of the fact that every point in the maze has exactly one path to every other point. Because I needed to connect all rooms in a way I can reach every room starting at a certain position I thought this kind of maze could be useful.
The generation of such a maze is very simple and can be implemented using a small depth-first-search-method with a few tweaks.
The main idea then was to simply merge the map containing the rooms with the one containing the generated maze. To do this I needed to add the following two limitations to the room-placement:
The reason for this is that I don't want rooms to directly lie next to a parallel passing corridor.
With this technique I was able to create nice looking dungeons like the one shown on the following picture:
But as you might already see, because of the underlying maze these are very difficult dungeons. So I started thinking about an algorithm to reduce the amount of deadends and redundant corridors and I came up with a method which does exactly this.
Based on the already generated dungeon the algorithm first builds a graph and computes the minmal spanning tree. Then all unused edges are removed and the result is a dungeon with perfectly connected rooms. After making the algorithm a little dumber I was also able to control the difficulty.
The advantages of this method are evidently. It is simple, creates nice looking dungeons and can be scaled to huge maps.
But there are some disadvantages too which caused me to find another, better and much more complicated method. These disadvantages are among others:
In order to make this post not too long I decided to split the topic of dungeon generation up into multiple parts. So my next post will be about how to overcome the issues in the first approach.
Today I want to tell you what I'm currently working on and what the next steps in the development of my dungeon-game will be.
As I already said, I have made a prototype a few months ago. Included were mainly graphical and physical tests and some attempts to generate good looking dungeons.
But as usual for prototyping my code was ugly and not flexible enough to build upon it.
Therefore I started working on the proper version of the game a few weeks ago and now I'm at a point having the following features:
Most of them will sound quite boring to you but it is very important to have a solid base to build on.
My current goal is still to achieve the same functionality as in my prototype, so more graphical improvements, a particle-system and the lighting system are needed.
Talking about lighting-system, I am currently focusing on a rendering technique called "deferred shading". It allows me to render as many lights in the scene as I want without big loss of performance. To summarize this shortly:
Sorry for my bad explanation-skills but if you really want to learn more about that, simply google it.
The result of using this technique is, that the complexity of rendering lights turns from O(n * k) to
O(n + k), where n is the number of objects and k the number of light sources.
And for the more visual people I have a screenshot:
Here you can see the different textures I'm rendering the scene to. In the top left there is the diffuse-component, in the bottom left corner you can see the position of each rendered pixel encoded to simple RGB-values and in the bottom right there are the normals.
Some insiders might already have noticed that I am also using bump-mapping for better details and more realistic lighting.
That's it for now! I think my next post will be about how I (plan to/already) generate random dungeons.
This is my first post on IndieDB but I hope that there are many following.
At first let me introduce myself. My name is Tom and I live and study in germany. Early this year I got my bachelor's degree in computer science and currently the main attention is on my master study.
I'm programming since I was 10 years old (started with QBasic) and therefore it was clear to me, that I want to spend my life doing such things.
This kind of blogging is totally new to me and I hope to create posts regularly.
To realize that it is of course necessary to have a topic to write about and as you might already have deduced from the site I'm writing on that this topic is a game I'm currently working on.
So here we are. After some boring sentences about me and my motives let's come to the more interesting part:
My current game is a 3D-dungeon-crawler in which (in the current idea) the main goal is to level up and to get deeper and deeper.
I love games without ending and with procedural generated things so that the experience is different everytime you play and therefore this will be my main goal.
Based on SDL and OpenGL I write the whole engine by myself and therefore it is a huge amount of work to even do simple things.
I've already developed a small prototype (mainly for graphical testing purposes) and a very few pictures of that can be found on my twitter-account. Maybe I'll share more of that in some upcoming writings.
My progress is kind of slow because I only work on this in my free time but I hope it is fast enough to create new posts from time to time.