Like many of my colleagues with an interest in architecture and technology, I stumbled upon a terrific game made by Oskar Stålberg called Townscaper. Townscaper is a single-person game where the ultimate purpose is to design your own personalized medieval town. The interface is highly intuitive, the results are varied and interesting, and most importantly it feels natural and easy to design and envision using this game. In its short lifetime the game has been met with plenty of positive reviews and a community of followers eager to post their proud creations on twitter. Although under the hood there are plenty of reasons for this game’s success, there is a particular algorithm that makes this game so intuitive and automatic at the same time. This algorithm, called the wave function collapse, has a lot in common with the way we solve a Sudoku.

Sudoku? Really?

For people who have been living in outer space, Sudoku is a combinatorial number placement puzzle where the objective is to fill a 9x9 grid with numbers from 1-9 following 3 simple rules.

-       You cannot place repeating numbers in the same column.

-       You cannot place repeating numbers in the same row.

-       You cannot place repeating numbers in the same neighbourhood (a neighbourhood is a 3 x 3 sub-grid within the 9x9 grid.

If we wanted to solve a Sudoku using a consistent procedure, we could start by writing all possible numbers in all cells of the 9x9 grid. Every time we add a new number this number may affect other cells. So, if we imagine an empty Sudoku all its grid cells can be filled with a number from 1-9.

If we begin completing this Sudoku, we choose a cell and a number from the available numbers. If we select, for example, the centre cell and the number 5, we will as well have to eliminate the number 5 from all the cells in the same column, row, and neighbourhood.

If we wanted to solve a Sudoku entirely using this approach, we would have to do this repeatedly for all the grid’s cells. To minimize the probability of reaching to a point where our puzzle is unsolvable, we will try to choose the cells that have the fewest amount of possible numbers.

This method will enable us to solve procedurally countless hypothetical Sudoku puzzles, with plenty of variation in our results. Bear in mind that there is no guarantee that a puzzle is solvable and the only way of knowing if a Sudoku is solvable is by trying to solve it. A classical Sudoku puzzle that are typically found in magazines and newspapers are usually predesigned so that there is only one possible solution.

A further example

It’s unlikely you are reading this blog to learn how to solve Sudokus, but instead want to know what this has to do with architectural design, medieval town modelling, townscaper etc. Bear with me, we are almost there. What if we create a new type of Sudoku; one with our own rules and our own tiles? Following another popular game by Oskar Stålberg, we will now substitute numbers with tile paintings.

Instead of using Sudoku’s placement rules, we will make our own rules to solve this puzzle. Let’s say that we want to create a much larger randomised painting. We want our painting to be rational, so we will use the colours on the border of tiles to determine if two tiles can be placed next to one another.

If we set up a similar system as the one we described previously for solving Sudokus, we can solve this puzzle by choosing tiles from the available options and let the system eliminate the conflicting tile options in affected cells.

By choosing the computer to automatically solve this puzzle, we can get results of varying painting scenes where adjacency coherency is a driving force to its formation.

Both the sudoku solving procedure and the painting composition procedure can be thought of as variations of the wave function collapse algorithm.

Wave function collapse vs design solving

To summarize the wave function collapse algorithm follows these steps:

-       Define rules we want our solution to follow

-       Set up a notional solution space that contains all the possible states of all the possible decisions that can be made.

-       Make decisions that have a ripple-like effect on later decisions available.

-       This process is repeated until we get to a point where there is only one possibility for each decision, and that forms our end solution.

This structure is really similar to the way we solve certain design problems in the AEC industry. Let’s take as an example, designing the layout of an apartment in an empty floor plan. We usually start by, sometimes theoretically, determining a set of rules for how we intend to place elements/spaces in our floor plan. We then focus on a particular space or an item of furniture. For now let’s use the kitchen worktop as an example and determine all of the possible locations we could place it. If the rules for the kitchen worktop placement stipulate that it must be against a wall this limits the locations available for placement.

Once we choose a location for the kitchen, we proceed with the next element. If we want our dining table to be close to the kitchen, our decision on the location for the kitchen helps us limit the possible locations available for the dining table. By following similar rules systematically for the other pieces of furniture we can arrive at a final design solution.

This approach can be applied to many scenarios in the AEC industry as long as we have a clear set of rules and have defined relationships between our decisions. There are three sections of this method we can alter to solve diverse problems.

1)    Representation of cells: Cells can represented as numbers, colours, façade tiles following a pattern, objects in a room, trees in a landscape, etc.

2)    Rules of what should be acceptable/desirable: We may define not only adjacencies but also repetition, proximity to an entrance, etc.  

3)    Interactivity: We can decide what level of automation we want the user to experience, we can let the algorithm give plenty of solutions, or we can also guide some key decisions to alter results given by the algorithm.  

One thing is clear, and this is the same for many types of algorithms, we need to ensure we are choosing the right types of problems to adapt this algorithm for. Like genetic algorithms, this approach is capable of solving many problems, but there are always limitations. The first problem we may face is the creation of rules. Rules must be precise enough to take into consideration all design principles that create valid results, whilst still being flexible enough to be applicable in different scenarios. There are no guarantees that this method will be capable of delivering solutions, even if they are technically possible.

Using the Wave function collapse in an architectural design problem

Let’s start exploring potential architectural design scenarios where the wave function collapse algorithm could be used. An idea that came to mind, was dealing with zone allocation through a defined adjacency matrix.

If we imagine a hypothetical design scenario, the layout of an office. The designer is presented with an empty floor space and needs to allocate a list of people in the office space. To determine where individuals should sit, we may use an adjacency matrix, adjacency diagram, or explicit rules of what rooms are compatible. Since the wave function collapse is well suited to deal with adjacencies, we will use adjacencies as a driving force for our design solution.  

Going back to our example we can start with an empty rectangular floor. In this example, we will not consider the entrance to the building, or predefined fixed spaces such as bathrooms, escalators etc.

We have 8 people we want to fit in this office space. Each person has chosen a furniture arrangement for his/her office and somebody they find incompatible to be next to.

We will start by initializing our system by placing everybody in every available space. If we choose to allocate Eleanor in an available space, this will have a ripple effect in other available spaces affected by Eleanor. We can set this system to run automatically or manually guide certain placement decisions for the algorithm.

‍

‍