Wave Function Collapse से प्रक्रियात्मक hexagonal map बनाना

• Wave Function Collapse (WFC) algorithm का उपयोग करके लगभग 4,100 hexagonal tiles से बना मध्ययुगीन शैली का island map अपने-आप generate करने वाला प्रोजेक्ट
• हर tile में road, river, coast, cliff, forest, village जैसी terrain जानकारी शामिल है, और Three.js WebGPU व TSL shader की मदद से इसे लगभग 20 सेकंड में generate किया जाता है
• बड़े grid में होने वाली failures को हल करने के लिए इसे 19 hexagonal subgrid में बांटा गया, और backtracking व local-WFC recovery system से 86% से अधिक success rate हासिल की गई
• visual स्तर पर PBR material, WebGPU-आधारित shader, water reflection·wave effect, post-processing (lighting·depth of field·grain) आदि लागू कर depth बढ़ाई गई
• BatchedMesh rendering और single material sharing के जरिए हजारों tiles को 60fps पर render किया जाता है, जो procedural generation और real-time graphics के संयोजन की संभावना दिखाता है

---

प्रक्रियात्मक map generation का overview

• यह प्रोजेक्ट AD&D dungeon dice generation method से प्रेरित है, जहां user को खुद design करने की जरूरत नहीं पड़ती और algorithm अपने-आप दुनिया बनाता है
• generate किया गया map road, river, coastline, cliff, forest और village के साथ मध्ययुगीन island जैसा है, और लगभग 4,100 hexagonal cells से बना है
• Three.js WebGPU और TSL shader का उपयोग करके पूरा map लगभग 20 सेकंड में तैयार हो जाता है

Wave Function Collapse (WFC) algorithm

• WFC adjacent tiles की edge matching constraint के आधार पर terrain बनाता है
• hexagonal tile में 6 edges होती हैं, इसलिए square tile की तुलना में इसमें 50% अधिक constraints होते हैं
• हर tile के लिए 6-direction edge type और weight define किया जाता है; उदाहरण के लिए, 3-way road intersection में road और grass edges बारी-बारी से होती हैं
• algorithm इस तरह काम करता है
  1. सभी cells को सभी possible states के साथ initialize करना
  2. सबसे ज्यादा constrained cell चुनकर उसे एक state में ‘collapse’ करना
  3. adjacent cells से impossible states हटाते हुए constraint को propagate करना
  4. सभी cells solve होने तक यही प्रक्रिया दोहराना

बड़े grid और modular समाधान

• छोटे grid में यह स्थिर रहता है, लेकिन 4,000 से अधिक cells पर failure probability तेजी से बढ़ती है
• इसे हल करने के लिए map को 19 hexagonal subgrid में बांटा गया, जहां हर grid को independently solve किया जाता है, लेकिन boundary tiles को fixed constraints की तरह रखा जाता है
• अगर boundary constraints आपस में टकराएं, तो सिर्फ backtracking से समस्या हल नहीं होती

backtracking और recovery system

• backtracking गलत चयन को पीछे ले जाकर दूसरा tile आज़माने की विधि है, और इसे अधिकतम 500 बार तक चलाया जाता है
• लेकिन grids के बीच के conflicts को अलग recovery system से संभाला जाता है
  • चरण 1: Unfixing — conflict वाले cell को फिर से variable state में बदलना और आसपास के cells को नए constraints के रूप में सेट करना
  • चरण 2: Local-WFC — radius 2 cells (19 cells) के क्षेत्र को फिर से solve करके boundary compatibility सुनिश्चित करना, अधिकतम 5 प्रयास
  • चरण 3: Drop & Hide — failure होने पर उस cell को हटाकर उसे mountain tile से ढक देना ताकि वह स्वाभाविक लगे
• इस multi-layer recovery से पूरे map generation की success rate लगभग 86% तक पहुंचती है

3D elevation handling

• map में 5-step elevation level होते हैं, और slope व cliff tiles ऊपर-नीचे के levels को जोड़ते हैं
• अगर यह गलत जुड़ें, तो road cliff पर जाकर रुक सकती है या river ऊपर की ओर बहती हुई दिख सकती है
• elevation जानकारी को instance color में encode किया गया है, ताकि shader lowland और highland color palette को blend कर सके

hexagonal coordinate system

• 6-direction structure की वजह से hexagonal layout में साधारण 2D coordinates से adjacency calculation जटिल हो जाती है
• इसे आसान बनाने के लिए cube coordinate system (q, r, s) का उपयोग किया गया
• WFC वास्तविक geometry से ज्यादा edge-matching graph structure पर ध्यान देता है, इसलिए coordinate system मुख्य रूप से rendering और multi-grid placement में उपयोग होता है

tree और building placement

• WFC local pattern में मजबूत है, लेकिन large-scale distribution के लिए उतना उपयुक्त नहीं है
• tree और building की density Perlin noise field से तय की जाती है, जिससे forest और village का natural clustering बनता है
• अतिरिक्त logic के जरिए road ends पर building, coast पर harbor·windmill, और hill पर stone henge रखा जाता है

water effect implementation

• समुद्र सिर्फ एक साधारण plane नहीं है, उसमें sparkle और coastal wave effects भी शामिल हैं
• Sparkles को Voronoi noise की जगह small scrolling texture + noise mask से implement किया गया, जिससे GPU load कम हुआ
• Coast Waves के लिए coast mask को blur करके distance-based sine-wave band बनाई जाती है
• cove समस्या में blur-आधारित distance calculation सटीक नहीं रहती, इसलिए CPU आसपास के cells की जांच करके ऐसे क्षेत्र का mask बनाता है जहां wave को पतला दिखाना हो

tile निर्माण और alignment

• base model के लिए KayKit Medieval Hexagon Pack का उपयोग किया गया, लेकिन missing connection tiles (जैसे sloped river, cliff variation आदि) को Blender में सीधे बनाया गया
• सभी tiles की चौड़ाई 2 units रखी गई, और UV alignment error होने पर seams दिखाई देने लगती हैं, इसलिए precise mapping जरूरी है

visual effects और rendering

• यह Three.js WebGPU + TSL shader से implement किया गया है, और GLSL की जगह node-based shader का उपयोग करता है
• post-processing stack
  1. GTAO से shadowing को उभारना
  2. Depth of Field से miniature effect देना
  3. vignetting·film grain से analog texture जोड़ना
• dynamic shadow map को camera view के हिसाब से हर frame में फिर से adjust किया जाता है, ताकि zoom करने पर भी shadow sharp बनी रहे

performance optimization

• BatchedMesh के जरिए हर grid के tiles और decorations को जोड़कर एक draw call में render किया जाता है
• सभी meshes single material share करती हैं, जिससे shader state switching कम होती है
• नतीजतन 38 BatchedMesh, 4,100+ cells, और 60fps rendering हासिल होती है

मुख्य आंकड़े और tech stack

• 30 tile types, 19 grids, ~4,100 cells, 500 backtracking attempts, 5 Local-WFC attempts, 20-second generation, 100% success rate (500 tests)
• Three.js r183, TSL shader, Web Workers, Vite build, BatchedMesh, Seeded RNG का उपयोग

अनुभव और source

• live demo में map को expand करके पूरा generation देखा जा सकता है
• GitHub source code उपलब्ध है, और 50 से अधिक parameters के जरिए lighting, color, water और WFC settings को adjust किया जा सकता है

सारांश

• यह dice की जगह algorithm द्वारा दुनिया बनाए जाने का अनुभव देता है, जहां हर बार अलग terrain और road·river connections को explore किया जा सकता है
• procedural generation, graphics optimization और shader तकनीकों को जोड़ने वाला WebGPU-आधारित map generation experiment

[GN⁺]

Hacker News टिप्पणियाँ

• लेख में backtracking को बस 500 स्टेप तक सीमित किया गया है, लेकिन वास्तव में constraint programming एक बेहद दिलचस्प और जटिल क्षेत्र है
  Knuth का Algorithm X और dancing links इस्तेमाल करके, लेख में बताए गए "Layer 2" क्षेत्र को 86% से अधिक सफलता दर के साथ हल किया जा सकता है
  साथ ही, अलग-अलग heuristics लागू करने पर साधारण brute force की तुलना में खोज बहुत तेज़ हो सकती है। जिसने भी Sudoku solver बनाया है, वह जानता होगा कि brute force कितनी जल्दी धीमा पड़ जाता है

  • इस तरह की constraint-based combinatorial optimization problems के लिए पहले से ही कई dedicated solvers और high-level modeling languages मौजूद हैं
    उदाहरण के लिए MiniZinc एक high-level modeling language देता है जो कई solver backends को support करता है
    खुद algorithm लिखने के बजाय ऐसे industrial-grade solver का उपयोग करके समस्या को model करना, और solver को random या exhaustive search से उत्तर ढूँढ़ने देना अधिक कुशल होता है
    इससे solver लिखने में समय लगाने के बजाय, आप problem definition को समायोजित करके और दिलचस्प maps बनाने पर ध्यान दे सकते हैं

• मेरे laptop (11th-gen Core i5, Iris Xe, Chrome का latest version) पर demo 5 FPS पर चल रहा है। लगता है GPU bottleneck है
  लेख में कहा गया था कि यह mobile पर 60 FPS पर चलता है, इसलिए मुझे उम्मीद थी कि यह थोड़ा अधिक efficient होगा
  map सुंदर है, लेकिन WFC की tile-level constraints की वजह से अप्राकृतिक नतीजे आते हैं। क्योंकि non-local influence को दर्शाना मुश्किल होता है
  टाइल्स को एक-एक करके explore करने वाले game के लिए यह ठीक है, लेकिन पूरे map generation के लिए उपयुक्त नहीं है
  Red Blob Games का noise-based approach बेहतर परिणाम दिखाता है। rivers को humidity tracking से, और roads या bridges को अलग pass में handle करने पर यह ज़्यादा तेज़ और robust होगा
  फिर भी WFC एक दिलचस्प programming problem है, इसलिए implementation अपने आप में मज़ेदार रही होगी। कुल मिलाकर यह शानदार लेख और प्रभावशाली demo था

  • क्या यह Windows या Linux पर चल रहा था, या फिर CPU rendering इस्तेमाल हो रही थी?
  • मेरे mobile पर यह ठीक चल रहा है। जानना चाहूँगा कि FPS कैसे मापा गया। साइट पर कोई संकेत नहीं था, तो क्या आपने Chrome Dev Tools में देखा?

• Oskar Stålberg ने कई games में Wave Function Collapse(WFC) का उपयोग किया है। उनमें सबसे प्रसिद्ध Townscaper है
  संबंधित प्रस्तुति वीडियो SGC21 - Beyond Townscapers में देखा जा सकता है

• इससे Jasper Flick का Unity tutorial Hex Terrain याद आ गया
  यह project पहले से बने tiles को constraints के साथ मिलाता है, जबकि Jasper के tutorial में tile boundaries को dynamically generate किया जाता है
  दोनों approaches दिलचस्प हैं और पढ़ने में मज़ेदार हैं

• यह सच में बहुत शानदार project था
  वैसे अगर लेखक यह पढ़ रहे हों, तो जानना चाहूँगा कि क्या उन्होंने tile की superposition state (संभव विकल्पों के set) को bitfield के रूप में व्यक्त करने पर विचार किया था
  मैंने पहले WFC implement करते समय bitfield पर बदलने के बाद speedup बहुत ज़्यादा देखा था। backtracking की तुलना में पूरे chunk को फिर से compute करना अधिक तेज़ हो गया था

  • मेरा भी लगभग ऐसा ही अनुभव रहा है। मेरा WFC bot Carcassonne map generate करता है, और bitset library इस्तेमाल करने के बाद performance में बड़ा सुधार आया
    यह समय-समय पर state को stack में save करता है, और फँसने पर आखिरी state पर वापस लौट जाता है
    variable name tenper देखकर मुझे अपने पुराने रूप पर थोड़ा गुस्सा आता है

• लगता है constraints को संतुष्ट करने वाली arrangement ढूँढ़ना सबसे कठिन हिस्सा है
  मैंने सोचा कि क्या SAT solver इस्तेमाल करने वाला कोई विकल्प हो सकता है। लेकिन उस स्थिति में शायद हमेशा ‘आसान’ solutions ही मिलें और randomness कम हो जाए
  कुछ SAT solvers शुरुआती variable values को random बना सकते हैं, लेकिन इसका मतलब यह नहीं कि solution भी random होगा। जानना चाहूँगा कि क्या किसी ने ऐसा कुछ आज़माया है

  • SAT solver की computational complexity भी अधिक होती है, और formal methods न पढ़े हुए लोगों के लिए इसे समझना मुश्किल हो सकता है
    दूसरी ओर WFC एक साधारण brute force तरीका है, इसलिए इसे implement करना आसान है, और अगर dead ends बहुत ज़्यादा न हों तो computational cost कम रहती है
    games में perfect solution से ज़्यादा ‘काफ़ी अच्छा’ परिणाम पर्याप्त होता है, इसलिए WFC ज़्यादा व्यावहारिक हो सकता है

• यह प्रेरणादायक project था। references भी शानदार हैं और source code भी public है
  अगर इसमें Here Dragons Abound की visual style को जोड़ दिया जाए, तो यह बहुत बढ़िया लगेगा

• शायद OP को पहले से पता हो, लेकिन Red Blob Games की Hexagon math page में शानदार उदाहरण और code बहुत हैं

  • लेख में उस साइट का link पहले से दिया गया है

• non-square grid में WFC की पड़ताल दिलचस्प है
  ऐसा लगता है कि constraint propagation की complexity पारंपरिक उदाहरणों की तुलना में कहीं अधिक होगी
  ऐसे जटिल topology में Constraint Logic Programming जैसे दूसरे constraint solvers expressiveness और performance दोनों में फ़ायदेमंद हो सकते हैं

• इससे Dorfromantik याद आया। Steam लिंक

  • वह उसी नाम के board game पर आधारित है। BoardGameGeek page देखें