地形上の水シミュレーション
(lisyarus.github.io)- 地形を掘ったり埋めたりできるゲームでは、湖・川・水たまりが新しい境界へ流れ出す必要があるため、高速で安定した格子ベースの水シミュレーションが必要
- 目標は、約1mスケールで地形と同じ格子を使い、水の保存・制御可能な安定性・線形の更新コストを満たす2D高さ場モデル
- Smoothed Particle Hydrodynamics と Stable Fluids は、それぞれ高解像度の粒子流体と閉じた流体体積に向いており、地形上の自由表面を高速に処理したい条件とは合わない
- 採用した virtual pipes 方式は staggered grid に水位とセル間の流量を保存し、流れの加速・流出スケーリング・水柱更新をいくつかの2D配列ループで処理する
- 適切な
dtとgでは水らしく見える結果が得られるが、慣性と速度拡散がないため、速い水流が湖の中へ入り込んでもそのまま伝播しないという限界が残る
地形編集ゲームで水が難しい理由
- ストラテジーゲームや都市・村シミュレーションにおいて、水は自然な境界、航海・釣り・交易・海戦、飲料水・輸送・景観といった役割を担える
- 地形を直接変えられると、水処理の難度は大きく上がる
- 土・砂・粘土のような資源を地面から掘り出すなら、地形も一緒に除去されるほうが自然
- 石や金属鉱石も、地表上のオブジェクトとして扱うより、地面を掘りながら採掘する方式のほうが合っている
- 斜面に建物を建てられないなら、建設前に地形を平坦化する必要がある
- 創造的な表現ツールとして地形編集そのものを提供できる
- 核心となる状況は、湖や水たまりの境界を掘って水路が開いたとき、水がどこへどれだけ流れるか
単純な解決策では足りない点
- 可能な回避策としては、水を初期位置に固定する、特定の高さ以下をすべて水とみなす、深く掘りすぎないよう制限する、Minecraft や Dwarf Fortress 式の単純な流れモデルを使う、といった方法がある
- これらの方式は代替案としては可能だが、主モデルとして使うには単純すぎるか、ブロック感が強すぎる
- Dwarf Fortress のモデルは他の例より近いが、3Dを前提に設計されており、必要な問題は主に2D地形上の水
- Timberborn はここで扱うものと同じモデルを使っている
求めるシミュレーション条件
- 目標とする水モデルは次の条件を満たす必要がある
- 地形と同じ格子で動作することが望ましい
- 平均スケールは約1m程度で、小さな水しぶきまでシミュレートする必要はない
- 水は地形上の高さ場として捉え、垂直方向の流れや垂直断面の空隙は考慮しない
- 水は流れるべきであり、シミュレーション誤差で消えてはならない
- 安定性を制御できる必要がある
- 1ステップのコストはシミュレーションサイズに対して線形であるべきで、数回のループで終わる形が理想的
既存の流体シミュレーションとの不一致
- Smoothed Particle Hydrodynamics は印象的な高解像度流体の結果を作れるが、ここで必要な問題とは異なる
- 1mサイズの水粒子は水風船のように見える可能性がある
- 粒子をさらに小さくすると性能コストが増える
- 目標は高解像度の写実性ではなく、高速でそれらしいモデル
- Jos Stam の Stable Fluids は、閉じたタンクのように流体で満たされた体積を扱うモデルに近い
- 地形上の自由表面を直接扱う問題とは異なる
- 一部の段階で疎な線形システムを反復的に解く必要があり、コストが大きい
- Navier-Stokes 全体を解くアプローチであり、ここで必要なのは shallow water equations
Shallow water equations と格子の選択
- Shallow water equations は、地形上の水層を鉛直方向に平均化し、2D方程式として扱うアプローチ
- “Shallow” は、水柱の鉛直方向の大きさが、関心のある水平方向スケールよりはるかに小さいという仮定を意味する
- 川の水深が数m〜数十mで、関心距離がkm単位の場合のように成り立ち得る
- 一般的な collocated grid は水位と速度を同じセルに保存するが、流体力学では問題が生じ得る
- 1階微分を素朴に離散化すると、方向の偏りや不安定性が生じることがある
- 左右から入り上下へ出ていく流れが同じセルにあると、全体速度が0のように見える矛盾が生じる
- Staggered grid は、水位・密度のような値はセルに、速度や流れはセル間のエッジに保存する
N x Nの水位配列(N+1) x NのX方向流量配列N x (N+1)のY方向流量配列
Virtual pipes 方式
- Virtual pipes は、水セル同士が仮想的なパイプで接続されているとみなして流れを計算する方法
- 参照した論文の1つは複数レベルの水柱と垂直接続も扱い、もう1つは主に水力侵食（hydraulic erosion）を扱うが、ここではその目標は除外する
- 保存する値は3つ
water: 各セルの水柱高さflowX: 水平方向に隣接するセル間の総水流量flowY: 垂直方向に隣接するセル間の総水流量
- 速度の代わりに**流量（flow, flux）**を保存する
- 流量は単位時間あたりに通過する水の体積と見なせる
- 空のセル間の流れは自然に0と定義される
- 速度は流量を断面積で割った値なので、水がほとんどないときに0/0やしきい値の問題が生じ得る
1ステップを構成する3段階
- シミュレーションの1ステップは3段階に分かれる
- 流れの加速: 隣接セルの水面高さの差に応じてセル間の流れを増やす
- 流出スケーリング: 1つのセルから出ていく水が実際の保有量より多い場合、流出流量を減らす
- 水柱更新: 隣接する流れに応じて各セルの水位を増減させる
-
流れの加速
- 隣接する2つのセルの水位が異なると、高い側から低い側へ流れが加速する
- X・Y方向の内部エッジについて流れを更新し、
g,dt,dx,dyが使われる - 仮想パイプの断面積
Aはgとの積としてのみ使われるため、単純な用途ではgに含めたものとして扱える - 摩擦は各ステップで流れを減らす形で追加される
- 論文は
pow(friction, dt)係数を推奨している - より直感的な値として使うために
pow(1-friction, dt)を使用できる friction=0は以前の流れを完全に消す最大摩擦、friction=1は摩擦なしと見なせるdtが大きいほどシミュレーションは速いが、不安定になり得る- 流体シミュレーションでは Courant-Friedrichs-Lewy condition が重要
- 実際には安定するまで
dtを下げる必要があり、使用した値はおおよそ0.001〜0.01
-
水柱更新
- 各セルは隣接する4つの流れを見て水を増減させる
- 左・下から入ってくる
flowX(x,y),flowY(x,y)は加える - 右・上へ出ていく
flowX(x+1,y),flowY(x,y+1)は引く - 計算された流れに従って、セル間で水を実際に移動させる段階
-
流出スケーリング
- 流れが大きすぎると、更新後にあるセルの水位が負になる可能性がある
- 各セルの出ていく流れだけを合計し、1ステップで取り除かれる水が実際の水量を超えるかを検査する
- 除去量が大きすぎる場合、出ていく流れを同じ比率で減らし、水位が0以上を維持するようにする
- この段階が負の水量を防ぐ中核的な安定化装置
地形、境界条件、粘性処理
- 地形は、流れの加速段階で水柱高さの代わりに水面高さを使う形で反映する
- 水面高さ =
terrain(x,y) + water(x,y) - 地形が高いセルは、同じ水柱高さでも表面が高くなるため水が移動し得る
- 水面高さ =
- 境界条件は境界の流量値で暗黙に決まる
flowX(0,y),flowX(N,y),flowY(x,0),flowY(x,N)が境界にあたる- 0にしておくと壁のように動作する
- 流入値は水を追加し、流出値は水を除去する
- 地形上の水では、マップ端の水が消える流出境界が自然な場合がある
- 川が境界を横切る部分は流入境界にして、川水が流れるようにできる
- 境界流量は各シミュレーションステップの開始時に再設定する必要がある
- 流出スケーリングが境界流量を変え、流出境界が壁のように変わり得るため
- 論文には、水位に応じて流れを減らす粘性項もある
- 薄い水層は内部の力のため動きにくく、厚い水層はより自由に動くという考え方
- マグマの流れのような場面では有用かもしれない
- 水では使用せず、大きな地形スケールでは粘性の影響はほとんどない
実装の流れと性能特性
- 全体のコードは次の順序で構成される
- 境界流量の初期化
pow(1-friction, dt)摩擦係数の事前計算- X流量の加速
- Y流量の加速
- 負の水量を防ぐための流出スケーリング
- 水柱更新
- シミュレーションの大半は、いくつかの2D配列を走査する4つのループと単純な数式で終わる
- C++ の更新コード全体は water_2d.cpp で見られる
- 動画例は数日前に公開した WebGPU water simulator によるもので、動画内の粒子は可視化用であり、シミュレーションには参加していない
- 適切な
dtとgの値を見つけると安定して見え、要件を満たし、水らしく見える結果が得られる
残る限界
- このモデルには慣性と速度拡散がない
- 速い水流が湖に入っても湖の内側へそのまま伝播せず、全方向へ広がる
- 水位が同じなら、反対方向の平行な2つの水流が相互作用せずに存在できる
- 水がある領域に初めて入るとき波が発生し、やや奇妙に見えることがある
六角形・三角形格子への拡張
- 対象ゲームは正方形格子ではなく、正規三角形格子を使用する
- 三角形格子は六角形格子の双対（dual）と見なせる
- 隣接する六角形の中心を線で結ぶと正規三角形格子になる
- Red Blob Games の hexagonal grids 記事で、axial coordinate system を pointy-top hex 方向の双対格子に使う形に似ている
- 三角形格子も、少し傾いた通常の2D配列に保存できる
- 水柱高さは格子頂点に保存し、水面レンダリングを容易にする
- 流れは3方向に分かれる
- X方向流量
- Y方向流量
- Z方向流量
N x N頂点格子では次の配列を使う(N+1) x NのX流量配列N x (N+1)のY流量配列(N+1) x (N+1)のZ流量配列。ただし bottom-left と top-right の値は使わない
- 正方形格子と比べると、境界条件、加速、流出スケーリング、水更新にZ流量を追加すればよい
- 最も難しい部分はインデックスを間違えないこと
- 三角形・六角形格子用の C++ コードは water_2d_hex.cpp で見られる
- この方式は正方形格子より少し等方的かもしれない
1件のコメント
Hacker Newsのコメント
流体シミュレーションを扱った別のアプローチとして、Coding Adventure の動画がある
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
手続き型生成ゲームで水文学シミュレーションが難しい理由の一つは、水がたまると周囲のマスに影響し、その影響がさらに別の周囲のマスへと広がり続ける点にある
手続き型生成は並列化に向いていることが多いが、実際には最も並列化が必要に見える無限領域では、この種の計算をうまく並列化するのが難しい
このテーマはあまり深く探究されているのを見たことがなく、関連する作業をしている人の中では https://nickmcd.me が特に好きだ。これまで見た手続き型地形の中でも屈指の出来だと思う
ただしその作業も、シミュレーション設計の都合で領域が制限されている。あり得る解法としては、壊れない流域境界を手続き的に生成し、その流域全体を一度に並列シミュレーションする方式が最もよさそうに見える
とても興味深い問題だが、自分の知識の範囲外なので主に観察者の立場だ
ある点の値に影響を与え得る領域と、その点の値が影響を与え得る領域を指し、まさに上で述べた内容に通じている。場合によってはその領域を事前に知ることもできる
たとえば 10 時間ステップをシミュレーションするなら、10 グリッドセル分の境界を設ける。各領域で 10 ステップ計算した後、並列計算された別の境界シミュレーションと境界状態を同期し、それを繰り返せばよい
少し話はそれるが、記事で資源採集のために地形操作が必要だと書かれていた部分を思い出した
Animal Crossing は地形操作なしでもかなり賢く効率的に処理していたと以前から思っている。木を切ると丸太が出るが、出る量は一定までで、実質的にリキャスト時間がある
高価な地形操作がなくてもフィードバックと有限資源らしさを与えられる。もちろんすべてのゲームに合うわけではなく、小さなマップでよりうまく機能するが、検討する価値はある。ゲームに本当に必要でないなら、地形操作はしない方がよいことが多い
資源の供給方法としては標準的だが、リキャスト時間では無限資源の問題はなくならず、速度が遅くなるだけだ。それに少し退屈で影響も弱い
このテーマをすっきり掘り下げた記事で、Timberborn に触れてくれたのもうれしい
最近そのゲームに完全にはまっているので、まだやったことがないなら強く勧めたい。物理ベースの水の流れがゲーム内のもう一人のキャラクターのようで、水をせき止めてエンジンに使い、畑に供給する方法を見つけるのが中核となるゲームループだ
面白く、実装も本当によくできている。こういうものを開発するときの最大の危険は、きれいな結果を眺めながらパラメータをいじっているうちに何時間も溶かしてしまうことだ
2011 年に論文作業のため、自分でGPUベースの流体力学を実装したことを思い出した。表面、つまり組織の上を流れる流体である血液を扱い、2D でシミュレーションした後、重力と表面の傾きを考慮してメッシュ上に投影した
短い動画も YouTube に上げている: https://youtu.be/4vGrNc-GGW8
本当にすごい
最近 o3-mini-high の助けを借りて似たようなアイデアを試した。アルゴリズムのアイデアを説明したところ、手動介入なしで 3D に実装してレンダリングしてくれた。ただしプロンプトは何度か与えた
https://3d-water-sim.netlify.app/
まだ完璧ではないが、いじっている途中で止めたからで、反復するたびにかなり大きく改善していた。面白いのは、地形生成のために CDN などから持ってくるのではなく、Perlin ノイズの動くバージョンを最初からきちんと実装していたことだ
旅路と到着点の違いに関する問いだ
記事中の「このモデルには慣性と速度の拡散がない。速い水流が湖に流れ込んでも、湖の内側へそれ以上伝播せず、蓄積された慣性を無視したまま全方向に広がる。水位が同じなら、反対方向に流れる2本の平行な水流も互いに相互作用しないことがありうる」とある部分は、同じ方向の周囲6つの流れ矢印と平均を取れば解決できそうに思える。
前後の矢印には大きい重みを、横の矢印には小さい重みを与える形である。たとえば次のような矢印があるとき
-a-> -b->
-c-> -d-> -e->
-f-> -g->
New_d = d * (1 - 2*.1 - 4*.01) + (c+e).1 + (a+b+f+b).01
ここで .1 と .01 は適当に置いた重みなので調整が必要で、振動を減らすのに使うようなべき乗を入れることもできる。その係数まで含めると、次のようにできるかもしれない。
New_d = d * (1 - 2*.1 - 4*.01 - .001) + (c+e).1 + (a+b+f+b).01
grid 0: 各セルの水位
grid 1: 各辺の水流、つまり1次微分
grid 2: 各セルの水加速度、つまり2次微分
各格子が前の格子の双対格子であり、その微分値を保存する構造である。実際には辺のデータを特別扱いする必要はなく、頂点データだけを置いて純粋に双対格子として扱ってもよさそうである。辺の流れは、その辺の両端頂点の流れの和として導ける。
したがって、流れで流体の高さを更新し、どの速度でどれだけの流体質量がセルに入ってきたかに応じて加速度を更新し、その後に加速度と現在の流体高さで流れを更新する。流体力学には詳しくないが、数値シミュレーションの観点では妥当に見え、対角方向の流れも可能になる。
記事で述べられている通り、計算量ははるかに増えるので、その程度の現実性が実際のユースケースに必要かを先に見極めるべきである。
数年前に気になって作った粗い成果物: https://aperocky.com/hydrosim/
この個人プロジェクトが冷たい保管棚に入る前まで、侵食 をどう扱うかを突き止められなかった。筆者がこの部分に触れ、方程式まで添えていたのがよかった。
最近、似たものを公開した。ランダムな heightfield 生成、堆積物の移動、侵食まで入っている: https://github.com/Ono-Sendai/terraingen
うちの会社の優秀な開発者が研究プロジェクトの一環として作った教育用 洪水シミュレーション を直接触れる。
https://flood.concord.org/
大きな効果を見るには、下のツールバーでモデル値を変える必要がある。
隣接セルをもとに WebGL 上でセル値を計算するセルベースのシミュレーションである。その計算を行うシェーダーはここにある。
https://github.com/concord-consortium/flooding-model/blob/ma...