I scrapped the online algorithm and opted for an offline algorithm instead. I also got rid of the template system, because it is not very flexible. The new algorithm uses a room partitioning strategy to create a bunch of rooms first and then connects them with corridors. The dungeons created in this manner are a lot more interesting and unpredictable.
At first, I tried using a Quadtree to create the rooms. The problem with that was that if you increased the randomness, the algorithm would result in rather elongate rooms (see the example image below). This is due to the fact that when dividing a long rectangle into four, then one ends up with at least two smaller rectangles that are longish. I wanted to have rooms that are almost square, so I tried a different strategy.
Quadtree room partition, leading to elongate rooms
The next thing I tried was a BSP-like approach. Instead of splitting the rooms in four, I only split them in two. The axis was chosen depending on the ratio of the sides which leads to the kinds of rooms I wanted. To connect the rooms, the algorithm starts at the root of the tree and connects from its "splitpoint" (the center of the axis where the room was divided) to the splitpoint of its two children. These children will then connect to theirs and so on. Leaves (which don't have a splitpoint) are connected using their centers. This approach guarantees that every room will be connected. It also makes sure that there are no unwanted intersections between rooms and corridors or corridors and corridors. It didn't quite work for the example image below, but it has been fixed in the final version (see the last image).
Dungeon created using BSP
The BSP-approach worked pretty well, but due to its binary nature, it would only create one corridor per partition. From a gameplay perspective, this would lead to a lot of backtracking which is rather undesirable. To solve this problem, I tried to combine the benefits of both approaches using a hybrid tree. Rooms will usually be split in four, so you'd have many corridors to choose from. If the algorithm encounters an elongate room, it will use only one axis to split it in half. Connecting the rooms works the same as before.
Dungeon created using the Hybridtree
And here is a video of how it looks ingame:
The next step in terms of random dungeon generation would be an algorithm that fills the rooms with life. But before doing that, I might have a look at networking instead. It's always a good idea to incorporate network code at an early stage of development.
In this Dev-blog, we will share the progress of our first game.
This game can be described as a cooperative real-time roguelike with rts elements. It's yet to be decided how much "roguelike" the game will be, but it will definitely be some sort of dungeon crawler. Imagine Brütal Legend meets Diablo.
The "team" currently consists of two people, moppele and myself. I will do all the coding and moppele will provide ideas for gameplay mechanics and help with problem solving. Due to the absence of a decent artist, I will also be responsible for all the textures and animations. Here is a screenshot, of what the game could look like:
Mockup of a dungeon
Random levels are one of the most important parts of a dungeon crawler, especially in terms of replayability. That's why I started to develop algorithms for random level generation. The first thing I tried was using an online algorithm based on room templates. This algorithm has several advantages. For one, it is very easy to code, extensible and having room templates allows for a lot of artistic freedom. It also allows to have dynamically changing difficulty and stuff like that. But there are also downsides. It is very hard to control the behaviour of the algorithm and having different types of connections between the rooms is also not an easy thing to do. You also have to provide lots of templates to keep the levels interesting and non-repetitive.
I uploaded a short video, so you can see the algorithm in action. I made it so that you can see the rooms popping into existence whenever the player sees a new room. This is just a very first test of random dungeon generation. There are other techniques that I want to try out to see which one works best.
And here is an image of the room templates that were used for this level:
Room templates that were used to generate the dungeon in the video
