Capping neighbour height difference on heightmap?

Question

I am generating a heightmap with some basic perlin noise but I need to cap the differences between each neighbouring value. A cardinal neighbour can only be -1, 0, +1 in difference while diagonal neighbour can range from -2 to +2. What is a good approach to make sure the map is generated within these rules? Does perlin or a small extension help me do this or should I make 2nd pass after the map is generated by perlin or simplex? I am currently doing the latter where I go over each tile and change it's cardinal neighbours according to it's own value but it is going over the same position/number very often.

Answer 1

You already mentioned the two broad solution categories. Here are some specifics about each.

Capping the values as they are generated:
The potential problem with this is that depending on your implementation, you need to be careful about checking values before they are assigned. For instance, the very first value generated won't have any neighbors yet. Also, if the yet to be calculated neighbors have been initialized to a default value, the code could incorrectly assume the first value generated is okay when it isn't. These are pretty standard things to check for and don't prevent you taking this route, but you'll need to account for them.

Post-process correction:
One way to do this without back tracking, is to process the nodes in a such a way that only prior nodes are considered. For instance, assume you process a grid of nodes as follows:

0 1 2
3 4 5
6 7 8

Let's assume you don't have any 'wrap around connectivity' (i.e. you cannot walk off the top of the grid to reach the bottom, etc). Then, for adjusting the value at the given position of [x,y] you only consider the following neighbors: [x-1,y], [x-1,y-1], [x,y-1], & ignoring any positions that aren't legal neighbors. That means that position [0,0] will always keep its original value because [-1,0], [-1,-1], [0,-1] are not valid.

If you do have wrap around connectivity, then you need to the following additional logic:

• do not wrap any coords with 0 around. For instance, [0,0] will still keep its original value; it is not allowed to wrap around & look at [max x,0], [max x, max y], [0,max y]. Even though they are legal neighbors (with wrapping) they have not yet been processed.
• if you are at position [max x, y], you need to consider the neighbors [0,y] & [0,y-1].
• if you are at position [x, max y], you need to consider the neighbors [x-1,0], [x,0] & [x+1,0]
• if you are at [max x, max y], you need to consider all neighbors

In either case though, the basic idea is the same, for any position, you adjust its height based only on neighbors that have already been processed. That leads to another way to implement the logic: have a companion grid of boolean values that record if a position has been processed yet. Only consider neighbors that have been flagged as processed.

Answer 2

Perlin and Simplex noise are both forms of gradient noise, meaning at each corner of a grid, they pseudorandomly choose a gradient vector that determines the rate of increase of the output value in the neighborhood of that point.

So you can use this to establish an upper bound on how much the output can increase over a distance of one heightmap cell, horizontally or vertically. With this upper bound in hand, we can adjust our noise scaling parameters until we can guarantee that we change by at most ±1.0 over that span.

Let's say you're sampling a single layer of Perlin noise like this:

float value = Noise(input * frequency) * amplitude;

The maximum slope this attains is (amplitude * frequency) times the maximum component of the gradient vectors used in your noise function. If you wrote your own or have access to the source code, you can check these directly, otherwise you can make an informed inference by consulting reference implementations or sampling your noise at points close to the grid points.

If you're summing multiple octaves of noise, then these slopes combine additively too (in the worst case of constructive interference — in practice you'll get destructive interference too and see more average values overall, but for our guarantees it's the extremes we care about).

So, we just need to choose our amplitudes and frequencies so that the sum of these product times our maximum gradient component is less than 1 divided by the span between heightmap cells.

For example, if there's a span of 1 unit between heightmap cells, and my noise gradient vectors have a maximum value of ±1 on any axis, I might choose octaves like this...

octave     amplitude    frequency   contribution
------------------------------------------------
  1           28          1/70       0.4
  2            9          1/30       0.3
  3            3          1/15       0.2
  4            1          1/10       0.1

So now the maximum possible increase in function value from one heightmap cell to its neighbour totals to 1.0.

The higher the amplitude of any one octave, the longer a distance I need to spread that noise octave over, to ensure it never bumps me up two steps in a single bound.