Procedurální generování vesnic ve hře Minecraft pomocí algoritmu Wave Function Collapse

• Thesis title in Czech: Procedurální generování vesnic ve hře Minecraft pomocí algoritmu Wave Function Collapse
• Thesis title in English: Procedural Generation of Minecraft Villages utilizing the Wave Function Collapse Algorithm
• Key words: Procedurální generování obsahu|Wave Function Collapse|Generování vesnic|Minecraft
• English key words: Procedural content generation|Wave Function Collapse|Village generation|Minecraft
• Academic year of topic announcement: 2020/2021
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Software and Computer Science Education (32-KSVI)
• Supervisor: Mgr. Vojtěch Černý
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 19.01.2021
• Date of assignment: 19.01.2021
• Confirmed by Study dept. on: 10.01.2022
• Date and time of defence: 02.02.2022 09:00
• Date of electronic submission: 07.01.2022
• Date of submission of printed version: 10.01.2022
• Date of proceeded defence: 02.02.2022
• Opponents: Adam Dingle, M.Sc.

Guidelines

Generating large-scale 3D structures is a difficult task, due to the large state space and the difficulty of expressing mostly a large number of conditions for the final structures. The target of this thesis is to use a recent Wave Function Collapse (WFC) algorithm to create a village generator for Minecraft. For integration the student will use Minecraft Forge modding middleware. The thesis will include comparison of generated structures to default Minecraft villages as well as other Minecraft Village generators available.

The student will:

Implement a generic kotlin WFC library that is applicable to other uses besides village generation
Create a Village Generation Library (VGL) that uses the WFC library to generate diverse village models
Implement a Minecraft mod that uses the VGL and enables the user to generate villages in defined regions
Showcase generated villages
Compare results with existing village generators

References

Noor Shaker, Julian Togelius, and Mark J. Nelson (2016). Procedural Content Generation in Games: A Textbook and an Overview of Current Research. Springer. ISBN 978-3-319-42714-0.
Tanya X. Short and Tarn Adams. 2017. Procedural Generation in Game Design (1st. ed.). A. K. Peters, Ltd., USA.
Isaac Karth and Adam M. Smith. 2017. WaveFunctionCollapse is constraint solving in the wild. In Proceedings of the 12th International Conference on the Foundations of Digital Games (FDG '17). Association for Computing Machinery, New York, NY, USA, Article 68, 1–10. DOI:https://doi.org/10.1145/3102071.3110566
Michael Cerny Green, Christoph Salge, and Julian Togelius. 2019. Organic building generation in minecraft. Proceedings of the 14th International Conference on the Foundations of Digital Games. Association for Computing Machinery, New York, NY, USA, Article 80, 1–7. DOI:https://doi.org/10.1145/3337722.3341846
Bucklew, C. B., and Grinblat, J. 2019. Math for Game Developers: End-to-End Procedural Generation in ‘Caves of Qud’. https://www.gdcvault.com/browse/gdc-19/play/1026313.

Preliminary scope of work

Wave Function Collapse algoritmus Maxima Gumina generuje nové obrázky na základě poskytnutých ilustrací. Zamýšleným použitím algoritmu je generování obrázků ve stylu ilustrací tak, aby byla dodržena lokální podobnost ve výstupním obrázku se vstupním. Naše práce má za cíl generalizování původní myšlenky algoritmu pro použití v dalších doménách. Dále máme za cíl použití algoritmu na problém generování vesnic ve 3D sandboxové hře Minecraft. Výstupem práce bude generická WFC knihovna a Minecraft mod, který umožňuje generování struktur pomocí WFC. Doufáme, že naše WFC knihovna pomůže komukoliv s použitím WFC v rámci jakéhokoliv projektu v jazyku Kotlin a že náš Minecraft mod pomůže nastínit výhody a limity použití WFC algoritmu na komplexních úlohách.

Preliminary scope of work in English

Maxim Gumin’s Wave Function Collapse (WFC) algorithm is an example-driven image generation algorithm emerging from the craft of procedural content generation. The intended use of the algorithm is to generate new images in the style of given examples by ensuring local similarity. Our work aims to generalize the original work to make the algorithm applicable in other domains. Furthermore, we aim to apply it in a more difficult task of village generation in the 3D sandbox video game Minecraft. We will create a generic WFC library and a Minecraft mod, which will allow for structure generation using WFC. We hope that our WFC library will be beneficial to anyone exploring WFC and its applications in the Kotlin language and that our Minecraft showcase reveals some of the benefits and limits of the algorithm in complex problems.