Minecraft Terrain

Yesterday, on my day off, I played around with generating some Minecraft-like terrain. A lot of people see Minecraft and think "Hey, that doesn't look too complicated...I could do that!" As a result, we have lots of Minecraft clones and articles about implementing Minecraft-like terrain. I think that's great, because it inspires people who don't have much graphics programming experience to give it a try. A game like Crysis doesn't exactly do that. It's just too much complexity for a single person to handle.

Anyway, the first step in my journey to copy Minecraft was to implement a "mesher." A mesher converts a 3D bitmap containing block data into a quad mesh that's displayable using OpenGL. This part was surprisingly easy, at least for the simple approach I took. I decided to sweep each "column" of blocks in the X, Y, and Z directions, and generate the quad faces that way. This doesn't allow quad faces to span across multiple blocks, but it does allow you to cull inside faces that aren't visible. My algorithm is basically:

prevType = air
for block in column:
  if block.type == prevType:
    # Do nothing, b/c the block is an 
    # "inside" or culled block    
  elif block.type != air:
    renderFrontFace()
    # Transition from air => not air.  
    # Render front face of the block.
  elif block.type == air:
    renderBackFace()
    # Transition from not air => air.  
    # Render back face.

renderFrontFace() and renderBackFace() are different, because the winding order is different from the front and back faces of a cube. If you don't use backface culling, you could actually use renderFrontFace() in both cases above.

Generating the randomized terrain was much more difficult. I tried a 3D Perlin noise implementation, since that's what Notch apparently used for Minecraft. In Notch's 3D Perlin noise scheme, if the noise value for a block is above a certain threshold, you make the block type "air," otherwise, you make it "rock." This worked OK, but my end result didn't have smooth transitions like Minecraft's. I quickly discovered that the "Perlin noise" I used wasn't actually Perlin noise. In particular, the noise generator didn't interpolate fractional input values. I decided to play around with this "fake" Perlin noise anyway, to see if I could get a good effect.

The first modification I did was to add the block height (y coordinate) to the output of the Perlin noise, so that as you go up in the +y direction, the probability of getting an air block increases. This worked (it generated hills at the surface), but the hills were very blocky.

So, I searched for a better noise function. I eventually stumbled upon a simplex noise implementation written in Java, and started using that. Simplex noise is very similar to true Perlin noise. The result was smoother, but still too high frequency: lots of small, choppy hills, and no epic cliffs or overhangs as found in Minecraft. The caves in the lower blocks were good though. I read somewhere that increasing the sample frequency could help. So instead of using simplexNoise(x, y, z) I used simplexNoise(x/a, y/b, z/b). I eventually settled with a=48, b=32, c=48. Because the simplex noise function I used interpolates fractional values, the result was much smoother!

Not bad! Next, I wanted to work on level-of-detail block generation, since this greatly reduces the number of vertices that are necessary to render the terrain. To generated a lower level of detail, I increased the stride of the mesher by a power of 2 for each level of detail. So, instead of iterating over every block and generating faces for each block, I iterated over every N blocks and generated faces that were N times larger than the normal faces. Here's the result:

LOD sample size = 0:


LOD sample size = 2:

This was pretty easy, compared with actually generating the random terrain! My next goal is to create a "Minecraft planet" by wrapping Minecraft terrain around a sphere. That should be tricky, because cubes do not wrap nicely around a sphere.