- Projet de génération automatique d’une carte d’île médiévale composée d’environ 4 100 tuiles hexagonales à l’aide de l’algorithme Wave Function Collapse (WFC)
- Chaque tuile contient des informations de terrain comme des routes, rivières, côtes, falaises, forêts et villages, avec une génération en environ 20 secondes grâce à Three.js WebGPU et aux shaders TSL
- Pour résoudre les échecs sur les grandes grilles, la carte est divisée en 19 sous-grilles hexagonales, avec un système de backtracking et de récupération Local-WFC qui assure un taux de réussite supérieur à 86 %
- Côté rendu visuel, le projet applique des matériaux PBR, des shaders basés sur WebGPU, des effets de réflexion et de vagues sur l’eau, ainsi que du post-traitement (éclairage, profondeur de champ, grain) pour renforcer le relief
- Le rendu de plusieurs milliers de tuiles à 60 fps est obtenu grâce à BatchedMesh et au partage d’un matériau unique, montrant le potentiel de la combinaison entre génération procédurale et graphismes temps réel
Vue d’ensemble de la génération procédurale de carte
- Le projet s’inspire de la méthode de génération aux dés de donjon d’AD&D et adopte une approche où l’algorithme construit le monde de lui-même sans conception manuelle par l’utilisateur
- La carte générée prend la forme d’une île médiévale avec routes, rivières, littoral, falaises, forêts et villages, et se compose d’environ 4 100 cellules hexagonales
- L’ensemble de la carte est généré en environ 20 secondes avec Three.js WebGPU et des shaders TSL
L’algorithme Wave Function Collapse (WFC)
- WFC construit le terrain à partir de contraintes imposant que les bords (edges) des tuiles adjacentes soient compatibles
- Comme une tuile hexagonale possède 6 bords, elle comporte 50 % de contraintes en plus par rapport à une tuile carrée
- Chaque tuile définit des types de bords dans 6 directions ainsi qu’un poids (
weight) ; par exemple, un carrefour routier à 3 directions alterne bords de route et bords d’herbe
- L’algorithme
- initialise toutes les cellules avec tous les états possibles
- sélectionne la cellule la plus contrainte et la fait « s’effondrer » vers un état
- propage la contrainte en supprimant les états impossibles des cellules voisines
- répète jusqu’à résolution complète de la grille
Grandes grilles et résolution modulaire
- Le système est stable sur de petites grilles, mais la probabilité d’échec augmente fortement au-delà de 4 000 cellules
- Pour y remédier, la carte est divisée en 19 sous-grilles hexagonales résolues indépendamment tout en conservant les tuiles de bordure comme contraintes fixes
- En cas de conflit entre contraintes de bordure, le backtracking seul ne suffit pas
Système de backtracking et de récupération
- Le backtracking consiste à annuler un mauvais choix pour essayer une autre tuile, jusqu’à 500 tentatives maximum
- Mais les conflits entre grilles sont traités par un système de récupération distinct
- Étape 1 : Unfixing — les cellules en conflit redeviennent variables et les cellules environnantes servent de nouvelles contraintes
- Étape 2 : Local-WFC — une zone de rayon 2 cellules (19 cellules) est résolue à nouveau pour rétablir la compatibilité des bordures, avec jusqu’à 5 essais
- Étape 3 : Drop & Hide — en cas d’échec, la cellule concernée est supprimée puis recouverte par une tuile de montagne pour masquer naturellement le problème
- Cette récupération multicouche permet d’atteindre un taux de réussite global d’environ 86 %
Gestion de l’altitude en 3D
- La carte comporte 5 niveaux d’altitude, avec des pentes et des tuiles de falaise reliant les niveaux supérieurs et inférieurs
- Une mauvaise connexion peut provoquer des erreurs, comme des routes bloquées par des falaises ou des rivières qui s’écoulent vers le haut
- Les informations d’altitude sont encodées dans les couleurs d’instance, ce qui permet au shader de mélanger des palettes de couleurs pour basses et hautes altitudes
Système de coordonnées hexagonales
- À cause de sa structure en 6 directions, l’hexagone rend les calculs de voisinage complexes avec un simple repère 2D
- Le projet utilise un système de coordonnées cubiques (q, r, s) pour simplifier la recherche des cellules adjacentes
- Comme WFC se concentre davantage sur la structure de graphe d’appariement des bords que sur la géométrie réelle, ce système de coordonnées sert surtout au rendu et à l’agencement des grilles multiples
Placement des arbres et des bâtiments
- WFC est performant pour les motifs locaux, mais peu adapté aux distributions à grande échelle
- La densité des arbres et des bâtiments est donc déterminée par un champ de bruit de Perlin, afin de créer des regroupements naturels de forêts et de villages
- Une logique supplémentaire place des bâtiments en bout de route, des ports et moulins à vent sur les côtes, et des cromlechs (
henge) sur les collines
Mise en œuvre des effets d’eau
- La mer n’est pas un simple plan : elle inclut des reflets scintillants et des vagues côtières
- Les scintillements (Sparkles) sont réalisés non pas avec du bruit de Voronoï, mais avec une petite texture défilante + un masque de bruit, afin de réduire la charge GPU
- Les vagues côtières (Coast Waves) sont générées en floutant un masque de côte pour produire des bandes sinusoïdales basées sur la distance
- Dans le problème des criques (Cove), le calcul de distance basé sur le flou manque de précision ; le CPU inspecte donc les cellules voisines pour générer un masque des zones où les vagues doivent être affinées
Création et alignement des tuiles
- Le modèle de base utilise le KayKit Medieval Hexagon Pack, mais les tuiles de connexion manquantes (rivières en pente, variantes de falaise, etc.) ont été créées manuellement dans Blender
- Toutes les tuiles sont normalisées à une largeur de 2 unités, et un mauvais alignement des UV peut révéler les coutures aux bordures, d’où la nécessité d’un mapping précis
Effets visuels et rendu
- L’implémentation repose sur Three.js WebGPU + shaders TSL, avec des shaders basés sur des nœuds plutôt que sur GLSL
- Pile de post-traitement
- GTAO pour accentuer l’occlusion
- Depth of Field pour un effet miniature
- Vignettage et grain filmique pour une texture analogique
- La shadow map dynamique est réajustée à chaque frame selon le champ de vision de la caméra, afin de conserver des ombres nettes même en zoomant
Optimisation des performances
- BatchedMesh regroupe les tuiles et décorations de chaque grille pour les rendre en un seul draw call
- Tous les meshes partagent un matériau unique, ce qui minimise les changements d’état du shader
- Résultat : 38 BatchedMesh, plus de 4 100 cellules et un rendu à 60 fps
Principaux chiffres et stack technique
- 30 types de tuiles, 19 grilles, ~4 100 cellules, 500 backtracks, 5 essais de Local-WFC, 20 secondes de génération, 100 % de réussite (sur 500 tests)
- Utilisation de Three.js r183, shaders TSL, Web Workers, build Vite, BatchedMesh et Seeded RNG
Démo et code source
- La démo live permet d’agrandir la carte et de générer l’ensemble
- Le code source GitHub est public, avec plus de 50 paramètres pour ajuster l’éclairage, les couleurs, l’eau et les réglages WFC
Résumé
- Le projet propose une expérience où l’algorithme crée le monde à la place de dés, avec à chaque fois un terrain différent et de nouvelles connexions de routes et de rivières à explorer
- Une expérimentation de génération de carte basée sur WebGPU qui combine génération procédurale, optimisation graphique et techniques de shader
1 commentaires
Avis sur Hacker News
L’article dit simplement que le backtracking a été limité à 500 étapes, mais en réalité la programmation par contraintes est un domaine très intéressant et complexe
En utilisant l’Algorithm X de Knuth et les dancing links, on pourrait probablement résoudre la zone « Layer 2 » mentionnée dans l’article avec un taux de réussite supérieur à 86 %
En appliquant aussi diverses heuristiques, on peut explorer bien plus vite qu’avec une simple brute force. Toute personne ayant déjà écrit un solveur de Sudoku sait à quel point la brute force peut devenir lente
Par exemple, MiniZinc fournit un langage de modélisation de haut niveau compatible avec plusieurs backends de solveur
Plutôt que d’écrire soi-même l’algorithme, il est plus efficace de modéliser le problème avec ce genre de solveur industriel et de laisser le solveur trouver une solution par recherche aléatoire ou exhaustive
Cela permet de se concentrer, au lieu de passer du temps à écrire un solveur, sur l’ajustement de la définition du problème pour créer des cartes plus intéressantes
Sur mon ordinateur portable (Core i5 de 11e génération, Iris Xe, dernière version de Chrome), la démo tourne à 5 FPS. Le GPU semble être le goulot d’étranglement
L’article disait que ça tournait à 60 FPS sur mobile, donc je m’attendais à quelque chose de plus efficace
La carte est magnifique, mais les contraintes au niveau des tuiles de WFC produisent des résultats peu naturels, car il est difficile d’y refléter une influence non locale (non-local influence)
C’est correct pour un jeu où l’on explore tuile par tuile, mais pas idéal pour générer une carte complète
L’approche basée sur le bruit de Red Blob Games donne de meilleurs résultats. Si les rivières sont gérées par suivi de l’humidité et les routes ou ponts par un passage séparé, ce sera aussi plus rapide et plus robuste
Cela dit, WFC reste un problème de programmation intéressant, donc l’implémentation a sûrement été plaisante. Globalement, c’était un excellent article et une démo impressionnante
Oskar Stålberg a utilisé Wave Function Collapse (WFC) dans plusieurs jeux, notamment Townscaper
On peut voir une présentation liée dans SGC21 - Beyond Townscapers
Cela m’a rappelé le tutoriel Unity de Jasper Flick, Hex Terrain
Ce projet assemble des tuiles préparées à l’avance selon des contraintes, tandis que le tutoriel de Jasper génère dynamiquement les frontières des tuiles
Les deux approches sont intéressantes et agréables à lire
Très beau projet
Au cas où l’auteur passerait par là, je me demande s’il a envisagé de représenter l’état de superposition des tuiles (l’ensemble des options possibles) avec un bitfield
Quand j’ai implémenté WFC il y a quelque temps, passer à un bitfield a donné un gain de vitesse énorme. Recalculer un chunk entier devenait même plus rapide que faire du backtracking
Il fonctionne en sauvegardant l’état dans une pile à intervalles réguliers, puis en revenant au dernier état quand il se retrouve bloqué
En voyant qu’une variable s’appelle
tenper, j’en veux un peu à la version passée de moi-mêmeTrouver une disposition qui respecte les contraintes semble être la partie la plus difficile
Je me demande s’il existerait une alternative utilisant un SAT solver. En revanche, cela risquerait peut-être de toujours trouver des solutions « faciles » et de réduire l’aléa
Certains solveurs SAT permettent d’initialiser aléatoirement les valeurs des variables, mais cela ne veut pas forcément dire qu’ils produisent des solutions aléatoires. Je me demande si quelqu’un a déjà essayé quelque chose de ce genre
À l’inverse, WFC repose sur une brute force simple, donc c’est facile à implémenter et, tant qu’il n’y a pas trop d’impasses, le coût de calcul reste faible
Dans un jeu, on n’a pas besoin d’une solution parfaite : un résultat « suffisamment bon » suffit souvent, ce qui peut rendre WFC plus pratique
C’était un projet inspirant. Les références sont excellentes et le code source est aussi publié
Ce serait sympa d’y combiner le style visuel de Here Dragons Abound
L’OP le sait peut-être déjà, mais la page sur les mathématiques des hexagones de Red Blob Games contient beaucoup d’excellents exemples et de code
L’exploration de WFC sur des grilles non carrées (non-square) est intéressante
La complexité de la propagation des contraintes semble bien plus élevée que dans les exemples habituels
Sur ce type de topologie complexe, d’autres solveurs de contraintes comme la Constraint Logic Programming pourraient peut-être avoir l’avantage en expressivité comme en performances
Cela m’a fait penser à Dorfromantik. Lien Steam