Help on algorithm to place rooms on a limited space

Question

I'm working on a small house design project and one of its most important parts is a section where the user can give some info about how he wants his rooms (for example, a house with 10 x 10 meters, having a 3x3 living room, a 3x3 kitchen, two 4 x 5 bedrooms, and a 4x2 bathroom), and then the program generates a map of the house according to the requeriments made.

For now, I'm not worried about drawing the map, just arranging the rooms in a way they don't overlap (yes, the output can be pretty ugly). I've already made some searches and found that what I want is very similar to the packing problem, which has some algorithms that handle this problem pretty well (although it's a NP-complete problem).

But then I had one more restriction: the user can specify "links" between rooms, for example, he may wish that a room must have a "door" to a bathroom, the living room to have a direct to the kitchen, etc (that is, the rooms must be placed side by side), and this is where the things get complicated.

I'm pretty sure that what I want configures a NP-problem, so I'm asking for tips to construct a good, but not necessarily optimal implementation. The idea I have is to use graphs to represent the relationship between rooms, but I can't find out how I can adapt the existent packing algorithms to fit this new restriction. Can anyone help me?

Answer 1

I don't have a full answer for you, but I do have a hint: Your connectivity constraints will form what is known as a planar graph (if they don't, the solution is impossible with a single-story house). Rooms in the final solution will correspond to areas enclosed by edges in the dual of the constraint graph, so all you need to do then is take said dual, and adjust the shape of its edges, without introducing intersections, to fit sizing constraints. Note that you will need to introduce a vertex to represent 'outside' in the constraint graph, and ensure it is not surrounded in the dual. You may also need to introduce additional edges in the constraint graph to ensure all the rooms are connected (and add rooms for hallways, etc).

Answer 2

You might find this interesting. It's a grammar for constructing Palladian villas.

To apply something like that to your problem, I would have a way to construct one at random, and then be able to make random changes to it, and use a simulated annealing algorithm.