Generative floor plans with Permutation algorithm

[solub]

Dear all,

I would need your help to implement a permutation algorithm allowing the generation of building plans, that I’ve recently stumbled on while reading Professor Kostas Terzidis’ latest publication: Permutation Design: Buildings, Texts and Contexts (2014).

CONTEXT

• Consider a site (b) that is divided into a grid system (a).
• Let’s also consider a list of spaces to be placed within the limits of the site ( c ) and an adjacency matrix to determine the placement conditions and neighboring relations of these spaces (d)

Quoting Prof. Terzidis:

“A way of solving this problem is to stochastically place spaces within the grid until all spaces are fit and the constraints are satisfied”

The figure above shows such a problem and a sample solution (f).

ALGORITHM (as briefly described in the book)

1/ “Each space is associated with a list that contains all other spaces sorted according to their degree of desirable neighborhood.”

2/ “Then each unit of each space is selected from the list and then one-by-one placed randomly in the site until they fit in the site and the neighboring conditions are met. (If it fails then the process is repeated)”

Example of nine randomly generated plans:

PROBLEMS

As you can see, the explanation is relatively vague and step 2 is so unclear (in terms of coding) that I don’t even know what question to ask. Worse, I don’t even understand how exactly permutation is related to that final sorting/fitting step.

All I have so far are “pieces of the puzzle”. On one hand:

• a “site” (list of selected integers)
• an adjacency matrix (nestled lists)
• “spaces” (dictionnary of lists)

from random import shuffle

n_col, n_row = 7, 5
to_skip = [0, 1, 21, 22, 23, 24, 28, 29, 30, 31]
site = [i for i in range(n_col * n_row) if i not in to_skip]

#Makes a copy of "site" and shuffle its order for future random placing
ssite = site; shuffle(ssite)

n = 2
k = (n_col * n_row) - len(to_skip)
rsize = 30

#Adjacency matrix
adm = [[0, 6, 1, 5, 2],
       [6, 0, 1, 4, 0],
       [1, 1, 0, 8, 0],
       [5, 4, 8, 0, 3],
       [2, 0, 0, 3, 0]]

spaces = {"office1": [1 for i in range(4)], 
          "office2": [2 for i in range(6)], 
          "office3": [3 for i in range(6)],
          "passage": [4 for i in range(7)],
          "entry": [5 for i in range(2)]}


def setup():
    size(600, 400, P2D)
    background(255)
    rectMode(CENTER)
    
    #Grid's background
    fill(70)
    rect(width/2 - (rsize/2) , height/2 + rsize/2 + n_row , rsize*n_col, rsize*n_row)
    
    #Displaying site (all selected units)
    fill(255)
    for i in site:
        rect(width/2 - (rsize*n_col/2) + (i%n_col * rsize), height/2 + (rsize*n_row/2) + (n_row - ((k+len(to_skip))-(i+1))/n_col * rsize), rsize, rsize)
    
    
    #For each unit in each space...
    i = -1
    fill(0)
    for space in spaces.items():
        for unit in space[1]:
            
            i+=1
  
            #get the indices of its desired neighbors in sorted order
            ada = adm[unit-1]
            sorted_indices = sorted(range(len(ada)), key = lambda k: ada[k])[::-1]
            
            #place each unit number randomly in the site
            text(unit, width/2 - (rsize*n_col/2) + (ssite[i]%n_col * rsize), height/2 + (rsize*n_row/2) + (n_row - ((k+len(to_skip))-(ssite[i]+1))/n_col * rsize))

And on the other hand:

• a simple permutation algorithm

rsize = 30
n_col, n_row = 4, 3
n, k = 2, int(n_col * n_row) 
bits = [[] for i in range(int(pow(n, k)))]


def setup():
    size(400, 400, P2D)

    for i in range(int(pow(n, k))):
        for j in range(k):
            bit = (i/int(pow(n, k-j-1)))%n + 1
            bits[i].append(bit)

def draw():
    background(255)

    for i in range(k):
        bit = bits[frameCount%len(bits)][i]
        if bit == 1: fill(0)
        if bit == 2: fill(255, 0, 0)

        rect(width/2 - (rsize*n_col/2) + (i%n_col * rsize), height/2 + (rsize*n_row/2) + n_row - (k-(i+1))/n_col * rsize, rsize, rsize)

        fill(0)
        text(bit-1, 60+i*8, 20)
        
    text("GENE:", 20, 20)
    text(u"NO.", 20, 40)
    text(frameCount, 45, 40)
    text("Remaining", 20, 60)
    text(len(bits) - frameCount, 90, 60)
    
    if frameCount == len(bits): noLoop()

I would really appreciate if someone could help connect the dots and explain me how that permutation algorithm is supposed to re-order the units based on their degree of desirable neighborhood.

Of course any code/suggestion is more than welcomed (be it in Java or Python or even pseudo-code).

[Lexyth]

You‘re lucky, because just yesterday i made a very similar Permutation algorith to create easily differentiable fonts (Although it didn‘t work quite nicely, because my similarity comparator is too simple…). And that question number 2 is exactly what i did. You probably want to first create a fitness variable. In my case it was calculated via similarity, But in your case you can just See how many of the condotions you set are true. Thats easy to do, by just looping through each room you have and See how many conditions are positive and just add +1 to the Fitness var each Time a condition is met. Now that you have done that, just do the following. Create a new Room, without adding it in, just create it and assign it a fictive position. And then, do what you just did, But this Time telling the loop, that there is the room you just created at the Position it is set to. And make sure the code doesn‘t also calculate the room that was „replaced“ (Note that it should not really be replaced, yet). After that you will have a new Fitness value, which Well just call fitnessNew for now. Now just compare Fitness and fitnessNew and See which one is higher. If Fitness is higher, repeat the „createNewFakeRoom“ Part, if it is Smaller, set the newRoom you just created and checked to the Position it should be and remove the old one that was there. Now repeat this as Long as you want. If you Need better explanation, i can add a Mock code, just Tell me.

[solub]

Hi @Lexyth, thank you for your comment.

@Lexyth

If you Need better explanation, i can add a Mock code, just Tell me.

Yes, indeed. I would appreciate if you could provide a pseudo-code to illustrate your explanation as I’m not sure you’re talking about Permutation.

[Lexyth]

So… i‘m not sure either if it‘s permutation i‘m Talking about, But i‘m sure it‘s what is required in step 2). And as far as i can Tell, that should be Permutation… though i might be wrong on the Terminology.

Step 2 is essentially just trial and error, but more efficient.
You have to place a random „room“ from your List somewhere and See if the conditions are met. If they are, then it‘s good and can be placed, if not retry.

The mock code should be like this :

Room[] rooms = new Room[10];

void setup() {
  //set all rooms with their conditions
  //and maybe set a random layout first
}

void draw() {
  Room newRoom = copy(room[0]);
  newRoom.setPosition(random);
  if (newRoom.getFitness() > room[0].getFitness()) {
    room[0] = newRoom;
  }
}

class Room{
  boolean isPlaced = false;
  Condition[] condition;
  int conditionsMet;

  Room(Condition[] con) {
    condition = con;
  }

  void checkConditions() {
    conditionsMet = //how many conditions are true
  }

  void getFitness() {
    int result;
    for (all rooms) {
      room[i].checkConditions();
      result = room[i].getConditionsMet();
    }
    return result;
  }

// there should be Setters, getters and other things, But i‘ll just call them from outside, Even if they don‘t really exist, Else the code will get too Long. It should be obvious what they do from their names then. 
}

class Condition{
  //stuff to define condition
}

[solub]

@Lexyth Thank you for the explanations and apologies for the late reply.

Although the idea of computing a fitness score for every cell picked at random seemed simple at first, implemeting that logic while respecting the conditions mentionned above proved to be more complex.

After a rather popular but unsuccessful stackoverflow bounty and a couple of emails exchanged with Professor Terzidis (many thanks to him) I finally came up with the following workaround (please note that this version doesn’t use any adjacency matrix but adding weight to the neighboring selection process shouldn’t be an issue):

Script

n_col, n_row, csize = 7, 5, 50 
grid = [[0 for y in xrange(n_row)] for x in xrange(n_col)]
toSkip = (0, 1, 21, 22, 23, 24, 28, 29, 30, 31)
c = ('#FF0000', '#00FF00', '#0000FF', '#FFFF00', '#00FFFF')
spaces = (("office1", 4), 
          ("office2", 6), 
          ("office3", 6), 
          ("passage", 7), 
          ("entry", 2))


def setup():
    size(1000, 600, P2D)
    strokeWeight(4)
    background(255)
    frameRate(1000)
    textSize(14)
    fill(0)
    
    
def draw():
    pass
    
    
def mousePressed():
    findSolution()
    drawSolution()
    

def findSolution():
    global attempts
    
    #Instantiate/clear "attempts" and "toFill" at every click
    attempts = 0
    toFill = (n_col * n_row) - len(toSkip)
    
    while toFill > 0:
        
        #Increment attempts at every loop
        attempts += 1
            
        #Instantiate/clear "site", "toFill" and "done" at every attempt/loop
        site = [i if i not in toSkip else None for i in range(n_col * n_row)]
        toFill = (n_col * n_row) - len(toSkip)
        done = 0
        
        #Pick random 'x' and 'y' values within site
        xr = int(random(7))
        yr = int(random(5))
        
        for i, s in enumerate(spaces):
            numCells = 0
            k = 0
            
            while numCells < s[1]:
                k += 1
                
                #Saving up original random values 
                xr_, yr_ = xr, yr
                
                #Pick one neighboring cell randomly
                if random(1) < .5: xr += int(random(-2, 2))
                else: yr += int(random(-2, 2))
                
                xr = constrain(xr, 0, n_col - 1)
                yr = constrain(yr, 0, n_row - 1)  
                            
                #Check whether random cell is empty or not
                idx = xr + yr * n_col
                empty = False if site[idx] == None else True
                    
                if empty == True:
                    
                    #Place unit in cell
                    grid[xr][yr] = i+1
                    
                    #Remove it from list of available cells
                    site[idx] = None
                
                    #Update number of unit to place + number of empty cells left
                    numCells += 1
                    toFill -= 1
                    
                #Convert back to their original values if selected cell is already taken, before reloop
                else: xr, yr = xr_, yr_
                
                #Safety valve
                if k > 100:
                    done = 1
                    break
                                
            if done == 1: break

                                
def drawSolution():
    background(255)
    text('Attempts: %i' % attempts, width/2 - textWidth('Attempts:   ')/2, height>>2)
    pushMatrix()
    translate(width/2 - (n_col*csize) / 2, height/2 - (n_row*csize) / 2)
    
    xy = ((1, 0), (-1, 0), (0, 1), (0, -1))
    
    for y in xrange(n_row):
        for x in xrange(n_col):
            if grid[x][y] != 0:
            
                #Draw site
                pushStyle()
                noStroke()
                fill(c[grid[x][y]-1])
                rect(x * csize, y * csize, csize, csize)
                popStyle() 
            
                text('%i' % grid[x][y], x*csize + csize/2, y*csize + csize/2)  
                
                #Draw site borders
                idx = x + y * n_col
                if idx / n_col == 0: line(x * csize, y * csize , x * csize + csize, y * csize)
                if idx / n_col == n_row-1: line(x * csize, y * csize + csize, x * csize + csize, y * csize + csize)
                if idx % n_col == 0: line(x * csize, y * csize, x * csize, y * csize + csize)
                if idx % n_col == n_col-1: line(x * csize + csize, y * csize, x * csize + csize, y * csize + csize)
                
                #Draw spaces limits
                for i, loc in enumerate(xy):
                    
                    x_ = constrain(x + loc[0], 0, n_col - 1)
                    y_ = constrain(y + loc[1], 0, n_row - 1)
                    
                    #If neighbor has not same unit value (does not belong to same space) -> draw line
                    if grid[x][y] != grid[x_][y_]:

                        if i == 0: line(x*csize + csize, y*csize, x*csize + csize, y*csize + csize)         
                        elif i == 1: line(x*csize, y*csize, x*csize, y*csize + csize)
                        elif i == 2: line(x*csize, y*csize + csize, x*csize + csize, y*csize + csize)
                        elif i == 3: line(x*csize, y*csize , x*csize + csize, y*csize)
    popMatrix()

I also made a 3D interactive version based on that script that makes possible to select spaces and allocate/widthdraw units with a grid controller (see short live demo here).

Hopefully someone will find this algorithm as fun as I did.

[jeremydouglass]

This is an interesting solution (with the “safety valve”). I notice that you begin by randomizing xr and yr – is it important to you to be able to sort or enumerate the solutions that you find? e.g. using itertools and generators.

[solub]

Hi Jeremy,

The safety valve solution is from Mr. Terzidis and it is indeed a clever trick.
Answering your question: no it is not important at the moment but that might be something I’ll take into consideration later. What would you suggest in this regard ? Saving every permutation for every xr and yr available in the grid ?

[jeremydouglass]

I think it depends on what you are trying to do – if you want them to have ids / be sortable that might not make them sequential, for example. I’ve been working on a series of related problems recently in representations of the partition of space on the comics page.

So (for the sake of argument) imagine you have a 7x5 structure that could contain floorplans, with available space indicated with ‘1’ as in your images.

0011111
1111111
1111111
0000111
0000111

…which you could encode from binary. This could be done with either endianness; here it is rendered as 8589919111. So that structure could be named w.h.encoding, e.g. 7.5.8589919111. There are infinite potential structures, and there are exactly 2^(7*5) potential structures on the 7x5 grid – either a bit is available or it isn’t. However most of those structures are probably invalid given rules like connectivity or minimum room size – for example, 7.5.21 encodes a spaced row of three little outhouses on a 7x5 grid – 10101 – and that probably doesn’t count as a structure for floorplans.

…BUT if we don’t care that some of the plans are invalid, then we can make any collection of valid structures sortable in this way. That might satisfy some intuitive requirements of ordering – that first all structures on the same grid be grouped together, and next all floorplans on the same structure be grouped together in a sort.

Now, within a given structure (like this roughly L-shaped example) each room encountered in LRTB order could also be binary encoded. So the first green room is:

0	0	1	1	0	0	0
0	0	1	1	0	0	0
0	0	1	1	0	0	0
0	0	0	0	0	0	0
0	0	0	0	0	0	0

or 6493175808. Next comes the pink room

0	0	0	0	1	1	1
0	0	0	0	0	0	1
0	0	0	0	0	1	1
0	0	0	0	0	0	0
0	0	0	0	0	0	0

which is 1881194496 et cetera, so one representation of a floor plan is an ordered series of room terms on a grid, w.h.room1.room2.room3, e.g.

7.5.6493175808.1881194496…

These aren’t very human readable – hex would tighten them a bit, but they are very long, and really just a data encoding format that happens to be expressed in an ordered way. But they have interesting properties – such as the fact that all floorplans with the same “upper-left” room will be sorted together.

Another alternative is to use a binary word for each grid cell big enough to store the room count + 1 (empty), then encode a room number in each cell. So:

0	0	1	1	2	2	2
3	3	1	1	4	4	2
3	3	1	1	5	2	2
0	0	0	0	5	5	5
0	0	0	0	5	5	5

…has five rooms, so it is w.h.r = 7.5.5. Five plus one rooms can be stored in three bits, so

000	000	001	001	010	010	010
011	011	001	001	100	100	010
011	011	001	001	101	010	010
000	000	000	000	101	101	101
000	000	000	000	101	101	101

Which means this is layout 7.5.5.91963938972438651623329235309

This one has different sorting properties than the previous one – it sorts by room count and then by grid cell, not by room. That means different structures with the same initial room tile all appear grouped together, which may be counter-intuitive or seem arbitrary. It is still too long to be human readable, but much more compact than the previous one. If you wanted to create an index to these, you would walk through generating them in an ordered rather than random fashion, check their validity, and then assign a floorplan a number (1, 2, 3, 4, 5) … but there are a lot of them to walk through and check. According to OEIS, these are the possible compositions (floorplans) on an NxN grid:

1		1
2		12
3		1434
4		1691690
5		19719299768
6		2271230282824746
7		2584855762327078145444
8		29068227444022728740767607050
9		3230042572278849047360048508956727420
10		3546545075986984198328715750838554116235343894

https://oeis.org/A145835

… so that is a LOT of checking time and index storage space once you are north of 5x5. Also, space partion is NP hard

Another way to encode a spatial partition in a sortable way that is more compact (I have been using it in my work) is as a bit array of edges. Basically, encode the walls, not the rooms, with 1 for a wall and 0 for no wall. That doesn’t get you sequential numbering, but it does get you a much, much more compact representation of a given floorplan – which you can then convert to and from a grid of labeled room numbers.

So this:

 0.0|1.1|2.2.2
 - - . . - - .
 3.3|1.1|4.4|2
 . . . . . - -
 3.3|1.1|5|2.2
 - - - - . - -
 0.0.0.0|5.5.5
 . . . . . . .
 0.0.0.0|5.5.5

…becomes (w-1) * h + w * (h-1) edges, or 58 edges internal edges on a 7x5

.|.|..  = 010100
--..--. = 1100110
.|.|.|  = 010101
.....-- = 0000011
.|.||.  = 010110
----.-- = 1111011
...|..  = 000100
....... = 0000000
...|..  = 000100

…encoded w.h.edges, that makes this specific floorplan 7.5.93672357798379524. This is the most compact representation, but it doesn’t group by structure or by room when sorted.

One way to combine the concise advantages of different approaches would be to sort on the grid w,h then the structure, then the wall grid:

w.h.struct.walls
7.5.8589919111.93672357798379524

Once clusted by a given structure, a set of floorplans sorts logically, with changing walls in the lower right gradually building up to changes in the upper left.