Créer une carte hexagonale procédurale avec Wave Function Collapse

• 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
  1. initialise toutes les cellules avec tous les états possibles
  2. sélectionne la cellule la plus contrainte et la fait « s’effondrer » vers un état
  3. propage la contrainte en supprimant les états impossibles des cellules voisines
  4. 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
  1. GTAO pour accentuer l’occlusion
  2. Depth of Field pour un effet miniature
  3. 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