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.

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.

• 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.

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

1. 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.).

2. Sélection de la plus faible entropie : Choisir la cellule avec le moins d’états possibles (la plus faible entropie).

3. Effondrement de la cellule : Sélectionner au hasard l’un des états valides restants.

4. Propagation des contraintes : Mettre à jour les cellules voisines pour éliminer les états qui ne sont plus valides en fonction de la cellule effondrée.

5. 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.

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.

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.

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 ».

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

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.

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

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

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.

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.

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.

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.

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.

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

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.

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