Simulasi Air di Atas Medan
(lisyarus.github.io)- Dalam gim yang memungkinkan pemain menggali dan menimbun medan, danau, sungai, dan genangan harus mengalir keluar melewati batas baru, sehingga dibutuhkan simulasi air berbasis grid yang cepat dan stabil
- Tujuannya adalah model heightfield 2D yang memakai grid yang sama dengan medan pada skala sekitar 1 m, sekaligus memenuhi konservasi air, stabilitas yang dapat dikendalikan, dan biaya pembaruan linear
- Smoothed Particle Hydrodynamics dan Stable Fluids masing-masing dirancang untuk fluida partikel beresolusi tinggi dan volume fluida tertutup, sehingga tidak cocok dengan kebutuhan memproses permukaan bebas di atas medan secara cepat
- Metode virtual pipes yang dipilih menyimpan tinggi air dan aliran antar-sel pada staggered grid, lalu memproses percepatan aliran, penskalaan aliran keluar, dan pembaruan kolom air dengan beberapa loop array 2D
- Dengan
dtdangyang tepat, hasilnya tampak seperti air, tetapi masih ada keterbatasan karena tidak ada inersia dan difusi kecepatan, sehingga aliran air cepat tidak terus merambat masuk ke dalam danau
Mengapa air sulit dalam gim dengan modifikasi medan
- Dalam gim strategi atau simulasi kota/desa, air dapat berperan sebagai batas alami, pelayaran, memancing, perdagangan, pertempuran laut, air minum, transportasi, atau estetika
- Jika medan dapat diubah langsung, tingkat kesulitan penanganan air meningkat tajam
- Saat sumber daya seperti tanah, pasir, atau lempung digali dari tanah, lebih alami jika medannya ikut terangkat
- Batu dan bijih logam juga lebih cocok ditambang dengan menggali tanah daripada sebagai objek di atas permukaan
- Jika bangunan tidak bisa dibangun di lereng, medan harus diratakan sebelum konstruksi
- Modifikasi medan itu sendiri dapat disediakan sebagai alat ekspresi kreatif
- Situasi intinya adalah ketika batas danau atau genangan digali sehingga jalur air terbuka: ke mana dan seberapa banyak air akan mengalir
Bagian yang tidak cukup diselesaikan oleh solusi sederhana
- Beberapa jalan pintas yang mungkin adalah membekukan air di posisi awalnya, menganggap semua area di bawah ketinggian tertentu sebagai air, membatasi agar pemain tidak bisa menggali terlalu dalam, atau memakai model aliran sederhana ala Minecraft atau Dwarf Fortress
- Cara-cara ini mungkin sebagai alternatif, tetapi terlalu sederhana atau terlalu terasa berbentuk blok untuk dijadikan model utama
- Model Dwarf Fortress lebih dekat dibanding contoh lain, tetapi dirancang dengan asumsi 3D, sedangkan masalah yang dibutuhkan terutama adalah air di atas medan 2D
- Timberborn menggunakan model seperti yang dibahas di sini
Kondisi simulasi yang diinginkan
- Model air yang ditargetkan harus memenuhi kondisi berikut
- Sebaiknya berjalan pada grid yang sama dengan medan
- Skala rata-ratanya sekitar 1 m, dan tidak perlu mensimulasikan cipratan kecil
- Air dipandang sebagai heightfield di atas medan, tanpa mempertimbangkan aliran vertikal atau celah pada penampang vertikal
- Air harus mengalir, dan tidak boleh menghilang karena galat simulasi
- Stabilitas harus dapat dikendalikan
- Biaya satu langkah harus linear terhadap ukuran simulasi, idealnya selesai dalam beberapa loop
Ketidakcocokan dengan simulasi fluida yang ada
- Smoothed Particle Hydrodynamics dapat menghasilkan fluida beresolusi tinggi yang mengesankan, tetapi berbeda dari masalah yang dibutuhkan di sini
- Partikel air berukuran 1 m dapat terlihat seperti balon air
- Jika partikel dibuat lebih kecil, biaya performanya meningkat
- Tujuannya bukan realisme beresolusi tinggi, melainkan model yang cepat dan tampak masuk akal
- Stable Fluids karya Jos Stam lebih dekat ke model yang menangani volume yang sepenuhnya terisi fluida, seperti tangki tertutup
- Ini berbeda dari masalah yang secara langsung menangani permukaan bebas di atas medan
- Pada beberapa tahap, sistem linear jarang harus diselesaikan secara iteratif, sehingga biayanya besar
- Pendekatan ini menyelesaikan Navier-Stokes penuh, sedangkan yang dibutuhkan di sini adalah shallow water equations
Shallow water equations dan pilihan grid
- Shallow water equations adalah pendekatan yang merata-ratakan lapisan air di atas medan pada arah vertikal dan menanganinya sebagai persamaan 2D
- “Shallow” berarti asumsi bahwa ukuran vertikal kolom air jauh lebih kecil daripada skala horizontal yang menjadi perhatian
- Ini dapat berlaku misalnya saat kedalaman sungai beberapa meter hingga puluhan meter, sementara jarak yang diperhatikan berskala kilometer
- Collocated grid umum menyimpan tinggi air dan kecepatan pada sel yang sama, tetapi dapat menimbulkan masalah dalam dinamika fluida
- Jika turunan pertama didiskritisasi secara naif, bisa muncul bias arah atau ketidakstabilan
- Jika aliran masuk dari kiri-kanan dan keluar ke atas-bawah berada pada sel yang sama, muncul kontradiksi seolah-olah kecepatan totalnya 0
- Staggered grid menyimpan nilai seperti tinggi air dan densitas di sel, sedangkan kecepatan atau aliran disimpan pada edge antar-sel
- Array tinggi air
N x N - Array aliran arah X
(N+1) x N - Array aliran arah Y
N x (N+1)
- Array tinggi air
Metode virtual pipes
- Virtual pipes adalah metode yang menghitung aliran dengan menganggap sel-sel air terhubung oleh pipa virtual
- Salah satu paper yang dirujuk juga menangani kolom air multi-level dan koneksi vertikal, dan paper lain terutama membahas erosi hidraulik, tetapi tujuan tersebut dikecualikan di sini
- Nilai yang disimpan ada 3
water: tinggi kolom air tiap selflowX: total aliran air antara sel-sel tetangga horizontalflowY: total aliran air antara sel-sel tetangga vertikal
- Yang disimpan bukan kecepatan, melainkan aliran (flow, flux)
- Aliran dapat dilihat sebagai volume air yang lewat per satuan waktu
- Aliran antar-sel kosong secara alami didefinisikan sebagai 0
- Kecepatan adalah aliran dibagi luas penampang, sehingga ketika air nyaris tidak ada dapat muncul masalah 0/0 atau ambang batas
Tiga tahap dalam satu langkah
- Satu langkah simulasi dibagi menjadi tiga tahap
- Percepatan aliran: meningkatkan aliran antar-sel sesuai perbedaan tinggi permukaan air pada sel tetangga
- Penskalaan aliran keluar: jika air yang keluar dari suatu sel lebih banyak daripada jumlah yang sebenarnya dimiliki, kurangi aliran keluar
- Pembaruan kolom air: menambah atau mengurangi tinggi air tiap sel sesuai aliran tetangga
-
Percepatan aliran
- Jika tinggi air dua sel bertetangga berbeda, aliran dipercepat dari sisi yang lebih tinggi ke sisi yang lebih rendah
- Aliran diperbarui untuk edge internal arah X dan Y, dengan memakai
g,dt,dx, dandy - Luas penampang pipa virtual
Ahanya digunakan sebagai perkalian dengang, sehingga untuk penggunaan sederhana dapat diperlakukan seolah-olah digabung keg - Gesekan ditambahkan dengan mengurangi aliran pada setiap langkah
- Paper merekomendasikan koefisien
pow(friction, dt) - Agar nilainya lebih intuitif,
pow(1-friction, dt)dapat digunakan friction=0dapat dianggap sebagai gesekan maksimum yang sepenuhnya menghapus aliran sebelumnya, sedangkanfriction=1berarti tanpa gesekan- Semakin besar
dt, simulasi semakin cepat tetapi dapat menjadi tidak stabil - Dalam simulasi fluida, Courant-Friedrichs-Lewy condition penting
- Dalam praktiknya,
dtharus dikurangi sampai stabil, dan nilai yang digunakan kira-kira0.001hingga0.01
-
Pembaruan kolom air
- Setiap sel melihat empat aliran di sekitarnya untuk menambah atau mengurangi air
flowX(x,y)danflowY(x,y)yang masuk dari kiri dan bawah ditambahkanflowX(x+1,y)danflowY(x,y+1)yang keluar ke kanan dan atas dikurangkan- Ini adalah tahap yang benar-benar memindahkan air antar-sel sesuai aliran yang dihitung
-
Penskalaan aliran keluar
- Jika aliran terlalu besar, setelah pembaruan tinggi air di suatu sel dapat menjadi negatif
- Hanya aliran keluar dari tiap sel yang dijumlahkan, lalu diperiksa apakah air yang akan dikeluarkan dalam satu langkah melebihi jumlah air yang benar-benar dimiliki
- Jika jumlah yang dikeluarkan terlalu besar, aliran keluar dikurangi dengan rasio yang sama agar tinggi air tetap 0 atau lebih
- Tahap ini adalah perangkat stabilisasi utama yang mencegah jumlah air negatif
Medan, kondisi batas, dan penanganan viskositas
- Medan direfleksikan pada tahap percepatan aliran dengan menggunakan tinggi permukaan air alih-alih tinggi kolom air
- Tinggi permukaan air =
terrain(x,y) + water(x,y) - Sel dengan medan lebih tinggi memiliki permukaan yang lebih tinggi meski tinggi kolom airnya sama, sehingga air dapat bergerak
- Tinggi permukaan air =
- Kondisi batas ditentukan secara implisit oleh nilai aliran batas
flowX(0,y),flowX(N,y),flowY(x,0),flowY(x,N)adalah batas- Jika dibiarkan 0, itu bekerja seperti dinding
- Nilai masuk menambahkan air, dan nilai keluar menghapus air
- Untuk air di atas medan, batas aliran keluar yang membuat air di tepi peta menghilang bisa terasa alami
- Bagian sungai yang melintasi batas dapat dibuat sebagai batas masuk agar air sungai mengalir
- Aliran batas harus diatur ulang pada awal setiap langkah simulasi
- Karena penskalaan aliran keluar dapat mengubah aliran batas sehingga batas aliran keluar berubah seperti dinding
- Dalam paper juga ada suku viskositas yang mengurangi aliran sesuai tinggi air
- Idenya adalah lapisan air kecil sulit bergerak karena gaya internal, sedangkan lapisan air besar bergerak lebih bebas
- Ini dapat berguna untuk aliran magma
- Untuk air, ini tidak digunakan, dan pada skala medan besar pengaruh viskositas hampir tidak ada
Alur implementasi dan bentuk performa
- Keseluruhan kode disusun dalam urutan berikut
- Inisialisasi aliran batas
- Prahitung koefisien gesekan
pow(1-friction, dt) - Percepatan aliran X
- Percepatan aliran Y
- Penskalaan aliran keluar untuk mencegah jumlah air negatif
- Pembaruan kolom air
- Sebagian besar simulasi selesai dengan 4 loop yang menelusuri beberapa array 2D dan rumus sederhana
- Kode pembaruan C++ lengkap dapat dilihat di water_2d.cpp
- Contoh video berasal dari WebGPU water simulator yang dipublikasikan beberapa hari lalu; partikel dalam video hanya untuk visualisasi dan tidak ikut dalam simulasi
- Jika nilai
dtdangyang sesuai ditemukan, hasilnya terlihat stabil, memenuhi kebutuhan, dan tampak seperti air
Keterbatasan yang tersisa
- Model ini tidak memiliki inersia dan difusi kecepatan
- Meski aliran cepat masuk ke danau, ia tidak terus merambat ke bagian dalam danau, melainkan menyebar ke segala arah
- Jika tinggi air sama, dua aliran paralel yang berlawanan arah dapat tetap ada tanpa saling berinteraksi
- Saat air pertama kali memasuki suatu area, muncul gelombang, dan ini dapat terlihat agak aneh
Memperluas ke grid heksagonal dan segitiga
- Gim yang dituju tidak menggunakan grid persegi, melainkan grid segitiga reguler
- Grid segitiga dapat dilihat sebagai dual dari grid heksagonal
- Jika pusat heksagon yang berdekatan dihubungkan dengan garis, akan terbentuk grid segitiga reguler
- Ini mirip dengan bentuk penggunaan axial coordinate system pada grid dual dari arah pointy-top hex dalam artikel hexagonal grids dari Red Blob Games
- Grid segitiga juga dapat disimpan dalam array 2D biasa yang sedikit miring
- Tinggi kolom air disimpan pada vertex grid agar rendering permukaan air lebih mudah
- Aliran dibagi menjadi tiga arah
- Aliran arah X
- Aliran arah Y
- Aliran arah Z
- Pada grid vertex
N x N, array berikut digunakan- Array aliran X
(N+1) x N - Array aliran Y
N x (N+1) - Array aliran Z
(N+1) x (N+1), dengan nilai bottom-left dan top-right tidak digunakan
- Array aliran X
- Dibandingkan grid persegi, cukup tambahkan aliran Z ke kondisi batas, percepatan, penskalaan aliran keluar, dan pembaruan air
- Bagian tersulit adalah tidak salah dalam indexing
- Kode C++ untuk grid segitiga/heksagonal dapat dilihat di water_2d_hex.cpp
- Metode ini bisa sedikit lebih isotropik daripada grid persegi
1 komentar
Opini Hacker News
Ada beberapa video Coding Adventure yang memakai pendekatan lain untuk membahas simulasi fluida
Rendering Fluids: https://www.youtube.com/watch?v=kOkfC5fLfgE
I Tried Putting my Fluid Simulation on a Planet: https://www.youtube.com/watch?v=8nIB7e_eds4&t=817s
GitHub: https://github.com/SebLague/Fluid-Sim?tab=readme-ov-file
[0] https://www.youtube.com/playlist?list=PLFt_AvWsXl0dT82XMtKAT...
[1] https://github.com/SebLague/Geographical-Adventures
Salah satu alasan simulasi hidrologi sulit dalam game dengan generasi prosedural adalah ketika air menumpuk, ia memengaruhi sel-sel di sekitarnya, lalu pengaruh itu terus menyebar lagi ke sel-sel sekitar lainnya
Generasi prosedural sering cocok untuk paralelisasi, tetapi justru pada area tak terbatas, tempat paralelisasi tampak paling dibutuhkan, perhitungan semacam ini sulit diparalelkan dengan benar
Saya belum banyak melihat topik ini dieksplorasi, dan di antara orang-orang yang mengerjakan hal terkait, saya khususnya menyukai https://nickmcd.me. Itu termasuk terrain prosedural terbaik yang pernah saya lihat
Namun pekerjaan itu pun areanya terbatas karena desain simulasinya. Sebagai solusi yang mungkin, pendekatan yang tampak paling baik adalah membuat batas daerah aliran sungai yang tidak bisa ditembus secara prosedural, lalu mensimulasikan seluruh daerah aliran sekaligus secara paralel
Ini masalah yang sangat menarik, tetapi di luar cakupan pengetahuan saya, jadi saya lebih banyak berada di posisi pengamat
Istilah itu merujuk pada wilayah yang dapat memengaruhi nilai di titik tertentu, dan wilayah yang dapat dipengaruhi oleh nilai titik tersebut; ini berhubungan langsung dengan yang dibahas di atas. Dalam beberapa kasus, wilayah itu bisa diketahui sebelumnya
Misalnya untuk mensimulasikan langkah 10 jam, beri batas selebar 10 sel grid. Hitung 10 langkah di tiap area, lalu sinkronkan keadaan batas dengan simulasi batas lain yang dihitung secara paralel, dan ulangi
Sedikit keluar topik, tetapi saya teringat bagian tulisan yang menyebut manipulasi terrain diperlukan untuk pengumpulan sumber daya
Saya selalu berpikir Animal Crossing menanganinya dengan cukup cerdas dan efisien tanpa manipulasi terrain. Saat menebang pohon, Anda mendapat kayu gelondongan, tetapi jumlahnya terbatas dan pada dasarnya ada waktu tunggu sebelum bisa digunakan lagi
Ini bisa memberi rasa adanya umpan balik dan sumber daya terbatas tanpa manipulasi terrain yang mahal. Tentu tidak cocok untuk semua game dan lebih pas di peta kecil, tetapi layak dipertimbangkan. Jika tidak benar-benar diperlukan untuk game, sering kali lebih baik tidak melakukan manipulasi terrain
Sebagai cara memberikan sumber daya, itu memang standar, tetapi waktu tunggu tidak menghilangkan masalah sumber daya tak terbatas, hanya memperlambatnya. Selain itu agak membosankan dan dampaknya lemah
Ini tulisan yang menggali topik tersebut dengan rapi, dan senang melihat Timberborn disebut
Belakangan saya benar-benar kecanduan game itu, jadi kalau belum mencobanya saya sangat merekomendasikannya. Aliran air berbasis fisika terasa seperti karakter lain di dalam game, dan mencari cara membendung air untuk dipakai di mesin serta mengairi ladang adalah loop gameplay utamanya
Menarik dan eksekusinya juga sangat baik. Risiko terbesar saat mengembangkan hal seperti ini adalah menghabiskan berjam-jam hanya mengutak-atik parameter sambil menikmati hasil yang indah
Ini mengingatkan saya pada 2011 ketika saya mengimplementasikan sendiri hidrodinamika berbasis GPU untuk pekerjaan makalah. Saya menangani darah sebagai fluida yang mengalir di atas permukaan, yaitu jaringan, mensimulasikannya dalam 2D lalu memproyeksikannya ke atas mesh dengan mempertimbangkan gravitasi dan kemiringan permukaan
Saya juga mengunggah video singkat ke YouTube: https://youtu.be/4vGrNc-GGW8
Benar-benar keren
Baru-baru ini saya bereksperimen dengan ide serupa dengan bantuan o3-mini-high. Saya menjelaskan ide algoritmanya, lalu ia mengimplementasikan dan merendernya dalam 3D tanpa intervensi manual. Namun prompt-nya saya masukkan beberapa kali
https://3d-water-sim.netlify.app/
Belum sempurna, karena saya berhenti mengutak-atiknya, dan setiap iterasi sebelumnya membuatnya meningkat cukup besar. Yang menarik, untuk generasi terrain ia tidak mengambil dari CDN atau semacamnya, tetapi mengimplementasikan versi noise Perlin yang berfungsi dari awal dengan benar
Ini pertanyaan tentang perbedaan antara perjalanan dan tujuan
Bagian dalam tulisan yang mengatakan, “Model ini tidak memiliki inersia dan difusi kecepatan. Meski arus air yang cepat masuk ke danau, ia tidak merambat lebih jauh ke bagian dalam danau, melainkan menyebar ke segala arah sambil mengabaikan inersia yang terakumulasi. Jika ketinggian air sama, dua arus air paralel yang mengalir ke arah berlawanan pun bisa saja tidak saling berinteraksi,” sepertinya bisa diatasi dengan mengambil rata-rata bersama 6 panah aliran di sekitar yang searah
Caranya dengan memberi bobot besar pada panah depan-belakang, dan bobot kecil pada panah di samping. Misalnya ketika ada panah seperti ini
-a-> -b->
-c-> -d-> -e->
-f-> -g->
New_d = d * (1 - 2*.1 - 4*.01) + (c+e).1 + (a+b+f+b).01
Di sini .1 dan .01 adalah bobot yang dipilih sembarang sehingga perlu disetel, dan bisa juga memasukkan pemangkatan seperti yang digunakan untuk mengurangi osilasi. Jika koefisien itu ikut dimasukkan, bentuknya bisa menjadi seperti ini
New_d = d * (1 - 2*.1 - 4*.01 - .001) + (c+e).1 + (a+b+f+b).01
grid 0: tinggi air di tiap sel
grid 1: aliran air di tiap sisi, yaitu turunan pertama
grid 2: percepatan air di tiap sel, yaitu turunan kedua
Strukturnya adalah tiap grid merupakan grid dual dari grid sebelumnya dan menyimpan nilai turunannya. Sebenarnya, tanpa perlu memperlakukan data sisi secara khusus, sepertinya cukup menyimpan data titik sudut dan memprosesnya murni sebagai grid dual. Aliran pada sisi dapat diturunkan dari jumlah aliran di dua titik sudut ujung sisi tersebut
Jadi tinggi fluida diperbarui berdasarkan aliran, lalu percepatan diperbarui berdasarkan seberapa banyak massa fluida yang masuk ke sel dan dengan kecepatan berapa, setelah itu aliran diperbarui berdasarkan percepatan dan tinggi fluida saat ini. Saya tidak begitu paham dinamika fluida, tetapi dari sudut pandang simulasi numerik ini tampak masuk akal, dan aliran diagonal juga menjadi memungkinkan
Seperti disebutkan dalam tulisan, beban komputasinya jauh meningkat, jadi perlu dipertimbangkan dulu apakah tingkat realisme sebesar itu memang dibutuhkan untuk kasus penggunaan nyata
Ini hasil kasar yang saya buat beberapa tahun lalu karena penasaran: https://aperocky.com/hydrosim/
Sampai proyek pribadi ini masuk ke rak penyimpanan dingin, saya belum berhasil mencari tahu cara menangani erosi. Saya suka penulis membahas bagian ini dan bahkan menyertakan persamaannya
Baru-baru ini saya merilis sesuatu yang mirip. Ada pembuatan heightfield acak, perpindahan sedimen, sampai erosi: https://github.com/Ono-Sendai/terraingen
Anda bisa mencoba langsung simulasi banjir edukatif yang dibuat oleh developer hebat di perusahaan kami sebagai bagian dari proyek riset
https://flood.concord.org/
Untuk melihat efek yang besar, Anda perlu mengubah nilai model di toolbar bawah
Ini adalah simulasi berbasis sel yang menghitung nilai sel di WebGL berdasarkan sel-sel tetangga. Shader yang melakukan perhitungan itu ada di sini
https://github.com/concord-consortium/flooding-model/blob/ma...