Recursive refining mapgen API prototype

[MillersMan]

This is an early prototype of the API for recursive mapgens as proposed in #4839. It is still work in progress.

I've created a simple demo mapgen which creates just a stone-field which is based on a simple pink noise. The mapgen itself is in the DEMO AREA of mapgen_rec.h/mapgen_rec.cpp. The rest of those files is just the API and its implementation.

The execution/information flow for the generation is basically the following:

1. Create root fragment with very low resolution
   1.1 Allocate buffers (engine)
   1.2 Initialize buffers (mapgen)
2. Split the fragment
   2.1 Allocate the fragment and the buffer (engine)
   2.2 Run the passes (engine)
   2.2.a Each pass can read from as many buffers as it wants (pass)
   2.2.b Each pass writes to at least one buffer (pass)
   2.2.c At least one splitted fragment buffer has to be written. Those buffers will be used as inputs for the next iteration of step splitting (engine)
   2.2.d It is possible to write to temporary buffers that are only available to following passes in the same splitting process
3. If not at full resolution repeat step 2 with the generated fragment (engine)
4. Create the nodes based on the buffers from the full-resolution fragment and optionally classic noise. (mapgen)

All this is done when invoking just one function in the basic recursive mapgen. All the real mapgen itself has to do is to specify the buffers, the passes and how the buffers map to the passes. O course it also has to also implement those two steps that are marked with (mapgen). The code of those steps is very similar to that of existing mapgens.

Passes could be implemented in a configurable way and therefor could be shared between mapgens. E.g. only the first line of NoisePass::doSplit has to be changed for different noise functions.

The result of step 2 is cached. Therefore on average the resulting fragment only corresponds to one or two splitting operations independently of what resolution was chosen for the root fragment.

Note: The mapgen is still somewhat buggy and will never release the allocated fragments and buffers. It just works stable enough for testing and is more of an demonstration of what the API should look like.

[Fixer-007]

Can you post demo screenshot? :)

[Thomas--S]

Screenshot:

Map of the terrain:

[MillersMan]

Some background on the used noise:
The basic noise consists of an quadric bezier-like interpolation between random control points. That noise is combined in multiple octaves to create the final noise.
I think it should be possible to use real gradient noise aka Perlin Noise with a second noise-buffer (one for value and the other for the tangents).

Advantages when compared to classic noise

• The performance is independent of the octaves. As the overall performance is constant so is the performance of a single noise function.
• Persist and scale are fully supported
• Offset could be defined by setting it in the root-fragment

Disadvantages when compared to classic noise:

• Spread isn't supported directly. It could be emulated to some degree by setting the amplitude to zero above a given level. This would behave like pow(2, highest_non_zero_level) as the spread-value.
• Octaves are identical to the levels. A different value for the parameter could be emulated by setting the amplitude to zero below a given level.
• Lacunarity is always 2.0 (or 0.5 depending on the interpretation)

This demo corresponds to the following parameters: lacunarity=0.5, persist=2.1, spread=1, octaves=max_level=8, scale=0.2, offset=0. However the basic noise-function and the interpolation are different. Therefore it could not be reproduced with classic noise.

[rubenwardy]

any progress on this?

[paramat]

It's very interesting, but pink noise is a boring example, i'd like to see more interesting structures shown as examples, such as a downhill river system.

[MillersMan]

Sorry no progress at the moment as my dev system was broken and I don't have a replacement yet.

[paramat]

Good to hear from you.

[MillersMan]

Even though I don't find time to actually write code, I could give some updates on the design:

1. I have now a proper name: Deconvolution Mapgen as each iteration is a deconvolution operation. Currently I'm using one fixed function for all resolutions. But theoretically one could replace this function with multiple neural networks and the result would be a Deconvolution Neural Network (the inversion of a Convolution Neural Network aka CNN used in image recognition) which is already used for image reconstruction or generation of new images.
   The nice thing is that one could train a DNN on small map samples and integrate it as passes in my implementation which allows to use a neural network to create a full 60000x60000x60000 map with learning algorithms. (Edit: this might make a nice science project and could give some press coverage. And it is cool, too. That's why I mentioned this. But I don't think that it is a solution for everyday games)

2. In the current version the mapgen has to initialize the buffers in addition to the passes. This task could be automated by not connecting inputs and outputs of passes to buffers but outputs of passes to inputs of other passes. The allocation (and maybe even the reuse) of buffers would then be done by the engine.
   The result would be a graph similar to those known from shader designers and a mapgen could be designed with similar tools.

3. I decided to replace the plenty of small helper classes by one single helper class that has all needed functions. Disadvantage: The programmer of the passes has to know which function to use for which task. Advantage: Cleaner code and the pass programmer now has to know which class to use.

4. I did some experiments to improve the heuristics that decide the resolution and borders of the buffers for an optimal performance. While not really tested yet, this could slightly improve performance and allows automatic adjustment for very complex mapgens in which case it might give bigger speed ups.

5. With all those automatism I don't see an issue in implementing an optional splitting in Y direction in the initial version. That would allow for water-falls and volcanoes that reach down to the bottom of the world.

[rubenwardy]

Given that this has been sitting around for a while and isn't yet ready for review, would you be willing to close the PR for now? This sort of thing is probably best on the forum, or at least being reopened when you have time

[paramat]

Closing until it becomes relevant to merging.

[MillersMan]

You can keep this closed (stopped working on this as I did a complete rewrite with a slightly different approach). Nevertheless there are good news that I will add to the related issue.