Over the course of this project, a few ways of arranging rooms neatly, while all adjacency requirements are fulfilled, have been suggested. I have not yet settled on which method to use, and I am still writing different experimental sketches exploring then. Currently I am exploring two ideas: the Pull-Push algorithm, and the Throw-Stuff-At-The-Wall-and-See-What-Sticks (Throw-and-Stick for short) algorithm. Both methods are Box-Packing algorithms at their heart. I feel that the most important part of a program like Autoarchitect is the geometric solver, i.e. the "room packer". How good can the program be if it can't even make sure that the kitchen is away from the bedrooms? or that the garage opens to the front? Today I will talk about the Pull-Push algorithm.
The first prototype, shown in an earlier post, is based on an algorithmic idea I like to call Pull-Push. It assumes that the rooms are physical objects that have physical relationship with each other, and they attract each other if they are related. The rooms are placed initially in their relative correct places, so the room which needs morning sunlight is placed on the east-ish. This influences the room's eventual position in the room. Then all rooms that are related to each other, or would be marked as "adjacent" in an adjacency schedule, pull each other. Then it goes through all the rooms to check if they're intersected or not, then pushes them out of each other.
To best illustrate this, see the above diagram. (Please excuse the crudeness of these drawings, as animating boxes is a bit more difficult than I anticipated.) It shows three rooms that are related to each other, as you can see by the black pipe connecting them. The first step would be to pull them towards each other in a straight line. However, due to the original position of the rooms, two of them end up intersecting each other.
This is resolved by the second part of the operation: Push. The algorithm identifies intersecting cubes based on their geometries and positions, and pushes them away from each other. You end up with three adjacent rooms. Naturally, with a plan with more than three rooms, the second step does not necessarily resolve all conflicts. So you go back to the beginning to adjust rooms that should be related to each other, then resolve any intersections: Pull, Push.
One way the basic logic of this algorithm could be improved is to bound it by a site boundary, so rooms are not pushed outside the site. This prevents some weird bugs and infinite loops from happening.
In the next blog post I will post about the Throw-and-Stick algorithm, also known as Genetic Algorithms. The implementation is fairly simple, but the results are not necessarily so.