10 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>
diff --git a/docs/img/biomalheights.jpg b/docs/img/biomalheights.jpg
new file mode 100644
index 000000000..a01faef87
--- /dev/null
+++ b/docs/img/biomalheights.jpg
diff --git a/docs/img/biomeheights.jpg b/docs/img/biomeheights.jpg
new file mode 100644
index 000000000..9dda27b0e
--- /dev/null
+++ b/docs/img/biomeheights.jpg
diff --git a/docs/img/biomeheightsavg.jpg b/docs/img/biomeheightsavg.jpg
new file mode 100644
index 000000000..c8217cafc
--- /dev/null
+++ b/docs/img/biomeheightsavg.jpg
diff --git a/docs/img/gaussprobability.jpg b/docs/img/gaussprobability.jpg
new file mode 100644
index 000000000..77da24748
--- /dev/null
+++ b/docs/img/gaussprobability.jpg
diff --git a/docs/img/perlincompositor1.jpg b/docs/img/perlincompositor1.jpg
new file mode 100644
index 000000000..0d8f93cd9
--- /dev/null
+++ b/docs/img/perlincompositor1.jpg
diff --git a/docs/img/perlincompositor2.jpg b/docs/img/perlincompositor2.jpg
new file mode 100644
index 000000000..11fc5b51d
--- /dev/null
+++ b/docs/img/perlincompositor2.jpg
diff --git a/docs/img/perlincompositor3.jpg b/docs/img/perlincompositor3.jpg
new file mode 100644
index 000000000..46a2583ba
--- /dev/null
+++ b/docs/img/perlincompositor3.jpg
diff --git a/docs/img/roofprobability.jpg b/docs/img/roofprobability.jpg
new file mode 100644
index 000000000..e7a155113
--- /dev/null
+++ b/docs/img/roofprobability.jpg
diff --git a/docs/img/smallfoliageclumps.jpg b/docs/img/smallfoliageclumps.jpg
new file mode 100644
index 000000000..4cc6cbc00
--- /dev/null
+++ b/docs/img/smallfoliageclumps.jpg