Grounded

I've been making progress on my project! I finally got some basic physics implemented (after three days of debugging), so you can walk around the world now. I also did some optimization; things are running a lot faster now. Sections of the world are now generated on demand, so you can walk around indefinitely. I'm not saving or loading sections yet though. I also added in some variation in the terrain, so now there are patches of snow and snow capped mountain peaks.

This week I'm going to talk about how I'm generating the world.

Step 0: Building Blocks

The game world is made up blocks. Blocks have two properties; shape and material. Blocks are grouped into chunks. Each chunk is 16 blocks wide, 16 blocks deep, and 256 blocks tall. The shape of a block is an 8 bit number. Each bit corresponds to one of the corners. The resulting block must have a vertex at each indicated corner and must be constructed in such a way as to be convex.

The order of the vertices is important. This particular order lets me use bit shifts to compare the left side of one block to the right side of another (likewise with front and back, top and bottom).

Step 1: Terrain Generation

Terrain is generated using a method similar to (though technically different from) Perlin noise. When a chunk is generated, I sample the noise function to create a height map. This height map determines the height of the corners, not of the centers of the blocks. Any corner that is below the height map is present; corners that are above are not.

There is an additional step after this. Blocks that would result in a flat shape are removed, and 'corner' blocks are modified to look better.

Step 2: Mesh Generation

Simply rendering each block is much too slow, so some more work is required to draw the game world. Each chunk gets its own mesh which is generated once and then sent to the GPU. Prototype vertices for each shape are stored in a large lookup table. Vertices are sorted based on which side of the block they correspond to. When creating the mesh, any faces that would be 'inside' the chunk are not added to the mesh. A face is 'inside' if it is covered up by an adjacent block. This eliminates the majority of the faces. Note that this method doesn't eliminate hollow bubbles inside the mesh, even though they can't be seen from the outside.

Each block requires some additional processing. The vertices must be translated so that they're in the correct position. The texture coordinates are adjusted based on the material. With the particular way I'm constructing the blocks, there are 112 different possible triangles (including front and back faces). Each material in the material lookup table has a byte for each of these triangles. That byte determines which part of the texture to show for the corresponding triangle.

Step 3: Rendering

The last step is pretty simple. Chunks are kept sorted by how far away they are from the player. When it comes time to render the world, the chunks are drawn nearest to farthest (excluding chunks that are completely outside the view frustum). This improves performance by taking advantage of the z-buffer. This also helps eliminate z-fighting that can occur at the borders between chunks. The end result is a big beautiful world rendered in real-time.