From 376d5e7ff0d2daab13aee0bf184a3ef5375bd1e6 Mon Sep 17 00:00:00 2001 From: Mattes D Date: Fri, 30 May 2014 22:31:51 +0200 Subject: Initial commit of the Generator article. --- docs/Generator.html | 119 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 119 insertions(+) create mode 100644 docs/Generator.html diff --git a/docs/Generator.html b/docs/Generator.html new file mode 100644 index 000000000..f71ce1c71 --- /dev/null +++ b/docs/Generator.html @@ -0,0 +1,119 @@ + + +Generating terrain in MCServer + + +

Generating terrain in MCServer

+

This article explains the principles behind the terrain generator in MCServer. It is not strictly +specific to MCServer, though, it can be viewed as a generic guide to various terrain-generating algorithms, +with specific implementation notes regarding MCServer.

+ +

Preface: How it's done in real life

+

The nature has many complicated geological, physical and biological processes working on all scales from +microscopic to planet-wide scale, that have shaped the terrain into what we see today. The tectonic plates +collide, push mountain ranges up and ocean trenches down. Erosion dulls the sharp shapes. Plantlife takes +over to further change the overall look of the world.

+

Generally speaking, the processes take what's there and change it. Unlike computer generating, which +usually creates a finished terrain from scratch, or maybe with only a few iterations. It would be unfeasible +for software to emulate all the natural processes in enough detail to provide world generation for a game, +mainly because in the nature everything interacts with everything. If a mountain range rises, it changes the +way that the precipitation is carried by the wind to the lands beyond the mountains, thus changing the +erosion rate there and the vegetation type.

+ +

Expected properties

+

For a MineCraft-like game terrain generator we need the generator to have several properties: +

+

+ +

Reversing the flow

+

As already mentioned, the nature works basically by generating raw terrain composition, then "applying" +erosion, vegetation and finally this leads to biomes being formed. Let's now try a somewhat inverse +approach: First generate biomes, then fit them with appropriate terrain, and finally cover in vegetation +and all the other stuff.

+

Splitting the parts like this suddenly makes it possible to create a generator with the required +properties. We can generate a reasonable biome map chunk-wise, independently of all the other data. Once we +have the biomes, we can compose the terrain for the chunk by using the biome data for the chunk, and +possibly even for neighboring chunks. Note that we're not breaking the first property, the biomes can be +generated separately so a neighboring chunk's biome map can be generated without the need for the entire +neighboring chunk to be present. Similarly, once we have the terrain composition for a chunk, we can +generate all the vegetation and structures in it, and those can again use the terrain composition in +neighboring chunks.

+ +

The ComposableGenerator pipeline

+

This leads us directly to the main pipeline that is used for generating terrain in MCServer. For +technical reasons, the terrain composition step is further subdivided into Height generation and Composition +generation, and the structures are really called Finishers. For each chunk the generator generates, in this +sequence: +

+

+ + + + +

The beautiful thing about this is that the individual components can be changed independently. You can +have 5 biome generators and 3 height generators and you can let the users mix'n'match. +

+ +

Using coherent noise for the generation

+

For a great tutorial on coherent noise, see the LibNoise +documentation.

+

Coherent noise is a type of noise that has three important properties that we can use to our advantage: +

+

We'll be mostly using Perlin noise in this article. It is the easiest one to visualise and use and is one +of the most useful kinds of coherent noises. Here's an example of a Perlin noise generated in 2 dimensions:

+ +

It comes only naturally that such a 2D noise can be used as a terrain height map directly:

+ +

However, this is not the only use for this noise, and 2 dimensions is not the limit - this noise can be +generated for any number of dimensions.

+ +

Generating biomes

+

The easiest way to generate biomes is to not generate at all - simply assign a single constant biome to +everywhere. And indeed there are times when this kind of "generator" is useful - for the MineCraft's Flat +world type, or for testing purposes, or for tematic maps. In MCServer, this is exactly what the Constant +biome generator does.

+

Of course, there are more interesting test scenarios for which multiple biomes must be generated as easy +as possible. For these special needs, there's a CheckerBoard biome generator. As the name suggests, it +generates a grid of biomes.

+

Voronoi diagram

+

These two generators are more of a technicality, we need to make something more interesting if we're +going for a natural look. The Voronoi generator is the first step towards such a change. Recall that a +Voronoi diagram is a construct that creates a +set of areas where each point in an area is closer to the appropriate seed of the area than the seeds of any +other area:

+ +

The overall shape of a Voronoi diagram is governed by the placement of the seeds. In extreme cases, a +seed could affect the entire diagram, which is what we don't want - we need our locality, so that we can +generate a chunk's worth of biome data. We also don't want the too much irregular diagrams that are produced +when the seeds are in small clusters. We need our seeds to come in random, yet somewhat uniform fashion.

+

Luckily, we have just the tool: Grid with jitter. Originally used in antialiasing techniques, they can be +successfully applied as a source of the seeds for a Voronoi diagram. Simply take a regular 2D grid of seeds +with the grid distance being N, and move each seed along the X and Y axis by a random distance, usually in +the range [-N / 2, +N / 2]:

+ +

Such a grid is the ideal seed source for a Voronoi biome generator, because not +only are the Voronoi cells "reasonable", but the seed placement's effect on the diagram is localized - each +pixel in the diagram depends on at most 5 x 5 seeds around it:

+ + + -- cgit v1.2.3 From 869cd7a2080d6072f90016afd7067f871482a5ac Mon Sep 17 00:00:00 2001 From: Mattes D Date: Sun, 1 Jun 2014 15:19:01 +0200 Subject: Hot-fixed AnvilStats compilation for MSVC2013. --- Tools/AnvilStats/AnvilStats.sln | 45 +++++++++++++++++++++++++++++----------- Tools/AnvilStats/Globals.h | 22 ++++++++++++++++++++ Tools/AnvilStats/SpringStats.cpp | 2 +- 3 files changed, 56 insertions(+), 13 deletions(-) diff --git a/Tools/AnvilStats/AnvilStats.sln b/Tools/AnvilStats/AnvilStats.sln index 6e2481d84..46bed8969 100644 --- a/Tools/AnvilStats/AnvilStats.sln +++ b/Tools/AnvilStats/AnvilStats.sln @@ -1,32 +1,53 @@ - -Microsoft Visual Studio Solution File, Format Version 10.00 -# Visual C++ Express 2008 -Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "AnvilStats", "AnvilStats.vcproj", "{CF996A5E-0A86-4004-9710-682B06B5AEBA}" +Microsoft Visual Studio Solution File, Format Version 12.00 +# Visual Studio Express 2013 for Windows Desktop +VisualStudioVersion = 12.0.21005.1 +MinimumVisualStudioVersion = 10.0.40219.1 +Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "AnvilStats", "AnvilStats.vcxproj", "{CF996A5E-0A86-4004-9710-682B06B5AEBA}" ProjectSection(ProjectDependencies) = postProject - {EA9D50FD-937A-4EF5-8C37-5F4175AF4FEA} = {EA9D50FD-937A-4EF5-8C37-5F4175AF4FEA} + {B61007AC-B557-4B67-A765-E468C0C3A821} = {B61007AC-B557-4B67-A765-E468C0C3A821} EndProjectSection EndProject -Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "zlib", "..\..\VC2008\zlib.vcproj", "{EA9D50FD-937A-4EF5-8C37-5F4175AF4FEA}" +Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "zlib", "..\..\lib\zlib\zlib.vcxproj", "{B61007AC-B557-4B67-A765-E468C0C3A821}" EndProject Global GlobalSection(SolutionConfigurationPlatforms) = preSolution Debug|Win32 = Debug|Win32 + DebugProfile|Win32 = DebugProfile|Win32 + MinSizeRel|Win32 = MinSizeRel|Win32 Release profiled|Win32 = Release profiled|Win32 Release|Win32 = Release|Win32 + ReleaseProfile|Win32 = ReleaseProfile|Win32 + RelWithDebInfo|Win32 = RelWithDebInfo|Win32 EndGlobalSection GlobalSection(ProjectConfigurationPlatforms) = postSolution {CF996A5E-0A86-4004-9710-682B06B5AEBA}.Debug|Win32.ActiveCfg = Debug|Win32 {CF996A5E-0A86-4004-9710-682B06B5AEBA}.Debug|Win32.Build.0 = Debug|Win32 + {CF996A5E-0A86-4004-9710-682B06B5AEBA}.DebugProfile|Win32.ActiveCfg = Debug|Win32 + {CF996A5E-0A86-4004-9710-682B06B5AEBA}.DebugProfile|Win32.Build.0 = Debug|Win32 + {CF996A5E-0A86-4004-9710-682B06B5AEBA}.MinSizeRel|Win32.ActiveCfg = Release|Win32 + {CF996A5E-0A86-4004-9710-682B06B5AEBA}.MinSizeRel|Win32.Build.0 = Release|Win32 {CF996A5E-0A86-4004-9710-682B06B5AEBA}.Release profiled|Win32.ActiveCfg = Release profiled|Win32 {CF996A5E-0A86-4004-9710-682B06B5AEBA}.Release profiled|Win32.Build.0 = Release profiled|Win32 {CF996A5E-0A86-4004-9710-682B06B5AEBA}.Release|Win32.ActiveCfg = Release|Win32 {CF996A5E-0A86-4004-9710-682B06B5AEBA}.Release|Win32.Build.0 = Release|Win32 - {EA9D50FD-937A-4EF5-8C37-5F4175AF4FEA}.Debug|Win32.ActiveCfg = Debug|Win32 - {EA9D50FD-937A-4EF5-8C37-5F4175AF4FEA}.Debug|Win32.Build.0 = Debug|Win32 - {EA9D50FD-937A-4EF5-8C37-5F4175AF4FEA}.Release profiled|Win32.ActiveCfg = Release profiled|Win32 - {EA9D50FD-937A-4EF5-8C37-5F4175AF4FEA}.Release profiled|Win32.Build.0 = Release profiled|Win32 - {EA9D50FD-937A-4EF5-8C37-5F4175AF4FEA}.Release|Win32.ActiveCfg = Release|Win32 - {EA9D50FD-937A-4EF5-8C37-5F4175AF4FEA}.Release|Win32.Build.0 = Release|Win32 + {CF996A5E-0A86-4004-9710-682B06B5AEBA}.ReleaseProfile|Win32.ActiveCfg = Release|Win32 + {CF996A5E-0A86-4004-9710-682B06B5AEBA}.ReleaseProfile|Win32.Build.0 = Release|Win32 + {CF996A5E-0A86-4004-9710-682B06B5AEBA}.RelWithDebInfo|Win32.ActiveCfg = Release|Win32 + {CF996A5E-0A86-4004-9710-682B06B5AEBA}.RelWithDebInfo|Win32.Build.0 = Release|Win32 + {B61007AC-B557-4B67-A765-E468C0C3A821}.Debug|Win32.ActiveCfg = Debug|Win32 + {B61007AC-B557-4B67-A765-E468C0C3A821}.Debug|Win32.Build.0 = Debug|Win32 + {B61007AC-B557-4B67-A765-E468C0C3A821}.DebugProfile|Win32.ActiveCfg = DebugProfile|Win32 + {B61007AC-B557-4B67-A765-E468C0C3A821}.DebugProfile|Win32.Build.0 = DebugProfile|Win32 + {B61007AC-B557-4B67-A765-E468C0C3A821}.MinSizeRel|Win32.ActiveCfg = MinSizeRel|Win32 + {B61007AC-B557-4B67-A765-E468C0C3A821}.MinSizeRel|Win32.Build.0 = MinSizeRel|Win32 + {B61007AC-B557-4B67-A765-E468C0C3A821}.Release profiled|Win32.ActiveCfg = Release|Win32 + {B61007AC-B557-4B67-A765-E468C0C3A821}.Release profiled|Win32.Build.0 = Release|Win32 + {B61007AC-B557-4B67-A765-E468C0C3A821}.Release|Win32.ActiveCfg = Release|Win32 + {B61007AC-B557-4B67-A765-E468C0C3A821}.Release|Win32.Build.0 = Release|Win32 + {B61007AC-B557-4B67-A765-E468C0C3A821}.ReleaseProfile|Win32.ActiveCfg = ReleaseProfile|Win32 + {B61007AC-B557-4B67-A765-E468C0C3A821}.ReleaseProfile|Win32.Build.0 = ReleaseProfile|Win32 + {B61007AC-B557-4B67-A765-E468C0C3A821}.RelWithDebInfo|Win32.ActiveCfg = RelWithDebInfo|Win32 + {B61007AC-B557-4B67-A765-E468C0C3A821}.RelWithDebInfo|Win32.Build.0 = RelWithDebInfo|Win32 EndGlobalSection GlobalSection(SolutionProperties) = preSolution HideSolutionNode = FALSE diff --git a/Tools/AnvilStats/Globals.h b/Tools/AnvilStats/Globals.h index c673ecb01..df1430cc4 100644 --- a/Tools/AnvilStats/Globals.h +++ b/Tools/AnvilStats/Globals.h @@ -24,6 +24,15 @@ #define ALIGN_8 #define ALIGN_16 + #define FORMATSTRING(formatIndex, va_argsIndex) + + // MSVC has its own custom version of zu format + #define SIZE_T_FMT "%Iu" + #define SIZE_T_FMT_PRECISION(x) "%" #x "Iu" + #define SIZE_T_FMT_HEX "%Ix" + + #define NORETURN __declspec(noreturn) + #elif defined(__GNUC__) // TODO: Can GCC explicitly mark classes as abstract (no instances can be created)? @@ -40,6 +49,14 @@ // Some portability macros :) #define stricmp strcasecmp + #define FORMATSTRING(formatIndex, va_argsIndex) __attribute__((format (printf, formatIndex, va_argsIndex))) + + #define SIZE_T_FMT "%zu" + #define SIZE_T_FMT_PRECISION(x) "%" #x "zu" + #define SIZE_T_FMT_HEX "%zx" + + #define NORETURN __attribute((__noreturn__)) + #else #error "You are using an unsupported compiler, you might need to #define some stuff here for your compiler" @@ -194,6 +211,8 @@ typedef unsigned short UInt16; /// Faster than (int)floorf((float)x / (float)div) #define FAST_FLOOR_DIV( x, div ) ( (x) < 0 ? (((int)x / div) - 1) : ((int)x / div) ) +#define TOLUA_TEMPLATE_BIND(...) + // Own version of assert() that writes failed assertions to the log for review #ifdef _DEBUG #define ASSERT( x ) ( !!(x) || ( LOGERROR("Assertion failed: %s, file %s, line %i", #x, __FILE__, __LINE__ ), assert(0), 0 ) ) @@ -204,6 +223,8 @@ typedef unsigned short UInt16; // Pretty much the same as ASSERT() but stays in Release builds #define VERIFY( x ) ( !!(x) || ( LOGERROR("Verification failed: %s, file %s, line %i", #x, __FILE__, __LINE__ ), exit(1), 0 ) ) +typedef unsigned char Byte; + @@ -227,3 +248,4 @@ public: + diff --git a/Tools/AnvilStats/SpringStats.cpp b/Tools/AnvilStats/SpringStats.cpp index 637cf20b6..51b7f9d5d 100644 --- a/Tools/AnvilStats/SpringStats.cpp +++ b/Tools/AnvilStats/SpringStats.cpp @@ -109,7 +109,7 @@ bool cSpringStats::OnSectionsFinished(void) int Base = BaseY + z * 16; for (int x = 1; x < 15; x++) { - if (cChunkDef::GetNibble(m_BlockMetas, Base + x) != 0) + if (cChunkDef::GetNibble(m_BlockMetas, x, y, z) != 0) { // Not a source block continue; -- cgit v1.2.3 From 24bea1d0b2b1d0f7400632fd480a24dff84bcad1 Mon Sep 17 00:00:00 2001 From: Mattes D Date: Sun, 1 Jun 2014 22:33:53 +0200 Subject: Generator article now has all biome genertors and most their imgs. --- docs/Generator.html | 164 +++++++++++++++++++++++-- docs/img/biomes.jpg | Bin 0 -> 34538 bytes docs/img/distortedvoronoibiomes.png | Bin 0 -> 6012 bytes docs/img/finishers.jpg | Bin 0 -> 40652 bytes docs/img/jittergrid.jpg | Bin 0 -> 51390 bytes docs/img/jittergridlocality.jpg | Bin 0 -> 40758 bytes docs/img/multistepmapbiomes.png | Bin 0 -> 11103 bytes docs/img/perlin.jpg | Bin 0 -> 24105 bytes docs/img/perlinheightmap.jpg | Bin 0 -> 53543 bytes docs/img/temperaturehumiditydecisionhills.jpg | Bin 0 -> 88494 bytes docs/img/temperaturehumiditydecisionsimple.jpg | Bin 0 -> 51736 bytes docs/img/terraincomposition.jpg | Bin 0 -> 43271 bytes docs/img/terrainheight.jpg | Bin 0 -> 29098 bytes docs/img/twolevelbiomes.png | Bin 0 -> 33816 bytes docs/img/voronoijitterbiomes.png | Bin 0 -> 4268 bytes 15 files changed, 156 insertions(+), 8 deletions(-) create mode 100644 docs/img/biomes.jpg create mode 100644 docs/img/distortedvoronoibiomes.png create mode 100644 docs/img/finishers.jpg create mode 100644 docs/img/jittergrid.jpg create mode 100644 docs/img/jittergridlocality.jpg create mode 100644 docs/img/multistepmapbiomes.png create mode 100644 docs/img/perlin.jpg create mode 100644 docs/img/perlinheightmap.jpg create mode 100644 docs/img/temperaturehumiditydecisionhills.jpg create mode 100644 docs/img/temperaturehumiditydecisionsimple.jpg create mode 100644 docs/img/terraincomposition.jpg create mode 100644 docs/img/terrainheight.jpg create mode 100644 docs/img/twolevelbiomes.png create mode 100644 docs/img/voronoijitterbiomes.png diff --git a/docs/Generator.html b/docs/Generator.html index f71ce1c71..b7586a183 100644 --- a/docs/Generator.html +++ b/docs/Generator.html @@ -13,6 +13,7 @@ with specific implementation notes regarding MCServer.

microscopic to planet-wide scale, that have shaped the terrain into what we see today. The tectonic plates collide, push mountain ranges up and ocean trenches down. Erosion dulls the sharp shapes. Plantlife takes over to further change the overall look of the world.

+

Generally speaking, the processes take what's there and change it. Unlike computer generating, which usually creates a finished terrain from scratch, or maybe with only a few iterations. It would be unfeasible for software to emulate all the natural processes in enough detail to provide world generation for a game, @@ -35,11 +36,14 @@ distinction will be discussed later.

+ +

Reversing the flow

As already mentioned, the nature works basically by generating raw terrain composition, then "applying" erosion, vegetation and finally this leads to biomes being formed. Let's now try a somewhat inverse approach: First generate biomes, then fit them with appropriate terrain, and finally cover in vegetation and all the other stuff.

+

Splitting the parts like this suddenly makes it possible to create a generator with the required properties. We can generate a reasonable biome map chunk-wise, independently of all the other data. Once we have the biomes, we can compose the terrain for the chunk by using the biome data for the chunk, and @@ -49,6 +53,8 @@ neighboring chunk to be present. Similarly, once we have the terrain composition generate all the vegetation and structures in it, and those can again use the terrain composition in neighboring chunks.

+ +

The ComposableGenerator pipeline

This leads us directly to the main pipeline that is used for generating terrain in MCServer. For technical reasons, the terrain composition step is further subdivided into Height generation and Composition @@ -61,6 +67,7 @@ sequence:

  • Finishers

    • + @@ -69,6 +76,8 @@ sequence: have 5 biome generators and 3 height generators and you can let the users mix'n'match.

    + +

    Using coherent noise for the generation

    For a great tutorial on coherent noise, see the LibNoise documentation.

    @@ -79,41 +88,180 @@ documentation.

    parameters are given to the noise functions.
  • The noise can be seamlessly extended in any direction

    • +

    We'll be mostly using Perlin noise in this article. It is the easiest one to visualise and use and is one of the most useful kinds of coherent noises. Here's an example of a Perlin noise generated in 2 dimensions:

    - + +

    It comes only naturally that such a 2D noise can be used as a terrain height map directly:

    - + +

    However, this is not the only use for this noise, and 2 dimensions is not the limit - this noise can be generated for any number of dimensions.

    + +

    Generating biomes

    -

    The easiest way to generate biomes is to not generate at all - simply assign a single constant biome to -everywhere. And indeed there are times when this kind of "generator" is useful - for the MineCraft's Flat +

    The easiest way to generate biomes is to not generate them at all - simply assign a single constant biome +to everywhere. And indeed there are times when this kind of "generator" is useful - for the MineCraft's Flat world type, or for testing purposes, or for tematic maps. In MCServer, this is exactly what the Constant biome generator does.

    +

    Of course, there are more interesting test scenarios for which multiple biomes must be generated as easy as possible. For these special needs, there's a CheckerBoard biome generator. As the name suggests, it generates a grid of biomes.

    +

    Voronoi diagram

    -

    These two generators are more of a technicality, we need to make something more interesting if we're +

    Those two generators were more of a technicality, we need to make something more interesting if we're going for a natural look. The Voronoi generator is the first step towards such a change. Recall that a Voronoi diagram is a construct that creates a set of areas where each point in an area is closer to the appropriate seed of the area than the seeds of any other area:

    + +

    To generate biomes using this approach, you select random "seeds", assign a biome to each one, and then +for each "column" of the world you find the seed that is the nearest to that column, and use that seed's +biome.

    +

    The overall shape of a Voronoi diagram is governed by the placement of the seeds. In extreme cases, a seed could affect the entire diagram, which is what we don't want - we need our locality, so that we can generate a chunk's worth of biome data. We also don't want the too much irregular diagrams that are produced when the seeds are in small clusters. We need our seeds to come in random, yet somewhat uniform fashion.

    +

    Luckily, we have just the tool: Grid with jitter. Originally used in antialiasing techniques, they can be successfully applied as a source of the seeds for a Voronoi diagram. Simply take a regular 2D grid of seeds with the grid distance being N, and move each seed along the X and Y axis by a random distance, usually in the range [-N / 2, +N / 2]:

    - + +

    Such a grid is the ideal seed source for a Voronoi biome generator, because not only are the Voronoi cells "reasonable", but the seed placement's effect on the diagram is localized - each -pixel in the diagram depends on at most 5 x 5 seeds around it:

    - +pixel in the diagram depends on at most 4 x 4 seeds around it. In the following picture, the seed for the +requested point (blue) must be within the indicated circle. Even the second-nearest seed, which we will need +later, is inside that circle.

    + + +

    Calculating the jitter for each cell can be done easily by using a 2D Perlin noise for each coord. We +calculate the noise's value at [X, Z], which gives us a number in the range [-1; 1]. We then multiply the +number by N / 2, this gives us the required range of [-N / 2, +N / 2]. Adding this number to the X coord +gives us the seed's X position. We use another Perlin noise and the same calculation for the Z coord of the +seed.

    + +

    Here's an example of a biome map generated using the Voronoi + jitter grid, as implemented by the Voronoi +biome generator in MCServer:

    + + +

    Distorted Voronoi

    +

    The biomes are starting to look interesting, but now they have straight-line borders, which looks rather +weird and the players will most likely notice very soon. We need to somehow distort the borders to make them +look more natural. By far the easiest way to achieve that is to use a little trick: When the generator is +asked for the biome at column [X, Z], instead of calculating the Voronoi biome for column [X, Z], we first +calculate a random offset for each coord, and add it to the coordinates. So the generator actually responds +with the biome for [X + rndX, Z + rndZ].

    + +

    In order to keep the property that generating for the second time gives us the same result, we need the +"random offset" to be replicatable - same output for the same input. This is where we use yet another Perlin +noise - just like with the jitter for the Voronoi grid, we add a value from a separate noise to each +coordinate before sending the coordinates down to the Voronoi generator:

    + +DistortedVoronoiBiome(X, Z) := VoronoiBiome(X + PerlinX(X, Z), Z + PerlinZ(X, Z)) + + +

    The following image shows the effects of the change, as generated by MCServer's DistortedVoronoi biome +generator. It is actually using the very same Voronoi map as the previous image, the only change has been +the addition of the distortion:

    + + +

    As you can see, this already looks reasonable enough, it could be considered natural biomes, if it +weren't for several drawbacks: +

      +
    • There's no way to limit the neighbors. A desert biome can neighbor a tundra biome.
      • +
    • All the biomes are considered equal. There's no way to make oceans larger. A mushroom biome is +generated right next to other land biomes.
      • +

    + +

    Adding relativity

    +

    Our next goal is to remove the first defect of the distorted voronoi generator: unrelated biomes +generating next to each other. It is highly unlikely to find a jungle biome next to a desert biome, so we +want to have as few of those boundaries as possible. We could further improve on the selection of +biome-to-seed in the Voronoi generator. Or we can try a completely different idea altogether.

    + +

    Recall how we talked about the nature, where the biomes are formed by the specific conditions of a place. +What if we could make a similar dependency, but without the terrain? It turns out this is possible rather +easily - instead of depending on the terrain, we choose two completely artificial measures. Let's call them +Temperature and Humidity. If we knew the temperature of the place, we know what set of biomes are possible +for such temperatures - we won't place deserts in the cold and tundra in the hot anymore. Similarly, the +humidity will help us sort out the desert vs jungle issue. But how do we get a temperature and humidity? +Once again, the Perlin noise comes to the rescue. We can use a simple 2D Perlin noise as the temperature +map, and another one as the humidity map.

    + +

    What we need next is a decision of what biome to generate in certain temperature and humidity +combinations. The fastest way for a computer is to have a 2D array, where the temperature is one dimension +and humidity the other, and the values in the array specify the biome to generate:

    + + +

    We can even "misuse" the above diagram to include the hill variants of the biomes and have those hills +neighbor each other properly, simply by declaring some of the decision diagram's parts as hills:

    + + +

    The problem with this approach is that there are biomes that should not depend on temperature or +humidity, they generate across all of their values. Biomes like Oceans, Rivers and Mushroom. We could +either add them somewhere into the decision diagram, or we can make the generator use a multi-step decision: +

      +
    • Decide whether the point is in the ocean, land or mushroom
      • +
    • If it's land, decide if it's real land or river.
      • +
    • If it's real land, use a TemperatureHumidity approach to generate land-biomes
      • +
    +

    + +

    This is the approach implemented in MCServer's MultiStepMap biome generator. It generates biome maps like +this:

    + + +

    To decide whether the point is in the ocean, land or mushroom, the generator uses a DistortedVoronoi +approach where the seeds get the "ocean", "land" and "mushroom" values; special handling is added so that a +mushroom value is always surrounded by ocean values on all 8 sides:

    + + +

    For the Voronoi cells that are calculated as mushroom, the distance to the nearest-seed is used to +further shrink the mushroom biome and then to distinguish between mushroom and mushroom-shore:

    + + +

    The rivers are added only to the areas that have been previously marked as land. A simple 2D Perlin noise +is used as the base, where its value is between 0 and a configured threshold value, a river is created. This +creates the rivers in a closed-loop-like shapes, occasionally splitting two branches off:

    + + +

    For the leftover land biomes, the two Perlin noises, representing temperature and humidity, are used to +generate the biomes, as described earlier. Additionally, the temperature map is used to turn the Ocean biome +into FrozenOcean, and the River biome into FrozenRiver, wherever the temperature drops below a threshold.

    + +

    Two-level Voronoi

    +

    The 1.7 MineCraft update brought a completely new terrain generation, which has sparked renewed interest +in the biome generation. A new, potentially simpler way of generating biomes was found, the two-level +Voronoi generator.

    + +

    The main idea behind it all is that we create large areas of similar biomes. There are several groups of +related biomes that can be generated near each other: Desert biomes, Ice biomes, Forest biomes, Mesa biomes. +Technically, the Ocean biomes were added as yet another group, so that the oceans will generate in +approximately the size of the larger areas, too.

    + +

    For each column a DistortedVoronoi is used to select, which large area to use. This in turn results in +the list of biomes from which to choose. Another DistortedVoronoi, this time with a smaller grid size, is +used to select one biome out of that list. Additionally, the smaller DistortedVoronoi calculates not only +the nearest seed's distance, but also the distance to the second-nearest seed; the ratio between these two +is used as an indicator whether the column is in the "inside" or on the "outskirt" of the smaller Voronoi +cell. This allows us to give certain biomes an "edge" biome - the Mushroom biome has a MushroomShore edge, +the ExtremeHills biome have an ExtremeHillsEdge biome on the edge, etc.

    +
    +
    +
    + +

    The following image shows an example output of a TwoLevel biome generator in MCServer:

    + + + + +

    Terrain height

    diff --git a/docs/img/biomes.jpg b/docs/img/biomes.jpg new file mode 100644 index 000000000..0f7a31eea Binary files /dev/null and b/docs/img/biomes.jpg differ diff --git a/docs/img/distortedvoronoibiomes.png b/docs/img/distortedvoronoibiomes.png new file mode 100644 index 000000000..d56dff347 Binary files /dev/null and b/docs/img/distortedvoronoibiomes.png differ diff --git a/docs/img/finishers.jpg b/docs/img/finishers.jpg new file mode 100644 index 000000000..f8a0c2b91 Binary files /dev/null and b/docs/img/finishers.jpg differ diff --git a/docs/img/jittergrid.jpg b/docs/img/jittergrid.jpg new file mode 100644 index 000000000..a13fae923 Binary files /dev/null and b/docs/img/jittergrid.jpg differ diff --git a/docs/img/jittergridlocality.jpg b/docs/img/jittergridlocality.jpg new file mode 100644 index 000000000..faf4282c5 Binary files /dev/null and b/docs/img/jittergridlocality.jpg differ diff --git a/docs/img/multistepmapbiomes.png b/docs/img/multistepmapbiomes.png new file mode 100644 index 000000000..d32ac3d8e Binary files /dev/null and b/docs/img/multistepmapbiomes.png differ diff --git a/docs/img/perlin.jpg b/docs/img/perlin.jpg new file mode 100644 index 000000000..499fcdeae Binary files /dev/null and b/docs/img/perlin.jpg differ diff --git a/docs/img/perlinheightmap.jpg b/docs/img/perlinheightmap.jpg new file mode 100644 index 000000000..d941a2fc6 Binary files /dev/null and b/docs/img/perlinheightmap.jpg differ diff --git a/docs/img/temperaturehumiditydecisionhills.jpg b/docs/img/temperaturehumiditydecisionhills.jpg new file mode 100644 index 000000000..7c105f89e Binary files /dev/null and b/docs/img/temperaturehumiditydecisionhills.jpg differ diff --git a/docs/img/temperaturehumiditydecisionsimple.jpg b/docs/img/temperaturehumiditydecisionsimple.jpg new file mode 100644 index 000000000..b6cf916f6 Binary files /dev/null and b/docs/img/temperaturehumiditydecisionsimple.jpg differ diff --git a/docs/img/terraincomposition.jpg b/docs/img/terraincomposition.jpg new file mode 100644 index 000000000..52c2c2190 Binary files /dev/null and b/docs/img/terraincomposition.jpg differ diff --git a/docs/img/terrainheight.jpg b/docs/img/terrainheight.jpg new file mode 100644 index 000000000..0f8e52ddc Binary files /dev/null and b/docs/img/terrainheight.jpg differ diff --git a/docs/img/twolevelbiomes.png b/docs/img/twolevelbiomes.png new file mode 100644 index 000000000..a3104733f Binary files /dev/null and b/docs/img/twolevelbiomes.png differ diff --git a/docs/img/voronoijitterbiomes.png b/docs/img/voronoijitterbiomes.png new file mode 100644 index 000000000..42f0b7e40 Binary files /dev/null and b/docs/img/voronoijitterbiomes.png differ -- cgit v1.2.3 From cdddb1aeac88d5502da43e238c670da5492d462f Mon Sep 17 00:00:00 2001 From: Mattes D Date: Sun, 1 Jun 2014 22:35:29 +0200 Subject: AnvilStats: Added new biome colors. --- Tools/AnvilStats/BiomeMap.cpp | 35 ++--------------------------------- Tools/AnvilStats/BiomeMap.h | 2 +- 2 files changed, 3 insertions(+), 34 deletions(-) diff --git a/Tools/AnvilStats/BiomeMap.cpp b/Tools/AnvilStats/BiomeMap.cpp index 6505299ba..de8fc4ad7 100644 --- a/Tools/AnvilStats/BiomeMap.cpp +++ b/Tools/AnvilStats/BiomeMap.cpp @@ -5,38 +5,7 @@ #include "Globals.h" #include "BiomeMap.h" - - - - - -static const int g_BiomePalette[] = -{ - // ARGB: - 0xff0000ff, /* Ocean */ - 0xff00cf3f, /* Plains */ - 0xffffff00, /* Desert */ - 0xff7f7f7f, /* Extreme Hills */ - 0xff00cf00, /* Forest */ - 0xff007f3f, /* Taiga */ - 0xff3f7f00, /* Swampland */ - 0xff003fff, /* River */ - 0xff7f0000, /* Hell */ - 0xff007fff, /* Sky */ - 0xff3f3fff, /* Frozen Ocean */ - 0xff3f3fff, /* Frozen River */ - 0xff7fffcf, /* Ice Plains */ - 0xff3fcf7f, /* Ice Mountains */ - 0xffcf00cf, /* Mushroom Island */ - 0xff7f00ff, /* Mushroom Island Shore */ - 0xffffff3f, /* Beach */ - 0xffcfcf00, /* Desert Hills */ - 0xff00cf3f, /* Forest Hills */ - 0xff006f1f, /* Taiga Hills */ - 0xff7f8f7f, /* Extreme Hills Edge */ - 0xff004f00, /* Jungle */ - 0xff003f00, /* Jungle Hills */ -} ; +#include "../BiomeVisualiser/BiomeColors.h" @@ -139,7 +108,7 @@ void cBiomeMap::StartNewRegion(int a_RegionX, int a_RegionZ) unsigned char * BiomeRow = (unsigned char *)m_Biomes + z * 512; for (int x = 0; x < 512; x++) { - RowData[x] = g_BiomePalette[BiomeRow[x]]; + RowData[x] = g_BiomeColors[BiomeRow[x]]; } f.Write(RowData, sizeof(RowData)); } // for z diff --git a/Tools/AnvilStats/BiomeMap.h b/Tools/AnvilStats/BiomeMap.h index c590a3c63..f662094a5 100644 --- a/Tools/AnvilStats/BiomeMap.h +++ b/Tools/AnvilStats/BiomeMap.h @@ -41,7 +41,7 @@ protected: virtual bool OnDecompressedData(const char * a_DecompressedNBT, int a_DataSize) override { return false; } virtual bool OnRealCoords(int a_ChunkX, int a_ChunkZ) override { return false; } virtual bool OnLastUpdate(Int64 a_LastUpdate) override { return false; } - virtual bool OnTerrainPopulated(bool a_Populated) override { return !a_Populated; } // If not populated, we don't want it! + virtual bool OnTerrainPopulated(bool a_Populated) override { return false; } // We don't care about "populated", the biomes are the same virtual bool OnBiomes(const unsigned char * a_BiomeData) override; void StartNewRegion(int a_RegionX, int a_RegionZ); -- cgit v1.2.3 From 345d4778499494616a0fac8568fbefa881627285 Mon Sep 17 00:00:00 2001 From: madmaxoft Date: Mon, 2 Jun 2014 21:43:07 +0200 Subject: Generator article: Finished the Biome-gen section and images. --- docs/Generator.html | 39 ++++++++++++++++++++++++-------------- docs/img/multistepmapdistance.jpg | Bin 0 -> 44859 bytes docs/img/multistepmapgrid.jpg | Bin 0 -> 62455 bytes docs/img/perlinrivers.jpg | Bin 0 -> 58103 bytes docs/img/twolevellargeareas.jpg | Bin 0 -> 47661 bytes docs/img/twolevelsmallareas.jpg | Bin 0 -> 67231 bytes docs/img/twolevelsmallgrid.jpg | Bin 0 -> 122477 bytes docs/img/voronoi.png | Bin 0 -> 19306 bytes 8 files changed, 25 insertions(+), 14 deletions(-) create mode 100644 docs/img/multistepmapdistance.jpg create mode 100644 docs/img/multistepmapgrid.jpg create mode 100644 docs/img/perlinrivers.jpg create mode 100644 docs/img/twolevellargeareas.jpg create mode 100644 docs/img/twolevelsmallareas.jpg create mode 100644 docs/img/twolevelsmallgrid.jpg create mode 100644 docs/img/voronoi.png diff --git a/docs/Generator.html b/docs/Generator.html index b7586a183..0963f8505 100644 --- a/docs/Generator.html +++ b/docs/Generator.html @@ -109,7 +109,7 @@ biome generator does.

    Of course, there are more interesting test scenarios for which multiple biomes must be generated as easy as possible. For these special needs, there's a CheckerBoard biome generator. As the name suggests, it -generates a grid of biomes.

    +generates a grid of alternating biomes.

    Voronoi diagram

    Those two generators were more of a technicality, we need to make something more interesting if we're @@ -117,7 +117,7 @@ going for a natural look. The Voronoi generator is the first step towards such a Voronoi diagram is a construct that creates a set of areas where each point in an area is closer to the appropriate seed of the area than the seeds of any other area:

    - +

    To generate biomes using this approach, you select random "seeds", assign a biome to each one, and then for each "column" of the world you find the seed that is the nearest to that column, and use that seed's @@ -218,19 +218,24 @@ either add them somewhere into the decision diagram, or we can make the generato this:

    -

    To decide whether the point is in the ocean, land or mushroom, the generator uses a DistortedVoronoi -approach where the seeds get the "ocean", "land" and "mushroom" values; special handling is added so that a -mushroom value is always surrounded by ocean values on all 8 sides:

    - +

    To decide whether the point is in the ocean, land or mushroom, the generator first chooses seeds in a grid +that will be later fed to a DistortedVoronoi algorithm, the seeds get the "ocean" and "land" values. Then it +considers all the "ocean" seeds that are surrounded by 8 other "ocean" seeds and turns a random few of them +into "mushroom". This special seed processing makes the mushroom biomes mostly surrounded by ocean. The +following image shows an example seeds grid that the generator might consider, only the two framed cells are +allowed to change into mushroom. L = land, O = ocean:

    + -

    For the Voronoi cells that are calculated as mushroom, the distance to the nearest-seed is used to -further shrink the mushroom biome and then to distinguish between mushroom and mushroom-shore:

    - +

    Next, the generator calculates the DistortedVoronoi for the seeds. For the areas that are calculated as +mushroom, the distance to the nearest-seed is used to further shrink the mushroom biome and then to +distinguish between mushroom and mushroom-shore (image depicts a Voronoi cell for illustration purposes, it +works similarly with DistortedVoronoi). O = ocean, M = mushroom, MS = mushroom shore:

    +

    The rivers are added only to the areas that have been previously marked as land. A simple 2D Perlin noise is used as the base, where its value is between 0 and a configured threshold value, a river is created. This creates the rivers in a closed-loop-like shapes, occasionally splitting two branches off:

    - +

    For the leftover land biomes, the two Perlin noises, representing temperature and humidity, are used to generate the biomes, as described earlier. Additionally, the temperature map is used to turn the Ocean biome @@ -239,7 +244,7 @@ into FrozenOcean, and the River biome into FrozenRiver, wherever the temperature

    Two-level Voronoi

    The 1.7 MineCraft update brought a completely new terrain generation, which has sparked renewed interest in the biome generation. A new, potentially simpler way of generating biomes was found, the two-level -Voronoi generator.

    +DistortedVoronoi generator.

    The main idea behind it all is that we create large areas of similar biomes. There are several groups of related biomes that can be generated near each other: Desert biomes, Ice biomes, Forest biomes, Mesa biomes. @@ -253,13 +258,19 @@ the nearest seed's distance, but also the distance to the second-nearest seed; t is used as an indicator whether the column is in the "inside" or on the "outskirt" of the smaller Voronoi cell. This allows us to give certain biomes an "edge" biome - the Mushroom biome has a MushroomShore edge, the ExtremeHills biome have an ExtremeHillsEdge biome on the edge, etc.

    -
    -
    -
    + +

    The images below illustrate the process with regular Voronoi diagrams, for clarity purposes. The real +generator uses distortion before querying the small areas.

    +
    +
    +

    The following image shows an example output of a TwoLevel biome generator in MCServer:

    +

    Note that rivers are currently not implemented in this generator in MCServer, but they could be added +using the same approach as in MultiStepMap - by using a thresholded 2D Perlin noise.

    +

    Terrain height

    diff --git a/docs/img/multistepmapdistance.jpg b/docs/img/multistepmapdistance.jpg new file mode 100644 index 000000000..74e972b2a Binary files /dev/null and b/docs/img/multistepmapdistance.jpg differ diff --git a/docs/img/multistepmapgrid.jpg b/docs/img/multistepmapgrid.jpg new file mode 100644 index 000000000..7e7bf870f Binary files /dev/null and b/docs/img/multistepmapgrid.jpg differ diff --git a/docs/img/perlinrivers.jpg b/docs/img/perlinrivers.jpg new file mode 100644 index 000000000..148348aff Binary files /dev/null and b/docs/img/perlinrivers.jpg differ diff --git a/docs/img/twolevellargeareas.jpg b/docs/img/twolevellargeareas.jpg new file mode 100644 index 000000000..4d6b418b1 Binary files /dev/null and b/docs/img/twolevellargeareas.jpg differ diff --git a/docs/img/twolevelsmallareas.jpg b/docs/img/twolevelsmallareas.jpg new file mode 100644 index 000000000..8bfa54ab3 Binary files /dev/null and b/docs/img/twolevelsmallareas.jpg differ diff --git a/docs/img/twolevelsmallgrid.jpg b/docs/img/twolevelsmallgrid.jpg new file mode 100644 index 000000000..29f61c8ac Binary files /dev/null and b/docs/img/twolevelsmallgrid.jpg differ diff --git a/docs/img/voronoi.png b/docs/img/voronoi.png new file mode 100644 index 000000000..e61e183ef Binary files /dev/null and b/docs/img/voronoi.png differ -- cgit v1.2.3 From 6f7ac0089f891a2b432e7417424e5e88e2a6f341 Mon Sep 17 00:00:00 2001 From: madmaxoft Date: Mon, 2 Jun 2014 21:56:59 +0200 Subject: Generator article: fixed bad wording. --- docs/Generator.html | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/docs/Generator.html b/docs/Generator.html index 0963f8505..d965cf5d2 100644 --- a/docs/Generator.html +++ b/docs/Generator.html @@ -181,9 +181,9 @@ generated right next to other land biomes.

    Adding relativity

    -

    Our next goal is to remove the first defect of the distorted voronoi generator: unrelated biomes +

    Our next goal is to remove the first defect of the distorted Voronoi generator: unrelated biomes generating next to each other. It is highly unlikely to find a jungle biome next to a desert biome, so we -want to have as few of those boundaries as possible. We could further improve on the selection of +want to have as few of such borders as possible. We could further improve on the selection of biome-to-seed in the Voronoi generator. Or we can try a completely different idea altogether.

    Recall how we talked about the nature, where the biomes are formed by the specific conditions of a place. -- cgit v1.2.3 From 49b39f97e0d947c655aad64317a6500f94ad61ef Mon Sep 17 00:00:00 2001 From: madmaxoft Date: Tue, 3 Jun 2014 14:00:50 +0200 Subject: Generator article: Added TOC with links. --- docs/Generator.html | 51 ++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 44 insertions(+), 7 deletions(-) diff --git a/docs/Generator.html b/docs/Generator.html index d965cf5d2..d7eb6ba8d 100644 --- a/docs/Generator.html +++ b/docs/Generator.html @@ -8,7 +8,24 @@ specific to MCServer, though, it can be viewed as a generic guide to various terrain-generating algorithms, with specific implementation notes regarding MCServer.

    -

    Preface: How it's done in real life

    +

    Contents: +

    +

    + + +
    + +

    Preface: How it's done in real life

    The nature has many complicated geological, physical and biological processes working on all scales from microscopic to planet-wide scale, that have shaped the terrain into what we see today. The tectonic plates collide, push mountain ranges up and ocean trenches down. Erosion dulls the sharp shapes. Plantlife takes @@ -21,7 +38,10 @@ mainly because in the nature everything interacts with everything. If a mountain way that the precipitation is carried by the wind to the lands beyond the mountains, thus changing the erosion rate there and the vegetation type.

    -

    Expected properties

    + +
    + +

    Expected properties

    For a MineCraft-like game terrain generator we need the generator to have several properties:

    • The generator must be able to generate terrain in small chunks. This means it must be possible to @@ -37,8 +57,9 @@ distinction will be discussed later.

      • +
      -

      Reversing the flow

      +

      Reversing the flow

      As already mentioned, the nature works basically by generating raw terrain composition, then "applying" erosion, vegetation and finally this leads to biomes being formed. Let's now try a somewhat inverse approach: First generate biomes, then fit them with appropriate terrain, and finally cover in vegetation @@ -54,8 +75,9 @@ generate all the vegetation and structures in it, and those can again use the te neighboring chunks.

      +
      -

      The ComposableGenerator pipeline

      +

      The ComposableGenerator pipeline

      This leads us directly to the main pipeline that is used for generating terrain in MCServer. For technical reasons, the terrain composition step is further subdivided into Height generation and Composition generation, and the structures are really called Finishers. For each chunk the generator generates, in this @@ -77,8 +99,9 @@ have 5 biome generators and 3 height generators and you can let the users mix'n'

      +
      -

      Using coherent noise for the generation

      +

      Using coherent noise for the generation

      For a great tutorial on coherent noise, see the LibNoise documentation.

      Coherent noise is a type of noise that has three important properties that we can use to our advantage: @@ -101,7 +124,9 @@ generated for any number of dimensions.

      -

      Generating biomes

      +
      + +

      Generating biomes

      The easiest way to generate biomes is to not generate them at all - simply assign a single constant biome to everywhere. And indeed there are times when this kind of "generator" is useful - for the MineCraft's Flat world type, or for testing purposes, or for tematic maps. In MCServer, this is exactly what the Constant @@ -272,7 +297,19 @@ generator uses distortion before querying the small areas.

      using the same approach as in MultiStepMap - by using a thresholded 2D Perlin noise.

      +
      + +

      Terrain height

       + + +
      + +

      Terrain composition

       + + +
      + +

      Finishers

       -

      Terrain height

      -- cgit v1.2.3