And from the game that all roguelikes are like in some ways, Rogue:
To simplify slightly what we know of these dungeons:
- They have clearly defined rooms and corridors between them.
- There is a lot of unused space between the rooms.
- They are usually underground.
Digging through stone is usually a very costly proposition for humans, both in terms of energy, manpower and wages to pay the diggers. If you have a magical world where everyone and their part-time wizard cousin is running around with a magical wand of digging-and-stone-disposal, the cost goes down obviously. While contemporary military and government installations may have corridors far into the mountain and big separate rooms, the costs are typically prohibitive for anyone without a generous budget and ready access to a tunnel boring machine.
But for some reason we want cellars, as they have nice properties, in particular for storing potatoes and carrots. Some will have more ambitious needs, of course. But let us say we non-magical humans have dug out a cellar in the easiest way possible, by pick or explosives, then we certainly want to use every centimeter or inch of the cellar that we paid dearly for. We won't waste time on many corridors since that space can be used for actual activities, storage or a place to hang out during hot summer days. We might have small rooms here and there for pantry, washing room, storage, beer brewing and other needs that we somehow have.
So our goal is to generate cellars where we waste little or no space. They would have variation in room sizes and purposes. Corridors in roguelikes have a tactical purpose; you can fight enemies one-on-one and you can line up monsters in the corridor and then zap them all with a wand of lightning bolt. So we need some tactical possibilities to replace that, we cannot just be big open rooms. (Of course, access to magical wands of lightning bolt may be a bit limited for the magically challenged anyway)
For the first iteration we decide on some principles:
- No space wasted
- Variation in room sizes
- All rooms are accessible
- Bonus: Use architectural patterns like a hallway connecting to several rooms
The quickest way to approach this is to assume that somehow we dug a rectangular hole in the ground and we want to fill that with content. So at first we start with one big rectangular room and ask ourselves, is this what we want?
Most likely we decide to split up things a bit, we want our potato cellar to be different from where we chill out during hot august months. So we split this rectangle (randomly) within some rules for minimum size of rooms.
And now we have two rectangles that we may consider splitting up again within our rules for minimum rooms and where splits may happen. Let us split both rectangles because they are still big.
The green rectangle to the upper left seems to have small enough height, we don't want that one to shrink more, so let us say it is finished. Even though the pink room is kind of large, we like it as it is and do not divide it further, so we add that one as well to the finished rectangles. We go ahead and divide the lilac and light blue rectangles though.
Again we apply rules and divide further down by our rules and (random) choices till we have divided up things.
In a typical roguelike fantasy dungeon walls are clearly separate, and in my code I had a lot of safeguards to avoid "ugly" overlapping walls ruining the nice organised feel of separate rooms. However when we humans make interiors in our houses and cellars we have load-bearing walls and light walls that in almost all cases are not duplicated, but shared between rooms. So that is what we will do as well - the width of walls between rooms will be a single tile.
For my own code the easiest approach was to fix this in the division algorithm above where I gave the two divided rectangles overlapping coordinates for a wall. YMMV.
Assuming overlapping rectangles we just draw walls at the extent of the rectangles, looking something like this:
Bonus FeatureIn the above picture (from my generator previewer) we can see a very long vertical hallway in the middle of the map, and on the top there seems to be hallways to the left and right. Hallways are a feature that people tend to have in their house interiors and cellars so in this case we added one vertical and one horizontal. Ideally there should be a large chance that the upper hallways should open up into our main vertical hallway, but let us see what the random-generator decides on.
Since there is apparently not room for corridors between the rooms we need to connect rooms differently somehow. Humans generally connect their rooms in two ways; doors and knocking down light walls. So that is what we will do, too. In general we don't want to knock down very large walls so we keep walls that are above a certain size.
We search all the walls of each room for possible connections to another room (on the other side of the wall), and keep track of each connection point. We avoid corners of rooms as removing those seem like a bad idea - also reducing possible connections. Once we have all possible connection points we go to the next step.
If we went for the bonus feature of hallways we check if we can connect them first. If possible we try to knock down the walls, but it is a random choice, might not happen. If we didn't knowck down the walls, we put doors there at least.
We go through those rooms that are connected (ie have possibile connections for doors or knocked down walls) and check if we want to build a door there, knock down the wall or do nothing - after all not all walls have doors even if they have a shared wall. We might get something like this:
It is recommended after the first connection-pass above to check that all rooms are connected, as we rely on RNG it will sometimes fail to connect some rooms. There are many ways to check that rooms are connected, and popular choices are dijkstra-maps or a simple graph-check.
In case some rooms did not get connected, go through the unconnected rooms and increase the chance of connecting to adjacent rooms till all rooms are connected. If somehow a room cannot connect to adjacent rooms (maybe because of corners) - start the algorithm again with a new seed.
In the above generated cellar (in picture) we kept the doors to the hallways on the top, we removed several walls for some interesting nooks, and added doors to make exploring a little bit convoluted. We do not have the simple tactical benefits of corridors, but the combinations of smaller rooms and little nooks should give us some tactical possibilities - especially with some barrels, crates, urns with combustible material and other things.
We have done what we set out to do - we generate interiors with little wasted space, we have varied room sizes and we can reach all rooms just fine - even if it can be a bit convoluted. We also added hallways that in many cases open up into each other and that connect several rooms.
A small gif that describes how we split up the above cellar + some bonus cellars that came from different seeds: