Wave Function Collapse : générer un décor cohérent, puis le rendre jouable

Si vous avez joué à Bad North, à Townscaper ou à Caves of Qud, vous avez déjà vu WaveFunctionCollapse (WFC) à l'œuvre. Son créateur, Maxim Gumin, cite ces trois jeux sur la page du projet parmi ceux dont WFC génère les niveaux.

Gumin résume lui-même ce que fait son programme : il « generates bitmaps that are locally similar to the input bitmap ». On lui donne une petite image d'exemple, il en produit une nouvelle, plus grande, qui lui ressemble localement. Ce guide suit sa présentation, avec un petit programme en Python pour essayer et quelques tests que nous avons faits nous-mêmes.

Bad North. Capture : Steam.

Le vocabulaire

• Tuile : une pièce de décor qui occupe une case (de l'eau, du sable, un mur…).
• Grille : la carte à remplir, découpée en cases.
• Motif : un petit carré de N × N cases découpé dans l'image d'exemple.
• Propagation : quand une case est fixée, ses voisines perdent les options devenues impossibles, puis leurs voisines, et ainsi de suite.
• Contradiction : une case où plus aucune option n'est possible.
• Graine : le nombre qui fixe le tirage au sort. Même graine, même carte.

« Localement similaire », ça veut dire quoi

Gumin donne deux conditions. La première est stricte : la sortie ne doit contenir que des motifs de N × N cases qui existent dans l'exemple. La seconde est plus souple : un motif fréquent dans l'exemple doit être à peu près aussi fréquent dans les sorties. Dans ses exemples, N vaut généralement 3.

Autrement dit, chaque petit carré de 3 × 3 de la carte générée existe déjà quelque part dans l'exemple. C'est ce qui donne aux résultats un air de famille avec le modèle, sans jamais le recopier.

D'où vient le nom

Au départ, aucune case de la sortie n'est décidée : chacune est dans un état « superposé », un mélange de toutes les couleurs de l'exemple. Gumin emprunte ce vocabulaire à la physique quantique, en précisant pourquoi il s'agit seulement d'une inspiration : les coefficients de ces mélanges « are real numbers, not complex numbers, so it doesn't do the actual quantum mechanics, but it was inspired by QM ».

Le programme alterne ensuite deux étapes :

1. Observation : il choisit, parmi les zones pas encore décidées, celle dont l'entropie est la plus faible, c'est-à-dire celle où il reste le moins d'incertitude. Elle « s'effondre » sur un motif précis, tiré au sort selon les fréquences de l'exemple.
2. Propagation : cette nouvelle information se répercute sur le reste de la sortie.

À chaque tour, les possibilités diminuent. À la fin, tout est décidé : la « fonction d'onde » s'est effondrée.

Pourquoi commencer par la zone la plus sûre ? Gumin explique avoir remarqué que les humains font souvent pareil quand ils dessinent, et que c'est ce qui rend l'algorithme si agréable à regarder. Il ajoute que cette règle évite que les résultats penchent dans une direction, comme quand on remplit une grille ligne par ligne.

Les deux modèles

Le dépôt propose deux façons de s'en servir.

• Le modèle chevauchant (overlapping), celui décrit plus haut : les règles sont déduites d'une image d'exemple, découpée en motifs.
• Le modèle de tuiles simple (simple tiled) : on fournit directement une liste de tuiles et la liste des tuiles qui peuvent se toucher. Gumin le présente comme le cas le plus simple de l'algorithme, où la propagation se réduit à « adjacency constraint propagation », la vérification des voisinages.

Townscaper, d'Oskar Stålberg, lui aussi cité par Gumin. Capture : Steam.

Essayer le modèle simple en Python

Pour voir le modèle simple de près, voici un petit générateur que nous avons écrit en Python pour ce guide. Il utilise quatre tuiles (eau, sable, herbe, forêt) avec une règle : l'eau touche le sable, le sable l'herbe, l'herbe la forêt, et l'eau ne touche jamais la forêt. Il suit les deux étapes décrites par Gumin et choisit lui aussi la case d'entropie la plus faible. Il ne demande rien d'autre que Python 3.

import math
import random

# Quatre tuiles et leurs poids : plus le poids est grand, plus la tuile sort souvent.
TILES = {"eau": 2, "sable": 2, "herbe": 5, "foret": 4}

# Les voisins autorisés : une tuile peut toujours toucher sa propre famille.
VOISINS = {
    "eau": {"eau", "sable"},
    "sable": {"eau", "sable", "herbe"},
    "herbe": {"sable", "herbe", "foret"},
    "foret": {"herbe", "foret"},
}


def entropie(options):
    """Entropie de Shannon des tuiles encore possibles, pondérée par leurs poids."""
    total = sum(TILES[t] for t in options)
    return -sum(TILES[t] / total * math.log(TILES[t] / total) for t in options)


def generer(largeur, hauteur, graine, pendant=None):
    rng = random.Random(graine)
    grille = [[set(TILES) for _ in range(largeur)] for _ in range(hauteur)]
    while True:
        # 1. Observer : la case indécise la moins « chaotique ».
        indecises = [
            (entropie(grille[y][x]) + rng.random() * 1e-3, x, y)
            for y in range(hauteur)
            for x in range(largeur)
            if len(grille[y][x]) > 1
        ]
        if not indecises:
            return grille
        _, x, y = min(indecises)
        # 2. Effondrer : tirer une tuile selon les poids.
        options = sorted(grille[y][x])
        choix = rng.choices(options, weights=[TILES[t] for t in options])[0]
        grille[y][x] = {choix}
        # 3. Propager : chaque voisin perd les tuiles devenues impossibles.
        pile = [(x, y)]
        while pile:
            cx, cy = pile.pop()
            permis = set().union(*(VOISINS[t] for t in grille[cy][cx]))
            for nx, ny in ((cx + 1, cy), (cx - 1, cy), (cx, cy + 1), (cx, cy - 1)):
                if 0 <= nx < largeur and 0 <= ny < hauteur:
                    reste = grille[ny][nx] & permis
                    if not reste:
                        raise ValueError(f"contradiction en ({nx}, {ny})")
                    if reste != grille[ny][nx]:
                        grille[ny][nx] = reste
                        pile.append((nx, ny))
        if pendant:
            pendant(grille)

Enregistrez-le sous le nom wfc.py, puis lancez ceci pour afficher une carte en lettres (e pour eau, s pour sable, h pour herbe, f pour forêt) :

import wfc

carte = wfc.generer(40, 20, graine=7)
for ligne in carte:
    print("".join(next(iter(case))[0] for case in ligne))

Changez la graine pour obtenir une autre carte.

Pourquoi ces quatre tuiles donnent des cartes sans forme

En faisant tourner ce code, on obtient vite des cartes bruitées : des damiers, ou des cartes presque entièrement couvertes d'eau, sans vraies îles. Gumin explique pourquoi. Un jeu de tuiles où l'on ne peut jamais se retrouver bloqué est ce qu'il appelle un jeu « facile », et « without special heuristics easy tilesets don't produce interesting global arrangements » : l'influence d'une tuile sur les autres s'estompe très vite avec la distance.

Nos quatre tuiles en sont un bon exemple : sur 140 cartes, aucune ne s'est bloquée, et celles que nous avons regardées ne formaient pas de vraies îles. Avec le modèle chevauchant et une seule île de 24 × 24 cases dessinée comme exemple, les mêmes quatre tuiles ont en revanche donné des côtes, des plages et des forêts entourées de prairie.

Les contradictions

Pendant la propagation, il arrive qu'une case perde toutes ses options. Gumin le dit sans détour : l'algorithme « has run into a contradiction and can not continue ». Savoir à l'avance si un exemple permet de générer une sortie est un problème NP-difficile : il n'existe pas de méthode rapide qui réussisse à tous les coups. En pratique, note-t-il, l'algorithme tombe pourtant « surprisingly rarely » sur une contradiction.

Nos tests vont dans le même sens. Après avoir ajouté à nos règles « le sable ne touche jamais le sable », pour forcer des plages d'une seule case, une carte sur 1 000 s'est bloquée.

La version de Gumin s'arrête alors sans rien renvoyer : il faut relancer avec une autre graine. D'autres implémentations reviennent en arrière : elles sauvegardent avant chaque choix et, en cas de blocage, reprennent depuis la sauvegarde en interdisant le choix fautif. C'est ce que fait Marian Kleineberg dans sa ville générée : « My current solution is backtracking ».

Ajouter ses propres contraintes

Gumin souligne que WFC accepte des contraintes, et qu'on peut donc le combiner avec d'autres méthodes ou avec un travail fait à la main. Sur la page du projet, une animation montre WFC terminer un niveau commencé par un humain.

C'est utile, parce que WFC ne vérifie que des voisinages. Il ne garantit pas qu'on puisse aller d'un point à un autre. Nous l'avons testé sur 40 cartes générées à partir de notre île, en cherchant un chemin à pied entre le point de terre le plus à l'ouest et celui le plus à l'est : il en existait un sur 23 cartes seulement. Sur les 17 autres, les deux points étaient sur des îles différentes.

Pour éviter ça, on peut vérifier chaque carte après coup et jeter celles qui ne conviennent pas, ou imposer le chemin pendant la génération. La bibliothèque DeBroglie propose par exemple une contrainte qui, d'après sa documentation, « ensures that there is a valid path between relevant tiles ».

Les développeurs de Caves of Qud ont présenté leur méthode à la GDC en 2019 : WFC génère la base des cartes, puis des étapes supplémentaires relient les zones et peuplent les donjons.

Caves of Qud (Freehold Games). Capture : Steam.

D'où vient WFC

Gumin cite ses inspirations sur la page du projet. La principale est la thèse de Paul Merrell, Model Synthesis (2009), qui déduisait déjà des règles de voisinage entre tuiles à partir d'un modèle d'exemple. WFC généralise cette idée à des motifs de N × N qui se chevauchent, ce qui permet de partir d'une seule image. Selon Gumin, faire varier N permet de rendre la sortie plus ou moins proche de l'exemple. Il présente aussi WFC comme un algorithme de synthèse de texture, qui convient particulièrement à la génération de niveaux et au pixel art.

Pour essayer sans programmer

• Une version graphique interactive est disponible sur itch.io, et la page du projet propose une version officielle pour Windows.
• Une démo du modèle chevauchant tourne directement dans le navigateur.
• Gumin indique aussi des adaptations pour Unreal Engine 5, Godot 4 et Unity.

Sa démonstration vidéo montre la grille se remplir en direct :

Bad North, côté coulisses

Oskar Stålberg a présenté en 2018 son utilisation de WFC pour les îles de Bad North. La conférence est en anglais.

Bad North. Capture : Steam.

Sources

• Maxim Gumin, WaveFunctionCollapse, page et code du projet (2016).
• Paul C. Merrell, Model Synthesis, 2009.
• Isaac Karth et Adam M. Smith, WaveFunctionCollapse is Constraint Solving in the Wild, FDG 2017.
• Marian Kleineberg, Infinite procedurally generated city with the Wave Function Collapse algorithm (6 janvier 2019).
• BorisTheBrave, documentation de DeBroglie sur les chemins.
• Brian Bucklew (Freehold Games), Tile-Based Map Generation using Wave Function Collapse in Caves of Qud, GDC 2019.
• Oskar Stålberg, Wave Function Collapse in Bad North, EPC 2018.

Images : captures publiées sur Steam par Plausible Concept (Bad North), Oskar Stålberg (Townscaper) et Freehold Games (Caves of Qud).