🤖 AI

Evolutionary Wave Function Collapse

Dit artikel stelt een evolutionair zoekframework voor dat de kleine inputvoorbeelden die worden gebruikt door Wave Function Collapse (WFC) optimaliseert om kwalitatief betere procedurele inhoud te genereren, waarbij wordt aangetoond dat deze aanpak de generatie effectief verbetert in domeinen waar globale eigenschappen voortkomen uit lokale beperkingen, zoals doolhofconnectiviteit en kerkers layouts.

Oorspronkelijke auteurs: Dipika Rajesh, Ahmed Khalifa, Julian Togelius

Gepubliceerd 2026-07-03

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Dipika Rajesh, Ahmed Khalifa, Julian Togelius

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een robot probeert te leren om een kaart te tekenen voor een videogame. Je hebt twee verschillende manieren om dit te doen, en dit artikel gaat over het proberen te mengen van deze twee om het beste van beide werelden te krijgen.

De Twee Benaderingen

1. De "Nabootsende" Robot (Wave Function Collapse)
Denk aan de eerste methode, genaamd Wave Function Collapse (WFC), als een zeer getalenteerde maar lichtelijk kortzichtige nabootser.

Hoe het werkt: Je laat de robot een klein vierkantje van 4x4 zien van een plaatje (zoals een klein stukje van een kerker of een doolhof). De robot kijkt naar hoe de tegels in dat kleine stukje aan elkaar grenzen (bijv. "een muur zit meestal naast een vloer").
Het Resultaat: Het gebruikt die kleine lokale regels om een enorme, complexe kaart te bous.
Het Probleem: De robot is "kortzichtig". Hij weet dat een muur naast een vloer ligt, maar hij begrijpt het grote plaatje niet. Hij weet niet dat de kaart één grote verbonden lus moet zijn, of dat er precies één sleutel en één deur moet zijn. Hij volgt alleen de lokale regels, wat soms leidt tot slordige of kapotte kaarten.

2. De "Trial-and-Error" Kunstenaar (Evolutionary Search)
De tweede methode is als een beeldhouwer die duizenden standbeelden maakt, de lelijke ervan weggooit en de goede bewaart om iets betere versies van te maken.

Hoe het werkt: Je genereert veel willekeurige kaarten, controleert welke leuk zijn om te spelen, en laat de beste "voortplanten" om nieuwe generaties te creëren.
Het Probleem: Dit duurt een hele lange tijd. Je moet de hele enorme kaart bouwen, testen, en dan weer opnieuw beginnen. Het is rekenintensief en traag.

Het Grote Idee: De "Genotype" en de "Phenotype"

De auteurs van dit artikel vroegen zich af: Wat als we de "Trial-and-Error" kunstenaar de kleine 4x4 patch laten ontwerpen, en de "Nabootsende" robot de grote kaart laten bouwen?

Ze behandelden de kleine 4x4 patch als het Genotype (het DNA of het blauwdruk) en de enorme kaart die de robot bouwt als de Phenotype (het eigenlijke levende wezen of het eindproduct).

In plaats van de hele enorme kaart te laten evolueren (wat traag is), lieten ze de kleine 4x4 patch evolueren. De "Nabootsende" robot (WFC) fungeerde als de machine die dat kleine DNA omzette in een volledige, grote level.

Het Experiment: Twee Verschillende Werelden

Ze testten dit idee in twee verschillende videogame-werelden om te zien of het werkte:

1. De Doolhof Wereld (Het "Lokale" Succes)

Het Doel: Een doolhof creëren waar je van start naar finish kunt lopen zonder vast te komen zitten.
Het Resultaat: Het werkte geweldig!
De Analogie: Stel je voor dat je een robot leert om een bakstenen muur te bouwen. Als je tegen de robot zegt "elke steen moet op twee stenen eronder rusten", zal de muur van nature sterk en verbonden zijn. Het "Doolhof"-doel (connectiviteit) is een lokale regel. Als de kleine patch goede lokale verbindingen heeft, zal de grote kaart van nature een verbonden doolhof zijn. De evolutionaire zoektocht vond snel de perfecte kleine patch die de robot uitstekende doolhoven liet bouwen.

2. De Zelda Wereld (De "Globale" Strijd)

Het Doel: Een kerker creëren met precies één speler, één sleutel, één deur en enkele vijanden, waarbij de speler daadwerkelijk bij de sleutel en de deur kan komen.
Het Resultaat: Het was veel moeilijker.
De Analogie: Stel je voor dat je een robot vertelt een huis te bouwen, maar je geeft hem alleen regels over hoe bakstenen tegen elkaar aan liggen. De robot kan een prachtig huis bouien, maar hij kan per ongeluk twee voordeuren bouwen of het dak vergeten. Het "Zelda"-doel vereist globale regels (bijv. "Er moet precies één sleutel in het hele gebouw zijn"). De kleine 4x4 patch "weet" niet van het hele gebouw. Zelfs hoewel de evolutionaire zoektocht de kaarten er georganiseerder uit liet zien, bleef de robot worstelen om het exacte aantal sleutels en deuren juist te krijgen, omdat hij alleen naar de lokale omgeving keek, niet naar het hele huis.

Wat Ze Vonden

Wanneer het werkt: Als het ding dat je wilt (zoals een verbonden pad) natuurlijk voortkomt uit hoe kleine stukjes in elkaar passen, is deze hybride methode fantastisch. Het vindt snel de perfecte "blauwdruk".
Wanneer het moeite heeft: Als het ding dat je wilt strikte, grote-plaatje-regels vereist (zoals "precies één sleutel" of het tellen van objecten over de hele kaart), loopt de methode tegen een muur aan. De "Nabootsende" robot heeft simpelweg niet het hersencapaciteit om het grote plaatje te begrijpen, hoe goed de kleine blauwdruk ook is.

De Conclusie

Het artikel concludeert dat je evolutie kunt gebruiken om een "kortzichtige" robot te leren betere kaarten te bouwen, maar alleen als de regels van het spel lokaal zijn. Als het spel strikte, globale regels nodig heeft (zoals "precies één sleutel"), is deze methode alleen niet voldoende. De robot heeft een manier nodig om naar de hele kaart te kijken, en niet alleen naar de kleine patch die hij op dat moment kopieert.

Technische Samenvatting: Evolutionary Wave Function Collapse

Probleemstelling

Procedurele Content Generatie (PCG) in videogames staat vaak voor een afweging tussen controleerbaarheid en schaalbaarheid. Wave Function Collapse (WFC) is een populaire methode voor het genereren van content op basis van lokale nabijheidsrestricties die zijn geleerd van kleine voorbeeldinputs. Hoewel WFC zelfvoorzienend en snel is, mist het een globaal begrip; het kan oplosbaarheid niet garanderen of globale restricties (bijv. specifieke aantallen entiteiten of bereikbaarheid tussen verre punten) afdwingen. Daarentegen staat Search-Based PCG (SBPCG) expliciete optimalisatie naar complexe doelstellingen toe, maar is het vaak computationeel duur en moeilijk te specificeren voor ontwerpers. Dit onderzoek onderzoekt of deze benaderingen gehybridiseerd kunnen worden: specifiek, of evolutionaire zoektocht gebruikt kan worden om de inputs (de kleine voorbeeldafbeeldingen) te optimaliseren die aan WFC worden geleverd, in plaats van de uiteindelijke levels direct te evolueren. Dit behandelt WFC als een stochastische genotype-naar-fenotype mapping.

Methodologie

De voorgestelde methode, Evolutionary Wave Function Collapse, evolueert compacte inputafbeeldingen (genotypes) die dienen als de kiem voor WFC om grotere gamelevels (fenotypes) te genereren.

Representatie: Individuen in de populatie worden gerepresenteerd als kleine $4 \times 4$ tegelgrids. Deze grids worden geïnitialiseerd met willekeurige tegels uit de tileset van het doelspel.
Genotype-naar-Fenotype Mapping: De $4 \times 4$ input wordt door het WFC-algoritme gehaald. WFC extraheert alle $2 \times 2$ nabijheidspatronen uit deze input en gebruikt deze als restricties om een groter output-level te genereren. De generatie is stochastisch; hetzelfde genotype kan verschillende outputs produceren op basis van de willekeurige seed.
Geëvalueerde Domeinen:
1. Maze Domain (Doolhof-domein): Genereert $8 \times 8$ kaarten. De fitnessfunctie beloont een enkel verbonden begaanbaar gebied en lange begaanbare paden.
2. Zelda Domain: Genereert $16 \times 16$ dungeon-lay-outs. De fitnessfunctie is een gewogen som ( $0,7 \cdot R_{entity} + 0,3 \cdot R_{play}$ ) die specifieke entiteitsaantallen beloont (één speler, één sleutel, één deur, tot maximaal 25 vijanden) en speelbaarheid (bereikbaarheid tussen speler, sleutel en deur).
Evolutionaire Zoektocht: Het systeem gebruikt een evolutionair algoritme met tournament selection (omvang 3), mutatie en elitism.
- Populatie: Omvang van 10 over 100 generaties.
- Mutatie: Tussen de 1 en 5 tegelposities worden per nakomeling gemuteerd. De mutatiekans ( $p$ ) begint op 0,5 en past zich aan op basis van fitnessverbetering om exploratie en exploitatie in evenwicht te houden.
- Baseline: De methode wordt vergeleken met een Random Search baseline waarbij populaties in elke generatie willekeurig worden opnieuw gesampled, waarbij de beste chromosomen behouden blijven.

Belangrijkste Resultaten

De studie evalueert de effectiviteit van deze hybride benadering in domeinen met variërende afhankelijkheden tussen lokale en globale structuren.

Maze Domain (Lokale structuur dominant):
- Evolutionaire zoektocht presteerde aanzienlijk beter dan random search en convergeerde snel naar hoogpresterende inputs binnen de eerste 40 generaties.
- Geëvolueerde outputs vertoonden coherente, verbonden lay-outs met lange continue paden.
- De resultaten suggereren dat gewenste eigenschappen zoals connectiviteit natuurlijk ontstaan uit herhaalde lokale nabijheidsrelaties, wat dit domein zeer compatibel maakt met de WFC-representatie.
Zelda Domain (Globale structuur vereist):
- Evolutionaire zoektocht produceerde meer gestructureerde outputs dan random search (bijv. herkenbare kamers, betekenisvolle plaatsing van entiteiten) en bereikte hogere fitnesswaarden.
- Echter, het prestatieverschil was kleiner dan in het Maze-domein.
- Het systeem had moeite met het gelijktijdig voldoen aan strikte globale restricties (specifiek het garanderen van exact één speler, één sleutel en één deur).
- Fitnesscurves vertoonden een vroege snelle verbetering gevolgd door stagnatie nabij een lokaal optimum, wat aangeeft dat de afhankelijkheid van WFC van lokale patronen het vermogen beperkt om globale gameplay-afhankelijkheden te modelleren.

Betekenis en Claims

Het artikel claimt dat Evolutionary Wave Function Collapse een effectieve strategie is voor het sturen van procedurele generatie wanneer doelstellingen overeenkomen met lokale structurele regelmatigheden.

Hybride Voordeel: De aanpak combineert succesvol de compacte representatie en snelheid van WFC met de optimalisatiecapaciteiten van evolutionaire zoektocht.
Domeinafhankelijkheid: De methode is het meest effectief in domeinen waar globale eigenschappen (zoals connectiviteit) indirect voortkomen uit lokale relaties. Het is minder effectief in domeinen die expliciete, symbolische globale restricties vereisen (zoals specifieke entiteitsaantallen of progressievolgorde), omdat WFC deze globale afhankelijkheden niet inherent modelleert.
Beperkingen: De auteurs erkennen dat de stochastische aard van WFC ruis introduceert in de fitnessevaluatie (aangezien elk genotype slechts één keer werd geëvalueerd). Bovendien blijft de lokale aard van WFC een fundamentele beperking; evolutionaire zoektocht kan de onmogelijkheid van het onderliggende model om globale regels direct af te dwingen niet overwinnen.

Het artikel concludeert dat hoewel deze methode de kwaliteit en organisatie van de generatie verbetert, toekomstig werk de mogelijkheid moet verkennen om expliciete mechanismen voor het oplossen van globale restricties te integreren in de evolutionaire WFC-pipeline om domeinen te adresseren die strikte symbolische restricties vereisen.