Rather than giving you exact solutions, I'm rather going to primarily offer you ideas and tools that may help you to solve problems of this sort. Teach a man to fish and all that.
- Any computation must be limited (in range).
- When you have problems like "I cannot do that till I do this, but I cannot do this till I do that", you are usually doing too much at once. You need to layer your approach more finely to do one set of things at a time, then another set, then another etc.
- You are better off reducing the dataset you work with, even in finite ranges.
I'll refer back to these principles by number through this answer, so keep them in mind.
Finity vs. Infinity
how do you know which one's the lower end if it goes on indefinit(el)y?
I don't know how far the region extends on each side
...Your words. You need to start defining limits (principle #1), because your code cannot process inifinite ranges in finite time. Only you can decide those limits. What's the worst that can happen? You a try a value and it doesn't work out: so try another. Until you get something that works.
I noticed in your question that you have a blue and a green area, one smaller than the other. OK. These are usually called terrain chunks, but we'll call them biomes: these are important processing elements, as using them we don't have to scan every single column every time we need to do something - e.g. seeking water. Instead, we can scan just the biomes.
You can generate your world in two ways: by column primarily, OR by biome and then by column. I would suggest the latter, as it gives better control and efficiency (principle #3). Imagine we start out generating the world as a biome array:
Now you have an abstract idea of each biome: What it consists of, where it
starts in x, where it
ends in x. You can see that the
end of each biome is neighboured by the
start of the next.
Now we take this data and from it and (principle #2) create an array of heights, per biome as
width = biome.end - biome.start; biome.columns = new Column[width]. Then we populate each column in that array. So for the array above we might get
Looping over the columns as shown here, we'd now fill in some important intermediate data to the biomes array:
columns: [7 elements]
columns: [6 elements]
columns: [4 elements]
We've now populated
maxHeight fields accordingly for that biome from our generated columns. This gives more control, as you will see next.
Remember: Chunks are used to limit the problem (#2). That's why we generate biomes first (i.e. our primary data structures) and then only generate columns. This makes the world manageable.
You can cheaply generate large numbers of biomes without the considerably higher cost of generating large numbers of columns for every one - until later. What's more: You could dictate the
maxheight before you generate the columns. Maybe you can already begin to see how this might help you to determine lake heights without having to examine every single column: You could maybe even (no guarantees), before ever generating columns, pre-dictate min and max levels of lakes, given the min and max ground heights. Then generate ground and water columns.
You cannot determine water levels for columns / biomes you haven't generated yet. You cannot scan around the current location when you haven't yet generated the locations that come after it. With that in mind, here are some solutions.
- Only scan backward, to biomes you have already generated along with their water heights (assuming you always generate forward from
world.biomes). This will always be a scan of some fixed distance backward, let's call it
- Generate forward, but only scan from a biome that is say
scanDistance / 2 units back from the highest-indexed biome (last generated). Generate at least
scanDistance biomes before you begin scanning. Now you can scan back, and forward to the end, by
scanDistance / 2, from the centre, without hitting the bounds of your world's array of biomes.
OR (my recommendation)
- Generate biomes only in your 1st pass (see Chunks / Biomes); figure out in your 2nd pass what the water levels will be. To do this, run through the world around the current location-of-interest by some excessive extent first, in a
scanDiameter that is centred around the current location, generating land with indentations first. P.S. You can generate many biomes this way (probably millions if you like, though I'd start smaller - see principle #3). Then run a second pass and evaluate parameters like
maxheights of those areas.
Remember, you cannot scan further than the range of biomes (even if they don't yet have columns) that you have already generated (principle #1). Your code must take this into account.
Maybe you are happy with just generating
maxheight, then generating columns, then determining lake levels via scan. Maybe you prefer to pre-generate numbers for
maxlakeheight before touching concrete columns at all. Maybe you generate land columns and in another pass, use that to determine water columns / levels. Or maybe you do something altogether different that is only inspired by what we've talked about here.
Procedural generation is a field of infinite possibilities. Nothing we've talked about is set in stone. Don't be locked into just one way of thinking. Keep an open mind in your explorations.