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.
kqr 38 days ago [-]
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.
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.
ttul 38 days ago [-]
What shocked me is that Nick is only 25 years old. Wow.
NotAnOtter 37 days ago [-]
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.
bodge5000 38 days ago [-]
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)
setr 38 days ago [-]
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
bodge5000 36 days ago [-]
> 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.
setr 33 days ago [-]
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
38 days ago [-]
TheGRS 38 days ago [-]
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.
Agentlien 38 days ago [-]
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
elliotbnvl 38 days ago [-]
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):
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.
fingerlocks 38 days ago [-]
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.
elliotbnvl 38 days ago [-]
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.
gus_massa 38 days ago [-]
> 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
Where .1 and .01 are weight that I just invented but must be tweaked, perhaps with a power like the one they use to kill osculations. That coefficient can also be included:
I 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.
chabska 38 days ago [-]
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.
gus_massa 38 days ago [-]
The first evacuation (without the dumping coefficient)
is as good as conserving momentum as the original model. (Assuming you calculate all the new values using a new matrix instead of overwriting the old ones.) It breaks energy conservation, but that simulates the friction between oposite direction currents, without going to the whorls level.
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.
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.
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.)
lisyarus 38 days ago [-]
Very cool! Based on the video you're also doing some hierarchical subdivisions?
vladms 37 days ago [-]
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...
h1fra 38 days ago [-]
Game developers are truly on an other level
ikety 38 days ago [-]
Always makes me feel like a CRUD monkey when I see this stuff
all2 38 days ago [-]
Add a water sim to your crud?
m12k 38 days ago [-]
"This button lets you edit the blog post. This button saves it. And this one lets you pour a stream of water over it"
magicalhippo 38 days ago [-]
"And this button turns your blog into a Doom map"
(ie letters being walls, background the floor)
pornel 38 days ago [-]
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.
lisyarus 38 days ago [-]
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.
FrustratedMonky 38 days ago [-]
Guess this explains why water effects in Minecraft are bit kludgy. It isn't so simple.
AlotOfReading 38 days ago [-]
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.
adrianpluis 38 days ago [-]
interesting perspective. I see how this can get tedious even for a large business like Microsoft.
matheist 38 days ago [-]
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.
semi-extrinsic 38 days ago [-]
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.
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.
Clor 38 days ago [-]
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.
lisyarus 38 days ago [-]
Interesting, thanks! Is it kinda like the Gibbs phenomenon?
matheist 38 days ago [-]
Take a look at the other reply, which says it's actually not dispersion. My mistake!
lisyarus 38 days ago [-]
Yeah I've seen it, no worries! :)
wiz21c 38 days ago [-]
What the author implemented is a specific case of Saint Venant shallow water equations (in case you want to know where it comes form).
lisyarus 38 days ago [-]
Yep, it literally says that in the article
tithe 38 days ago [-]
I like that analogy, rules are pipes through which behavior flows.
esafak 38 days ago [-]
The author might enjoy Populous, Powermonger, Realms, etc.
jordanmorgan10 38 days ago [-]
Yup I’ll just take your word for it
amelius 38 days ago [-]
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.
Voltage 38 days ago [-]
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.
hgomersall 38 days ago [-]
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
[0] https://www.youtube.com/playlist?list=PLFt_AvWsXl0dT82XMtKAT...
[1] https://github.com/SebLague/Geographical-Adventures
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.
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.
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)
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 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.
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
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
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.
It’s a journey versus destination question.
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
then Where .1 and .01 are weight that I just invented but must be tweaked, perhaps with a power like the one they use to kill osculations. That coefficient can also be included: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.
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.
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.
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...
That's Creeper World for you.
https://www.youtube.com/watch?v=XCyPT2e95zY&t=420s
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.)
(ie letters being walls, background the floor)
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.
See e.g. the classic exposition by Leveque:
https://www.clawpack.org/riemann_book/html/Shallow_water.htm...
Computational accuracy is not important to me at all.