3
\$\begingroup\$

I am making a Voxel game and I'd like to add rivers that can be redirected. So I thought that if a player replaces a river block or digs up a block next to a river block the river would repath itself to the sea. The rivers path would have a direction and a speed in that direction.

The rivers path would be determined by these rules: If the river can go down in its direction it will and then pick up speed. or if it has a speed under 2 and it can go sideways and down it will and keep its direction. Otherwise it will keep going in its direction until blocked, where it will pick a new direction. If the river can't go anywhere it will fill up the layer its on like a bathtub and go up. Repeat until it reaches the ocean.

However I can't figure out how you can know what to fill. The data would be stored in some sort of height map. 1 = same level, 0 = down a level, 2 = up a level

For example:

222222
211112
211112
211112
211112
222222

I can tell that the 2s completely surround the 1s meaning that all the 1s should get filled with water if the river goes up. But how can a computer tell?

\$\endgroup\$
3
\$\begingroup\$

A fairly straightforward algorithm for this can be established, if you can assume some fixed 2D grid of cells, each of which contains a value for the level of the water in them. Imagine an infinitely tall grid of perspex dividers, at the bottom of which are holes/tubes to facilitate flow between adjacent cells. What's key is to not think about the cells themselves, but the connections between cells. E.g. in the simplest grid:

A B

C D

there are 4 connections between individual cells (between A and B, between B and D, between C and D, and between A and C). You can make diagonal connections as well if you like, it doesn't make a difference to the core algorithm. You can also add solid cells, connections into which are blocked, which in your case would form the banks of your imaginary river.

Imagine that you start with some initial state. It won't necessarily be 'level' or in equilibrium, and if it isn't, you expect that the first few updates will cause flow between the cells until equilibrium is reached.

Phase 1

For each connection, look at the cells on either side, and calculate the difference in water level between them. Say, for example, that A has a level of 3 and B has a level of 1. Then the connection from A to B has a 'pressure' of 2 (3-1) in the direction of B. If the cell on the other side of the connection is not empty (say because it's ground), then the pressure will be 0. If the cell on the other side has more water than this cell, the pressure will be some negative number.

The end result of this phase will be a numeric value for each connection as to how quickly water will flow through that connection, and in which direction. This is an 'instantaneous' value, in that it describes potential for flow when you next update. It is not trying to describe how much water will flow, just how much water wants to flow.

Phase 2

For each cell, look at the pressure of all of the connections that touch that cell. Use the information on those pressures to decide how much fluid to transfer from this cell to the cells on the other side of the connections. For example, say A (with its level of 3) has an outward pressure of 2 towards B (with level 1), and an outward pressure of 1 towards C (which has level 2). So in the next update, you'd transfer twice as much fluid to cell B as you do towards C.

Exactly how much fluid to transfer between cells is something you decide is sensible. Limiting that rate of transfer will cause your fluid to flow more slowly (like treacle instead of water), and you want to have a damping value of some sort to stop oscillation (e.g. water flowing from A to B, then B to A, then A to B, but never settling). It's also crucial to distribute the outwards flow between all connections (e.g. not just send all water out along the first connection you process)

What's key is that you only transfer in one direction. Because when you come to process cell B, you don't want to 'pull' fluid from A, because you may have already 'pushed' fluid from A to B.

The reason why you do it in two phases is so that you can make the decision on how fast the flows will be between cells, before you start changing the values of the individual cells. Otherwise fluid moving from A to B would affect the decision of how much fluid wants to move from B to D.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ It's worth noting that this is a rubbish algorithm for doing any sort of realistic water motion. In it, water has no momentum, viscosity, and the modelling of the flow as a regular grid is not physically realistic at all. But for simplistic river flow modelling, it should serve. It's also fairly easy to add things like water sources (cells or connections that change to a particular level over time), and sinks (cells or connections that drain water out of the system). \$\endgroup\$ – MrCranky Nov 6 '16 at 15:43
  • \$\begingroup\$ It doesn't matter if it's not very realistic. It just needs to be ok. That seems like a pretty good algorithm. However I still would like to know how I can determine if a group of 1s is surrounded by 2s. \$\endgroup\$ – Ben Beazley Nov 6 '16 at 16:30
  • \$\begingroup\$ In the sort of a simulation I've proposed, you wouldn't track the river's speed, you just let the water flow. Digging up a block by the river would open up a connection to the dug up cell; similarly filling in a block in the river would block connections to that cell. You get the 'flow' effect by introducing water at the source of the river, and taking it away at the 'sea' end, and trusting the levelling algorithm to cause the water to shift from one cell to the next naturally. If you care more about the flow than the levelling, then this is probably not the algorithm to use. \$\endgroup\$ – MrCranky Nov 7 '16 at 13:56
  • \$\begingroup\$ Now I re-read your question, I realise that you seem to want something a bit simpler than what I propose. If you just want to have water spread in all directions until it finds a ground block at the same level, then look into flood fill algorithms. \$\endgroup\$ – MrCranky Nov 7 '16 at 14:00
  • \$\begingroup\$ While obvious, I find it (far too) amusing that the term flood fill was coined for pixels acting like a fluid, and here is being suggested for actually modeling a fluid represented as (vo|pi)xels. \$\endgroup\$ – Sean Middleditch Dec 9 '16 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.