Simulating water over terrain

2025 Feb 4

If you don’t want a long an boring introduction, skip directly to the virtual pipes method description.
I will get a little bit sad if you do this, though x)

I’m somewhat obsessed with terrain generation, grid-based games, simulations, and stuff like that. And this stuff often involves water, — or at least it seems natural for water to be there.

Say, you’re generating a map for a strategy game, and you don’t want the map borders to just be filled with inpenetrable void (like in old-school RTS games). Wouldn’t it be nice for the border to be filled with water, like in this map from one of my abandoned projects:

This provides a nice natural border, and maybe allows you to introduce some more water-related mechanics like sailing, fishing, trading, and sea warfare. Here’s a 3D view of a similar island from the same project, for no particular purpose:

Or, say, you’re making a peaceful village/town simulation game and you want your town to have a river for drinking, fishing, transportation, or even pure aesthetics. Or maybe you want a river just as a divider between areas, like in my first released game:

I hope I’ve convinved you: having water is really nice. (Not that it wasn’t obvious anyway).

But water has problems.

Contents

Problems with water

Most games don’t allow terrain modification, which is reasonable — not every game needs it. Even those that do can often get away with some simplistic approach: I can easily imagine being able to fill up a hill in a game like Civilization (though it would probably break a lot of stuff gameplay-wise), and it doesn’t interact with water in any way.

My game, however, does need terrain modification:

Why? Well, uhm, because my design docs say so! I promise, it was somewhere on that page… or that one…

Seriously, though, there are indeed a couple of reasons in my case:

• Some resourses in my game are literally taken from the ground, like dirt, sand, and clay, and it just makes sense that when you dig them up, the ground gets removed (otherwise we’d get an infinite source, which is not ideal)
• Similarly, for stuff like stones & metal ores I’d prefer for them to get excavated from the ground when mining (instead of having a shiny “gold ore” boulder lying on the ground, as many games do), and it makes sense that the mined ground gets removed as well
• My game doesn’t allow constructing buildings on slopes, so it’s important to be able to level the terrain before building something on it, like in The Sims
• I want to give the player a ton of tools for creative expression, and terrain modification is one of them
• Let’s be honest, everybody loves terrain modification

So, OK, that does this have to do with water? Say, you have a lake, or even a puddle, and you’ve dug up its border and opened a free passage for the water to flow out. What does the water do?

There are a number of simple options:

• Water doesn’t go anywhere, and stays where it was initially generated (of course, this just feels boring and dumb)
• Water doesn’t flow; instead, everything below a certain height level is considered water, like in Sapiens
• Water also exists below some level, but you can’t even dig that far, or maybe you can only dig one level down to remove hills/mountains, like in RimWorld
• Water flows using some extremely simplistic model, like in Minecraft
• Water flows using some nice but still simplistic cellular-automata-ish model, like in Dwarf Fortress

Among these solutions, not one feels satisfactory to me. They are good fallbacks to consider if I fail to find a better option, but as a main water model they are just too…boring. Dwarf Fortress comes closer than others, but still, their model is too blocky yet also designed for 3D, which I don’t really need (see the next section).

For years (yep, literally) I was passively searching for a model that would work for my needs. I researched a ton of literature on fluid simulations, particularly in climate & oceans/rivers simulations, and got really scared because most of the models used there are insanely complicated, while their applicability to my case was always blurry since the scientific community usually doesn’t cover game design. One time I even managed to compute something like the expected currents flowing around an island, by solving a mass conservation equation for the liquid flow, i.e. something like (nabla (text{mass}cdottext{velocity})=0):

It’s already something, but I need a dynamic model, not a static assignment of currents. (It can still be useful for some funny climate map generation, I guess.) By the way, it is theoretically easy to turn a dynamic model into a static one: just add equations like (frac{dX}{dt}=0) for all your state variables (X), saying that you have a steady state (i.e. a solution that’s perfectly stable and doesn’t change with time, like a slowly flowing river).

I could just give up, of course. After all, it’s important to remember that, in the end, I’m not making some reality simulator, — I’m making a game, and I’m free to bend the rules of it any way I see fit. However, I also couldn’t shake off the feeling that some clever combination of simple formulas should work for my case. And I was right!

By the way, if reading this section made you scream “TIMBERBOOOORN” seven times, guess what: they use exactly the same model as I’m going to describe.

Also, if you know other models that you think would suit my case — tell me! I’d love to hear about them!

The setup

I’ve said the phrase “my case” four times already, but what exactly do I mean? Here’s the list of features I want my water simulation to have:

• The simulation should probably work on a grid, preferably on the same grid I’m using for the terrain
• The average scale of the simulation should be around 1 meter or so, — I don’t care about tiny splashes of water, while a kilometer-wide simulation is too coarse for something like a city builder game (I can easily add fake higher-frequency visual details on the rendering side without having to simulate them)
• I’m fine with assuming that water is a height field over the terrain, i.e. it doesn’t flow vertically and it doesn’t have gaps in vertical cross-sections, because my game’s terrain is itself a height field, and because this basically reduces the problem to 2D
• Water should be able to flow (duh)
• Water shouldn’t magically disappear due to simulation errors (this happens with some models I tried before)
• The simulation should be controllably stable
• The simulation should be fast enough, ideally the cost of a single simulation step should be linear in the simulation size (i.e. a few for-loops over the simulation domain)

As you can guess, I’ve found such a model, and this is what this article is about. But first,

Non-solutions

Let me describe a couple of popular options that do not suit my scenario.

Smoothed Particle Hydrodynamics is an insanely popular way to do fluid simulations which produces impressive results. However, this method also solves a completely different problem! It gives you realistic, highly detailed and beautiful simulations, which is not what I want. Remember the “average scale” thing I said earlier? Having 1 meter-sized water particles doesn’t really work, — they’ll look like water-filled balloons, — but having smaller particles hits performance too much. I don’t need a high-detailed simulation, I want a fast and reasonable one!

Jos Stam’s Stable Fluids is probably the most well-known fluid simulation work known in computer graphics, which also solves a different problem. It works with a full volume of fluid, rather than with a free surface like I need. Think of a closed tank filled with water, as opposed to water over terrain. It is also far from fast: some steps of the simulation require iteratively solving a sparse linear system, which is doable but still expensive.

In fact, I’ve implemented Stable Fluids once, and it’s a really fun and impressive model, it’s just a model for a different thing (it solves the full Navier-Stokes instead of the shallow water equations that we actually need):

Shallow water equations

Beware: I’m not a physicist, and this section might be full of complete nonsense.

Now, whenever we talk about seeking a mathematical model of something, it usually means we need some equations to solve. Generally, fluid motion is described by the Navier-Stokes equations, or by the simpler Euler equations. However, these equations also don’t talk about a free water surface, but instead about a volume completely filled with fluid.

If we look at the variables these equations work with, we see fluid velocity, pressure, density, thermodynamic work, stress tensor, and some other things, and you’d need a good full course in fluid dynamics to figure out which of these are known, which are unknowns, and which can be derived from others (after lazily researching this for years I still don’t know the answer, btw). Notice that there’s nothing like “amount of water” here. We do have mass density, but all equations divide by it, so we can’t really have zero density or a boundary between fluid and air. (This can actually be done using stuff like the particle-in-cell and marker-and-cell methods, if I’m not mistaken.)

Even in the simplest form, these equations involve pressure (p), which is unknown and changes with time, but there’s no equation for how exactly it evolves! I.e. there’s no (frac{dp}{dt}=dots) equation. Instead, the time evolution of the pressure field is implicitly built into the other equtaions. This is closely related to the projection step in the Stable Fluids solver.

What we need is to take something like Navier-Stokes, assume that we have a layer of water on top of some terrain (commonly called the bed in this case), and do some sort of averaging out along the vertical direction, so that we’re left with purely 2D equations describing