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.

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 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.

Answer 3

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

Room placement phase

Now with connecting doors!

Answer 4

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.'

Answer 5

I am trying to design procedural spaceships for a game of mine, and I came across a similar problem, with the added issue that I needed to be able to generate irregular layouts (not bounded to a square or rectangular outline). My solution was as follows:

1. start with an empty square or rectangular map of tiles

2. generate random room center points; each point has a position and parameters for the room width and height; eg, a point at (13, 3) on the map that is the center of a room that is 8 * 2 tiles, thus tiles with a horizontal distance of 4 and a vertical distance of 1 will be inside the room.

3. move the room centers until they are spaced out by a specified hall width or they are adjacent; determine which to do by each room. eg, room 1 moves over until its edges/walls are at least 2 tiles apart from those of room 2

4. fill in the tiles above, below, or to either side of each room with hallways; choose which sides to fill in based on the position relative to the center of the map, eg a room up and to the left of the origin fills the space below and to the right of it with hallway tiles.

5. draw in the walls of both the house and each room, and doors where needed. First change any empty space tiles that border room or hallway tiles into walls. Then change any hallway tiles that border room tiles into walls.

So in theory it should look like this (periods are empty space, numbers are rooms, w is walls, h is hallways), although I haven't actually tried to implement it just yet; I apologize if this looks really bad in text I tried to make it look good:

(room one is 2x2 tiles, room 2 is 4x3, and room 3 is 3x2, hall width is four)

Step 1:

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

Step 2:

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . 1 1 . . . 2 2 2 2 . . . . 

. . . . . . . 1 1 . . . 2 2 2 2 . . . . 

. . . . . . . . . . 3 3 3 . . . . . . . 

. . . . . . . . . . 3 3 3 . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

Step 3:

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . 2 2 2 2 . . . . 

. . . . . . . . . . . . 2 2 2 2 . . . . 

. . . . . . . . . . . . 2 2 2 2 . . . . 

. . . . . 1 1 . . . . . . . . . . . . . 

. . . . . 1 1 . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . 3 3 3 . . . . . . 

. . . . . . . . . . . 3 3 3 . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

Step 4:

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . h h h h 2 2 2 2 . . . . 

. . . . . . . . h h h h 2 2 2 2 . . . . 

. . . . . . . . h h h h 2 2 2 2 . . . . 

. . . . . 1 1 h h h h h h h h h . . . . 

. . . . . 1 1 h h h h h h h h h . . . . 

. . . . . . . h h h h h h h h h . . . . 

. . . . . . . h h h h h h h h h . . . . 

. . . . . . . h h h h 3 3 3 . . . . . . 

. . . . . . . h h h h 3 3 3 . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . 

Step 5:

. . . . . . . w w w w w w w w w w . . . 

. . . . . . . w h h h w 2 2 2 2 w . . . 

. . . . . . . w h h h w 2 2 2 2 w . . . 

. . . . w w w w h h h w 2 2 2 2 w . . . 

. . . . w 1 1 w h h h w w w w w w . . . 

. . . . w 1 1 w h h h h h h h h w . . . 

. . . . w w w w h h h h h h h h w . . . 

. . . . . . w h h h w w w w w h w . . . 

. . . . . . w h h h w 3 3 3 w w w . . . 

. . . . . . w h h h w 3 3 3 w . . . . . 

. . . . . . w w w w w w w w w . . . . . 

. . . . . . . . . . . . . . . . . . . . 

from here you could add doors randomly in walls between rooms and hallways.

This would in theory be a great way to generate these ships, but I have yet to test it, and just in this example I noticed one potential unwanted artifact; there is one hallway space jutting out of the actual hall like this (capital H):

h h h h h w .

w w w w H w .

3 3 3 w w w .

3 3 3 w . . .

which is unwanted if you want rectangular hallways as well. A potential solution would be to take any hallway space surrounded on three sides by walls and replace it with a wall, and then remove all walls that are only bordering (including by diagonal) other walls and empty space because they are not necessary.

If you want a tile based solution, especially one not bound to a specific shape (although if you generate too many rooms in too small a rectangle they will spread outwards and become stuck at the edges in a rectangular shape, so make sure to generate a large enough map of empty space that the rooms won't hit the borders) then this should work :)