WaveFunctionCollapse

Wave Function Collapse

Role: research + programming
Size: solo
Time span: 2 months
Engine: Unity

About

A solo research project of my own choice!
Wafe Function Collapse is an algorithm commonly used for procedural conent generation such as levels, maps or even textures.
This project features a center square, with a tile system and flexible input. This page is an abbreviated version of my read.md of: git link

Short-form summary:

This project gave me the opportunity work out a research topic.
In this page you will find an explanation on how the project works, my thoughts after finishing it and what my I've learned.

There are two aspects I would emphasize when asked what I've learned in this project:
1. Practice documenting work
In DAE we work on many projects, but not that many we have to document. I think its extremely important that any project I work on, can be passed on to the next person responsible and it's not a treasure hunt for logical choices.
Practicing writing about not only the result, but also the general topic of this project saves time even for myself when looking back on it, and will be handy for those ahead of me.

2. Be critical of results, cons are as valuable to learn as pro's
In this project I experienced some up- and downsides (written down on the git-page and below). WFC showed me many upsides but also that its strengths lie in combining it with other algorithms.
I was very happy with my results, and could have left it at mentioning it works fine and is cool. But by not isolating the pro's, but taking into account the cons, I started to see the true value of WFC and how I would continue working on this project.

Introduction:

This was a solo project exploring a topic of my own choice!
It was an immensely hard choice to pick this over AI topics such as neural network programming and flow field.
What Quantum states are and the references I've used will be left on my Git page. On here I will delve more into my process and what I've learned.

Contents of the project

WFC Core

The core is the starting tile and the central script holding the grid.
It's my first time working with a C# multidimentional array. As shown on the image below I hold a list of directions that still need to be collapsed, aswell as an array of available directions. This was to leave the options open to go diagonal.
If I would do it again I would probably choose a Dictionary as an alternative as I see it as the C# equivalent of a map, making it easier to search.
WaveFunctionCollapse
This core goes through the following steps: 1. define the current x and y. 2. Add all nodes to the current nodes options. 3. in each direction, check the neighbours direction and check if its within the grid size. 4. if its valid, remove the nodes that are not compatible between that node and the current nodes list. 5. do a safety duplicate check. 6. Instantiate the node


Nodes and NodeConnections:

The Node and Nodeconnections are something I'm very proud of, but also something I still consider open to improvements.
The node decides what outputs it holds, such as a road going eastwards or water going southwards, aswell as its prefab.
WFC Node image
The node connections then has a name indicating what direction and type it is going to such as [Road Going Downwards]
This has all the nodes that are allowed to be placed under any tile that has a valid connection connecting to the road coming from above itself.
The system is reusable and easily expandable. The main downside and opportunity in the usage lays in it taking a little while to set-up, but is very easily modifyable, and easy to add new tiles to existing Nodes and connections. WFC NodeConnection image;

The results


The good

Easy to understand
-> The algorithm works very intuitively and the core concept personally doesn't feel hard to grasp
-> The way I built it made it very expandable and made the creation of new tiles not that hard
Versatile
WFC is not only used for levels, but can be used for anything that sequentially follows anything, in any dimention. Examples such as music
Result
The result makes for a cool landscape that can be further controlled by adding weights to the connections.
Compatibility with other algorithms
This seems like the main feature of WFC to me. It can offer both an awesome base template for a level, or be used to give some extra detail here and there.
Strong with itself
A big strength I can see here is that it gives me the feeling (I have not tried this) that it's even stronger when layered with itself. This can be through using smaller WFC'es to generate for example buildings, to then again use as templates in the larger WFC.

The bad

Things i disliked about - and felt lacking from working with WFC Fights itself
The algorithm either needs my version which is less reliant on Entropy, but is of lower quality, or quickly feels like an NP-Complete problem.
If there is a mistake made in the structure, it can be hard to debug. The key to avoiding this seemed like planning ahead with the observation method between nodes. (subjective point)
Also the result
I liked the results, but they were scattered and hard to control
The two main things i lack that give more controlability is a method of giving a starting input and weights, but from the results I've seen, they still are quite lackluster compared to manual placement for finer works.

The ugly

Use a Gridmap/Bitmap instead of a starting tile
I feel like it's not a WFC in the truest sense as i cannot give it a starting input, which is one of the big advantages on using this algorithm on a smaller scale
Weights
Another aspect I wish I added as it also gives more controlability over the output result

What did I learn?

1. How to document, and put it on a readme.md
  Noting down how to use a project and the process is a key factor to not repeating tasks and cooperating with other colleagues.
I personally am a big fan of x.y.z formatting for chapters, and is something I usually do. Reflecting on my own readme and improving on it helped me make it more clear by using imagery and focussing on what's important.
I am of the opinion that new documentation should be in-line and similar to existing documentation, but this project helped a lot in discovering my style of incorporating programming into how I documented for my previous degree.


2. Results are not restricted to positive ones, and negative conclusions can give even more insight
  I went into this project hoping to make a procedural tile system. I came out with one I wouldn't use in a game, but armed with more ideas and directions to get to an even better one.
The most important conclusion I came to was not how good/bad WFC is, but how intertwined it can work with other algorithms. The time I put into this project might have cost me a good chunk of time, but it also showed me the direction I'd go in if I'd make a procedural level system. I adore learning, so I love researching. After this project I'll try to stand still more after the project to look back, and not wrap it up and go to what then seems like the next appropriate project.

3. Think more about the visual structure and usage of a project
Because of my past experiences, I'm very experienced in creative thinking and visualising structures of code fast.
This however doesn't mean that it's always correct. My UI is very expandable, easily usable, but could still use simplification and more linking.
Drawing out, writing down and talking to peers about ideas helps greatly with finding improvements for the project.
One of my biggest strength is empathy and having a very good feeling of what people like, but when working on tools I should consider clarity vs quality.
I think I could have made a central controlling system for Nodes and NodeConnections, which is more work on the programming side, but would be well worth it.

Conclusion

WFC seems like a strong tool, yet weak on its own. It feels a bit too messy on a larger scale, but controllable enough to make solid rougher wholes, that can then be refined through other methods.
This project was a joy to work on, and has tingled my interest in proceduralism. Yet I do think that AI interests me more, which was one of my personal goals to discover for this project.
I think theres a lot of room for improvements, but I'd definitely be able to use the project for wilder, rougher landscapes.

From the research I've found I think there's still a lot more possibilities to be done with WFC to help gameplay programmers create fascinating mechanics, and not for it to be used predominantly as a general tool to apply art


Relevant Links

Git research page