2
\$\begingroup\$

It seems like every procedural dungeon generation tutorial focuses on how to avoid overlapping rooms, so how would one go about intentionally overlapping those rooms instead, possibly treating the overlapping areas as either new rooms or connecting passageways?

In trying to imagine how this might be done, I think that there might need to be a property for each room that is similar to how opacity works with digital color mixing, and that it could then operate on what would essentially be a modified flood fill algorithm, but are there other approaches that would be well-suited to this? What other considerations might be necessary?

As an example of what I'm talking about, consider this image, where there exist seven rectangles of varying opacities (leading to the creation of further colors by virtue of overlapping):

an image of overlapping, differently colored squares, each with a different opacity level

The idea would be that each of the seven color areas would represent a room, and then each blended color would then also be treated either as a room of its own, or as a "corridor" of sorts (but probably functionally still a room) that attaches directly to an adjoining room--no gaps or other transitional spaces.

This post appears to be the closest thing that I can find to an answer to this question, but it seems to be concerned with eliminating corridors rather that allowing for overlap:

Dungeon Generation with no corridors and room dependencies

EDIT: Upon rereading my post, I feel that I have maybe been too vague about the question. I think that my intention, initially, was to ask in a more generic way, so that it might help someone else too, but that's probably not doing anybody any favors here, especially because the word "trivial" has come up a few times now. That in mind, here are some additional details / considerations that hopefully serve to direct this post a bit better (and I promise, I'm not trying to be obtuse or to cause grief):

  1. This is for a game prototype that takes place in outer space, and it is intended to be something similar to a roguelike (with procedurally-generated maps and room progression), while still maintaining the feeling of an "open, nebulous, continuous space," hence the desire for the rooms to be, or to at least feel, interconnected (which I'm struggling to conceive of as anything other than "overlapping" at this moment; there very well could be a different solution that I'm not aware of), not simply connected, if that makes sense.
  2. To the point of a comment below, it is probably a single, large, interconnected space* that I'm imagining, which possibly defeats some of the purpose of the question. The wrench in the gears here is that the space should not be "uniform", which is to say that although it should be treated as, in effect, a continuous space, the individual areas within that space should behave differently, with relation to placement (e.g. the overlap of "Room A" and "Room B" should behave differently than the overlap of "Room B" and "Room C", and so forth). The purpose of the different behaviors could be to have an overlapping area act as a temporary barrier to entry, to introduce different asset spawning rules / conditions, to impact the ability to navigate and traverse the space, etc.; I see all of those potential purposes as being less important, initially, than enabling the behaviors to exist in the first place.
  3. The randomization of room placement is something that I think of as a requirement. The map of rooms should, ideally, be different each time (and this is what led me to look into procedural generation in the first place). The color image above may have been a bit misleading, in that it implied that I was looking for an approach that focused on manipulating color channels, when instead the imagined goal was to manipulate something like the alpha channel of a color channel component (which, as I think it has been pointed out, could simply be a single value from 0 to 1, rather than a full-on RGBA value set). This was probably not the best way to communicate the idea, but I had hoped that the idea would translate, but I'm not sure that I know of a better analogy than how opacity functions. This may confuse the issue further, but consider this image instead:

an alternate diagram, functionally the same as the one above, but with a different shape and alphabetical labels for rooms

Here, the overall shape is not so uniform as above, but I think that it does what I would like it to, in concept (ignoring the accidental overlapping of Room D with itself), so I hope that it does make more sense this way, compared to the other image--if not, and it does turn out to be more confusing, I can attempt to clarify where I am able to. I'm thinking of each outlined section as a "room unit", which, again, might not make the most sense, but it's how I'm able to best picture it right now.

I should also note that I'm using rectangular shapes purely for convenience. Upon reexamining the post that's linked here, something along the lines of an overlapped Voronoi patterned shape, or even overlapping circles, would probably also suffice--though this leads me to ask another question: would it be a mistake to generate room shapes, before overlapping them, and if so, why?

\$\endgroup\$
6
  • 3
    \$\begingroup\$ Procedural generation questions usually do well when they include a few examples of the kind of output you want the algorithm to generate, and optionally a few "negative examples" of cases to avoid. Once we have a clear target, it becomes easier to design an algorithm to achieve that target, and to evaluate or compare algorithms for how well they achieve it. \$\endgroup\$
    – DMGregory
    Commented Apr 27 at 19:41
  • \$\begingroup\$ If you have 3x3 rooms, in the extrem case you have 9 rooms in the middle when the center of each room can't be placed on top. \$\endgroup\$
    – Zibelas
    Commented Apr 27 at 19:49
  • \$\begingroup\$ I've added an image and some additional explanation, both of which hopefully help to explain the question a bit more. \$\endgroup\$
    – NJJ_002
    Commented Apr 27 at 20:18
  • 1
    \$\begingroup\$ Are there some other constraints? If you have a collections of rooms, it's trivial to randomly select one & then randomly generate a position within it to serve as the corner point for a new room which would overlap the existing one. \$\endgroup\$
    – Pikalek
    Commented Apr 27 at 20:48
  • 1
    \$\begingroup\$ You may be overthinking this. Do you need the rooms to have unique IDs at the end of the generation process? Or do you just need... a single large connected space? Unless you can answer that question with certainty, there is no point continuing down this line of thinking, as there are much simpler ways to do this than what you suggest. And even if you do need IDs, it's probably still simpler not to do it the way you suggest. \$\endgroup\$
    – Engineer
    Commented Apr 28 at 0:40

2 Answers 2

3
\$\begingroup\$

This is trivial. There is no need for you to reinvent the wheel here, that's for sure. The reason avoiding intersections is always discussed is that it is extremely easy to generate a connected space, due to line crossings (topological non-planarity).

Some background

If you're really interested, you could start by reading about graph theory and how it relates to the generation of mazes. This is fundamentally an issue of graph-connectedness. Computer mazes are typically nothing more than a grid of cells which are considered to be 4-connected with their neighbours (north, south, east and west), and which are open (0) or 1 (closed).

More to the point...

Let's say your stone is black, your passages are white, and we're going to flood-fill in blue to find subgraphs / (dis)connected areas.

  1. Starting with a totally black / filled grid. Randomly generate some white rectangles in your grid, preferably without letting them overwrite the border cells (the outer walls / boundaries of your dungeon, building or whatever). Some will overlap, some won't.

  2. Scan the map, top to bottom and left to right, to find the coordinates of every single open / white / 0 cell. Store those in a global "open list".

  3. Create a new variable sized array that is your "room cells list". Pick an open cell at random from that list. Flood-fill from the cell you just picked. For every cell filled thus, remove its coordinates from the global "open list" and add them to your local "room list".

  4. Repeat step 3 (creating a new "room list" each time) until you have no cell coordinates left in the global "open list". You are done, and you now have multiple arrays, each of which represents a connected subgraph, or area of the map which is separate from others.

You can then find a way to artifically connect those subgraphs if and as you wish.

A word to the wise

None of this requires color channel manipulation. It can be done using 0s for open and 1s for closed, or vice versa if you prefer. Plain binary. Logic quite trivial and repetitive. Consequently, these traditional processes for maze generation are usually extremely efficient, and easy to understand as the algorithm steps forward.

My advice is do not involve multi-colour schemes where you don't need to... some very difficult and long-standing mathematical problems have focused around how many colours can be adjacent to one another... you may start having intractable problems with such an approach. I speak from trial and error experience. Let the buyer beware.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ @NJJ_002 My question is "Why do you need to do it this way?". For useful answers, you'd need to give others a good reason for why you prefer to invent a new algorithm rather than learning about simpler existing algorithms (heck, or just unintended results) that do exactly this -- generate overlapping, rectangular, axis-aligned rooms on a regular pixel grid. Until you can do that, as well as describing your improved algorithm clearly, you'll get (if any) answers that don't help . Hey, I went down a lot of those rabbitholes in my youth; it can be educational in terms of what not to do. \$\endgroup\$
    – Engineer
    Commented Apr 28 at 23:10
  • 1
    \$\begingroup\$ I think (from experience) what's going to happen here is as follows. You'll think something like, "I'll get this working in spite of others". And you'll do that, you'll get it working to some degree, and be very pleased about it. And you'll realise years later, that it was a complete waste of time, because there was a better approach to doing this (indeed, many better approaches). But sometimes, that's how we learn, we stubborn human beings... we have to do it our way first, before we learn a better way. \$\endgroup\$
    – Engineer
    Commented Apr 28 at 23:13
  • 1
    \$\begingroup\$ Just to clarify, I don't think that I'm looking for a new algorithm per se, but that I'm looking for an algorithm--one of which you have generously provided, and though I haven't had an opportunity to try it yet, I thank you for that. I think that after some more research, I might be looking at something related to "binary space partitioning," but I'm also unsure if that's the right direction for what I'm considering. \$\endgroup\$
    – NJJ_002
    Commented Apr 28 at 23:14
  • 1
    \$\begingroup\$ I've provided close to countless algorithms in the link on mazes which I sent you. That site alone is worth what many other procedural generation websites can provide. It has helped me for over a decade now. \$\endgroup\$
    – Engineer
    Commented Apr 28 at 23:15
  • 1
    \$\begingroup\$ @NJJ_002 Binary space partitioning is described in the mazes link I posted in the answer. That is an excellent algorithm for you to begin with, I agree. GLHF! \$\endgroup\$
    – Engineer
    Commented Apr 28 at 23:15
2
\$\begingroup\$

The process would be the same. You would procedurally generate N rooms, and then use a compositing function to combine them into one world. However, usually real rooms exhibit non-overlapping behavior. So game designers have to take extra effort to develop procedures that don't generate overlaps.

That being said, what you describe is actually just another procedure to generate non-overlapping rooms:

The idea would be that each of the seven color areas would represent a room, and then each blended color would then also be treated either as a room of its own, or as a "corridor" of sorts (but probably functionally still a room) that attaches directly to an adjoining room--no gaps or other transitional spaces.

What happened here is you asked "what if we do X," got a visual image of what that might be like, and then asked "how do I make that into rooms?" And the first thing you did was break them up into individual rooms of one color (just with more colors than before)

Which is totally a fine approach. I just point it out to show how intuitive the idea of non-overlapping rooms is. It's hard to come up with an approach which simultaneously feels right and is overlapping.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .