# Procedural... house with rooms generator

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.

• 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. 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. Jan 23 '13 at 19:02
• @pek Please create an answer for your solution, don't put it in the question. 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). Jun 26 '13 at 13:51

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:

• 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. 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
• @pek I found something useful, if you still interested. Look at this, also google L-system. 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

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.

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!

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.'
• Can you include pictures? That would be great. I did skim the paper and the rooms they generated looked good from an architectural POV. Aug 21 '13 at 8:00
• Very interesting method, I'll have to examine it more closely myself for any ideas I may be able to take away from it. Dec 25 '15 at 5:16
• I came here to relax from work... Surprise my topic of research comes out. I am too lazy to write an answer based on my own research (I have only designed the bare-bones of the algoirthm yet, so it's not worth it anyway) or describing Danil Nagy's approaches to the problem, so I will just leave this here autodeskresearch.com/publications/… May 1 '19 at 6:22

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:

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 :)

• You could also find dead-end hallways and convert them into closets/utility rooms, stairs/ladders/lifts to a different level, or, if they border an outside wall, entryways/airlocks. Oct 1 '20 at 17:17