Simulating water over terrain(lisyarus.github.io)
lisyarus.github.io
Simulating water over terrain
https://lisyarus.github.io/blog/posts/simulating-water-over-terrain.html
59 comments
I really enjoy Coding Adventure. He has a small game 'Geographical Adventures' which has lovely music and is really relaxing [0] [1]
[0] https://www.youtube.com/playlist?list=PLFt_AvWsXl0dT82XMtKAT...
[1] https://github.com/SebLague/Geographical-Adventures
[0] https://www.youtube.com/playlist?list=PLFt_AvWsXl0dT82XMtKAT...
[1] https://github.com/SebLague/Geographical-Adventures
One of the challenges with simulated hydrology, especially in procedurally generated games that I’ve found, is that water accumulates and can affect nearby cells, which affects other nearby cells, and so on.
So although procedural generation is often a great case for parallelizing, one of the cases you’d most want parallelization for can’t really be parallelized on unbounded domains.
I haven’t seen a lot of exploration of this topic.
One of my favourite people on the internet working on this stuff is https://nickmcd.me — he’s got some of the best procedurally generated terrain I’ve seen.
But his work is also domain-constrained due to the simulation design.
I’ve thought about potential solutions and I think the best way would be to procedurally generate water shed boundaries that can’t be broken. Then you can parallelize and simulate an entire water shed at once.
It’s such an interesting problem, but it’s also way out of my knowledge domain so I’m mostly just an observer.
So although procedural generation is often a great case for parallelizing, one of the cases you’d most want parallelization for can’t really be parallelized on unbounded domains.
I haven’t seen a lot of exploration of this topic.
One of my favourite people on the internet working on this stuff is https://nickmcd.me — he’s got some of the best procedurally generated terrain I’ve seen.
But his work is also domain-constrained due to the simulation design.
I’ve thought about potential solutions and I think the best way would be to procedurally generate water shed boundaries that can’t be broken. Then you can parallelize and simulate an entire water shed at once.
It’s such an interesting problem, but it’s also way out of my knowledge domain so I’m mostly just an observer.
If you get curious, in the space of solving partial differential equations they sometimes speak about "regions of influence" and "regions of dependence" – this refers to exactly what you are talking about – given a specific point, there is some area that can influence its value, and there is some area that can be influenced by its value. Sometimes it's possible to know ahead of time which those areas are.
Amazing resource, thank you!
No, seriously, do check https://nickmcd.me Incredible!
Yeah interesting question. Presumably you can do it by having a border around each region, and a max speed of effect propagation (i.e. causality). Then if you want to simulate e.g. 10 time steps, you have a border of 10 grid cells. So do 10 time steps on each region, then synchronise border state with other parallel border sims. Then rinse and repeat.
What shocked me is that Nick is only 25 years old. Wow.
Came here to do a worse job of writing this comment. Terrain generation via water simulations are cool, except they don't work for the primary use cases for terrain generation. Water simulations are inherently slow you have to choose to either
1) Have a small domain
2) Have a large resolution
3) Have a very long initial load time
Any of these suck for game development.
1) Have a small domain
2) Have a large resolution
3) Have a very long initial load time
Any of these suck for game development.
Off topic, but the post mentions needing terrain manipulation for resource gathering.
I always thought animal crossing had a clever and efficient approach to this without any terrain manipulation. You can chop a tree, and it'll dispense logs, but only so many before it essentially has a cooldown. You get the feedback and the finite resources, without expensive terrain manipulation.
Of course that doesn't work for every game, and really works better on smaller maps, but something worth considering. Terrain manipulation is pretty expensive, if your game doesn't need it it's probably better to do without (again, a generalisation)
I always thought animal crossing had a clever and efficient approach to this without any terrain manipulation. You can chop a tree, and it'll dispense logs, but only so many before it essentially has a cooldown. You get the feedback and the finite resources, without expensive terrain manipulation.
Of course that doesn't work for every game, and really works better on smaller maps, but something worth considering. Terrain manipulation is pretty expensive, if your game doesn't need it it's probably better to do without (again, a generalisation)
The blog mentioned that strategy, in the form of gold ore in a gold ore boulder found lying around
It a standard strategy for resource dispensation (though cooldown doesn’t alleviate the infinite resource problem; it just slows it down), it’s just… boring and unimpactful
It a standard strategy for resource dispensation (though cooldown doesn’t alleviate the infinite resource problem; it just slows it down), it’s just… boring and unimpactful
> it’s just… boring and unimpactful
It's also cheap and easy. You have limited resources to work with in game dev, even more if you care about performance on anything but the most powerful machines. I'm of the opinion that those resources should be spared for what makes your game unique and fun.
It's also cheap and easy. You have limited resources to work with in game dev, even more if you care about performance on anything but the most powerful machines. I'm of the opinion that those resources should be spared for what makes your game unique and fun.
If the actual act of resource acquisition isn’t actually meaningful to gameplay, it should probably be eliminated outright. The correct thing to do is simply consider it a resource node with ownership, and grant resource stacks automatically at a given time interval. This is probably the cheapest, easiest strategy while allowing for gatekeeping.
In animal crossing of course, half the point of the game is to kill time peacefully, so it wouldn’t apply. With the game in question, the meaningfulness is unknown
In animal crossing of course, half the point of the game is to kill time peacefully, so it wouldn’t apply. With the game in question, the meaningfulness is unknown
[deleted]
Neat dive on this topic, and I appreciate calling out Timberborn! I'm obsessed with that game currently, big big big recommendation if you haven't checked it out yet. The water physics are like another character in the game and figuring out how to dam up a bunch of water to use in your engines and to water your fields is an essential part of the gameplay loop.
This was fun and really nicely executed. By far the biggest risk when developing this stuff is just wasting hours looking at the pretty results and playing around with tweaking parameters.
This brought back memories of implementing my own GPU-based fluid dynamics in 2011 for my thesis. It was also for fluid (blood) across a surface (tissue) and was simulated in 2D but projected across the mesh with considerations for gravity and surface inclination. Even put a short video of it on YouTube: https://youtu.be/4vGrNc-GGW8
This brought back memories of implementing my own GPU-based fluid dynamics in 2011 for my thesis. It was also for fluid (blood) across a surface (tissue) and was simulated in 2D but projected across the mesh with considerations for gravity and surface inclination. Even put a short video of it on YouTube: https://youtu.be/4vGrNc-GGW8
This is super, super cool!
I was experimenting with a similar idea recently with the help of o3-mini-high. I talked it through my idea for an algorithm, and it implemented and rendered it in 3D with no manual intervention (although I did prompt it a number of times):
https://3d-water-sim.netlify.app/
It's not perfect yet because I stopped playing with it, but it was improving significantly with each iteration.
Fun fact, it implemented a working version of perlin noise correctly from scratch instead of pulling it from a CDN or something as part of this, for the terrain generation.
I was experimenting with a similar idea recently with the help of o3-mini-high. I talked it through my idea for an algorithm, and it implemented and rendered it in 3D with no manual intervention (although I did prompt it a number of times):
https://3d-water-sim.netlify.app/
It's not perfect yet because I stopped playing with it, but it was improving significantly with each iteration.
Fun fact, it implemented a working version of perlin noise correctly from scratch instead of pulling it from a CDN or something as part of this, for the terrain generation.
Curious, when you do these exercises, is for entertainment or learning? If the latter, do you find it still worthwhile to read the blog post of this thread, since you didn’t implement anything yourself?
It’s a journey versus destination question.
It’s a journey versus destination question.
Both! But more for entertainment right now, since I already know how to build most of what I ask for and it’s more about the final product and being able to rapidly iterate and realize ideas. I’m finding a lot of what I enjoyed about programming is the thing I make (although the journey is also pleasant), so I feel significantly more capable with AI as another tool in my toolbox. As Simon Willison said, it lets me knock out all the little tech projects I fantasize about but just don’t have the time or energy to build myself. It’s a huge force multiplier.
> Of course, this model isn't perfect. One of the most obvious problems is that it doesn't have inertia and velocity diffusion. A fast water stream entering a lake won't propagate further inside the lake, but will instead spread out in all directions, ignoring all accumulated inertia. Two parallel water streams going in opposite directions can exist and not interact with each other (provided the water levels are equal).
I guess that can be solved averaging he value of a flow arrow with the 6 neighbor arrows in the same direction. With a big weight with the arrows that are in the front and back, and a small weight for the arrows that are on the sides. For example with these arrows
I guess that can be solved averaging he value of a flow arrow with the 6 neighbor arrows in the same direction. With a big weight with the arrows that are in the front and back, and a small weight for the arrows that are on the sides. For example with these arrows
-a-> -b->
-c-> -d-> -e->
-f-> -g->
New_d = d * (1 - 2*.1 - 4*.01) + (c+e)*.1 + (a+b+f+b)*.01
New_d = d * (1 - 2*.1 - 4*.01 - .001) + (c+e)*.1 + (a+b+f+b)*.01I would say the proper solution is to add another grid for the second derivative, this time matching the original grid. That is
grid 0: water height in each cell
grid 1: water flow at each edge (first derivative)
grid 2: water acceleration in each cell (second derivative)
So each grid is the dual of the previous one and stores its derivative. In fact I don't think you even need to store edge data as a special case, just corner data and work purely with dual grids. You can derive the edge flow by taking the sum of the flow at the two corners of the edge. So you update the fluid height based on flow, then you update acceleration based on how much fluid mass flowed into the cell with what velocity, then you update the flow based on acceleration and current fluid height. I don't really know fluid dynamics, but looking at it purely from a numerical simulation standpoint, it sounds about right. It would also let you have diagonal flow.
grid 0: water height in each cell
grid 1: water flow at each edge (first derivative)
grid 2: water acceleration in each cell (second derivative)
So each grid is the dual of the previous one and stores its derivative. In fact I don't think you even need to store edge data as a special case, just corner data and work purely with dual grids. You can derive the edge flow by taking the sum of the flow at the two corners of the edge. So you update the fluid height based on flow, then you update acceleration based on how much fluid mass flowed into the cell with what velocity, then you update the flow based on acceleration and current fluid height. I don't really know fluid dynamics, but looking at it purely from a numerical simulation standpoint, it sounds about right. It would also let you have diagonal flow.
That violates conservation of momentum. To get realistic flow, you need to use continuity equation to preserve the energy of the flow and let the shear dissipate and diffuse into whorls. Which is a lot of extra calculation, as pointed out in the article, so you need to ask yourself if that level of realism is really necessary for your use case.
The first evacuation (without the dumping coefficient)
I agree that this is not 100% realistic, but I think it's a good and simple addition to the model in the article, and tweaking the coefficients it may give a good enough visual result.
New_d = d * (1 - 2*.1 - 4*.01) + (c+e)*.1 + (a+b+f+b)*.01
I agree that this is not 100% realistic, but I think it's a good and simple addition to the model in the article, and tweaking the coefficients it may give a good enough visual result.
Crude plug of a curiosity I had a few years ago: https://aperocky.com/hydrosim/
I couldn't figure out erosion before this project moved to the cold shelf of personal project storage.. I liked how author mentioned this and attached the equations.
I couldn't figure out erosion before this project moved to the cold shelf of personal project storage.. I liked how author mentioned this and attached the equations.
I also released something similar recently, with random heightfield generation and sediment transport and erosion too: https://github.com/Ono-Sendai/terraingen
You can play with an educational flooding simulation a great developer (not me) at my company built as part of a research project:
https://flood.concord.org/
NOTE: you need to change the model values in the bottom toolbar to see big effects.
It is a cell-based simulation that uses WebGL to calculate cell values based on adjacent cells. The shader that does that is here:
https://github.com/concord-consortium/flooding-model/blob/ma...
https://flood.concord.org/
NOTE: you need to change the model values in the bottom toolbar to see big effects.
It is a cell-based simulation that uses WebGL to calculate cell values based on adjacent cells. The shader that does that is here:
https://github.com/concord-consortium/flooding-model/blob/ma...
How about simulating water, then sending bombs into it?
That's Creeper World for you.
https://www.youtube.com/watch?v=XCyPT2e95zY&t=420s
That's Creeper World for you.
https://www.youtube.com/watch?v=XCyPT2e95zY&t=420s
Nice explanation. I like the viscosity part, I implemented something similar a couple of years ago in an open source RTS game engine (test video at: https://www.youtube.com/watch?v=cQW8WXNpYXk), and without viscosity water was spreading thin and due to floating point, at some point it was spreading on flat surfaces and "evaporating".
Also, the grid resolution required to obtain nice waves was a bit too much for the effort I put 5 years ago (probably needed another thread, etc.)
Also, the grid resolution required to obtain nice waves was a bit too much for the effort I put 5 years ago (probably needed another thread, etc.)
Very cool! Based on the video you're also doing some hierarchical subdivisions?
The hierarchical subdivision is done only at the rendering steps to reduce the number of polygons. A better rendering would be anyhow required, but I was more curious if the rest of the game would be fine with different and dynamic levels of water. The units seem to behave fine, but due to performance being rather poor I did not polish the code...
Game developers are truly on an other level
Always makes me feel like a CRUD monkey when I see this stuff
Add a water sim to your crud?
"This button lets you edit the blog post. This button saves it. And this one lets you pour a stream of water over it"
"And this button turns your blog into a Doom map"
(ie letters being walls, background the floor)
(ie letters being walls, background the floor)
Storing values at the edges of cells makes the math simpler, but unfortunately makes a GPU implementation harder.
In this setup one edge update affects two cells, so the cells are no longer trivially independent. It's still possible to update cells in parallel, but it requires splitting the update into two checkerboard-like passes.
In this setup one edge update affects two cells, so the cells are no longer trivially independent. It's still possible to update cells in parallel, but it requires splitting the update into two checkerboard-like passes.
It's true that it makes it more complicated on the GPU side in general, but specifically in this scenario everything works out just fine, mostly because all updates effectively ping-pong between flow & water height buffers, and you never change both in the same kernel.
Guess this explains why water effects in Minecraft are bit kludgy. It isn't so simple.
Water and lava in Minecraft were originally even simpler flood fills. If you dug into a source at max height (64) of the 256x256 map, it would flood the entire world with an expanding wall of death.
interesting perspective. I see how this can get tedious even for a large business like Microsoft.
The waves when the water is first entering the area is called numeric dispersion, it's a consequence of discretizing. It can be mitigated somewhat by smoothing the entering wall of water so that there's not a sharp discontinuity.
I don't think so, the waves are actual shock waves which are a solution to the Riemann problem for the shallow water equations because they are nonlinear hyperbolic equations. You can find them even before you start introducing any numerical grid or discretization.
See e.g. the classic exposition by Leveque:
https://www.clawpack.org/riemann_book/html/Shallow_water.htm...
See e.g. the classic exposition by Leveque:
https://www.clawpack.org/riemann_book/html/Shallow_water.htm...
Very interesting, my mistake! I'm more familiar with acoustics and assumed it was the same phenomenon, but it looks like I jumped to a mistaken conclusion.
I agree 100% with this comment -- you can clearly see the energy separating into its component frequencies as the solution evolves. The reason is that different frequencies of the solution propagate at different speeds. Smoothing the discontinuity would indeed reduce the high frequency components, such that the effects wouldn't appear so extreme. The shallow water equations only allow for one shock wave mode as far as I recall, it wouldn't explain why we seem to get increasingly more shocks as the solution evolves.
I like that analogy, rules are pipes through which behavior flows.
The author might enjoy Populous, Powermonger, Realms, etc.
Yup I’ll just take your word for it
I always find it a bit of a disappointment when the focus is only on how a simulation looks rather than if it is physically accurate.
Given my interest in games and demos, I feel the opposite. I'm always in search of the real-time method that looks plausible and can cover huge areas in 3d space.
Computational accuracy is not important to me at all.
Computational accuracy is not important to me at all.
It's nothing like that complicated. They just need to retuculate the splines.
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