🤖 AI

Evolutionary Wave Function Collapse

Cet article propose un cadre de recherche évolutionnaire qui optimise les petits exemples d'entrée utilisés par Wave Function Collapse (WFC) pour générer du contenu procédural de plus haute qualité, démontrant que cette approche améliore efficacement la génération dans des domaines où des propriétés globales émergent de contraintes locales, tels que la connectivité des labyrinthes et les configurations de donjons.

Auteurs originaux : Dipika Rajesh, Ahmed Khalifa, Julian Togelius

Publié 2026-07-03

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Dipika Rajesh, Ahmed Khalifa, Julian Togelius

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'apprendre à un robot à dessiner une carte pour un jeu vidéo. Vous avez deux méthodes différentes pour faire cela, et cet article traite de la tentative de les mélanger pour obtenir le meilleur des deux mondes.

Les deux approches

1. Le robot « Imitateur » (Wave Function Collapse)
Considérez la première méthode, appelée Wave Function Collapse (WFC), comme un imitateur très talentueux mais légèrement myope.

Comment ça marche : Vous montrez au robot un minuscule carré de 4x4 d'une image (comme un petit fragment de donjon ou de labyrinthe). Le robot observe comment les tuiles de ce minuscule fragment s'assemblent entre elles (par exemple : « un mur se trouve généralement à côté d'un sol »).
Le résultat : Il utilise ces règles locales minuscules pour construire une carte immense et complexe.
Le problème : Le robot est « court-voyant ». Il sait qu'un mur touche un sol, mais il ne comprend pas la vue d'ensemble. Il ne sait pas qu'une carte doit être une seule grande boucle connectée, ou qu'il doit y avoir exactement une clé et une porte. Il se contente de suivre les règles locales, ce qui conduit parfois à des cartes désordonnées ou défectueuses.

2. L'artiste par « Essai et Erreur » (Evolutionary Search)
La deuxième méthode est semblable à un sculpteur qui crée des milliers de statues, jette les plus laides et garde les meilleures pour en créer des versions légèrement améliorées.

Comment ça marche : Vous générez de nombreuses cartes aléatoires, vérifiez lesquelles sont amusantes à jouer, puis vous « faites se reproduire » les meilleures pour créer de nouvelles générations.
Le problème : Cela prend un temps très long. Vous devez construire toute la grande carte, la tester, puis recommencer. C'est coûteux en termes de calcul et c'est lent.

La grande idée : Le « Génotype » et le « Phénotype »

Les auteurs de cet article se sont demandé : Et si nous laissions l'artiste par « Essai et Erreur » concevoir le minuscule patch de 4x4, et que nous laissions le robot « Imitateur » construire la grande carte ?

Ils ont traité le minuscule patch de 4x4 comme le Génotype (l'ADN ou le plan) et la grande carte que le robot construit comme le Phénotype (la créature vivante réelle ou le produit final).

Au lieu de faire évoluer toute la grande carte (ce qui est lent), ils ont fait évoluer le minuscule patch de 4x4. Le robot « Imitateur » (WFC) servait de machine pour transformer ce minuscule ADN en un niveau de grande taille.

L'expérience : Deux mondes de jeux différents

Ils ont testé cette idée dans deux mondes de jeux vidéo différents pour voir si cela fonctionnait :

1. Le Monde du Labyrinthe (Le succès « Local »)

L'objectif : Créer un labyrinthe où l'on peut marcher du départ à l'arrivée sans rester coincé.
Le résultat : Cela a très bien fonctionné !
L'analogie : Imaginez que vous apprenez à un robot à construire un mur de briques. Si vous dites au robot « chaque brique doit reposer sur deux briques en dessous d'elle », le mur sera naturellement solide et connecté. L'objectif du « Labyrinthe » (la connectivité) est une règle locale. Si le petit patch possède de bonnes connexions locales, la grande carte sera naturellement un labyrinthe connecté. La recherche évolutive a rapidement trouvé le petit patch parfait qui permettait au robot de construire de superbes labyrinthes.

2. Le Monde de Zelda (La lutte « Globale »)

L'objectif : Créer un donjon avec exactement un joueur, une clé, une porte et quelques ennemis, où le joueur peut réellement atteindre la clé et la porte.
Le résultat : C'était beaucoup plus difficile.
L'analogie : Imaginez que vous dites à un robot de construire une maison, mais que vous ne lui donnez que des règles sur la façon dont les briques se touchent. Le robot pourrait construire une belle maison, mais il pourrait accidentellement construire deux portes d'entrée ou oublier de mettre un toit. L'objectif de « Zelda » nécessite des règles globales (par exemple : « Il doit y avoir exactement une clé dans tout le bâtiment »). Le petit patch de 4x4 ne « sait » pas ce qui se passe dans tout le bâtiment. Même si la recherche évolutive a rendu les cartes plus organisées, le robot a toujours eu du mal à obtenir le compte exact de clés et de portes car il ne regardait que le voisinage local, et non la maison entière.

Ce qu'ils ont découvert

Quand cela fonctionne : Si ce que vous voulez (comme un chemin connecté) découle naturellement de la façon dont les petites pièces s'assemblent, cette méthode hybride est fantastique. Elle trouve rapidement le « plan » parfait.
Quand cela échoue : Si ce que vous voulez nécessite de compter des choses à travers toute la carte ou de garantir que des objets spécifiques existent à des endroits précis (contraintes globales), la méthode se heurte à un mur. Le robot « Imitateur » n'a tout simplement pas la capacité cérébrale de comprendre la vue d'ensemble, peu importe la qualité du petit plan initial.

La conclusion

L'article conclut que vous pouvez utiliser l'évolution pour apprendre à un robot « court-voyant » à construire de meilleures cartes, mais seulement si les règles du jeu sont locales. Si le jeu nécessite des règles strictes et globales (comme « exactement une clé »), cette méthode seule ne suffit pas. Le robot a besoin d'un moyen de regarder l'ensemble de la carte, et pas seulement le petit patch qu'il est en train de copier.

Résumé Technique : Wave Function Collapse Évolutif

Énoncé du Problème

La génération de contenu procédural (PCG) dans les jeux vidéo est souvent confrontée à un compromis entre contrôlabilité et extensibilité. Le Wave Function Collapse (WFC) est une méthode populaire pour générer du contenu basé sur des contraintes d'adjacence locales apprises à partir de petits exemples d'entrée. Bien que le WFC soit autonome et rapide, il manque de compréhension globale ; il ne peut garantir la solvabilité ni imposer des contraintes globales (par exemple, des nombres spécifiques d'entités ou la joignabilité entre des points distants). À l'inverse, la PCG basée sur la recherche (SBPCG) permet une optimisation explicite vers des objectifs complexes, mais elle est souvent coûteuse en termes de calcul et difficile à spécifier pour les concepteurs. Cette étude examine si ces approches peuvent être hybridées : plus précisément, si la recherche évolutive peut être utilisée pour optimiser les entrées (les petites images d'exemple) fournies au WFC, plutôt que d'évoluer directement les niveaux finaux. Cela traite le WFC comme une mise en correspondance stochastique génotype-phénotype.

Méthodologie

La méthode proposée, le Wave Function Collapse Évolutif, fait évoluer des images d'entrée compactes (génotypes) qui servent de germe au WFC pour générer des niveaux de jeu plus vastes (phénotypes).

Représentation : Les individus de la population sont représentés par de petites grilles de tuiles de $4 \times 4$ . Ces grilles sont initialisées avec des tuiles aléatoires provenant de l'ensemble de tuiles (tileset) du jeu cible.
Mise en correspondance Génotype-Phénotype : Le génotype $4 \times 4$ est transmis à l'algorithme WFC. Le WFC extrait tous les motifs d'adjacence $2 \times 2$ de cet échantillon et les utilise comme contraintes pour générer un niveau de sortie plus grand. La génération est stochastique ; le même génotype peut produire des sorties différentes selon la graine aléatoire (seed).
Domaines Évalués :
1. Domaine Labyrinthe (Maze) : Génère des cartes de $8 \times 8$ . La fonction de fitness récompense une région traversable unique et connectée ainsi que de longs chemins navigables.
2. Domaine Zelda : Génère des configurations de donjons de $16 \times 16$ . La fonction de fitness est une somme pondérée ( $0,7 \cdot R_{entité} + 0,3 \cdot R_{jouabilité}$ ) récompensant des comptes d'entités spécifiques (un joueur, une clé, une porte, jusqu'à 25 ennemis) et la jouabilité (accessibilité entre le joueur, la clé et la porte).
Recherche Évolutive : Le système utilise un algorithme évolutif avec une sélection par tournoi (taille 3), de la mutation et de l'élitisme.
- Population : Taille de 10 sur 100 générations.
- Mutation : Entre 1 et 5 positions de tuiles sont mutées par descendant. La probabilité de mutation ( $p$ ) commence à 0,5 et s'adapte en fonction de l'amélioration de la fitness pour équilibrer l'exploration et l'exploitation.
- Base de référence (Baseline) : La méthode est comparée à une recherche aléatoire (Random Search) où les populations sont rééchantillonnées aléatoirement à chaque génération, tout en conservant les meilleurs chromosomes.

Résultats Clés

L'étude évalue l'efficacité de cette approche hybride dans des domaines présentant des dépendances variables entre la structure locale et globale.

Domaine Labyrinthe (Structure Locale Dominante) :
- La recherche évolutive a nettement surpassé la recherche aléatoire, convergeant rapidement vers des entrées performantes dès les 40 premières générations.
- Les sorties évoluées présentaient des configurations cohérentes et connectées avec de longs chemins continus.
- Les résultats suggèrent que les propriétés souhaitées, comme la connectivité, émergent naturellement de relations d'adjacence locale répétées, rendant ce domaine hautement compatible avec la représentation WFC.
Domaine Zelda (Structure Globale Requise) :
- La recherche évolutive a produit des sorties plus structurées que la recherche aléatoire (par exemple, des pièces reconnaissables, un placement significatif des entités) et a atteint des valeurs de fitness plus élevées.
- Cependant, l'écart de performance était plus faible que dans le domaine du Labyrinthe.
- Le système a eu des difficultés à satisfaire simultanément des contraintes globales strictes (notamment garantir exactement un joueur, une clé et une porte).
- Les courbes de fitness ont montré une amélioration rapide initiale suivie d'une stagnation près d'un optimum local, indiquant que la dépendance du WFC aux motifs locaux limite sa capacité à modéliser les dépendances de gameplay globales.

Signification et Revendications

L'article affirme que le Wave Function Collapse Évolutif est une stratégie efficace pour guider la génération procédurale lorsque les objectifs cibles s'alignent sur les régularités structurelles locales.

Avantage Hybride : L'approche combine avec succès la représentation compacte et la rapidité du WFC avec les capacités d'optimisation de la recherche évolutive.
Dépendance au Domaine : Cette méthode est plus efficace dans les domaines où les propriétés globales (comme la connectivité) émergent indirectement des relations locales. Elle est moins efficace dans les domaines nécessitant des contraintes globales symboliques explicites (comme des comptes d'entités spécifiques ou un ordre de progression) car le WFC ne modélise pas intrinsèquement ces dépendances globales.
Limites : Les auteurs reconnaissent que la nature stochastique du WFC introduit du bruit dans l'évaluation de la fitness (chaque génotype n'ayant été évalué qu'une seule fois). De plus, la nature locale du WFC reste une contrainte fondamentale ; la recherche évolutive ne peut surmonter l'incapacité du modèle sous-jacent à imposer directement des règles globales.

L'article conclut que bien que cette méthode améliore la qualité et l'organisation de la génération, les travaux futurs devraient explorer l'intégration de mécanismes explicites de résolution de contraintes globales dans le pipeline évolutif du WFC pour répondre aux domaines exigeant des contraintes symboliques strictes.