Procedural… house with rooms generator

Question

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:

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.
Thank you in advance.

Solution

First of all, 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. However, my "planning system" is more like A* + action preconditions than a full blown planning system with preconditions and effects.

Anyway, I'll leave the implementation for a blog post. Here are some screenshots with the results:

Floor plan generation phase

Room placement phase

P.S. I'm giving the answer to Shadows In Rain since he provided source code, but they were both correct.

Answer 1

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:

Answer 2

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

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.