Membuat peta heksagonal prosedural dengan Wave Function Collapse

• Proyek yang secara otomatis menghasilkan peta pulau bergaya abad pertengahan yang terdiri dari sekitar 4.100 ubin heksagonal menggunakan algoritme Wave Function Collapse (WFC)
• Setiap ubin memuat informasi medan seperti jalan, sungai, pesisir, tebing, hutan, desa, dan dibuat dalam sekitar 20 detik dengan Three.js WebGPU dan shader TSL
• Untuk mengatasi kegagalan yang muncul pada grid skala besar, peta dibagi menjadi 19 subgrid heksagonal, dan dengan backtracking serta sistem pemulihan local-WFC tingkat keberhasilan dijaga di atas 86%
• Dari sisi visual, proyek ini menerapkan material PBR, shader berbasis WebGPU, efek pantulan air dan ombak, serta post-processing (pencahayaan, depth of field, grain) untuk memperkuat kesan tiga dimensi
• Dengan rendering BatchedMesh dan berbagi satu material, ribuan ubin dapat dirender pada 60fps, memperlihatkan potensi gabungan antara generasi prosedural dan grafis real-time

---

Ikhtisar pembuatan peta prosedural

• Proyek ini terinspirasi dari metode pembuatan dadu dungeon AD&D, dengan pendekatan di mana algoritme membangun dunia sendiri tanpa perlu dirancang langsung oleh pengguna
• Peta yang dihasilkan berbentuk pulau abad pertengahan yang mencakup jalan, sungai, garis pantai, tebing, hutan, desa, dan tersusun dari sekitar 4.100 sel heksagonal
• Seluruh peta diselesaikan dalam waktu sekitar 20 detik menggunakan Three.js WebGPU dan shader TSL

Algoritme Wave Function Collapse (WFC)

• WFC membentuk medan berdasarkan batasan bahwa sisi (edge) ubin yang bersebelahan harus cocok
• Karena ubin heksagonal memiliki 6 sisi, jumlah kondisi batasannya 50% lebih banyak dibanding persegi
• Setiap ubin mendefinisikan tipe sisi 6 arah dan bobotnya; misalnya, persimpangan jalan 3 arah memiliki sisi jalan dan rumput yang berselang-seling
• Algoritme bekerja dengan langkah berikut
  1. Menginisialisasi semua sel dengan semua status yang mungkin
  2. Memilih sel yang paling terikat lalu "meruntuhkannya" ke satu status
  3. Menyebarkan perubahan sambil menghapus status yang tidak mungkin pada sel tetangga
  4. Mengulang hingga seluruh sel terselesaikan

Grid skala besar dan solusi modular

• Pada grid kecil sistem bekerja stabil, tetapi pada lebih dari 4.000 sel probabilitas gagal meningkat tajam
• Untuk mengatasinya, peta dibagi menjadi 19 subgrid heksagonal, masing-masing diselesaikan secara independen sambil mempertahankan ubin batas sebagai batasan tetap
• Jika batasan pada perbatasan saling bertabrakan, backtracking saja tidak cukup untuk menyelesaikannya

Backtracking dan sistem pemulihan

• Backtracking mengembalikan pilihan yang salah untuk mencoba ubin lain, dan dilakukan hingga maksimal 500 kali
• Namun, konflik antargrid ditangani oleh sistem pemulihan terpisah
  • Tahap 1: Unfixing — sel yang bertabrakan dikembalikan ke status variabel, lalu sel di sekitarnya dijadikan batasan baru
  • Tahap 2: Local-WFC — area dengan radius 2 sel (19 sel) diselesaikan ulang untuk memastikan kompatibilitas batas, hingga 5 percobaan
  • Tahap 3: Drop & Hide — jika tetap gagal, sel tersebut dihapus lalu ditutupi dengan ubin pegunungan agar terlihat alami
• Dengan pemulihan berlapis ini, tingkat keberhasilan pembuatan peta mencapai sekitar 86%

Pemrosesan elevasi 3D

• Peta memiliki 5 tingkat elevasi, dan ubin lereng serta tebing menghubungkan level atas dan bawah
• Jika tersambung dengan salah, dapat muncul kesalahan seperti jalan terputus oleh tebing atau sungai mengalir ke atas
• Informasi elevasi dikodekan sebagai warna instance, sehingga shader dapat mencampur palet warna dataran rendah dan dataran tinggi

Sistem koordinat heksagonal

• Karena struktur 6 arah, heksagon membuat perhitungan ketetanggaan menjadi rumit jika memakai koordinat 2D sederhana
• Untuk itu digunakan koordinat kubus (q, r, s) agar pencarian tetangga lebih sederhana
• Karena WFC lebih berfokus pada struktur graf pencocokan sisi daripada geometri nyata, sistem koordinat terutama dipakai untuk rendering dan penempatan multigrid

Penempatan pohon dan bangunan

• WFC kuat untuk pola lokal, tetapi kurang cocok untuk distribusi skala besar
• Kepadatan pohon dan bangunan ditentukan memakai field noise Perlin agar hutan dan desa membentuk klaster yang alami
• Logika tambahan menempatkan bangunan di ujung jalan, pelabuhan dan kincir angin di pesisir, serta henge di perbukitan

Implementasi efek air

• Laut bukan sekadar bidang datar, tetapi juga mencakup kilau dan ombak pesisir
• Kilau (Sparkles) diimplementasikan dengan tekstur kecil yang bergulir + noise mask alih-alih noise Voronoi, untuk mengurangi beban GPU
• Ombak pesisir (Coast Waves) dibuat dengan mem-blur mask pesisir untuk menghasilkan pita gelombang sinus berbasis jarak
• Pada masalah teluk (Cove), perhitungan jarak berbasis blur kurang akurat, sehingga CPU memeriksa sel sekitar untuk membuat mask area dengan ombak yang dibuat lebih tipis

Pembuatan dan penyelarasan ubin

• Model dasar menggunakan KayKit Medieval Hexagon Pack, tetapi ubin koneksi yang belum tersedia seperti sungai lereng dan variasi tebing dibuat sendiri dengan Blender
• Semua ubin diseragamkan pada lebar 2 unit, dan bila terjadi kesalahan penyelarasan UV, garis batas akan terlihat sehingga pemetaan presisi sangat penting

Efek visual dan rendering

• Dibangun dengan Three.js WebGPU + shader TSL, menggunakan shader berbasis node alih-alih GLSL
• Stack post-processing
  1. GTAO untuk menonjolkan bayangan
  2. Depth of Field untuk efek miniatur
  3. Vignetting dan film grain untuk memberi tekstur analog
• Dynamic shadow map disesuaikan ulang setiap frame mengikuti pandangan kamera agar bayangan tetap tajam saat diperbesar

Optimasi performa

• Dengan BatchedMesh, ubin dan dekorasi pada tiap grid digabung sehingga bisa dirender dengan satu draw call
• Semua mesh berbagi satu material untuk meminimalkan pergantian status shader
• Hasilnya, proyek ini mencapai rendering 38 BatchedMesh, 4.100+ sel, dan 60fps

Angka penting dan tech stack

• 30 jenis ubin, 19 grid, ~4.100 sel, 500 kali backtracking, 5 percobaan Local-WFC, 20 detik generasi, 100% tingkat keberhasilan (500 pengujian)
• Menggunakan Three.js r183, shader TSL, Web Workers, build Vite, BatchedMesh, dan Seeded RNG

Demo dan source

• Di demo live pengguna dapat memperluas peta dan menghasilkan ulang seluruh peta
• Source code GitHub dibuka ke publik, dengan lebih dari 50 parameter untuk mengatur pencahayaan, warna, air, dan konfigurasi WFC

Ringkasan

• Proyek ini menghadirkan pengalaman di mana algoritme, bukan dadu, yang menciptakan dunia, sehingga pengguna bisa menjelajahi medan, jalan, dan koneksi sungai yang selalu berbeda setiap kali
• Sebuah eksperimen pembuatan peta berbasis WebGPU yang menggabungkan generasi prosedural, optimasi grafis, dan teknologi shader

[GN⁺]

Komentar Hacker News

• Dalam artikel ini, backtracking katanya hanya dibatasi sampai 500 langkah, tetapi sebenarnya pemrograman kendala adalah bidang yang sangat menarik dan kompleks
  Dengan Algorithm X milik Knuth dan dancing links, sepertinya area "Layer 2" yang disebut di artikel bisa diselesaikan dengan tingkat keberhasilan lebih tinggi dari 86%
  Selain itu, dengan menerapkan berbagai heuristik, pencarian bisa dilakukan jauh lebih cepat daripada brute force sederhana. Siapa pun yang pernah membuat solver Sudoku pasti tahu betapa lambatnya brute force bisa menjadi

  • Untuk masalah optimasi kombinatorial berbasis kendala seperti ini, sudah ada banyak solver khusus atau bahasa pemodelan tingkat tinggi
    Misalnya, MiniZinc menyediakan bahasa pemodelan tingkat tinggi yang mendukung berbagai backend solver
    Daripada menulis algoritma sendiri, lebih efisien memodelkan masalahnya dengan solver industri seperti ini, lalu membiarkan solver mencari solusi secara acak atau menyeluruh
    Dengan begitu, alih-alih menghabiskan waktu menulis solver, kita bisa fokus menyesuaikan definisi masalah untuk membuat peta yang lebih menarik

• Di laptop saya (Core i5 generasi ke-11, Iris Xe, Chrome versi terbaru), demo berjalan di 5 FPS. Sepertinya bottleneck-nya ada di GPU
  Di artikel disebutkan bahwa ini berjalan di 60 FPS di mobile, jadi saya kira akan lebih efisien
  Petanya indah, tetapi kendala per ubin pada WFC membuat hasilnya terasa tidak alami. Sulit merefleksikan pengaruh non-lokal
  Untuk game yang menjelajahi ubin satu per satu, ini masih cocok, tetapi kurang pas untuk pembuatan peta secara keseluruhan
  Pendekatan berbasis noise dari Red Blob Games menunjukkan hasil yang lebih baik. Sungai bisa ditangani lewat pelacakan kelembapan, dan jalan atau jembatan lewat pass terpisah agar lebih cepat dan tangguh
  Meski begitu, WFC tetap masalah pemrograman yang menarik, jadi implementasinya pasti menyenangkan. Secara keseluruhan, artikelnya sangat bagus dan demonya mengesankan

  • Saya penasaran apakah ini dijalankan di Windows atau Linux, atau mungkin menggunakan rendering CPU
  • Di mobile saya berjalan baik. Saya penasaran bagaimana FPS-nya diukur. Tidak ada tampilannya di situs, jadi apakah Anda melihatnya lewat Chrome Dev Tools?

• Oskar Stålberg telah memakai Wave Function Collapse (WFC) di beberapa game. Yang paling terkenal mungkin Townscaper
  Video presentasi terkait bisa dilihat di SGC21 - Beyond Townscapers

• Ini mengingatkan saya pada tutorial Unity Hex Terrain dari Jasper Flick
  Proyek ini mencocokkan ubin yang sudah dibuat sebelumnya lewat kondisi kendala, sedangkan tutorial Jasper membuat batas ubin secara dinamis
  Kedua pendekatan sama-sama menarik dan enak dibaca

• Proyek yang benar-benar keren
  Sekadar catatan jika penulis melihat ini: saya penasaran apakah pernah mempertimbangkan merepresentasikan status superposition ubin, yaitu himpunan opsi yang mungkin, sebagai bitfield
  Saat dulu saya mengimplementasikan WFC, beralih ke bitfield memberi peningkatan kecepatan yang luar biasa. Menghitung ulang seluruh chunk malah jadi lebih cepat daripada backtracking

  • Saya juga punya pengalaman serupa. Bot WFC saya menghasilkan peta Carcassonne, dan performanya meningkat besar setelah memakai library bitset
    Mekanismenya adalah menyimpan status ke stack secara berkala, lalu jika buntu, kembali ke status terakhir
    Melihat nama variabel tenper membuat saya agak kesal pada diri saya di masa lalu

• Sepertinya bagian tersulit adalah menemukan susunan yang memenuhi semua kendala
  Saya sempat berpikir apakah ada alternatif menggunakan SAT solver. Hanya saja, kalau begitu mungkin yang ditemukan selalu solusi yang 'mudah' dan tingkat keacakannya menurun
  Beberapa SAT solver memang bisa mengacak nilai awal variabel, tetapi itu tidak otomatis berarti solusi akhirnya acak. Saya penasaran apakah ada yang pernah mencoba hal serupa

  • SAT solver juga punya masalah berupa kompleksitas komputasi yang tinggi, dan metode formal sulit dipahami bagi orang yang belum pernah mempelajarinya
    Sementara itu, WFC adalah pendekatan brute force yang sederhana sehingga mudah diimplementasikan, dan biaya komputasinya rendah selama jumlah jalan buntu tidak terlalu banyak
    Dalam game, hasil yang 'cukup bagus' sering kali sudah memadai dibanding solusi sempurna, jadi WFC bisa lebih praktis

• Proyek yang menginspirasi. Referensinya juga bagus dan source code-nya dibuka
  Akan menarik kalau dipadukan dengan gaya visual dari Here Dragons Abound

• Mungkin OP sudah tahu, tetapi halaman matematika Hexagon dari Red Blob Games punya banyak contoh dan kode yang sangat bagus

  • Situs itu juga ditautkan di artikelnya

• Menarik melihat eksplorasi WFC pada grid non-square
  Kompleksitas propagasi kendalanya tampaknya jauh lebih tinggi daripada contoh-contoh yang biasa
  Pada topologi serumit ini, solver kendala lain seperti Constraint Logic Programming mungkin lebih unggul dari sisi ekspresivitas dan performa

• Ini mengingatkan saya pada Dorfromantik. Tautan Steam

  • Itu didasarkan pada board game dengan nama yang sama. Lihat halaman BoardGameGeek