Wave Function Collapse : contraintes locales et jouabilité globale

Générer sous des règles explicites

Wave Function Collapse est utile pour agencer du contenu lorsque la compatibilité locale peut être énoncée clairement : quels bords de tuiles peuvent se rejoindre, ou quels motifs qui se chevauchent peuvent coexister. Il ne remplace pas la définition des objectifs du niveau. Il faut commencer par distinguer la cohérence visuelle des exigences telles qu'une sortie accessible ou une ressource garantie.

Domaines, entropie et propagation

L'implémentation d'origine maintient l'ensemble des motifs possibles, choisit une position non résolue à faible entropie, sélectionne un motif, puis propage les restrictions. Un ensemble de possibilités vide signale une contradiction. [1] Les explications issues de la résolution de contraintes décrivent le backtracking comme le retour à une décision antérieure pour essayer d'autres alternatives. [2] Toutes les implémentations de WFC n'incluent pas de backtracking, et l'entropie pondérée est plus spécifique qu'un simple comptage des options.

Exemple détaillé

Prenons, à titre d'illustration, une rangée de 3 cellules. Une tuile RoadEW possède des connexions de route à l'est et à l'ouest ; Grass n'en a aucune. La règle exige que les bords avec route rejoignent des bords avec route, et les bords vides des bords vides. La cellule de gauche est fixée à RoadEW, celle de droite à Grass, et la cellule du milieu admet initialement l'une ou l'autre tuile.

Le voisin de gauche impose RoadEW au milieu. Le voisin de droite l'interdit. Le domaine de la cellule du milieu devient vide : ces exigences fixes se contredisent. Relancer avec une autre graine aléatoire ne peut pas corriger cette configuration fixe précise. Il faut assouplir une exigence, introduire une tuile de transition compatible ou signaler l'échec.

Considérons maintenant une carte plus grande, localement valide. Des bords de route qui se correspondent peuvent tout de même former des boucles déconnectées. Un collapse réussi ne prouve donc pas l'existence d'un chemin entre l'entrée et la sortie. Cette propriété exige une contrainte supplémentaire, une structure de parcours réservée ou une vérification de connectivité distincte.

Flux de travail de création

Créez un petit catalogue de tuiles avec orientations, étiquettes de bords et poids explicites. Vérifiez chaque règle d'adjacence dans les deux directions concernées. Testez les conditions aux limites indépendamment des règles intérieures ; le bord du monde peut nécessiter une politique de fermeture spécifique. Ajoutez les tuiles progressivement, afin de pouvoir rattacher les contradictions à une modification de taille gérable.

Fixez des limites pour les décisions, le travail de propagation, le backtracking et les redémarrages. Conservez la graine, la version du catalogue, les contraintes fixes et l'emplacement de l'échec pour pouvoir reproduire le problème. Pour une génération à l'exécution, définissez si un travail inachevé rend la main (yield), produit une solution de repli ou rejette la requête.

Limites et validation

Les poids orientent les choix mais ne garantissent pas les proportions finales exactes de chaque tuile. La cohérence locale n'établit ni le rythme, ni l'accessibilité, ni la navigabilité, ni l'équilibre des ressources. Validez ces propriétés sur la représentation réelle du jeu, et pas seulement sur l'image générée.

Mesurez le temps de génération, la fréquence des contradictions, le nombre de redémarrages et le taux de rejet sur un jeu de graines varié. Présentez ces chiffres comme des mesures de projet lorsqu'ils ont effectivement été collectés. Pour les grands mondes, prévoyez comment les régions voisines s'accordent sur leurs frontières ; des chunks réussis indépendamment peuvent néanmoins ne pas se raccorder en un ensemble utilisable.

Sources

[1] WaveFunctionCollapse implementation — Maxim Gumin and contributors.

[2] Wave Function Collapse explained — Boris the Brave.