# What Graph Theory approaches or algorithms are useful for designing a House?

I have a set of data about a family, and I want the software to find a house design that fits the data (which includes stuff like preferences and whether they want a pool.

The current way I am going on about it right now is rather naive. There is a predetermined set of relationships between categories, or roles, of Rooms. So based on the data, I allocate "area pools", so to speak: a certain area for bedrooms, a certain area for "private sphere" rooms, and area for "public sphere" rooms. Crossing these "pools" with the requested rooms I created the `Room` objects I need. However, the relationships between them are naive as well: I just created a number of variables that represent roles, such as the `mainRoom`, `bedroomHub`, `diningTable`, etc, and assigned these variables to whatever `Room` object that should occupy this role via a series of `if` statements.

If the text description is not clear enough, here is the code that implemented this idea. It is ugly and ridiculous but it was good enough for demo purposes (did I mention this was work for my Masters of Architecture thesis?)

``````    // Constructor, of the House, no irony whatsoever
public House(Input input, BldgProgram bldgProgram)
{
mainList = new List<Room>();

Streetside = input.StreetSides;
MainStreet = input.MainStreet;

var privatePool = bldgProgram.PrivatePool / (GridSize * GridSize);
var publicPool = bldgProgram.PublicPool / (GridSize * GridSize);
var bedroomCount = bldgProgram.BedroomCount;
var kitchenPool = bldgProgram.KitchenPool / (GridSize * GridSize);

if(input.MainStreet == CardinalDirections.East || input.MainStreet == CardinalDirections.West)
Boundary = new Rectangle(input.PlotDepth / GridSize, input.PlotWidth / GridSize);
else
Boundary = new Rectangle(input.PlotWidth / GridSize, input.PlotDepth / GridSize);

var main = AddRoom<LivingRoom>("Main", 12 / GridSize, 16 / GridSize);
privatePool -= main.Area;

Room livingRoom;

if(privatePool > (24 / GridSize) * (12 / GridSize))
{
livingRoom = AddRoom<LivingRoom>(null, 24 / GridSize, 12 / GridSize);
privatePool -= livingRoom.Area;

PairRooms(main, livingRoom);
}
else
{
main.ExtendLength(privatePool);
livingRoom = main;
}

BedroomCtor(input, bldgProgram, bedroomCount, livingRoom);

var desiredRooms = input.Rooms;
Room diningRoom;

if(desiredRooms.HasFlag(InputRooms.DiningRoom)) // Sketch
{
var diningRoomSize = input.Total <= 8 ? 16
: Floor((input.Total - 8d) / 4) * 4 + 16;
// 12 * 16 for 8 people !! more for each extra 4 ppl add 4 ft.
diningRoom = AddRoom<DiningRoom>("Dining", 12 / GridSize, diningRoomSize / (12 * GridSize));
publicPool -= diningRoom.Area;

PairRooms(diningRoom, livingRoom);
}
else
{
livingRoom.ExtendLength(3);
diningRoom = livingRoom;
}

KitchenCtor(input.Total, bldgProgram.Kitchenette, livingRoom, diningRoom, desiredRooms);

#region Desired Rooms
// Ideally the code would cycle through those by the priority made by the client. or CRITERIA
// Check how many flags are satisfied. If the flags are more than a certain percentage:
// create a corridor/or private rooms hub, and connect the extra rooms to it.
// alternatively, if livingRoom has more than a certain number of connection,
// it is extended per extra connection.
//
// TODO TODO TODO
//
// if(publicPool > 0 && desiredRooms.HasFlag(InputRooms.Reception))
// {
//  int receptionHallArea = Function(input.Total); // What would that be?
//  var reception = AddRoom<Reception>(12 / GridSize, receptionHallArea / (12 * GridSize));

//  PairRooms(main, reception);

//  publicPool -= reception.Area;

//  if(publicPool > receptionHallArea)
//  {
//      // new Reception Room for te other gender .. maybe?
//  }
//  else
//  {
//      reception.ExtendLength(publicPool);
//      // There should be an entrypoint variable where I assign to the street in the end.
//  }
// }

// if(privatePool > 0 && desiredRooms.HasFlag(InputRooms.Library))
// {

// }

// Go through rooms in desiredRooms. Check if privatePool has enough space.
// Library
// Office
// GameRoom
// w/e
#endregion
}
``````

The commented out region is something I intended to implement but never got around to it.

The part of actually arranging the `Room`s in physical space is on the back of my mind, and is considered in things like determining the `Corridor`'s length. It is in another place in the code, however, and is only invoked when the `House` graph is constructed.

Now I graduated already, so this project is now a personal project rather than a school one. (My school's policy is that we own all our work. It is an art school and I guess they don't want to be stuck with too much crap.) I read some things about Graph theory, considering it might be useful to solving the problem. While I still have no idea how I would generate a graph of the house in an algorithmic fashion, I know a couple of things to check for:

1. It needs to be planar, ish. (Maybe dictate multiple floors if it not planar?)
2. I can have different types of Edges such as Doors, Windows, Plumbing (wet rooms should be adjacent), etc.
3. Different types of Nodes too: Roofed and Unroofed are the two most obvious.
4. Have little Pathing effort (I have no idea how to start with something like this but if I already have a graph I can judge it with some existing sort of algorithm, no?)
5. Buildability: balanced areas between different floors, or that Public rooms

One of the things I found out is that Graphs are often used by AI to find a desired "world state", but all I know about my world state is that the criteria it satisfies. Genetic algorithms seem to be a straightforward answer to this question, and I already use them for my geometric solver (without much success but that's another topic). I have two related issues with them: they're horribly inefficient (take a lot of time), and even when given time they're completely unpredictable, and imprecise.

The complete code of my `House` class, if you want to see the implementation, can be found here. From there you will find the whole project as it currently stands.

tl;dr An architect with not much coding experience is looking for advise towards designing an algorithm that can design houses for him. Am I missing something completely obvious? Is there anything I should read? Any comparable projects I can look at?

PS. One specific problem I never found a clear cut answer for is how do I treat the "outside"? Is it a thing to have a huge node that all nodes can connect to (even on multiple levels)?

• Do not include dialog about whether your question is on-topic or not in the question itself. It is irrelevant, and clutters up a question that is already a bit too long. If you want to discuss your question's topicality, do it here in the comments or on the Meta site. – Robert Harvey May 31 '16 at 22:00
• You probably want to look into something like “procedural dungeon generation”. Game programmers have been doing stuff like this for a while! There is also academic work such as Procedural Generation of Indoor Environments. – Jon Purdy Jun 1 '16 at 0:31

## Rough Modeling

The conventional aspects of house design and construction suggest modeling with a domain specific language that captures the business logic of dwelling and dwelling life cycles might be easier than using a general purpose programming language.

## Rough Mathematics

Though there are bounds on house configuration from convention, mathematically, the combinatorial space for possible house configurations is seems exponential. Particularly if actual constructed geometry is part of the equation.

## Rough Solutions

Lists of a family's requirements suggests a set of constraints and a problem space revolving about the idea of best fit suggests an optimization problem. This suggests a numeric approach over a graph based one. A numerical approach also avoids dealing with graph isomorphism when evaluating solutions.

### Numerical Approaches

1. Discreet Optimization is useful if statements about the quality of the solution are important. Discreet Optimization might entail geometric algorithms [as opposed to graph algorithms].
2. Machine Learning is useful if it is difficult to enumerate all the constraints.

### Generally

Good design, in my experience, is about delivering something that meets the spirit but not the letter of a formal specification. In the realm of construction there are millennia of human experience embodied in conventions and implicit requirements. It's going to be hard to capture all of those in a constraint system let alone a set of graph traversal rules.