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

Post a Comment

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...
9 comments
Read more

Warp

So, it turns out that I didn't use Criterium for the video game competition at Stanford.  I actually met a partner and went with another concept instead -- Warp.  It's kind of like Starfox and it's inspired by Rez, one of the first PS2 games.  Explosions and missiles fire in time with the music; we used ChucK , an audio processing language, to achieve this. We also made some destructible objects using rigid bodies, and I added some particle explosion effects.  We used Lua to for enemy AI, and wrote a small TCL-like script parser that reads in data for the level layout.  The buildings in the background are procedurally generated.  We used OGRE for the graphics (this was a loose requirement of the project) and Bullet for the physics.  I had a lot of fun with this project, and I've posted a video capture below.
1 comment
Read more

Sparse Voxel Octrees

Terrain implementation for games is a subject with a lot of depth. At the surface, it's very easy to get rudimentary terrain working via a noise function and fixed triangle grid. As you add more features, though, the complexity builds quickly. Overhangs, caves Multiple materials Destructive terrain Collision detection Persistence Dynamic loading Regions, biomes Very large scale Smooth features Sharp features Dynamic level of detail Extremely long view distances In isolation, each of these features can make terrain difficult to implement. Taken together, it takes a lot of care and attention to make it all work. Minecraft is probably the canonical example for terrain generation in the last generation of games. In fact, I'd say Minecraft's terrain is the killer feature that makes the game so great. Minecraft does an excellent job at 1-8, but for a recent planetary renderer project I was working on, I really wanted 9-12 too. In a series of articles, I'm planning to break do...
Post a Comment
Read more