Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I've been looking at some algorithms and articles about procedurally generating a dungeon. The problem is, I'm trying to generate a house with rooms, and they don't seem to fit my requirements.

For one, dungeons have corridors, where houses have halls. And while initially they might seem the same, a hall is nothing more than the area that isn't a room, whereas a corridor is specifically designed to connect one area to another.

Another important difference with a house is that you have a specific width and height, and you have to fill the entire thing with rooms and halls, whereas with a dungeon, there is empty space.

I think halls in a house is something in between a dungeon corridor (gets you to other rooms) and an empty space in the dungeon (it's not explicitly defined in code).

More specifically, the requirements are:

  • There is a set of predefined rooms
    I cannot create walls and doors on the fly.
  • Rooms can be rotated but not resized
    Again, because I have a predefined set of rooms, I can only rotate them, not resize them.
  • The house dimensions are set and has to be entirely filled with rooms (or halls)
    I.e. I want to fill a 14x20 house with the available rooms making sure there is no empty space.

Here are some images to make this a little more clear:

Typical dungeon generator Dungeon with no corridors House generator result

As you can see, in the house, the "empty space" is still walkable and it gets you from one room to another.

So, having said all this, maybe a house is just a really really tightly packed dungeon with corridors. Or it's something easier than a dungeon. Maybe there is something out there and I haven't found it because I don't really know what to search for.

This is where I'd like your help: could you give me pointers on how to design this algorithm? Any thoughts on what steps it will take? If you have created a dungeon generator, how would you modify it to fit my requirements? You can be as specific or as generic as you like. I'm looking to pick your brains, really.

share|improve this question
    
An odd recommendation: I strongly recommend checking out Christopher Alexander's books The Timeless Way Of Building and A Pattern Language, the architecture books that formed the original foundation for the notion of a (software) pattern; they essentially describe an explicit language for buildings and living spaces that can be turned into a top-down procedural construction method. –  Steven Stadnicki Jan 23 '13 at 18:12
    
Personally, I would try to make an algorithm like egarcias' answer. Begin by generating room placeholders (big areas that can be filled with varying numbers of rooms. Each room place holder is required to have a specific (or random with a lower bounds) size gap between them. The 'gap' space is what would be considered a hallway i.e. space that is in the house but not in a room, and the room place holders would be filled by random sized rooms similar to your 'dungeon with no corridors' example. –  Benjamin Danger Johnson Jan 23 '13 at 19:02
    
@pek Please create an answer for your solution, don't put it in the question. –  Byte56 Jun 24 '13 at 14:31
    
@Byte56 Done. Just to be clear, I did that because I didn't want to get credit since I only did what other people suggested. I understand though why that isn't ideal for the site's format, so, I added my answer. –  pek Jun 26 '13 at 13:47
    
Thanks @pek. Don't worry about getting credit, it's deserved and it's useful to people coming to the site to see the solution (and seeing it where it's expected is best). –  Byte56 Jun 26 '13 at 13:51

4 Answers 4

I think this is good case for using either binary or ternary space partition.

On first pass, split house space into halls and {blocks of rooms}. Get next big chunk, split it into {hall and chunk} or {2 chunks and hall between them}. On every step, rotate slicing direction by 90 degrees. Stop when {no more big chunks left} or {total hall area reached limit}.

On second pass, split remaining chunks into rooms. Get next big chunk and split it. Skip splitting some not-so-big chunks at random, to have some big rooms.

If any hall is facing much older hall, place wall (or wall with door) there.

Connect rooms with halls directly or through other already-connected rooms.

For example, you can see either my manually-crafted result or C++-alike partly-done pseudo-code. Final shot:

final shot

share|improve this answer
    
That's where my research resulted, in space partitioning. Your example with code gave me a very very good start. I'm currently reading on algorithms. One question though: one of my requirements is that rooms are predefined (i.e. there are 2x2 rooms with one door, 1x1 with two doors, but no 2x2 with three doors), so I cannot start partitioning and then decide on where I will place doors. I think I have to keep in mind my limitations while I'm partitioning. Do you have a suggest for how I would go about this? In any case, thank you very much for your answer and effort! –  pek Jan 27 '13 at 19:38
    
@pek I am not sure if mere mortal can find academic solution for this problem. You can try setting additional conditions for chunk-splitter and box-splitter, and then generating and dropping levels until you find one where all conditions can be met. –  Shadows In Rain Jan 27 '13 at 22:14
    
yeah, I was hoping that I was missing something. My first approach was with using A* to figure out how to fit the rooms in a given space, but it was lacking logic for the halls. Now I am thinking that I can use BSP to place halls, and then use A* to the blocks. The thing I'm mostly worried about is that it might be too expensive and not always produce a result. But I'll have to test this first. Maybe it won't be as bad? –  pek Jan 27 '13 at 22:51
2  
@pek I found something useful, if you still interested. Look at this, also google L-system. –  Shadows In Rain Feb 7 '13 at 2:23

You can take advantage from the fact that your desired design lumps the rooms in rectangular rooms surrounded by corridors. With that in mind, I would do this:

  1. Design the corridors and the "big spaces" for rooms
  2. Fill in each "big space" with rooms

2 steps

Filling up the big spaces with rooms can be done easily if you start with the rooms at the borders - they have specific constraints, for example the rooms facing a corridor can have a door on that wall, but the rooms facing the "outer walls" can not (they could have windows, perhaps). Rooms "inside" the big blocks of rooms will need at least one entrance.

share|improve this answer
up vote 10 down vote accepted

So, here is how I solved this problem. But first, I'd like to thank both @Shadows In Rain and @egarcia for their answers. They gave me a good direction which helped me get some results.

I used Shadows In Rain's space partitioning to generate a basic house and then followed egarcia's advice to fill in the area with rooms.

The space partitioning was pretty straightforward since 90% of the code was done by Shadows. The "fill in the rooms" part was a little more challenging. I decided to use a pseudo AI Planning system that uses A* to position the rooms appropriately. The good thing about using planning instead of just A* is that the preconditions help cut down the search space significantly.

Here are some screenshots with the results:

Floor plan generation phase Floor plan generation phase

Room placement phase Room placement phase

Now with connecting doors!
Now with connecting doors!

share|improve this answer

Dahl & Rinde have a thesis paper on Procedural Generation of Indoor Environments which uses a skeleton & regions approach to fill building interiors with rooms and hallways. The paper includes class diagrams for their prototype. There's also some good references in their bibliography, including the aforementioned A Pattern Language.

Their work was designed around the following simplifying assumptions:

  • only dealing with apartment buildings
  • no split levels
  • limiting the shape of buildings (envelope) must be polygonal
  • no holes in envelope
  • similar or linearly changing envelope thickness (I.E. no hourglass shapes)
  • only dealing with buildings that need corridors

Here's a brief overview of their process:

  • Find the skeleton for the envelope. Corridors are then placed along the skeleton based on distance from envelop, proximity to doors or stairs & proximity to previously placed corridors.
  • Next, the remaining non-corridor space is partitioned into maximum connected areas, each with a single continuous boundary. In some cases, this will require the insertion of a wall.
  • These regions are then divided into apartments attempting to allocate at least one window per apartment. In some cases smaller divisions will merge to avoid overly small apartments. Regions with no windows are simply ignored.
  • Finally, the apartments are divided into rooms using a weighted Voronoi-like diagram as a basis as follows:

    • Seed weights are used to influence the room size. Seeds are added at doors and windows. Additional seeds are added, generally one per desired room; while not explicitly stated, it looks as if the seeds are placed along the outer walls of the apartment.
    • Starting with the farthest point, a line between the given seed & all other points is calculated and then bisected a distance relative to the respective weights of the end points (E.G. if A & B had weights of 1 & 4, the bisecting point would be 1/4 of the way from A to B). The collection of bisecting lines, along with the outer wall then forms the cell for the seed.
    • Next, an S-Space wall skeleton (as per Peponis et al 1997) is created by partitioning the area with lines originate perpendicularly from the mid points between neighboring pairs of outer wall features (windows or doors).
    • Finally, walls are selected from the S-space skeleton that 'correspond as well as possible to the Voronoi cell walls.'
share|improve this answer
1  
Can you include pictures? That would be great. I did skim the paper and the rooms they generated looked good from an architectural POV. –  congusbongus Aug 21 '13 at 8:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.