Scan for water in 2D procedural terrain locale

Question

In my 2D-sideview game, I have certain biomes, each one having a unique sea level, or water height, (depending on the humidity of the biome). The terrain is composed of stacks of blocks, each being a type of land or being water. I want the height map to look something like this:

Terrain height does not always correlate to water height. It does so here for demo purposes.

Each lake must have a constant water height across.

What I've tried: To calculate if there is water in a region, I want to know the minimum water height of all biomes in that region. That will be the lake's water height.

However, I don't know how far the region extends on each side, so I can't find the minimum water height. If the water height was global/constant, I would search in both directions until I found a block above sea level (or a maximum distance was reached), but I don't know the water height, because I can't search for it, because I need the other water heights to search for this water height!

Some ideas that seem inefficient:

• Search for the endpoints of a potential lake at each biome water level, and choose the smallest water level to generate the lake.
• Find the smallest biome level in a max distance on each side, and choose the smallest water level to generate the lake.

Please tell there is a better way!

Edit:

• Terrain stacks (columns) are generated individually, then loaded into memory. When the player reaches a certain distance from the stack, it will get unloaded, and then regenerated again when the player is near. Every time a terrain stack is generated it must be exactly the same.
• For querying stack heights over and over again for calculating whether water should be on a stack, I cache the height and biome of some stacks beyond the loaded stacks in each direction; thus, it is not considered loaded (so entities can't move), but the basic information does not have to be recalculated.

Answer 1

This is a maximum subarray problem in disguise! It's a popular interview question. Instead of finding subarray sums, we're finding terrain that can hold water, and instead of finding the biggest subarray, we're finding all subarrays.

With the maximum subarray problem, we can track the current maximum subarray as we scan the array. The key insight is that once the sum is less than zero (because we have negative values), there is no point keeping the current subarray, so we reset and start counting from the current position instead.

Here's how we'd do it. Suppose we have the current terrain (a simplified version of your example:

#
##   ##
### ####
##########   #
########### ##
##############

First, flip it so that we start from the lower end (here we'll just scan right-to-left instead). Then transform it into the maximum subarray problem by looking at the slope of the terrain:

Heights: [3, 2, 1, 2, 3, 3, 4, 5, 5, 4, 3, 4, 5, 6]
Slopes:   [-1,-1, 1, 1, 0, 1, 1, 0,-1,-1, 1, 1, 1]

Then, we scan the slopes looking for largest subarrays. Since we're looking for valleys that can hold water, we are actually looking for negative sums.

const levels = [3, 2, 1, 2, 3, 3, 4, 5, 5, 4, 3, 4, 5, 6];
const slopes = [-1,-1, 1, 1, 0, 1, 1, 0,-1,-1, 1, 1, 1];
let currentSum = 0;
let currentWaterStart = 0;
let minSum = 0;
for (let i = 0; i < slopes.length; i++) {
  currentSum += slopes[i];
  minSum = Math.min(currentSum, minSum);
  if (currentSum >= 0) {
    if (minSum < 0) {
      console.log('Found water from ' + currentWaterStart + ' to ' + i);
      console.log(' depth ' + -minSum + ' level ' + levels[i+1]);
    }
    currentSum = 0;
    currentWaterStart = i;
    minSum = 0;
  }
}

The time complexity is O(n) and space complexity is O(1).

Answer 2

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.

Principles

1. Any computation must be limited (in range).
2. 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.
3. 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.

Biomes

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:

[
  {
     type:sand
     start:0
     end:7
     columns: [empty]
  },
  {
     type:grass
     start:7
     end:13
     columns: [empty]
  },
  {
     type:stone
     start:13
     end:17
     columns: [empty]
  },
  ...
]

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

      *#
*    **##
**  ***###
*******#####   oo
*******######oooo ...etc.

Looping over the columns as shown here, we'd now fill in some important intermediate data to the biomes array:

[
  {
     type:sand
     start:0
     end:7
     columns: [7 elements]
     minheight: 2
     maxheight: 5
  },
  {
     type:grass
     start:7
     end:13
     columns: [6 elements]
     minheight: 1
     maxheight: 5
  },
  {
     type:stone
     start:13
     end:17
     columns: [4 elements]
     minheight: 1
     maxheight: 2
  },
  ...
]

We've now populated minHeight and 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 minheight and 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.

Scanning solutions

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.

1. Only scan backward, to biomes you have already generated along with their water heights (assuming you always generate forward from world.biomes[0]). This will always be a scan of some fixed distance backward, let's call it scanDistance.
2. 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)

3. 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 minheights and 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.

Decisions, decisions...

Maybe you are happy with just generating minheight and maxheight, then generating columns, then determining lake levels via scan. Maybe you prefer to pre-generate numbers for minheight, maxheight, minlakeheight, 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.