Introduction
This will be a wrap-up post for the city generator project. In it I will outline some of the decisions made over the project, evaluate them, and what I would do better next time. The goal is to try and look at the project with as much of an objective view as possible.
Aspects of the project
Code Base
The code itself, although structured in a generally easy to understand way, suffers from a lack of abstraction. The code is tightly coupled to work in the way intended and not as robust as I would like. An example of this is evident in the usage of the grid partitioning script, a very specific script. It has the potential for different amounts of partitions but is only made with the city preset in mind.
Inside the code is the potential for clean results, because I am using an established algorithm the steps are already defined to work on. Another result of the approach I took is that the base code for the grid and cells are reusable. Functionality such as finding Moore neighbourhoods in grids are attachable in a smooth way.
If I were to start the project again for some unknown reason, I would like to think that it would be easier for starters. But also that I would think less of making the structure and have more working to be able to add onto. Over the project I have focussed more on making code which is object orientated and understandable/readable. On one hand this made the main scripts where the algorithm functions non-monolithic. On the other hand, it took up a lot of time in the rapid prototyping stage, where the goal is to create a working algorithm.
There are parts of the better code aren't perfect too, bugs created by running the main loop can occur. One of these is the tendency to not work the same way when using the same seed, it will get to a point and a different choice will be made, even if the same seed is used. As well as that, the "backtracking" is more akin to a reset of the algorithm, which is not effective most of the time. Especially with more complex input models, using a version of backtracking with more efficacy would be far better.
Using nested coroutines as planned created some difficulties within the main script. Anytime the grid needed a search it had to be within a coroutine. Otherwise in the next frame it may not be complete and the next step will run, breaking the algorithm. Also coroutines cannot return a different type other than IEnumerator or IEnumerable. Meaning the search cant return a result to check against, although there are ways around it. If done again, I would probably still choose the same way, but have the coroutines be all declared at the top. Another small caveat is to restart the algorithm, instead of clear the grids' values, I stop all coroutines and start at the very beginning again which could be optimized.
I consider the quality of the code to be very high considering the limitations in time. As well as the complexity of learning Wave Function Collapse as a whole. The implementations available online are of a better quality in conciseness and efficiency. But that's expected due to the style of programming used with the aim to have a more easily understandable code-base.
Documentation
There are many parts of the project's documentation. The first one is blog posts which could be more detailed in how the project is setup, but gives an overarching view of what's been done.
But in the project files there is also documentation from Doxygen. Viewable in UserPDFs in HTML files, which cover the code in more depth. Adding this type of documentation is so users of the code can use it without needing to look at the code itself. Unity itself has the same system in place with their online documentation, you can also install it locally with versions of Unity.
The blog posts could be improved, sometimes they do not say as much as I would like them too. And my writing abilities aren't substantial enough to create long and good posts. They are successful at getting across the general points I want to say which is the reason for them.
User Experience
This is the aspect which is the weakest of the project in it's current state. Even thought there are options such as presets, the project in general was not created with a product in mind. This means that the current user experience is an example of possibilities, instead of a product which is commercially viable. As a demo it does a fine job of showing wave function collapse's strengths and weaknesses but as a product it's weak. Another way to improve upon this is to have a wider field of propagation with potentials considered, also adding more tiles so the areas can have easier connections (for the city preset).
Conclusion
In the project, I have successfully implemented a version of the Wave Function Collapse algorithm. The code used is readable and very understandable with documentation to aid. It also includes optimizations in the propagation step, when to calculate entropies and information storage. But, I have unsuccessfully made an overall commercial quality project. Due to a lack of refinement in the workflow when utilizing the algorithm. The code itself is it at a commercial standard given the scope and time spent, it's the rest of the project which lets it down.
The implementation of the algorithm was the main intent of the project, so it can is a general success. Unfortunately my stretch goals and ideas on the edge of the scope of the project didn't come to fruition but the core is still there to work on.
Future Work
Due to the simple structure of the code and the potential ability to refactor aspects without too much trouble. In the future, the code will need refactoring to be more robust and generally easier to add more implementations of sections. Beyond that improvement, genericising the code to allow for other implementations of the algorithm is an idea.
Once the project's code is complete, there's the potential for it to be a refined package to put onto the asset store. Another idea would be to use it to create a game, building levels with the algorithm. But currently it has fulfilled the original purpose of creating the project.
References Across The Project
1001 Free Fonts. 2021. Montserrat Font - 1001 Free Fonts. [online] Available at: <https://www.1001freefonts.com/montserrat.font>.
Adams, C. and Louis, S., Procedural maze level generation with evolutionary cellular automata, 2017 IEEE Symposium Series on Computational Intelligence (SSCI), 2017, pp. 1-8, doi: 10.1109/SSCI.2017.8285213.
Bfnightly.bracketproductions.com. 2021. Wave Function Collapse - Roguelike Tutorial - In Rust. [online] Available at: <http://bfnightly.bracketproductions.com/chapter_33.html>.
BorisTheBrave.Com. 2021. Wave Function Collapse Explained. [online] Available at: <https://www.boristhebrave.com/2020/04/13/wave-function-collapse-explained/>.
Braunschweig, D., 2021. Input-Process-Output Model. [online] Press.rebus.community. Available at: <https://press.rebus.community/programmingfundamentals/chapter/input-process-output-model/#:~:text=The%20input%E2%80%93process%E2%80%93output%20>.
Brumme, (., 2021. The Mersenne Twister Pseudo Random Number Generator. [online] Create.stephan-brumme.com. Available at: <https://create.stephan-brumme.com/mersenne-twister/>.
CodingForSpeed, Code Optimisation Tips, Faster than Faster, Don't Waste 1 CPU Cycle or 1 Byte. 2021. Using Faster Psudo-Random Generator: XorShift. [online] Available at: <https://codingforspeed.com/using-faster-psudo-random-generator-xorshift/>.
Docs.unity3d.com. 2021. About Unity Test Framework | Test Framework | 1.1.30. [online] Available at: <https://docs.unity3d.com/Packages/com.unity.test-framework@1.1/manual/index.html>.
Docs.microsoft.com. 2021. Using POCO classes - OData. [online] Available at: <https://docs.microsoft.com/en-us/odata/client/using-poco-classes>.
Docs.microsoft.com. 2021. Use breakpoints in the debugger - Visual Studio (Windows). [online] Available at: <https://docs.microsoft.com/en-us/visualstudio/debugger/using-breakpoints?view=vs-2022>.
En.wikipedia.org. 2021. Brute-force attack - Wikipedia. [online] Available at: <https://en.wikipedia.org/wiki/Brute-force_attack>.
En.wikipedia.org. 2021. Cellular automaton - Wikipedia. [online] Available at: <https://en.wikipedia.org/wiki/Cellular_automaton>.
En.wikipedia.org. 2021. Constraint programming - Wikipedia. [online] Available at: <https://en.wikipedia.org/wiki/Constraint_programming>.
En.wikipedia.org. 2021. Entropy (information theory) - Wikipedia. [online] Available at: <https://en.wikipedia.org/wiki/Entropy_(information_theory)>.
En.wikipedia.org. 2021. NaN - Wikipedia. [online] Available at: <https://en.wikipedia.org/wiki/NaN>.
En.wikipedia.org. 2021. Von Neumann neighborhood - Wikipedia. [online] Available at: <https://en.wikipedia.org/wiki/Von_Neumann_neighborhood>.
En.wikipedia.org. 2021. Moore neighborhood - Wikipedia. [online] Available at: <https://en.wikipedia.org/wiki/Moore_neighborhood>.
Farnam Street. 2021. Entropy: The Hidden Force That Complicates Life - Farnam Street. [online] Available at: <https://fs.blog/entropy/>.
GeeksforGeeks. 2021. Backtracking | Introduction - GeeksforGeeks. [online] Available at: <https://www.geeksforgeeks.org/backtracking-introduction/#:~:text=Backtracking%20is%20an%20algorithmic%2Dtechnique,reaching%20any%20level%20of%20the>.
GitHub. 2021. GitHub - BorisTheBrave/DeBroglie: DeBroglie is a C# library implementing the Wave Function Collapse algorithm with support for additional non-local constraints, and other useful features.. [online] Available at: <https://github.com/BorisTheBrave/DeBroglie>.
GitHub. 2021. GitHub - emilk/wfc: A C++ port of Wave Function Collapse Tiling. [online] Available at: <https://github.com/emilk/wfc>.
GitHub. 2021. GitHub - mxgmn/WaveFunctionCollapse: Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics. [online] Available at: <https://github.com/mxgmn/WaveFunctionCollapse>.
Grid Bugs. 2021. Procedural Generation with Wave Function Collapse. [online] Available at: <https://www.gridbugs.org/wave-function-collapse/>.
Holtby, J., 2021. [online] Available at: <https://assetstore.unity.com/packages/tools/utilities/doxygen-tool-13962>
Johnson, L., Yannakakis, G. and Togelius, J., 2010. Cellular automata for real-time generation of infinite cave levels. Proceedings of the 2010 Workshop on Procedural Content Generation in Games - PCGames '10,.
Keane, T., 2011. Partial Differential Equations versus Cellular Automata for Modeling Combat. The Journal of Defense Modeling and Simulation: Applications, Methodology, Technology, 8(4), pp.191-204.
Kenney.nl. 2021. Kenney • Car Kit. [online] Available at: <https://www.kenney.nl/assets/car-kit>.
Kenney.nl. 2021. Kenney • City Kit (Commercial). [online] Available at: <https://www.kenney.nl/assets/city-kit-commercial>.
Kenney.nl. 2021. Kenney • City Kit (Roads). [online] Available at: <https://www.kenney.nl/assets/city-kit-roads>.
Kenney.nl. 2021. Kenney • City Kit (Suburban). [online] Available at: <https://www.kenney.nl/assets/city-kit-suburban>.
Klugh, D., 2021. Humble Object Pattern | DevLead.io. [online] Devlead.io. Available at: <https://devlead.io/DevTips/HumbleObject>.
Khalili Araghi, S. and Stouffs, R., 2015. Exploring cellular automata for high density residential building form generation. Automation in Construction, 49, pp.152-162.
Knospe, W., Santen, L., Schadschneider, A. and Schreckenberg, M., 1999. Disorder effects in cellular automata for two-lane traffic. Physica A: Statistical Mechanics and its Applications, 265(3-4), pp.614-633.
Mazzolini, R., 2016. Procedurally generating surface detail for 3D models using voxel-based cellular automata. Master of Science. University Of Cape Town.
Medium. 2021. The intuition behind Shannon’s Entropy. [online] Available at: <https://towardsdatascience.com/the-intuition-behind-shannons-entropy-e74820fe9800>.
Merrell, P., 2021. Model Synthesis. PhD. University of North Carolina.
Oskarstalberg.com. 2021. Wave - by Oskar Stålberg. [online] Available at: <https://oskarstalberg.com/game/wave/wave.html>.
Paul Merrell - Engineer. Graphics Researcher. Model Synthesis Creator. 2021. Model Synthesis - Paul Merrell. [online] Available at: <https://paulmerrell.org/model-synthesis/>.
Rosettacode.org. 2021. Linear congruential generator - Rosetta Code. [online] Available at: <https://rosettacode.org/wiki/Linear_congruential_generator>.
Rosin, P., 2006. Training cellular automata for image processing. IEEE Transactions on Image Processing, 15(7), pp.2076-2087.
Scott, T., 2021. [online] Youtube.com. Available at: <https://www.youtube.com/watch?v=1cUUfMeOijg>.
Stålberg, O., 2021. [online] Twitter.com. Available at: <https://twitter.com/OskSta/status/793806535898136576>.
Stålberg, O., 2021. [online] Available at: <https://twitter.com/OskSta/status/1447494168448753667>.
Technologies, U., 2021. Unity - Manual: Coroutines. [online] Docs.unity3d.com. Available at: <https://docs.unity3d.com/Manual/Coroutines.html>.
Technologies, U., 2021. Unity - Manual: ScriptableObject. [online] Docs.unity3d.com. Available at: <https://docs.unity3d.com/Manual/class-ScriptableObject.html>.
Technologies, U., 2021. Unity - Manual: Unit Testing. [online] Docs.unity3d.com. Available at: <https://docs.unity3d.com/Manual/testing-editortestsrunner.html>.
Technologies, U., 2021. Unity - Scripting API: MonoBehaviour. [online] Docs.unity3d.com. Available at: <https://docs.unity3d.com/ScriptReference/MonoBehaviour.html>.
Wada, M., Kuroiwa, J. and Nara, S., 2002. Completely reproducible description of digital sound data with cellular automata. Physics Letters A, 306(2-3), pp.110-115.
Xiao, X., Shao, S., Ding, Y., Huang, Z., Chen, X. and Chou, K., 2005. Using cellular automata to generate image representation for biological sequences. Amino Acids, 28(1), pp.29-35.
Zucconi, A., 2021. Nested Coroutines in Unity - Alan Zucconi. [online] Alan Zucconi. Available at: <https://www.alanzucconi.com/2017/02/15/nested-coroutines-in-unity/>.
Comments