Login
- Pseudo
- Code
Login
Register

Wave function collapse

on October 29, 2024

Introduction : Qu'est-ce que le Wave Function Collapse ?

Le Wave Function Collapse (WFC) est un puissant algorithme de génération procédurale qui suscite un vif intérêt dans le développement de jeux et la création de contenu. Bien qu’il s’inspire de concepts en mécanique quantique, le WFC est accessible et offre des applications uniques pour générer des motifs, des cartes et des mises en page suivant des règles spécifiques.

En physique, une fonction d’onde représente tous les états possibles dans lesquels une particule pourrait exister simultanément, et « s’effondre » en un seul état lors de l’observation. De manière similaire, l’algorithme WFC commence avec de nombreux états potentiels pour chaque tuile ou cellule et réduit progressivement chaque option en appliquant des contraintes, jusqu'à ce qu’une seule solution valide émerge.

Ce guide vous expliquera comment fonctionne le WFC, ses applications et comment l'utiliser avec PHP – un langage pas forcément associé à la génération procédurale, mais tout à fait capable de la gérer.

Comment fonctionne l'algorithme de Wave Function Collapse ?

L’algorithme WFC est un solveur basé sur des contraintes qui s’assure que les cellules voisines suivent des règles spécifiques. Ces règles peuvent représenter des exigences d’adjacence de tuiles dans un jeu, voire des contraintes de mise en page pour éviter le chevauchement d'éléments visuels.

Concepts de Base

Entropie : Dans le WFC, l’entropie désigne le nombre d'états valides restants pour une cellule. Une cellule avec une faible entropie a peu d’états possibles, tandis qu'une cellule avec une forte entropie en a plusieurs.
Propagation : Au fur et à mesure que les cellules s’effondrent, elles influencent leurs voisines en limitant les états que celles-ci peuvent avoir, réduisant ainsi leur entropie.
Effondrement : L’algorithme choisit toujours une cellule avec la plus faible entropie, l’effondre en un seul état, puis propage ce changement aux cellules voisines. Ce processus continue jusqu'à ce que toutes les cellules soient effondrées ou qu’une contradiction soit détectée.

Le WFC en Action

Voici une vue d’ensemble étape par étape du fonctionnement de l'algorithme WFC :

Initialisation : Chaque cellule commence avec tous les états possibles (par exemple, dans une carte en tuiles, une cellule pourrait représenter des options comme mur, sol, eau, etc.).
Sélection de la plus faible entropie : Choisir la cellule avec le moins d’états possibles (la plus faible entropie).
Effondrement de la cellule : Sélectionner au hasard l’un des états valides restants.
Propagation des contraintes : Mettre à jour les cellules voisines pour éliminer les états qui ne sont plus valides en fonction de la cellule effondrée.
Répéter ou gérer les contradictions : Si toutes les cellules s’effondrent avec succès, vous avez une solution. Sinon, il faudra gérer les contradictions.

Visualiser le WFC

Imaginez que vous résolvez un puzzle où chaque tuile doit s’ajuster parfaitement à ses voisines. Au départ, chaque cellule a plusieurs options de tuiles, mais à mesure que vous placez des tuiles, vous réduisez les choix des cellules environnantes jusqu'à ce que seules des configurations valides restent.

Implémenter le WFC en PHP : Guide Étape par Étape

Bien que PHP ne soit peut-être pas votre premier choix pour la génération procédurale, il fonctionne bien pour les projets web et la génération dynamique de mises en page. Voici comment implémenter le WFC en PHP.

Définir les Tuiles et Contraintes

Tout d'abord, nous définissons une classe Tile en PHP, où chaque tuile a des contraintes qui spécifient avec quelles autres tuiles elle peut être adjacente. Par exemple, une tuile « eau » peut être autorisée uniquement à côté de « eau » ou de « sable ».

class Tile {
    public $name;
    public $constraints;

    public function __construct($name, $constraints) {
        $this->name = $name;
        $this->constraints = $constraints;
    }
}

Initialiser la Grille

Ensuite, nous créons une grille où chaque cellule commence avec tous les états de tuile possibles :

$grid = array_fill(0, $width, array_fill(0, $height, ['eau', 'sable', 'forêt', 'montagne']));

Propager les Contraintes

Pour refléter l’état de chaque cellule, nous définissons une fonction qui met à jour les cellules voisines en fonction des contraintes d’une cellule effondrée.

function propagateConstraints(&$grid, $x, $y, $tile) {
    $directions = [
        'gauche' => [-1, 0],
        'droite' => [1, 0],
        'haut' => [0, -1],
        'bas' => [0, 1]
    ];
    foreach ($directions as $direction => $offset) {
        $dx = $x + $offset[0];
        $dy = $y + $offset[1];
        if (isset($grid[$dx][$dy])) {
            $grid[$dx][$dy] = array_intersect($grid[$dx][$dy], $tile->constraints[$direction]);
        }
    }
}

Effondrer la Cellule avec la Plus Faible Entropie

Nous sélectionnons la cellule avec la plus faible entropie, l’effondrons, puis propageons les contraintes aux cellules voisines.

function getLowestEntropyCell($grid) {
    $minEntropy = PHP_INT_MAX;
    $bestCell = null;

    foreach ($grid as $x => $row) {
        foreach ($row as $y => $cell) {
            if (count($cell) < $minEntropy && count($cell) > 1) {
                $minEntropy = count($cell);
                $bestCell = [$x, $y];
            }
        }
    }

    return $bestCell;
}

function collapseCell(&$grid, $x, $y) {
    $possibilities = $grid[$x][$y];
    if (empty($possibilities)) {
        throw new Exception("Contradiction détectée en [$x, $y]");
    }
    $choice = $possibilities[array_rand($possibilities)];
    $grid[$x][$y] = [$choice];
    propagateConstraints($grid, $x, $y, new Tile($choice, []));
}

Exécuter l'Algorithme

Pour terminer, nous exécutons l’algorithme jusqu’à ce que toutes les cellules soient effondrées.

while ($cell = getLowestEntropyCell($grid)) {
    list($x, $y) = $cell;
    collapseCell($grid, $x, $y);
}

// Afficher la grille
foreach ($grid as $row) {
    foreach ($row as $cell) {
        echo $cell[0] . ' ';
    }
    echo PHP_EOL;
}

Si une contradiction se produit, là où une cellule n’a pas d'options valides, vous pouvez essayer de revenir en arrière ou de redémarrer de manière aléatoire.

Gérer les Contradictions

Les contradictions surviennent lorsque les contraintes d’une cellule lui laissent aucun état valide. Pour y remédier, vous pouvez :

Revenir à un état précédent et essayer une autre option.
Redémarrer le processus avec des conditions initiales différentes.
Ajuster les calculs d’entropie pour éviter les contradictions plus tôt.

Exploration d’Autres Algorithmes de Génération de Cartes

Au-delà du WFC, il existe de nombreux autres algorithmes de génération procédurale, chacun étant adapté à des tâches spécifiques comme la génération de terrain, les formes organiques ou les structures complexes. Voici un aperçu de quelques alternatives :

Perlin & Simplex Noise : Idéal pour générer des terrains lisses et naturels comme des montagnes et des vallées.
Automates Cellulaires : Parfait pour créer des structures de grottes organiques.
Diagrammes de Voronoi : Utile pour diviser un espace en régions basées sur la proximité de points, parfait pour la génération de biomes.
L-Systems : Souvent utilisés pour créer des structures de branchement naturelles comme des arbres.
Génération de Donjons : Des algorithmes comme la partition binaire (BSP) et la marche aléatoire créent des pièces et des couloirs pour des structures de type donjon.

Chacun de ces algorithmes a des forces uniques, donc le choix dépend des besoins et des contraintes du projet.

Applications du Wave Function Collapse

Le WFC a une gamme d’applications :

Développement de jeux : Générer des cartes de tuiles cohérentes, des niveaux ou des cartes.
Génération d'images : Créer des motifs et textures qui suivent des règles d'adjacence spécifiées.
Plans de villes : Générer des mises en page où certaines structures doivent coexister.
Création de puzzles : Concevoir des puzzles comme le Sudoku ou des mots croisés qui reposent sur des règles d'adjacence.

Le Défi Technique avec Symfony UX

Intégrer l’algorithme WFC dans une application Symfony implique des défis uniques. Comme Symfony UX est conçu pour des expériences utilisateur réactives, il est essentiel de gérer les mises à jour continues d’une grille générée dynamiquement à mesure que WFC progresse. Ici, les composants LiveComponent et la gestion asynchrone de Symfony UX contribuent à créer une expérience fluide pour visualiser le WFC tout en garantissant des performances stables.

Un élément crucial de cette implémentation est Flow, un framework d’orchestration visuelle des données. Flow améliore considérablement la réutilisabilité et la modularité, des clés pour gérer des processus de génération procédurale complexes. Par exemple, chaque tâche du WFC, de l'effondrement des cellules à l'application des contraintes, est encapsulée comme une unité modulaire dans Flow. Cette approche simplifie le code et permet de réutiliser les fonctionnalités du WFC dans différents contextes, que ce soit pour des ensembles de données variés ou des tailles de grille différentes, avec peu de modifications.

Demo et sources

Voici une vidéo concrète générée par l'algorithme

Le code de cette implémentation Symfony est disponible ici : https://github.com/matyo91/flow-live

Conclusion

Le Wave Function Collapse est un outil fascinant pour la génération procédurale, combinant contraintes et aléatoire pour créer des sorties cohérentes et visuellement plaisantes. Bien que PHP ne soit pas forcément le premier langage auquel on pense pour le WFC, il est plus que capable de gérer l’algorithme, ouvrant des possibilités intéressantes pour la génération de contenu procédural sur le web.

Le WFC a de vastes applications, allant des jeux à la conception graphique en passant par la mise en page. Maîtriser cet algorithme ouvre la voie à la création de mondes et de motifs générés par algorithme, à la fois complexes et esthétiquement attrayants.

Ressources

Explorez ces ressources pour approfondir votre compréhension du WFC et des techniques de génération procédurale.

Wave function collapse on Wikipedia General : https://en.wikipedia.org/wiki/Wave_function_collapse
Wave function collapse on Wikipedia Algorithm : https://en.wikipedia.org/wiki/Model_synthesis
WaveFunctionCollapse Github : https://github.com/mxgmn/WaveFunctionCollapse
Coding Challenge 171 Wave Function Collapse : https://www.youtube.com/watch?v=rI_y2GAlQFM
Wave Function Collapse Explained : https://www.boristhebrave.com/2020/04/13/wave-function-collapse-explained
The Wavefunction Collapse Algorithm explained very clearly : https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm
The fascinating Wave Function Collapse algorithm : https://dev.to/kavinbharathi/the-fascinating-wave-function-collapse-algorithm-4nc3
A new way to generate worlds (stitched WFC) : https://www.youtube.com/watch?v=dFYMOzoSDNE
EPC2018 - Oskar Stalberg - Wave Function Collapse in Bad North : https://www.youtube.com/watch?v=0bcZb-SsnrA
Introduction to procedural generation with Wave Function Collapse : https://www.youtube.com/watch?v=ZdbpTkuStKI
Wave Function Collapse Is A Thing - Godot 4.1 C# (Full Lesson) : https://www.youtube.com/watch?v=OiJmO2BRcVE
Expanding Wave Function Collapse with Growing Grids for Procedural Content Generation : https://www.youtube.com/watch?v=2TDgZfc-bu0
The Wave Function Collapse algorithm : https://www.youtube.com/watch?v=qRtrj6Pua2A
A.I. Level Generation, High Res (Wave Function Collapse #6) : https://www.youtube.com/watch?v=bVI-i39lYP8
PHP-WFC : https://github.com/FeatheredSnek/phpwfc
Procedural Generation with Wave Function Collapse and Model Synthesis | Unity Devlog : https://www.youtube.com/watch?v=zIRTOgfsjl0
Model Synthesis : https://paulmerrell.org/model-synthesis
Wave Collapse Function algorithm in Processing : https://discourse.processing.org/t/wave-collapse-function-algorithm-in-processing/12983
Présentation du Wave Function Collapse (Procédural) https://www.youtube.com/watch?v=_pRIHB8Qbek
Automatic Generation of Game Content using a Graph-based Wave Function Collapse Algorithm : https://fr.slideshare.net/slideshow/automatic-generation-of-game-content-using-a-graphbased-wave-function-collapse-algorithm-191777606/191777606

Creative works

Creating Little Castles with Wave Function Collapse : https://www.youtube.com/watch?v=MyMbbmWVCDw
Eternal Mist. Example of Wave Function Collapse (for #screenshotsaturday ). Indie Game Devlog #2.1 : https://www.youtube.com/watch?v=Ff0tXzaMpvU
Wave Function Collapse For Dummies Like Me (With Unity Example) : https://www.youtube.com/watch?v=57MaTTVH_XI
Procedural generation from a single example with WaveFunctionCollapse : https://www.youtube.com/watch?v=DOQTr2Xmlz0
EASY Wave Function Collapse Tutorial for Unity Games! (Unity Tutorial - Reupload) : https://www.youtube.com/watch?v=3g440SA2hKU
Why I use Wave Function Collapse to create levels for my game : https://www.youtube.com/watch?v=TO0Tx3w5abQ
How Townscaper Works: A Story Four Games in the Making | AI and Games #65 : https://www.youtube.com/watch?v=_1fvJ5sHh6A
Oisín Wave Function Collapse for poetry: https://github.com/mewo2/oisin
Townscaper : https://www.townscapergame.com/
unity-wave-function-collapse : https://selfsame.itch.io/unitywfc
Zelda WFC : https://observablehq.com/@makio135/zelda-wfc
Wave Function Collapse Demonstration : https://oskarstalberg.com/game/wave/wave.html
Infinite procedurally generated city : https://marian42.de/article/wfc/
Generating stairy scenes : https://x.com/exutumno/status/895683455299723265?lang=eu
Herbert Wolverson - Procedural Map Generation Techniques : https://www.youtube.com/watch?v=TlLIOgWYVpI
What Is Perlin Noise? Procedural Generating in Video Games : https://www.youtube.com/watch?v=9x6NvGkxXhU