diff options
Diffstat (limited to 'docs/Generator.html')
| -rw-r--r-- | docs/Generator.html | 210 |
1 files changed, 210 insertions, 0 deletions
diff --git a/docs/Generator.html b/docs/Generator.html index f6e7f1cd9..90a92c553 100644 --- a/docs/Generator.html +++ b/docs/Generator.html @@ -19,6 +19,8 @@ with specific implementation notes regarding MCServer.</p> <li><a href="#heightgen">Terrain height</a></li> <li><a href="#compositiongen">Terrain composition</a></li> <li><a href="#finishgen">Finishers</a></li> +<li><a href="#makefaster">Making it all faster</a></li> +<li><a href="#GPU">Executing on a GPU</a></li> </ul> </p> @@ -304,16 +306,224 @@ using the same approach as in MultiStepMap - by using a thresholded 2D Perlin no <hr /> <a name="heightgen"><h2>Terrain height</h2></a> +<p>As with biomes, the easiest way to generate terrain height is not generating at all - assigning a constant +height value to all columns. This is again useful either for internal tests, and for worlds like MineCraft's +Flat world.</p> + +<p>For a somewhat more realistic landscape, we will employ the good old 2D Perlin noise. We can use it +directly as a heightmap - each value we get from the noise is stretched into the desired range (usually from +40 to 120 blocks for regular MineCraft worlds) and used as the height value. However, this doesn't play too +well with the biomes we've just generated. If the biome says "ocean" and the Perlin noise says "mountain", +the end result will be unpleasant.</p> + +<p>So we want a height generator that is biome-aware. The easiest way of doing this is to have a separate +generator for each biome. Simply use the biome map to select which generator to use, then ask the appropriate +generator for the height value. Again, this doesn't work too well - imagine an ExtremeHills biome right next +to an Ocean biome. If no extra care is taken, the border between these two will be a high wall. The following +image shows a 2D representation (for simplification purposes) of the problem:</p> +<img src="img/biomeheights.jpg" /> + +<p>This requires some further processing. What we need is for the terrain height to be dependent not only on +the immediate biome for that column, but also on the close surroundings of the column. This is exactly the +kind of task that averaging is designed for. If we take the area of 9x9 biomes centered around the queried +column, generate height for each of the biomes therein, sum them up and divide by 81 (the number of biomes +summed), we will be effectively making a 9-long running average over the terrain, and all the borders will +suddenly become smooth. The following image shows the situation from the previous paragraph after applying +the averaging process: </p> +<img src="img/biomeheightsavg.jpg" /> + +<p>The approach used in MCServer's Biomal generator is based on this idea, with two slight modifications. +Instead of using a separate generator for each biome, one generator is used with a different set of input +parameters for each biomes. These input parameters modify the overall amplitude and frequency of the Perlin +noise that the generator produces, thus modifying the final terrain with regards to biomes. Additionally, the +averaging process is weighted - columns closer to the queried column get a more powerful weight in the sum +than the columns further away. The following image shows the output of MCServer's Biomal terrain height +generator (each block type represents a different biome - ocean in the front (stone), plains and ice plains +behind it (lapis, whitewool), extreme hills back right (soulsand), desert hills back left (mossy +cobble)):</p> +<a name="biomalheights"><img src="img/biomalheights.jpg" /></a> + +<p>One key observation about this whole approach is that in order for it to work, the biomes must be +available for columns outside the currently generated chunk, otherwise the columns at the chunk's edge would +not be able to properly average their height. This requirement can be fulfilled only by biome generators that +adhere to the second <a href="#expectedproperties">Expected property</a> - that re-generating will produce +the same data. If the biome generator returned different data for the same chunk each time it was invoked, it +would become impossible to apply the averaging.</p> + +<p>(TODO: height with variations (N/A in MCS yet)</p> <hr /> <a name="compositiongen"><h2>Terrain composition</h2></a> +<p>As with the other generators, the composition generator category has its easy and debugging items, too. +There's the "special" composition of "all the blocks are the same type", which fills the entire column, from +the bottom to the height, with a single blocktype. This generator is useful when testing the generators in +the other categories, to speed up the generation by leaving out unnecessary calculations. Another special +compositor is a similar one, that fills all blocks with the same type, but the type varies for each biome. +This way it's easy to see the generated biomes and possibly the heights for those biomes, as shown in the +previous section on the <a href="#biomalheights">height averaging screenshot</a>.</p> + +<p>For a natural look, we need to put together a more complicated algorithm. The standard set forth in +MineCraft is that the top of the world is covered in grass, then there are a few blocks of dirt and finally +stone. This basic layout is then varied for different biomes - deserts have sand and sandstone instead of the +grass and dirt layer. Mushroom biomes have mycelium in place of the grass. This per-biome dependency is +trivial to implement - when compositing, simply use the appropriate layout for the column's biome.</p> + +<p>The next change concerns oceans. The generated heightmap doesn't include any waterlevel indication +whatsoever. So it's up to the terrain compositor to actually decide where to place water. We do this by +configuration - simply have a value in the config file specifying the sealevel height. The compositor then +has to add water above any column which has a height lower than that. Additionally, the water needs to +override per-biome layout selection - we don't want grass blocks to generate under water when the terrain +height in the plains biome drops below the sealevel accidentally.</p> + +<p>The final feature in the compositor is the decision between multiple composition layouts within a single +biome. A megataiga biome contains patches of non-grass dirt and podzol blocks, and the ocean floor can be +made of dirt, gravel, sand or clay. A simple 2D Perlin noise can be used to select the layout to use for a +specific column - simply threshold the noise's value by as many thresholds as there are layout variations, +and use the layout corresponding to the threshold:</p> +<img src="img/perlincompositor1.jpg" /> +<img src="img/perlincompositor2.jpg" /> +<img src="img/perlincompositor3.jpg" /> + +<h3>Nether composition</h3> +<p>So far we've been discussing only the Overworld generator. But MineCraft contains more than that. The +Nether has a completely different look and feel, and quite different processes are required to generate that. +Recall that MineCraft's Nether is 128 blocks high, with bedrock both at the top and the bottom. Between these +two, the terrain looks more like a cavern than a surface. Not surprisingly, the Nether doesn't need a +complicated height generator, it can use the flat height. However, the terrain composition must take an +altogether different approach.</p> + +<p>The very first idea is to use the Perlin noise, but generate it in 3D, rather than 2D. Then, for each +block, evaluate the noise value, if below 0, make it air, if not, make it netherrack. + +<p>To make it so that the bedrock at the top and at the bottom is never revealed, we can add a value +increasing the more the Y coord gets towards the bottom or the top. This way the thresholding then guarantees +that there will be no air anywhere near the bedrock.</p> + +<p>(TODO)</p> <hr /> <a name="finishgen"><h2>Finishers</h2></a> +<p>Finishers are a vast category of various additions to the terrain generator. They range from very easy +ones, such as generating snow on top of the terrain in cold biomes, through medium ones, such as growing +patches of flowers, complicated ones, such as placing trees and generating caves, all the way to very +complicated ones such as villages and nether fortresses. There is no formal distinction between all these +"categories", the only thing they have in common is that they take a chunk of blocks and modify it in some +way.</p> + +<h3>Snow</h3> +<p>Snow is probably the easiest of the finishers. It generates a block of snow on top of each block that is +on top of the terrain and is not marked as non-snowable. It checks the chunk's heightmap to determine the top +block, then checks whether the block supports snow on its top. Rails, levers and tall grass don't support +snow, for example.</p> + +<h3>Ice</h3> +<p>Another example of an easy finisher. This scans through the world and turn each water block on the surface +into an ice block if the biome is cold. This means that any water block that is under any kind of other +block, such as under a tree's leaves, will still stay water. Thus an additional improvement could be made by +scanning down from the surface block through blocks that we deem as non-surface, such as leaves, torches, +ladders, fences etc. Note that MCServer currently implements only the easy solution.</p> + +<h3>Bottom lava</h3> +<p>Most worlds in MineCraft have lava lakes at their bottom. Generating these is pretty straightforward: Use +the user-configured depth and replace all the air blocks below this depth with lava blocks. Note however, +that this makes this generator dependent on the order in which the finishers are applied. If the mineshafts +generate before bottom lava, the mineshafts that are below the lava level will get filled with lava. On the +other hand, if bottom lava is generated before the mineshafts, it is possible for a mineshaft to "drill +through" a lake of lava. MCServer doesn't try to solve this and instead lets the admin choose whichever they +prefer.</p> + +<h3>Specific foliage</h3> +<p>There are generators for specific kinds of foliage. The dead bushes in the desert biome and lilypads in +the swamp biome both share the same generating pattern. They are both specific to a single biome and they +both require a specific block underneath them in order to generate. Their implementation is simple: pick +several random columns in the chunk. If the column is of the correct biome and has the correct top block, +add the foliage block on top.</p> + +<p>In order to generate the same set of coordinates when the chunk is re-generated, we use the Perlin noise's +basis functions (the ones providing the random values for Perlin cell vertices). These basically work as a +hash function for the coorinates - the same input coordinates generate the same output value. We use the +chunk's coordinates as two of the coords, and the iteration number as the third coordinate, to generate a +random number. We then check the biome and the top block at those coordinates, if they allow, we generate the +foliage block on top.</p> + +<p>Another example of specific foliage is the tall grass in the plains biome. There are quite a lot of these +tall grass blocks, it would be inefficient to generate them using the random-coords approach described above. +Instead, we will use a 2D Perlin noise again, with a threshold defining where to put the grass and where +not.</p> + +<h3>Small foliage</h3> +<p>For the flowers, grass, mushrooms in caves etc. we want to use a slightly different algorithm. These +foliage blocks are customarily generated in small "clumps" - there are several blocks of the same type near +together. To generate these, we first select random coords, using the coord hash functions, for a center of a +clump. Then we select the type of block to generate. Finally, we loop over adding a random (coord hash) +number to the clump center coords to get the block where to generate the foliage block:</p> +<img src="img/smallfoliageclumps.jpg" /> + +<p>In order to make the clump more "round" and "centered", we want the offsets to be closer to the clump +center more often. This is done using a thing called Gaussian function distribution. Instead of having each +random number generate with the same probability, we want higher probability for the numbers around zero, +like this:</p> +<img src="img/gaussprobability.jpg" /> + +<p>Instead of doing complicated calculations to match this shape exactly, we will use a much easier shape. +By adding together two random numbers in the same range, we get the probability distribution that has a +"roof" shape, enough for our needs:</p> +<img src="img/roofprobability.jpg" /> + +<p>(For the curious, there is a proof that adding together infinitely many uniform-distributed random numbers +produces random numbers with the Gaussian distribution.)</p> + +<p>This scheme can be used to produce clumps of flowers, when we select the 2D coords of the clump center on +the top surface of the terrain. We simply generate the 2D coords of the foliage blocks and use the terrain +height to find the third coord. If we want to generate clumps of mushrooms in the caves, however, we need to +generate the clump center coords in 3D and either use 3 offsets for the mushrooms, or use 2 offsets plus +searching for the closest opening Y-wise in the terrain.</p> + +<p>Note that the clumps generated by this scheme may overlap several chunks. Therefore it's crucial to +actually check the surrounding chunks if their clumps overlap into the currently generated chunk, and apply +those as well, otherwise there will be visible cuts in the foliage along the chunks borders.</p> + +<h3>Springs</h3> +<p>Water and lava springs are essential for making the underground quite a lot more interesting. They are +rather easy to generate, but a bit more difficult to get right. Generating simply means that a few random +locations (obtained by our familiar coord hashing) are checked and if the block type in there is stone. Then +we see all the horizontal neighbors of the block, plus the block underneath. If all of them except one are +stone, and the one left is air, our block is suitable for turning into a spring. If there were more air +neighbors, the spring would look somewhat unnatural; if there were no air neighbors, the spring won't flow +anywhere, so it would be rather useless.</p> + +<p>The difficult part about springs is the amount of them to generate. There should be a few springs on the +surface, perhaps a bit more in the mountaineous biomes. There should be quite a few more springs underground, +but there should definitely be more water springs than lava springs in the upper levels of the terrain, while +there should be more lava springs and almost no water springs near the bottom. To accomodate this, the +MCServer team has made a tool that scanned through MineCraft's terrain and counted the amount of both types +of springs in relation to their height. Two curves have been found for the distribution of each type of the +spring:</p> +<img src="http://mc-server.xoft.cz/img/vanilla_springs_huge.png" /> + +<p>MCServer uses an approximation of the above curves to choose the height at which to generate the +spring.</p> + +<!-- +<h3>Caves</h3> +<p>Caves are definitely one of the main things people notice about MineCraft terrain. There are quite a lot +of different algorithms available to generate terrain with caves. +--> +<hr /> + +<a name="makefaster"><h2>Making it all faster</h2></a> +<p>(TODO)</p> + +<a name="GPU"><h2>Executing on a GPU</h2></a> +<p>Much of the terain generation consists of doing the same thing for every single column or block in a chunk. This +sort of computation is much faster on a GPU as GPUs are massively parallel. High end GPUs can execute up to 30,000 +threads simultaneously, which would allow them to generate every block in half a chunk in parallel or every column +in over 100 chunks in parallel. A naive comparison suggests that a 800MHz GPU with 15,000 threads can execute parallel +code 250 times faster than a 3GHz CPU with 128 bit SIMD. Obviously we want to harness that power.</p> </body> </html> |