Worldlex Wiki Synthèse de modèles (également réduction de la fonction d'onde ou'wfc' ) est une famille d' algorithmes de résolution de contraintes couramment utilisés dans la génération procédurale , notamment dans l' industrie du jeu vidéo .
Parmi les jeux vidéo connus pour avoir utilisé des variantes de l'algorithme, on peut citer Bad North , Townscaper et Caves of Qud .
Le premier exemple de ce type d'algorithme a été décrit par Paul Merrell, qui l'a nommé « synthèse de modèles » dans son article de 2007 à i3D , et présenté également à la conférence SIGGRAPH de 2008 et dans sa thèse de doctorat de 2009 . Le nom « effondrement de la fonction d'onde » est ensuite devenu l'appellation courante pour une variante de cet algorithme, après la publication en 2016 d'une implémentation par Maxim Gumin sur un dépôt GitHub portant ce nom .
L'implémentation de Gumin s'inspire de plusieurs sources, notamment la thèse de doctorat de Merrell et le transfert de style des réseaux de neurones convolutifs . Le nom courant de l'algorithme, « effondrement de la fonction d'onde », provient d'une analogie entre sa méthode et les concepts de superposition et d'observation en mécanique quantique . Parmi les innovations de l'implémentation de Gumin figure l'utilisation de motifs superposés, permettant d'utiliser une seule image comme entrée de l'algorithme.
Certains ont émis l'hypothèse que la popularité plus grande de l'implémentation de Gumin par rapport à celle de Merrell pourrait être due à la moindre accessibilité de l'implémentation de « synthèse de modèles », à son orientation 3D ou peut-être aux contraintes informatiques du grand public à l'époque.
L'une des différences entre l'implémentation de Merrell et Gumin et la « réduction de la fonction d'onde » réside dans le choix de la cellule à « réduire » ensuite. L'implémentation de Merrell utilise une approche par balayage linéaire, tandis que celle de Gumin sélectionne systématiquement la cellule ayant l'entropie la plus faible.
Description
L'algorithme WFC, ou « synthèse de modèles », présente plusieurs variantes. Les implémentations de Gumin et Merrell sont décrites ci-dessous, et d'autres variantes sont mentionnées :
L'implémentation de Gumin
- L'image bitmap d'entrée est lue, et les motifs présents dans l'image bitmap sont comptés.
- Un tableau est créé avec les dimensions de la sortie souhaitée.
- Chaque cellule du tableau est initialisée dans un état « non observé ».
- Les étapes suivantes sont répétées :
- La cellule présentant le plus petit nombre d'états de sortie possibles est située
- « Réduisez » cette cellule à l'un de ses états possibles selon les règles
- Vérifiez que toutes les cellules sont toujours valides et respectent les règles.
- Une fois que toutes les cellules sont « réduites » dans un état définitif, renvoyez le résultat. Si le résultat est invalide, ignorez-le et répétez le processus jusqu'à ce qu'il soit valide.
La mise en œuvre de Merrell
La première version de Merrell est sensiblement la même que celle de Gumin, à quelques différences mineures près.
(1) Dans la version de Merrell, il n'est pas nécessaire de sélectionner la cellule présentant le plus petit nombre d'états de sortie possibles pour la réduction. Une approche par balayage linéaire est plutôt adoptée. Selon Merrell, cela permet de réduire le taux d'échec du modèle sans incidence négative sur sa qualité. Certains commentateurs ont toutefois noté que cette approche par balayage linéaire tend à générer des artefacts directionnels.
(2) L'approche de Merrell exécute l'algorithme par blocs, plutôt que d'un seul coup. Cette approche réduit considérablement le taux d'échec pour de nombreux modèles complexes de grande taille, notamment dans un espace 3D.
Développements
En avril 2023, Shaad Alaka et Rafael Bidarra de l'Université de Delft ont proposé « l'effondrement hiérarchique de la fonction d'onde sémantique ». L'algorithme est ainsi modifié pour fonctionner avec des ensembles de tuiles plus complexes que les ensembles simples et non structurés. Avant leurs travaux, toutes les variantes de l'algorithme WFC opéraient sur un ensemble uniforme de choix de tuiles par cellule.
Leur approche généralisée organise les ensembles de tuiles en une hiérarchie, composée de nœuds abstraits appelés « méta-tuiles » et de nœuds terminaux appelés « tuiles feuilles ». Par exemple, lors de la première passe, WFC pourrait faire d'une certaine tuile une méta-tuile de type « château » ; celle-ci, lors d'une seconde passe, sera réduite à d'autres tuiles selon une règle, par exemple une tuile « mur » ou « herbe ».