Hi all,

I'm having trouble coming up with a way to generate a specific kind of dungeon. My goal is something like this:

I've read several articles concering dungeons but they all generate a more classic lay out, separate rooms connected with corridors.

Thus the issue is that I can't come up with a good approach to split a given square area (32x32 for example) up into tightly placed rooms, who shouldn't be rectangular all the time, but also not to randomly shaped (think of jagged edges etc, since I will only be using horizontal and vertical walls).

Currently I'm just adding in random rectangles that either clip or merge with existing ones until the area is covered, which is slow and not always satisfactory. I tried using some variety of drunk-walk approaches, which was too random, and binary space partitioning which didn't really yield either.

So, what would be the most likely to work out? How can I tackle this?

Thanks in advance

If you are trying to make a rouge-like type game, you should have randomness. From what I played this randomness isn't exactly unique, and there is some repetition in dungeon layout. My approach would be (in case this is grid based) to define each room shape and later only position them so they are next to each other, by cheking next free (square) space on the side of the room.

Thanks for your reply!
Randomness is very important, and I know some repetition is ok but I want to steer clear from it as much as possible. It tends to stand out in larger dungeons pretty soon.

It's especially the shape of the rooms that I want to be more complex than just rectangles; predefining such rooms would lead to a lot of puzzling to get it all to fit, which would be slow. It doesn't have be done blazingly fast, but I do need to generate a lot of these sections to form a decent dungeon at some point, so it be great if it was.

I suppose some form of metatiling wouldn't be a bad idea though. I hadn't really considered that. Metatiles with some partial walls on them would be relatively easy to piece together and would form rooms automatically. I'll have to try it see it though.
And the dungeon is grid based, yes.

Thanks for your insights! It indeed does look like it's a lot of smaller nodes joined together.
I'll give that a try right away.

I think I can use such a morphing function somewhere, but I'll have to play with it a bit first.

I have a free afternoon to try both tiling and the second-pass bsp, so hopefully I have some cool results in a few hours.

I might try a method a bit like this:

1. subdivide the grid in both dimensions at many random points. eg. if it's a 50x50 grid, drop in 20 horizontal lines and 20 vertical lines at random positions. Re-select or remove duplicates. The lines you added divide the area into various rectangular regions of different sizes.
2. Pick a region and merge it with a neighbouring region, by removing any wall parts that they share. Each region will be adjacent to several others so I'd weight this heavily towards picking the adjacent region that shares most wall parts with this one, to reduce jaggedness.
3. Repeat step 2 a number of times.

The downside here is that you need a good representation of a region and ways to quickly determine adjacency. It might be the case that defining a region as a simple list of grid squares is sufficient, providing you can quickly find a region ID from a grid location as well.

Thanks for your input, Kylotan.

I've been trying out the options in this thread and so far it seems a combination of a (small) bsp-tree and what Kylotan described seems to give the best results. It will require some tweaking still but it's going in the proper direction, and I'm confident it will turn out the way I want it too.

Basically what happens now is that the grid is split at least two times, to make four different sized sections. This is to prevent long streaks of similar sized blocks in the next step.

Then randomly placed horizontal and vertical walls are added, and the resulting rooms are somewhat randomly merged.

This starts to look like the picture above, but there's still a bit of noise and jaggedness because my merging decision-making isn't optimal right now.

But I can work from here, thanks for help everyone!

Another potential approach:

• Generate random rectangles within your dungeon region.
• If the rectangle intersects another existing room, merge it into that room.
• If the rectangle does not intersect another existing room, make it a new room.

There are several options for scenarios where a rectangle intersects multiple rooms.

• Discard the rectangle entirely and generate another.
• Merge the rectangle with one of the rooms it intersects, either entirely (ie subtracting from the rooms it overlaps), or only the portions that do not overlap.

At some point, it'll likely be more efficient to switch to iteratively walking through any unused squares and adding them to existing rooms. That, or you can just leave a certain amount of unused squares as solid regions of the dungeon.

Try various limits on the upper and lower bounds of the rectangles dimensions to produce different dungeon results. Higher bounds should produce less jagged dungeons with fewer/larger rooms, while lower bounds would produce more jagged dungeons with more/smaller rooms.

After all that though, there's still the issue of adding doorways between rooms.