During this project, I want to do the practical parts of my BSc thesis "Procedural Generation of Unique Buildings". My thesis is about combining different procedural generation techniques to create a new algorithm for generating buildings. The practical parts of the thesis include:
- Implementation of Wave Function Collapse (WFC) algorithm
- Modifications of the WFC
- Implementation of the shape grammars
- Modifications of the shape grammars
- Demonstration mini-projects for WFC and shape grammars
- Generating houses for examples in the thesis
I can not guarantee that I will do all of the above, but this project will definitely help with my thesis. The project will be written in C# and I am using Unity. I foresee that shape grammars will be the most difficult part of this project because there is no solved way to implement them. 3D modeling will be difficult as well since the shapes need to be parametric.
The goal of this project is to have a code for WFC and shape grammars, code for my own algorithm, and some demonstrations for the thesis.
Maxim Gumin's repository for WFC: https://github.com/mxgmn/WaveFunctionCollapse
George Stiny's text about shape grammars: http://www.andrew.cmu.edu/user/ramesh/teaching/course/48-747/subFrames/readings/Stiny-1980-EPB7_343-351.IntroductionToShapeAndShapeGrammars.pdf
Milestone 1 (05.03)
- Make a visual demo for WFC (6h)
- Improve the WFC with the help of the visual demo (2h)
- Find some implementations of shape grammars (1h)
For the first task, I decided to create a program that takes an example of a tilemap, learns what tiles can be next to each other, and then tries to create a similar output.
For my first attempt, I tried to imitate this picture:
And my program produced this:
Then I tried with a more complex picture:
And the output was this:
It seems like the reference picture has been upscaled by the factor of two (see the fence corner in the output, it is 1/4 of the correct tile). When I tried to do the same with the doubled tile size, it ran into an impossible state.
Regardless, the results are quite boring. It seems that early on a tile is selected which can only have itself next to it, making all the tiles below it the same tile. Right now, all the tiles have the same weight. Perhaps if I set the weights to something different, the output would be more interesting?
After adding the custom weights, the results are much the same. I think the problem might be that I am merging tiles with different adjacencies into one wave, but they should be different waves. For example, a green tile that is next to the blue tile should be a different tile than a green tile that is next to a red tile.
It seems that the program is out of the scope of my project. So I just took a tilemap and defined the connections myself. This is the tilemap (source):
And the first production was this:
It seems like there are some seams! There is definitely a bug in my code.
There are still some boring parts, so I checked out the selection logic and discovered it was broken. Namely, I have started to use the Shannon Entropy, but the selection presumes that I am still using the possibility space size as the entropy. So I tried to fix it, but then it enters an impossible state. Needs more fixing!
I fixed the selection logic. Now the picture looks more random:
The problem was that I was using LUT for getting the sum of weights faster, but the data in LUT was wrong. Currently, I am just recalculating the sum with for loop each time. For the algorithm to work faster, I have to fix the LUT later.
But there are still seams. I seemed to mix the eastern and western T-junctions, after the fix, everything is perfect:
In regards to the implementation of shape grammars, I found two good resources. Firstly, Shapes, structures and shape grammar implementation by Iestyn Jowers, Chris Earl, and George Stiny. This paper discusses the limitations of current implementations. Then AI EDAM special issue: Advances in implemented shape grammars: Solutions and applications by Sara Eloy, Pieter Pauwels, and Athanassios Economou, which lists many implementations and discusses the difference between theoretical and real implementations.
I also think that split grammars will be much easier to implement than shape grammars since no new shapes can emerge.
Milestone 2 (19.03)
- Fix WFC weights LUT (2h)
- Implement a simple split grammar (6h)
- Keep working on the imitator (optional)
The problem with LUT was that when I was constructing the keys, I used left-shift and or-ed with 1. This means that earlier waves were placed onto more significant bits than later waves. But I have organized it as the least significant bit first. The fix was to flip the construction of the key, using the right-shift and or-ing with 128. Now the operation of summing the weights of the wave function is 8 times faster than before, and since it is one of the most used operations in the algorithm, it should speed the WFC up, especially with big grids.
I think the most problematic part of the algorithm is the ClassSet because I am making a new class for each of the entropies. This is potentially tens of thousands of classes, so tens of thousands of sets. That is a lot of dynamic allocation, and we all know that using memory is the slowest part of any program. I think the ClassSet should be implemented so it works with ranges of classes, instead of each class individually. Right now, entropies of 100, 1000, and 1002 all get their own class. But if I distribute them into bins, then 100 would be in one class, and 1000 and 1002 would be in the other. Of course, then the elements in each bin have to be sorted... Perhaps use a heap. More research is needed.
Split grammars were developed by Wonka et al: paper.
It turns out that split grammars are not unlike L-systems. I implemented the grammar with classes (types) as symbols, so they can carry attributes easily. Here is one of the outputs with the rule to add a quad where the vertices are the parent's edges' bisection points. The grammar works by replacing the original shape with a new quad and four triangles.
When I added another rule, which splits the quad into 4 equal rectangles, and added more iterations, we get some interesting results:
This is just the split grammar part, but Wonka et al. also developed attribute propagation, rule selection, and control grammars. Some of these will be developed in the next milestone.
Milestone 3 (09.04)
- Add the attribute propagation and rule selection logic to the split grammar (4h)
- Start implementing my thesis algorithm (10h)
- Optimize WFC ClassSet (2h)
Before I implemented the attribute matching, I added two other features to my split grammar: terminal shapes and epsilon. Firstly, terminal shape is a shape that will not be interpreted further, meaning that that shape will be included in the final product. In other words, this shape is not in any rules' LHS. Secondly, epsilon is a 'shape' that is void. If the epsilon is in the RHS of the rule, the production of that rule is empty. This is a way to remove space from the result.
Implementation of the attribute matching was quite straight forward. I created a dictionary which binds the rules and their attributes. There are four types of attributes: DefaultAttribute, which is [-infinity, +infinity], ScalarAttribute, which is a singular scalar [x, x], RangeAttribute, which is a range [x, y], and StrictAttribute, which is also a range [x, y]. The attributes match if they overlap, except StrictAttribute, which requires that the comparable fits into the comparer ([x_c, y_c] \in [x, y]). Adding new types of attributes should be easy, since they are based on IAttribute interface.
For a simple example, I added three new rules to my previous ruleset. Triangles have two new rules: T->D, where D is a terminal version of T, and T->epsilon. The quads have one new rule: split the quad into two. I use attributes for the split rules. If attribute "Angle" is 0, I split the quad into 4, if it is 1, I split the quad into 2. The attribute "Angle" alternates between 0 and 1 when the rotate quad rule is used. Here are some productions:
The ClassSet was indeed replaceable with a Heap. There was one difficulty. Namely, I used two ClassSets at the same time, one for selecting the next tile to collapse, and one for propagating that collapse. But during the propagation phase, I had to change the values in the first ClassSet (since the propagation changes entropy values). So I added support for changing the keys in the heap by using a dictionary, which keeps track of the tiles and on what indices they are situated in the heap. Changing the entropy value in the heap has O(logn) complexity, which is the same as adding/removing. The algorithm is quite fast. Producing 300x300 tiles took approximately 15 seconds. 40x40 is almost instant.
I migrated my algorithm to the graph, but it currently does not support context-sensitive rules. Adding context-sensitive rules is difficult, since I am using Types as symbols, and C# does not support a variable-length list of generic arguments. I have to come up with "contextual shapes", which represent multiple shapes as a single shape. This is also necessary since one can not convey attributed connections between shapes with a regular list.
The algorithm is noticeably slower. One possible suspect is the graph search. Although it currently only supports context-free rules (and so the search is O(n)), it is still slow because the search is performed before every replacement. It can be parallelized. The other suspect is just a big reliance on memory: many places use and allocate HashSets and Lists. I will not optimize the algorithm unless it is really necessary.
Milestone 4 (23.04)
- Add control grammars (2h)
- Add WFC (4h)
- Add Symmetry (3h)
- (Optional) Add context-sensitive rules (3h)
Implementing the control grammars was quite straightforward. I use strings as symbols, and terminals are tuples (locator, attribute, value, next), where locator specifies which shape of the split needs to change, attribute indicates what attribute to changes, value is the new value of that attribute, and next is a control symbol that is attached to that shape. The locator of a shape has to be specified in the split operation since it is impossible to determine a 'grid' layout (e.g look at the diamond replacement -- the four triangles and the quad in the middle do not form a logical coordinate grid). One problem I had with the implementation was that although the grammar assigned the new attributes, somehow every new shape had the same attributes. The solution was to create a copy of the attribute object for each new shape since we do not want them to share attributes (although, might come in handy when implementing the virtual connection).
Adding WFC was a bit more tricky. There were many sneaky bugs that slowed me down; I need to keep a better track of my objects, what can be changed and what is shared, etc. I decided to implement WFC as a second step in the control pipeline, activated after the control grammar. When the control grammar discovers a symbol that is not in LHS of any control grammar rule, it sets that symbol as an activator. Each WFC instance has an activator symbol attached to it, meaning that the grammar can determine when to evoke any specific WFC. In the following example I created a new grape grammar with four rules:
- Take a quad and split it into four equal quads (Quad -> Quad)
- Take a quad and split it into three triangles that are terminals (Quad -> Triad Triad Triad)
- Take a quad and split it into three equal quads that are terminals (Quad -> Bar Bar Bar)
- Take a quad and split it into eight triangles and an empty plus shape (Quad -> Triad Triad Triad Triad Triad Triad Triad Triad)
I also attach an attribute "Wave" to each rule: rule number 1 has 0, 2 has 1, etc. This is for enumerating the rules. Then a control grammar has one simple rule: S -> WFC1. This means that on a symbol S, evoke WFC1 on the split shapes. Finally, I created a WFC ruleset that distributes the "Wave" attribute thusly: 0 can be next to 1 and 2 (Quad next to 3xTriad or 3xBar), 1 can be next to 0, 2, and 3 (3xTriad next to Quad, 3xBar, and 8xTriad), 2 can be next to 0, 1, and 3, and 3 can be next to 1 and 2. In the pictures, it can be seen that in the same split, the Plus shape is never next to the Quad that is split into four equal quads.
This is a simple example. More complex uses will be created for the thesis. I also implemented a feature where an initial wave function can be set by using the control grammar. This way some features can be enforced (eg. a mandatory door at the (0, 1) location).
I implemented a simpler version of the symmetry, which just requires setting a boolean. That boolean determines whether the X-axis is flipped. Then it just checks whether the shape is symmetrical on the x-axis. If it is, a virtual connection between two identical shapes can be formed. When a split is performed on the virtually connected shapes, it is performed on both shapes. Currently, the connection does not persist after the split. This gives interesting results:
Some interpretations might seem to break that symmetry (can you figure out how?):
Unfortunately, I did not create any examples for my thesis. The control grammar, WFC, and symmetry took up all my time. But making illustrations will be my main focus during the next two weeks (and weekends..).
Milestone 5 (07.05)
- Streamline the symmetry (2h)
- Make examples and illustrations! (6h)
The symmetry was indeed streamlined. Now WFC and control grammar can be used in tandem with entanglement! One of the pictures below takes advantage of it (the failed one with two roofs).
I created a function for automatically illustrating rules. I used the same tools I have already been using to draw the lines: the C# Graphich object. It also supports printing text onto an image:
But it is not quite agreeable with small shapes and terminals are weird:
Fixing the terminal rules was simple. I just made a copy of the LHS of the rule and drew it without the symbol:
As my thesis refers to Kvartal a lot, I had to make an example production similar to it.
Finally, I had some mishaps along the way. Here are some interesting outputs...
Milestone 6 (21.05)
- Make an 'animation' of the derivation process (4h)
- Make the program easier to use (3h)
At first, I tried to create the animation within C#, but I found out quickly how non-trivial it is. Firstly, all the libraries that have been used for that purpose are deprecated and are for older .NET versions (I use 5.0, which is quite new). Secondly, the libraries that do exists are quite difficult to install on Linux (Emgu OpenCV). After messing with that for few hours I decided that I can make a simple Python script instead, which only took 10 minutes! Here is one of the first animations:
Here is the derivation process for the Kvartal example. This is very nice!
Finally, I have decided to not make the program easier to use, since the project was for creating a proof of concept of my algorithm and to produce illustrations. Said goals have been achieved and I believe that the software should not be used in further projects. Instead, a new project should be created which supports 3D and has an intuitive GUI.