Some semi-random thoughts on terrain generation

[xoft]

Generating a world:
===================

First of all, what is the world? What parts can it be split into? Can those parts be changed independently of each other?

- Terrain height
- Ores
- Biome
- Structures (caves, trees, villages, ...)
- Terrain composition (waterlevel height, 3 dirt on top of stone, beaches near waterlevel, ...)
- Small foliage (tall grass, mushrooms, ...)

Changing algorithm for any of the above part results in a different world, but the change doesn't require propagation into other parts. A part may depend on other part being calculated first (terrain height on biome, structures on terrain height), but the dependency is purely value-centric, not algorithm-centric. So why not make them interchangeable for the users? Suggested dependencies:
Terrain height -> Biome
Terrain composition -> Terrain height & Biome
Structures -> Terrain height
Small foliage -> Terrain height

Biome
Current generator only has one fixed constant biome. A newer implementation could change that into whatever biome distribution we want - distorted-voronoi like the original MC, settable constant biome or even checkerboard biomes.
Technically, the biome generator has to generate an array of 16x16 biome enumerations for each chunk.

Terrain height
Current generator doesn't take biomes into consideration and generates height only based on the internal noise function. A newer implementation can use several noise functions, one for each biome, and interpolate between them based on biome data provided by the Biome generator.

Terrain composition
This one is questionable. Who should be responsible for the basic terrain composition, such as the amount of dirt on top of stone, the waterlevel etc.? I think there should be a terrain compositing component. The basic one, working as the current version, just makes the top three layers dirt, fills water up to waterlevel and adds beaches near the water. An essential modification is to be used with biomes - desert biome needs sand terrain and swamp biome needs clay pools, etc.

Structures
Generated things that are larger than a single block need to be able to be calculated again (for the neighboring chunks) and may be cached. Currently there is no such thing in MCS and we really need one, at least for the trees. Having the structures generate in the same step as the rest of the chunk will allow us to provide full chunk data immediately after generating and lighting data in a 1-delayed level. Currently this 1-delayed level is used for trees, which would mean lighting would be available on 2-delayed level, which is too much strain (needs to check 5x5 areas of 5x5 chunks after each chunk is generated).

Small foliage
Currently small foliage is generated all over the terrain, which is not really acceptable. Things should be more rare and should adhere to their rules (mushrooms in the dark etc.). Biomes could also modify parameters such as the probability for each element's spawning.

Ores
Current generation of ores is satisfactory, but could benefit from some slight Biome dependency - for example a bit more coal in the swamp biome etc. If we ever make springs a part of ore generation, then this is even more important, since biomes could affect the number of springs both underground and overground.


How to generate...
==================

... Original MCServer terrain:
- use a constant biome ("plains" are used currently for the MapChunk packets)
- use the terrain height using builtin cNoise
- use trees and 3D-noise caves for structures, nothing else
- small foliage everywhere on the terrain

... Flat terrain (WG-flat-like):
- use a constant biome
- use a constant terrain height
- no structures, no trees

... MineCraft-like terrain:
- distorted-voronoi biomes, with another distorted-voronoi ocean selector
- terrain height dependent on biomes, interpolating
- trees, worm-nest-caves and possibly other structures
- small foliage dependent on biome and (direct) lighting conditions - maybe even 1-delayed for the correct lighting

[NiLSPACE]

so you want to try to import biomes???

[xoft]

I want to do so much more...

---

I've been trying to figure out how to fit overhangs / cliffs into the scheme I'm proposing. Because I LOVE overhangs And I think it's still possible - I'd put it into the "terrain composition" category. In certain biomes, after it receives the terrain height, it can actually add up to the value, creating the slopes up and the overhangs under them, eventually. So despite the terrain height generator generating a normal terrain, it will eventually contain overhangs above the height initially generated.

I'm not sure, though, if other structures, such as villages, can be made to work with this.

[xoft]

I've created an SVN branch for rewriting the generator in this way.

[xoft]

Thinking it through, ores are just a special case of structures and don't make much sense to implement otherwise. Especially if we throw underground dirt and gravel pockets into the equation. They just need a different set of parameters, but they share the same interface and logic - first vector data is generated describing the structure, independent of chunk borders, and only then chunks are intersected with this image to generate the actual block data.

[xoft]

Ran into a roadblock with this scheme: generating trees and overhangs kind of collides together: Overhangs are "added" on top of generated HeightMap when generating a chunk. So the tree generator, being a structure generator, sees the overhang for the current chunk. But trees need to "see" into the neighboring chunks as well - we don't want a tree "hugging" a wall - its trunk being right next to a wall.

So it seems we'll still need two kinds of structure generators - ones that needn't see neighbor chunks (e. g. caves, ores) and ones that generate only after the neighbor is generated (trees, villages). The second type I've dubbed "delayed structures". They'll work by splitting their work into quarter-chunk-sized pieces. The chunk will generate only with the normal structures, but then it will check its neighbors and for each neighbor it will generate the corresponding quarter - for the northeast quarter to generate, the chunk will need its north, east and northeast neighbors already generated.
I believe the Notchian generator uses a similar technique - there are no trees on the edge of a map, all the tree trunks stop 1/2 chunk before the map's edge. Similarly villages and even abandoned mineshafts don't generate closer than 8 blocks to the edge.

This might actually produce slightly buggy lighting. Since lighting is applied 1-chunk-delayed from the generation, it means the neighbors of the currently lit chunk needn't have all their delayed-structures generated yet. They are guaranteed to have an 8-block wide final data along the neighboring edge, but lighting can spread as far as 15 blocks. So in a dense forest areas lighting could "shine through" the not-yet-delay-generated area and make it into the chunk being lit.
This should not be a problem for trees, since light shines through the leaves anyway. I'm not sure if villages will suffer from it, though. They might, as houses can be larger than 8 blocks across.

[NiLSPACE]

what biomes will you import in MC-Server??
here is an list of all the biomes in minecraft.
http://www.minecraftwiki.net/wiki/Biomes

[xoft]

Actually I liked the pre-1.9 biomes more, so I just might be reproducing that first.
MCServer can use whatever biomes we want and then translate those biome IDs into client IDs as needed. On the client, the only two things a biome is governing is the foliage color and precipitation, so as long as we map logically, we can do whatever we want internally.

There's just too many problems with the 8-block-delayed generation of trees and villages, I think I'll go the other way - modify the possible overhang generator to work nicely with trees instead. So all the blocks are generated in one pass and the lighting in second pass, correctly.

[NiLSPACE]

ok but eh what biomes were in 1.9?? :S i forgot it xD

[xoft]

Hmm, actually those were already pre-1.8 biomes:
http://www.minecraftwiki.net/wiki/Histor...1.8_Biomes