Abstract

Met deze Bachelor-thesis streef ik naar het verder onderzoeken van Wave Function Collapse, een algoritme dat vaak voor level generatie benut wordt binnen Game Design. Er zijn al een aantal papers en theses rond Wave Function Collapse, die het op verschillende vlakken benaderen. Zelf ben ik de piste van het genereren van al bestaande levels opgegaan, om de mogelijkheden en limitaties verder op te zoeken. Allereerst ben ik zelf praktisch onderzoek begonnen, “kan ik zelf WFC implementeren?”, waarna ik dan met mijn eigen implementatie met casestudies aan de slag ben gegaan. Zelfs zonder al te veel moeite na het eenmaal implementeren van het algoritme kun je al snel bestaande levels nabootsen. De moeilijkheid ligt vooral bij het correct configureren van alle modules zodanig dat het naar de designer hun genoegen is.

Steekwoorden: Game Design, Wave Function Collapse, Algoritme, Level Generatie

Table of Contents

Introduction

Voor de Bachelor-opleiding Game Design onderzoek ik Wave Function Collapse. Dat is een algoritme dat binnen Game Design als tool voor het genereren van unieke levels toegepast word. In deze thesis streef ik om de volgende vragen te beantwoorden.

Hoe kan Wave Function Collapse gebruikt worden om herspeelbaarheid te verhogen?

Vooral bedoel ik hiermee, hoe ik het algoritme kan toepassen om levels te genereren, die designed zijn, maar nog steeds uniek.

Wat maakt een “designed” level uit?

Wat maakt een level “uniek”?

Ook de vraag hoe Wave Function Collapse in elkaar zit en werkt wordt in het verdere verloop van deze thesis beantwoord.

Eerst licht ik enkele games kort toe in State of the Art die Wave Function Collapse gebruiken, en andere spellen die ook op basis van procedurele generatie hun levels creëren. In het hoofdstuk Ontstaan ga ik verder in op de geschiedenis en van waar Wave Function Collapse komt. Praktisch Onderzoek licht verder toe hoe ik zelf met het algoritme aan de slag ben gegaan. Tot slot nog meerdere cases van al bestaande levels die ik naboots om de grenzen van deze technologie op te zoeken.

State of the Art

De eerste game die Wave Function Collapse (WFC) voor level generatie gebruikte was Proc Skater 2016 van Joseph Parker, Ryan Jones, en Oscar Morante. Als het over WFC gaat word Oskar Stålberg ook vermeld, die met Bad North 2018 en Townscaper 2021 WFC voor het genereren van 3D omgevingen populair heeft gemaakt. Op de Breda University of Applied Sciences Everything Procedural Conference 2018 gaf hij een presentatie rond WFC, waar hij WFC nader uitlegt en zijn implementatie in Bad North toelicht.

Stålberg gebruikt gedurende zijn talk de volgende terminologie:

• Modules zijn de tegels die op het veld gezet zullen worden. Zij bevatten de regels van hoe ze met elkaar samen mogen.
• Slots is iedere tegel in het grid wat gegenereerd zal worden. Elk van deze slots bevat een lijst aan mogelijke modules op basis van de regels voorheen vermeld.

In het verdere verloop van dit document volg ik deze terminologie op.

Bad North

Bad North is een real-time tactics spel, waar je met je gelimiteerde troepen op een klein eiland de aankomende vikingen moet afhouden. Het spel wordt gespeeld in campagnes, met een heleboel eilanden waar je de huizen moet verdedigen tegen de vikingen. Als speler controleer je je verschillende troepen, en kan deze wanneer je wilt van tegel verplaatsen, om zo zo goed mogelijk jezelf en de huizen tegen de vikingen te verdedigen. Er zijn een aantal verschillende troepen die je kunt vrijspelen: zwaardvechters, speerdragers, en boogschutters. Iedere troep heeft andere mogelijkheden, en het is aan de speler om deze zo goed mogelijk te benutten om de vikingen af te houden.

De reden waarom ik Bad North hier aanhaal, is vanwege de eilanden. Deze werden namelijk niet allemaal door de ontwikkelaar gemaakt, ze worden met onder andere Wave Function Collapse gegenereerd. Hij heeft een heleboel modules gemaakt die op bepaalde wijze naast elkaar mogen liggen, en aan de hand van die regels worden dan de levels gemaakt.

Om ervoor te zorgen dat ieder level een op zich eigen ervaring is, gebruikt hij een heel aantal modules die hij alleen soms aan zet. In Bad North werden een heleboel verschillende sets aan modules door Stålberg gestoken, en op basis van die sets worden de levels gegenereerd. Een voorbeeld hiervan zijn tunnels, dat is een collectie aan modules die in bovenstaande afbeelding aan stonden, maar onderstaande niet.

Townscaper

Townscaper is ook een spel van Stålberg, zelf noemt hij het meer speelgoed. In Townscaper gaat het erom gewoon gezellig een stadje te bouwen. Niet meer, niet minder.#

Hetgeen dat Townscaper uitmaakt, is het feit dat het stadje op basis van modules in elkaar gestoken word, en iedere keer als jij ergens een huisje plaatst, worden de modellen van alle geconnecteerde huisjes opnieuw berekend. Het verschil met Bad North is dat de modules niet per slot zijn, maar per hoek. Dit zorgt er ook voor dat het level waarop je bouwt niet een raster moet zijn, maar ook driehoeken, vijfhoeken, en zeshoeken kan bevatten.

Andere spellen

Ook andere spellen gebruiken procedurele level generatie. Spelunky 2008Spelunky is een roguelike, side-scrolling platformspel. genereert levels aan de hand van een vier bij vier grid, waar ieder element een ruimte krijgt, en op basis van het type ruimte wordt er een ruimte uit de handgemaakte lijst willekeurig gekozen en geplaatstIn het vier bij vier grid wordt boven begonnen en wordt iedere iteratie een richting gekozen in welke deze ruimte moet gaan (links, rechts, of onder). Aan de hand daarvan worden de ruimte types bepaald. Van zodra op de onderste lijn voor onder gekozen word, wordt bij de huidige ruimte het einde van het level geplaatst. De ruimtes die geen type toegewezen hebben gekregen, gaan ruimtes genereren die niet altijd zonder bommen of touwen bereikt kunnen worden.
Iedere ruimte heeft ook nog verdere aanpassingsmogelijkheden door middel van tegels die iedere ronde kunnen wijzigen, wat de levels nog dynamischer en unieker doorheen de rondes maakt..

1. Ontstaan

Wave Function Collapse is een algoritme origineel ontwikkeld door Maxim Gumin. Maxim Gumin’s versie neemt een kleine afbeelding als input, maakt hieruit een lijst waarvan ieder element een toestand van een voorbepaalde grootte voorsteld, en itereert dan door de elementen en collapsedCollapse in deze context betekent uit de mogelijke toestanden één willekeurig kiezen op basis van de gewichten die elke toestand heeft. deze, waarbij de naburige elementen bijgewerkt worden aan de hand van de nieuwe concretere informatie.

Bij het tonen van zijn interactieve demo WaveDie kun je via deze link zelf uitproberen: https://oskarstalberg.com/game/wave/wave.html. heeft Oskar Stålberg ook “constraint based programming” aangehaald. In de plaats van op basis van voorbepaalde groottes aan elementen een beeld te creëren, wordt er in Wave gekeken per tegel hoe het met andere tegels samenpast, in zijn geval op basis van kleuren aan de rand. Dit is ook hoe de level generatie in Bad North werkt, maar dan in 3D.

2. Praktisch Onderzoek

Met een basisverstand van WFC ben ik zelf aan de slag gegaan. Ik heb drie simpele modules gecreërd, en ze allemaal regels gegeven die bepalen in welke richting deze langs elkaar mogen bestaan.

Als volgt ben ik gaan kijken of ik voorgedefinieërde slots kan implementeren, en vooral hoe dat de resultaten beïnvloedt. Als een slot voorgedefinieërd is, heb ik als designer deze op voorhand bepaald, en is deze bij iedere keer dat je een level genereert hetzelfde. De voorgedefinieërde slots zorgen er voor dat ik als designer meer kan sturen hoe het level er gaat uitzien, terwijl het nog steeds iedere keer wat anders is, uniek.

Een level is uniek in mijn ogen wanneer het anders is als andere, en het een ervaring biedt die ook niet op te vinden is in andere levels. Dit zorgt voor dilemma’s waar ik als designer wel levels wil designen (door eventuele voorgedefinieërde slots, of het aanpassen van de gewichten per module) die iedere keer uniek zijn, maar ook de herspeelbaarheid wil verhogen door met bijvoorbeeld WFC levels te genereren, die dan wel uniek zijn qua opbouw en andere, maar niet per se op vlak van ervaring.

3. Nabootsing van bestaande Levels

Met het praktisch onderzoek naar mijn mogelijkheden achter de rug, ben ik gaan kijken hoe ik WFC kan inzetten om levels te genereren. Hiervoor heb ik inspiratie genomen uit bestaande games.

Super Mario Bros.

Super Mario Bros. heeft handgemaakte levels, die voor een bepaalde flow zorgen voorbepaald door de ontwikkelaars.

Met dit beeld als startpunt heb ik enkele tegels genomen en deze in mijn implementatie van WFC ingevoegd. Daarvoor heb ik de grond modules opgedeeld in 6 modules, namelijk de volledig omgeven module, de linker, rechter, en bovenste randen, en de twee hoeken tussen links-boven, en rechts-boven. Bijkomend zijn er nog de zwevende steen module en de lucht module (die door een kleine ruit in de video’s herkenbaar gemaakt is).

Onderstaande video gebruikt de zeven (eigenlijk acht) modules die boven vermeld werden, met redelijk arbitraire gewichten per module.

Voor de nogal willekeurige plaatsing van de zwevende stenen tegen te gaan, heb ik ook deze module nog twee variaties gegeven, een linker en rechter rand. De rode slots zijn voorbepaald door mij.

In onderstaande video gebruik ik nog steeds de negen eerder vermelde modules (of tien, als je de lucht module meetelt), maar heb de gewichten van iedere module zodanig proberen aanpassen, om dichter bij het inspiratiebeeld te komen.

Load Game

Legend of Zelda

Uit bovenstaande voorbeeld heb ik simpele modules geëxtraheerd. Allereerst heb ik met maar drie modules gewerkt, namelijk de bovenrand van de muur, onderste rand, en het gras.

Met dan een al wat duidelijker beeld over hoe en of het werkt, ben ik meer modules gaan implementeren. Om niet al teveel tijd te verdoen heb ik alleen de muren aan één kant geïmplementeerd, en hier de regels voor opgesteld. Eerst zonder dat de muren konden samenkomen, en daarna met. Dat is wat je hieronder ziet.

Load Game

De problematiek die hier nu boven komt, is de speelbaarheid van de levels. Ik kan zeker eender welk level genereren voor eender welk spel, maar kan ik van één punt naar een ander punt wandelen? Hoe kan een gegenereerd level speelbaar gemaakt worden?

Hier komen andere algoritmes bij kijken zoals bijvoorbeeld een pathfinding algoritme. Hiermee is het mogelijk om te checken of er tussen twee punten al dan niet een pad gaat.

Conclusion

De vraag waarmee ik begon was “Hoe kan Wave Function Collapse gebruikt worden om herspeelbaarheid te verhogen?”. Vooraleer ik hierop verder kon ingaan, ben ik eerst het ontstaan en de werking van het algoritme gaan onderzoeken (Ontstaan). Om mijn beperkte tijd zo goed mogelijk te benutten heb ik mijn focus gelegd op de herkomst van het algoritme (Maxim Gumin) en een ontwikkelaar die het algoritme aan de hand van zijn games populairder heeft gemaakt (Oskar Stålberg).

Op basis van redelijk kleinschalige prototypes ben ik gaan opzoeken wat de mogelijkheden en limitaties zijn van WFC. Hierbij heb ik veel aspecten van de voorbeeldgames laten vallen, die zeker van belang hadden kunnen zijn voor het al dan niet slagen van mijn onderzoek. De basis van mogelijkheden staat er, een meer gedetaileerde case study ontbreekt. Hierbij wil ik ook graag vermelden dat ik gedurende mijn onderzoek een interessante paper ben tegen gekomen, die het heeft over “Hierarchical Semantic Wave Function Collapse”, die volgens mij bij verder onderzoek definitief niet over het hoofd gezien kan worden.

References

Footnotes

Appendix

Acknowledgements

Mijn dank gaat uit naar Jeff Jacobs, die mij ondersteund heeft in dit bachelor-project.

Ook gaan bedankjes uit naar Unity, Aseprite, Visual Studio Code, en Blender, programma’s die ik gebruikte tijdens het prototypen.

Third Party Assets

In mijn prototypes heb ik gebruik gemaakt van:

• Sprites (afgeleid) van Super Mario Bros. (via MarioWiki)
• Sprites (afgeleid) van Legend of Zelda (via Wikipedia)

In deze thesis heb ik gebruik gemaakt van:

• Een geanimeerde afbeelding van Maxim Gumin (via GitHub)
• Schermafbeeldingen van Oskar Stålberg’s Wave demo (via oskarstalberg.com)