The World Builder - Rivers versus lakes

[RonHiler]

So I hit a bit of a snag when designing the world builder, and it has to do with water.

The background is this: Each map point is going to be given a rainfall amount, and that will add to the standing water on that point. So every point on the map (that is land) is going to have an elevation and a certain amount of water on it (ocean points are ignored, it is assumed that the point elevation + water height = sea level (which is equal to 0)).

So what do we do with this water? It will either stay put (standing water, i.e. a lake) or it will move (running water, i.e. a river). Which one it does is strictly a matter of neighbor point elevations.

At first glance, it seems straightforward enough, but actually, it gets a bit tricky. Obviously, if you have two points with different total elevations (by which I mean land elevation + height contributed by standing water), you want to even them out such that the total elevations are equal.

So: Lets say point A has a land elevation of 10 with 3 meters of standing water, and point B (which is a neigbor of point A) has an elevation of 9 meters with 5 meters of standing water. This is easy, we have a total elevation of 13 meters at point A and a total elevation of 14 at point B, so we make .5 cubic meters worth of water running, and move it from B to A, giving both a total elevation of 13.5 meters. Good. (for now we'll ignore the movement of topsoil and erosion this moving water will cause and just stay the land elevations stay static).

Now lets examine point C, also a neighbor of point A, but not of point B. Point C has a land elevation of 8 meters and 2 meters of standing water, giving us a total elevation of 10. Point A has a total elevation of 13.5 meters. So we move 1.75 cubic meters of water from A to C, giving both a total elevation of 11.75 meters.

But see the issue? A now is at 11.75 meters, and B is at 13.5 meters. Ever see a lake with bumpy water like that? Me neither.

I haven't really figured out a good way to deal with this yet. The only thing I have come up with so far is to create an ordered list (from lowest to highest land elevation) and first figure out all the points that will be connected to a particular lake, take all the water in those points and smooth them over the entire area.

But that could be tricky, and take a fair bit of time to do. Anyone have any better ideas?

[Strike]

Depending on what time spans you're trying to model...

Lakes (and rivers) actually *can* be bumpy, especially if you're dumping a large amount of water on a small area in a short time.
Flash floods are the extreme example of this.

I'd actually expect rivers and streams to be non-flat (monotonic decreasing, if not quite 'bumpy'), following the topography of the underlying riverbed.


But if you just want to know the average elevation once you figure out which points are part of a lake....
Can't you just average all the points together?

Point A was 10 + 3; Point B was 9 + 5; Point C was 8 + 2.

Averaging those totals gives... ( 13 + 14 + 10 ) / 3 = 37 / 3 ~ 12.33

( I'm leaving the question of where the lake ends and the input/output flows begin as an exercise for the reader--and you'll want to watch for any islands this process might create. )

[Shane Christopher]

Hrm, tricky, I read this last night and decided it was best to sleep on it.

What we have to do is think about how water works in stages. It falls as rain, it flows, it eventually reaches the sea, it falls as rain again, basically anyway.

This would seem to indicate to me atleast that we would need to iterate the water process as many times as necessary until all points have had their rainfall reach the sea.

I am assuming we will be using a constant rate of rainfall for each point? It is probably possible to factor in rainfall changes in what I am thinking but I will leave that for later, erosion, etc. can also be factored in for each time you iterate it.

Now we have to think about what a lake is, basically it is a natural dip in the land that has to fill up with water before there becomes an exit point for that water to flow down.

Okay, so on first iteration we allow for the rainfall on each tile, next for each tile it queries the overall height for the tiles around it and that tile basically tries to average out the height of water in that group of 9 tiles. Before actually putting that change into affect though we go through the entire list of tiles, judging where each tiles water will flow into before any changes are actually made. After all tiles are processed we effect what is essentially an instaneous change in water level for all tiles according to the simulation we just ran.

It is very important that the simulation be done at the same time for all tiles like this as in nature it is not that one square metre will be processed before the next.

Now, we will probably end up with bumpy water still, again we add rainfall to each point then repeat the process. We repeat this process until each tiles water has reached the sea and the process has started over. We must either keep a track of this somehow or simply let the world builder iterate the water step thousands of times, it doesn't particularly matter as this will be an initial step only done at map creation.

This should, if my head is working it out correctly result in what we are looking for.


EDIT: What's really gonna worry you is underground water flow

[RonHiler]

( I'm leaving the question of where the lake ends and the input/output flows begin as an exercise for the reader--and you'll want to watch for any islands this process might create. )

LOL, thanks. Unfortunately, that's the real tricky bit. If we know all the points that are going to be associated with a particular lake, then yeah, all we have to do is add up the standing water totals and smooth them over the points. That's the easy part.

The real hard part is coming to a determination of what points will comprise the lake area. If you start at a low point on the terrian that has standing water, you can presume you have a lake point (presuming it doesn't border an ocean point, if so you don't have a lake point, what you have is a river mouth point). So you have a lake point and now you want to check the points around it to see if they are also lake points. But with every point you add to it, two things change. The total water you have and the total surface area that water has to cover. This can cause the total elevation of the water area to either rise or drop.

If it rises, we're fine, we move on to the next point. But if it drops, all hell breaks loose. Let's say I've determined that 30 points are part of a lake (I started with the low point and kept adding points, with the water level rising at each point high enough to cover the land of the test points). But then I add the 31st point, and the effect is to *lower* the water level. Now what? Do I go back and check the first 30 points again to make sure they are still under water? What if they are not? Do I remove their water also from the total water? Then I have to recheck again? What if the level goes back up and the point that was underwater then above water once again submerges? We put the water back into the lake again?

What we have is a recursive issue, where one point change can affect all the other points, and it can be indefinite. It's a real boondoggle (it's a word! )

This would seem to indicate to me atleast that we would need to iterate the water process as many times as necessary until all points have had their rainfall reach the sea.

I don't think that's going to be practical. I expect the simulator is going to do a full iteration loop several thousand times (plate movement, water movement, tempatures, biomass, the whole works). We have to put a limit on the time spent in each iteration or it's gonig to take two days to create a world (jokes about God taking 6 days not withstanding). I can't spend that much time dealing with water. I think we need to come up with a simplified way to determine what water is donig without introducting iterations within the iterations, heh.

EDIT: What's really gonna worry you is underground water flow

LOL, no way. There are a few things even I'm not crazy enough to try to put in there, and that's one of them. Another one is land areas that are lower than sea level (e.g. Death Valley). My simulator won't do that, it will just make them ocean tiles.

[Shane Christopher]

As you are doing the iteration loop already several thousand times as you said couldn't you simply use the existing loop to run through the water process?

All you would have to do then is have a constant 'current water level' value for each tile that carries over to the next iteration that the rainfall gets added to for that iteration.

[RonHiler]

Ah, so you think it is unimportant that adjoining water tiles be perfectly "smoothed", but rather retain their bumpiness. You may be right. We simply move an amount of water from its origin to the lowest neighbor such that the levels equalize (if possible) and leave it at that. If lakes end up "bumpy" at the end of a particular iteration, who cares! No big deal.

That may work. I'll have to think about it. Not totally realistic, but it may be a workable solution.

And sorry Strike, I missed your comment on streams being "bumpy". Yes, they were always intended to be so, running water won't be averaged, it will just be moved. It was only lakes I was having a problem with

[Strike]

After you decided that you don't really need smooth, anyway...

The real hard part is coming to a determination of what points will comprise the lake area. If you start at a low point on the terrian that has standing water, you can presume you have a lake point (presuming it doesn't border an ocean point, if so you don't have a lake point, what you have is a river mouth point). So you have a lake point and now you want to check the points around it to see if they are also lake points. But with every point you add to it, two things change. The total water you have and the total surface area that water has to cover. This can cause the total elevation of the water area to either rise or drop.

That's irrelevant to the lake, though, right?
A point inside a lake where the (averaged) water-level is lower than the terrain height is an island, rather by definition.

If it rises, we're fine, we move on to the next point. But if it drops, all hell breaks loose. Let's say I've determined that 30 points are part of a lake (I started with the low point and kept adding points, with the water level rising at each point high enough to cover the land of the test points). But then I add the 31st point, and the effect is to *lower* the water level. Now what? Do I go back and check the first 30 points again to make sure they are still under water?

Wait till you find the boundaries of the lake. Then go back and see which tiles are really islands inside the lake.

What if they are not? Do I remove their water also from the total water?

Well, the water has to go somewhere, right? o.O Why not dump it into the lake?

I think we need to come up with a simplified way to determine what water is donig without introducting iterations within the iterations, heh.

... There are a few things even I'm not crazy enough to try to put in there, and [underground water flow is] one of them. Another one is land areas that are lower than sea level (e.g. Death Valley). My simulator won't do that, it will just make them ocean tiles.

Oh, drek. I just realized something about your initial conditions:

1) EACH tile has a rainfall amount.
2) Said water is classified as "moving" aka river or stream or "standing" aka lake.

What I'm envisioning is not what you described--my bad.
I'm used to places being *not* underwater, and I expect streams to be underwater. I guess you're modeling larger areas than I first thought--what I get for skimming instead of reading.

We have...
1) Water flows downhill.
2) Local minima hold water.
3) Water overflows into adjacent tiles when said tiles have a lower elevation+rainfall.

#3 is the problem: we don't know how to move water from one tile to surrounding tiles so that those nine tiles end at equal height, because all tiles flow into each other. We could set up 'relative flow' levels for each tile boundary, and then add rainfall to each tile individually, flowing outwards when indicated by the diagram we just generated.... I don't know that this would give flat lakes, though.

And anyways, by your original criteria, we will have parts of lakes classified as 'rivers' as the water tries to equalize itself out. I'm a bit confused here, could you provide an example using 9 tiles? (Maybe a square of 4 would be good enough, I'm not sure.)

Hm. Am I any closer to understanding this problem now?
Gah, no, I've gotta be missing something... you also go on to say "...running water won't be averaged, it will just be moved. It was only lakes I was having a problem with"

But you don't know how to tell the difference, right?!

[Shane Christopher]

A critical part of my idea is that water doesn't flow just from one tile to one other, it basically tries to average out the water level in the surrounding tiles by flowing out to them.

Say we have the following situation for example (overall height used here):

4,5,3
6,8,4
5,4,9

So we need some way of deciding how much water we want to see flowing out of the middle tile (the one we're dealing with) to the others in order to balance things out. First of all no water will flow into the bottom right tile as that's higher already then the mid tile.

My thinking at the moment is that we would add up the differences between the adjacent tile levels and the mid tile level first.

So the differences are:

4,3,5
2,-,4
3,4,-

At the moment I'm not sure whether to just ignore the bottom right tile or take it as a negative, I think ignoring it will work best.

So the total is 25.

Now we have to decide how much water the tile will be giving out so we get the average of the 7 tiles involved, again ignoring the bottom right tile and the mid tile.

31/7 = 4.428. This is the value that this tile thinks it will be equalised at, note it won't actually be equalised but I'm just trying to work out what the water will do naturally.

So we take:

8-4.428 which gives us 3.572 units of water that the tile will give out.

Now it's simply a matter of working out how much each tile gets from that amount.

Just changed my mind on the above, it wouldn't really be that realistic, instead maybe the following would be better.

Basically we take a certain amount of water off the middle tile one at a time and spread it out to the nearby tiles, repeating this until there is no tile higher then the middle tile.

For each 1 unit, or 0.1 unit (if you find it not taking that much time and want to get more accurate) you would do the following.

1 unit divided by the total difference of 25 gives us 0.04.

Now each tile gets its difference value multiplied by 0.04. So we get the following amounts given out:

0.16, 0.12, 0.20
0.08, ----, 0.16
0.12, 0.16, ----

If we add those up then that's the full 1 unit given out. Now while for purposes of calculations we add those values onto the surrounding tiles and take the 1 unit off the middle tile.

4.16, 5.12, 3.20
6.08, 7.00, 4.16
5.12, 4.16, 9.00

We repeat the step to find out the total amount of difference. In this case it's 17. I didn't think about this but it's probably always going to be <original difference> - (the amount of tiles affected + 1).

So we repeat the steps again, we are taking 1 unit off so 1 unit/17 is 0.0588~

So we have the difference*0.0588 to give us the amount each tile receives.

You'll note that for the next run through the left tile will be higher then the mid tile so that can now be ignored as with the bottom right tile.

Once you get to just one tile remaining lower then the mid tile you simply average their values out.


Now, very important that I mention this again, these changes will not take actual affect until all the tiles have gone through this process. That means that when we move on to the right hand tile to work out it's flow the tiles will all have their original values but we will keep track of the water they will have been given in total. So if the tile with elevation of 3 is given 1 unit by one tile and 2 units by another etc.. it will probably end up with quite a lot of water going into it.

Think of this as a splash effect, if you have water it will fill up a gap beside it to the point that it will be lower in the original point and higher in the point beside it, eventually though it will equal itself out through a few iterations. The same should happen with our simulation. That tile that used to be elevation 3 will probably be up around 9 or 10 at the end of the processing as it's lost no water due to it being the lowest around it and gained a lot. The next iteration it will give out a lot of water due to it being so high and gain only it's small rainfall so eventually through perhaps hundreds of iterations we'll come out with something realistic.

Obviously the granularity of the simulation comes into play in the realism. You might find that using a granularity of 0.1 or 0.2 units at a time leads to realistic results through just some hundreds of iterations quicker then a granularity of 1 unit at a time over thousands of iterations.

[RonHiler]

Oh, drek. I just realized something about your initial conditions:

1) EACH tile has a rainfall amount.
2) Said water is classified as "moving" aka river or stream or "standing" aka lake.

Correct. Although for purposes of terminology, it's more like:
1) EACH tile has a rainfall amount. Rainfall adds to standing water total.
2) Said water is converted to "moving" aka river or stream or remains "standing" aka lake.

This is to distinguish rainfall from water sitting on the ground. Initially all water is standing water. It gets converted to moving water when it is determined that there is an elevation difference between the tile it is sitting on and a neighboring tile.

We have...
1) Water flows downhill.
2) Local minima hold water.
3) Water overflows into adjacent tiles when said tiles have a lower elevation+rainfall.

#3 is the problem: we don't know how to move water from one tile to surrounding tiles so that those nine tiles end at equal height, because all tiles flow into each other. We could set up 'relative flow' levels for each tile boundary, and then add rainfall to each tile individually, flowing outwards when indicated by the diagram we just generated.... I don't know that this would give flat lakes, though.

Correct. Although I'm coming around to Shane's idea that flat lakes are not really critical to the process. It may be possible to have them, but it would take more time and effort than is really worth it, and wouldn't add anything to the simulation (of course, on our end-map that is the final map upon which the game will take place, we will ignore water heights and just draw lakes as an area of water).

And anyways, by your original criteria, we will have parts of lakes classified as 'rivers' as the water tries to equalize itself out. I'm a bit confused here, could you provide an example using 9 tiles? (Maybe a square of 4 would be good enough, I'm not sure.)

Actually, you may have caught me with a bad idea here.

The thought was that standing water always remained where it was. To move water, we needed to convert it to running water, even if it's just for the purpose of flattening a lake area. However, I'm thinking perhaps that's not such a good idea any more.

The reason being, running water will affect the topology. It's really the whole reason we are modelling water at all during the iterative process (otherwise I'd just skip it and put in lakes/rivers at the end). It's going to move topsoil, and to a lesser extent, affect the tile's underlying elevation. Standing water will not.

If we convert standing water to running water in lakes, it will affect the topology as well, and that's maybe not what I want to do.

I suggest we make a clear distinction between the two. Standing water will only be converted to running water when the entire water contents of the origin tile are moving toward the destination tile. If we are just moving standing water to average out "lake" areas, then we leave it as standing water and don't move around topsoil.

Tell me if you think I'm wrong, I'm easily swayed either way at this point, actually. I can see arguments on both sides.

Hm. Am I any closer to understanding this problem now?
Gah, no, I've gotta be missing something... you also go on to say "...running water won't be averaged, it will just be moved. It was only lakes I was having a problem with"

But you don't know how to tell the difference, right?!

I think you have it. It was the intent not to average running water, since what we are really doing is simply moving it en mass. It presumes the destination tile is of lower total elevation (land + water height) than the source tile land elevation, and that the addition of the water from the source tile to the destination tile will not raise the water height enough to cover the source tile.

In other words:

if (Destination elevation + Destination Water Height + Source Water Height < Source Elevation) then (Convert source tile water to running water and move it to destination tile [with accompanying changes to topology]).
else if (Destination elevation != Source Elevation) then (Average standing water heights)

Seems easy when written like that, heh. But of course trying to expand this to encompass 8 neighbor tiles, with each of those having their own 8 neighbors (and so on) is what makes it tricky.

Shane, I want to read your comments over 8 or 12 more times before commenting. This is a complex system, to be sure, heh.

[Shane Christopher]

Might I just point out that even in a large lake water is always moving from the entrance point to the exit point

This might be very minimal near the edges and I'm not sure how such a large tile area will cope with this, can you give us an estimate on the size of each tile we're talking about here?

EDIT: I guess my system would perhaps be better suited to a smaller scale water system. It would work I am sure of it but if a lake and a river are going to end up being the same size according to the scale of the tiles then that would present a problem.