Skip to main content

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.


Comments

Popular posts from this blog

Lua-Style Coroutines in C++

Lua's implementation of coroutines is one of my all-time favorite features of the language. This (short) paper explains the whole reasoning behind the Lua's coroutine implementation and also a little about the history of coroutines. Sadly, coroutines are not supported out-of-the box by many modern languages, C++ included. Which brings me to the subject of this post: Lua-style coroutines in C++! For those who don't know (or were too lazy to read the paper!), Lua's coroutines support three basic operations: Create: Create a new coroutine object Resume: Run a coroutine until it yields or returns Yield: Suspend execution and return to the caller To implement these three operations, I'll use a great header file: ucontext.h. #include <vector> #include <ucontext.h> class Coroutine { public: typedef void (*Function)(void); Coroutine(Function function); void resume(); static void yield(); private: ucontext_t context_; std

Criterium: Road Screenshots

I finally got around to making the road tool for Criterium.  The tool has two parts: a Java application that lets you paint roads on the 2D heightmap texture, and a Ogre-based tool that automatically converts a 2D path into a 3D mesh.  The Ogre-tool queries the heightmap to get the height of the road, and performs smoothing so there are no discontinuous road segments.  I've posted a screenshot below.  Also, I've got my GIMP terrain shown in the screenshot.  I generated it using random noise and the GIMP lightmap filter.

Jet: Particle Systems

Here's a demo of the new particle systems I've implemented in OpenGL.  Performance is much improved over the DirectX version.  Particles are initialized in C++ rather than in Lua.  Also, I use two particle buffers and swap between them, rather than using one buffer per particle system.  Anyway, here's a video capture: