My name is Michael Goodfellow. The first time I touched a computer was probably in 1971, and I immediately wanted to know how to program it. I worked in the software industry from 1975 to 2005, when I retired on disability. And yes, I still write code. Who knows why?
I learned programming writing computer games (which were played on typewriter-style terminals connected to mainframes), but I never got to write one professionally. I've wanted to write a game for years. I've taken a stab at it more than once. But before I could find the time to do it, games just got too good looking. For someone with no artistic ability to speak of, it just looked too hard. Half-Life2 (or even Half-Life) is not something you knock out in your spare time while working a day job. My friends -- all corporate systems programmers like myself -- agreed. When I mentioned writing a game (even an MMO!) they laughed, and laughed, and laughed.
But now Minecraft has come out and become a hit -- and it's a one-person project. Apparently there's still a niche out there for games that don't look like a million dollars (or 20 million...) So I'm going to try again.
When I've worked on projects before, it's just been me, the computer and complete silence, since none of my friends are interested in this kind of impossible project. This time, I might as well let it all hang out. I'll code in public for your amusement. And to let you follow along, I'll publish all the code open source. Even if I run out of steam, perhaps there will be some useful framework in there for some of you to use.
Finally, I know there are many other open source projects out there with rich frameworks. And so developing anything from scratch like this is kind of a waste of time. Plus there are all sorts of standard formats and interfaces you should support, and standard tools you could use. Wouldn't it be better to reuse someone else's code, to get a head start on this? But umm... Hey, look! A requirements document! Wouldn't you like to go have a 10 hour meeting about it?
The fact is, writing code with a blank slate where you can go off in any direction is fun. Reading through poorly documented code, supporting interfaces with 100 page specs, debugging other people's code, or trying to add features that were never intended is, well... not fun.
So let's get coding!
Part 1: It's a Small World
Since Minecraft is so popular, let's start with a world made of cubes. I will want to revisit this later, but for now, it's got a number of advantages. First, it's easy to code. Second, you can modify the world easily by adding and subtracting cubes. When we write a server and let all the people get together, we will want a modifiable world. And finally, if Minecraft can be a success with cubes, lots of other games could be written with that same style of graphics (look at CGI Lego animations on YouTube.) So someone might get some use out of even this simple world code.
If you are going to build out of cubes, the first data structure that comes to mind is the Octree. It divides all of your space into 8 cubes. If a cube has nothing in it, or all the same kind of cube in it (such as a volume of water or soil), then you are done. If the cube is not uniform, then you subdivide it into 8 child cubes. You do this repeatedly until you have reached the size-1 cubes that actually make up the world. See Figure 1 for an example of a world where only the top corner cube has been deleted. In Figure 2, you can see the tree of a more complex object -- a sphere with a slice cut away.
We can do a landscape the same way. We generate some heights from a pattern of Perlin Noise. We're using a tree of 128 by 128 by 128 (7 levels) so it could potentially have 2,097,152 individual cubes. This landscape is solid at the bottom, and the land doesn't extend very far vertically. It also doesn't have layers of dirt, gravel or ore below the surface. But due to the compression of the Octree, it only has 35,057 nodes. See Figure 3 for a view of it.
If we support multiple block types and color them a bit by height, adding a layer of water at the bottom, we get something that looks more like a landscape. See Figure 4. Since this has several different block types (which means more individual cubes that can't be combined into larger cubes), there are 47,297 nodes.
Now we have to do some optimization. I've been drawing this in the stupidest possible way. I just traverse the Octree, drawing each of the top 8 cubes. They recursively draw their 8 children and so on, until the entire tree is drawn. For the leaf cubes, it just draws all 6 sides of the cube, with a different texture on each side. This is horribly slow!
First, we shouldn't draw the sides that are facing away from us, since they don't show. That's an easy check to make in the code, and will save us half the time.
Second, we shouldn't draw the cubes that are behind us or outside what's called the view frustum. See Figure 5 for an idea of how the graphics are drawn. You have a volume that is projected onto the near view plane (your screen), which is in front of the camera point. All the cubes outside that truncated pyramid are not going to be seen, so we shouldn't draw them. To test this, I build a sphere around each of the cubes, and test if that sphere is on the right side of each of the six sides of the frustum. This is a slightly expensive test for each cube, but fortunately, we don't have to test them individually.
The nice thing about an Octree is that we can do this test on the nodes of the tree as we traverse it. For example, if one of the top eight cubes is outside the view, then we don't have to look inside it. All of its child cubes will be outside as well. See Figure 6 to show a clipping of the tree. I've moved the edges of the view in 25% from the true edge of the screen. You can see which cubes are still drawn. The larger cubes are the ones higher up in the tree which have no children.
Third, we can make better use of the graphics hardware by not drawing each cube independently and switching textures (the pattern on the faces) each time. Instead, we should draw all the soil top faces, then all the soil side faces, then the rock faces, etc. This just takes a bit of restructuring of the code. As we traverse the tree, we'll add the various faces to buffers, one per texture. Then we can output the faces in batches.
Finally, we are still drawing cubes that are buried in the ground and can't be seen. We need to skip cubes that are not exposed to the air. There a couple of ways to do this. We could just ask before we draw each face of a cube. We would calculate the position of a block in front of that face, and ask the tree if there is a block there. This isn't as slow as it sounds. Because the Octree is a tree, it only takes a maximum of 7 comparisons to find a block (because we made the tree 7 levels deep, or 27=128 cubes across.) There's going to be a special case for bigger blocks though. If for example we have a 4 by 4 by 4 block that is all soil, we will have to ask about each of the 16 blocks that might touch one of its faces (see Figure 7). The big block face is visible if there are any open spots on it.
After the "buried" algorithm has been applied to all the cubes, we basically are only painting the outer blocks. We'd also paint the walls of any caves or holes. The vast majority of the blocks are just invisible though, and we don't waste time on them. See Figure 8 for a view from below ground. All that interior space is no longer drawn.
If asking for the neighbor of each face of each cube is too slow (and it is), we could keep a set of six flags on each cube. These flags indicate whether a face is exposed or not. As we add or delete cubes to the world, we would update all the 6 neighbors of the changed cube, setting the flags to exposed or not. We would also set the flags of the new cube, based on which neighbors it has. With these flags, we can quickly decide which faces to draw as we draw the entire tree.
This is enough to go on for our first demo. Before we spend more time rendering a nice landscape, we need some more framework, which I'll cover in the next parts.
Add your comments via Disqus below. I will only moderate these when I get around to it, so hopefully, it will stay polite.
Update: One of the commenters, Florian Bösch, has his own writeup of the problem of rendering a block world, here. It's above the heads of anyone not deeply into graphics programming (including me!) but take a look at the video. I'm humbled!
If you want to try the program so far, download The Part 1 Demo. It has been tested on Windows 7, 32-bit and 64-bit. It will probably run under Vista or XP as well (my older programs did without problems.) We're not doing anything ambitious with the graphics here, so if you can run any 3D game, you should be able to run this. As for UI, this is all it does:
The Source Code
I've split this between a framework that does all the graphics code (the usual DirectX pile of goop) and the application code. Download The Part 1 Source for the C++ code, a roadmap to the source, and a build directory. This includes the executable demo and the files it needs. If you download this, you don't need to also download the demo zip above.
If you want to compile the code, the project is built with Microsoft Visual C++ 2010 Express. You will also need the DirectX Software Development Kit. It's possible you'll need the Windows 7 Software Development Kit too. These are all free from Microsoft.
Unfortunately, all three of these downloads are huge. Hopefully, if you are interested in game development, you already have them or an equivalent development environment. If not, I hope you have a fast internet connection! Download and install them in that order - Visual C++, then the DirectX SDK, then the Windows SDK.
blog comments powered by Disqus