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?