Home       About Me       Contact       Downloads       Part 1    Part 3   

Part 2: Going Places

November 29, 2010

I have to say that if you are launching something new on the net, there's nothing like a link from a high-traffic blog. Since Shamus Young linked me from his TwentySided blog last Friday, I've had 10,772 views of the writeup, 427 downloads of the demo, and 267 downloads of the source. Much better than I expected. Thank you, Shamus!

Those counts don't include the first few hours. I had originally purchased a VPS (Virtual Private Server) from Hazenet.co.uk for $14/mo. You get a virtual Linux box of your own to manage. I wanted this to run the server for my little world, once I get around to writing one. In the meantime, I figured I would just run Apache on it and let it serve the web pages too. Unfortunately, it got too much traffic and just fell over. When I noticed the comment about it crashing on Shamus's site, I tried it myself and it was very slow. So late Friday I switched the web pages to Hosting Matters, where I've had other sites.

Hopefully, the VPS will still be adequate to run some kind of server. I can get a real dedicated machine from Hosting Matters, but prices start at $140/mo, so I'm not in a hurry to switch. We'll see if this turns out to be a big deal.

Note that I've also added an RSS feed. It's here.


A commenter asked how much time has been spent on this. That's a hard question to answer because some of the code is old. The last time I took a stab at this was in 2008. There was a previous larger attempt at it in 2005. I scavenged through all that code to put together the framework used in this demo. In the source code, the Framework, Util and ImageUtil directories are all old code, although the Framework directory is a cleaned-up and simplified version of the old stuff. The directory TheGame is mostly new code.

I have a "timecard" program that I use to track how I spend my day. I know this seems rather OCD, but it's actually due to health reasons. I have medical stuff I'm supposed to do every few hours, and I constantly forget. So I wrote a program to nag me about it. Once I had that, it was natural to extend it and keep track of everything I do in a day, and show bar charts and long-term trends. OK, that is kind of OCD...

Over the last couple of weeks, I spent about 50 hours putting together the code for Part 1. Perhaps 20 hours of that was spent rummaging through my old code, trying to remember how DirectX worked, and simplifying the framework for general release. The new code, including the Octree, the visibility tests to find the buried cubes, and the rendering optimizations, probably took 30 hours or so. In addition, I spent around 9 hours doing the writeup. That includes writing the text, creating the figures, setting up the site and testing it all.

The result is 9,448 lines of code. That's just counting the lines (not statements) of C++ code, and not counting .h files. Those files tend to just duplicate the method declarations. Of that total, 1,804 are new lines of code in TheGame, 3,319 lines in Framework, and the rest misc. utilities I use for my projects. So this is not a large program.

For the non-programmer, I suppose you could divide these line counts by 50 to get page counts, but C++ source code is typically lots of short lines. If you divide the character counts by 2000, you get about 20 pages for the new source code written for Part 1, and 50 pages for the old framework.

The Plan

Fig 1: Our graphics so far
graphics so far

In Part 1, I may have created two misleading impressions. First, you might have thought that I was an experienced game programmer showing you the best way to implement a simple block world. Far from it! I have a lot of systems programming experience, but my 3d graphics experience is pretty much limited to what you've already seen. And my game programming experience consists of personal projects done over 30 years ago. On this project, I'll be learning as I go.

Second, you might have thought I just wanted to create a Minecraft ripoff with some minor variations. This is also not true. As it says on the home page, I want to create a "peer to peer virtual world that supports a real programming environment." I picked the cube world to implement as a first pass because it's easy, and because Minecraft is so popular. It's also the simplest user-modifiable world I can think of. Once you can add and delete blocks, you can build all kinds of things. The minimum amount of code to do that with any other sort of world (like Second Life) would be huge.

My plan is to quickly knock together the basic components of a shared world, with this cube landscape, some kind of avatars, and a simple server. Then I'll go back and revise and extend all the elements, probably many times. I don't expect this to be a short project. I'll try to maintain a balance between doing lots of infrastructure and making the demo steadily more interesting. I hope at least a few of you will follow along, try the demos, and add your comments.


At the end of the Part 1, you were a disembodied eye floating in space, only able to appreciate the magnificent landscape of cubes... Now, it's time to explore. You need the ability to move.

In a really good A-list game, I guess we'd model the arms and legs of the avatar, and we'd attach it all to a physics engine. That way, we'd know precisely where on your body you've been shot. And when a grenade went off near you, we'd throw your body on a nice trajectory, head over heels, into a wall, and your body would convincingly crumple up.

In my simple world, the avatar is a stick figure and always points straight up, so we're not doing any of that. Instead, we just have motion keys to control your position. We start timing when you press a key. At each refresh cycle, we get the duration since the key was pressed (or the last refresh cycle) and multiply this by the motion vector for that direction. So if you are moving forwards along X -- vector (1, 0, 0) -- for 16.6 milliseconds (the time for a 60hz display to refresh) at speed of 5 units per second, we add in a vector (1,0,0)*5*16.6/1000 = (0.083, 0, 0). We do this for all of the motion keys pressed at the time. Add all the motion vectors to the old position and we have a new position.

Amusingly, I had a really nasty bug in this years ago when I first implemented a 3d game. I was using the Windows GetTickCount function as a timer. Unbeknownst to me, the resolution of that timer is only 15 milliseconds. My display was running at 72hz, which is 13.8 milliseconds per refresh. The movement worked, but was a bit rough. It looked exactly as if I wasn't always rendering a frame in time. I spent hours trying to figure out how I could drop a frame, when the problem was the timer. Every now and then, I would get two frames between ticks of the timer, making it look like a frame was dropped (because the avatar position had not changed). In this demo, I'm using the Windows high-resolution performance timer, which has a 0.1 millisecond resolution.

Fig 2: A hop
We do need gravity, so that you can fall off of things. We implement that with a momentum vector, which is applied along with the movement vectors at each screen refresh. We get gravity by adding a bit of downward momentum on each refresh. Hitting the space key, which causes you to jump, is implemented by just adding some vertical momentum. This throws you into the air, and the motion keys let you move forwards. Then gravity pulls you down to the top of the higher cube, giving a nice little hop up (Figure 2).

To finish off movement, we just need to detect collisions with blocks in the world. With the Octree storing all my cubes, I figured that would be simple enough. Just take the bounding box around the old and new positions of the avatar, and check all the cubes that touch that box. If any cube in that volume is not air, the avatar has hit something solid. Since it's moving such a short distance on each refresh, I figured I would just reject the move, and that would be that. It turns out, it's not so simple.

First, rejecting a move when you hit something makes the world very sticky. You brush up against something and immediately stop. I wanted the sliding behavior that you get with most games now. Researching how that's done, I realized I needed the plane you collided with and the intersection point.

Second, when I added gravity, it seemed the avatar was stuck immediately when it hit the ground. I thought this must be some weird bug and was stumped for a minute. What could possibly keep it from moving when the code is so simple? Turns out, the gravity vector is always trying to pull the avatar through the floor. Since the rule was "if you hit a block, stop", it couldn't move anywhere.

So it turns out I need some real collision detection after all. What a nuisance! There are entire books written on this topic!

Collision detection

I'm not sure how accurately an A-list game these days model the avatars and other moving objects. Playing with Half-Life 2, Episode One, in the "Direct Intervention" chapter, I can throw the dead guards around with the gravity gun and see how well it's done.

The guard body (called a "ragdoll" in tutorials I've read) isn't checked against itself much. You can get his arm to stick through his guts, or get his legs twisted up pretty easily. But they do check against the console in the room, and the game engine does a really good job of collision detection. Although it's pretty easy to get a situation where the guard is floating a couple of inches above the console, it's hard to get the game to do what you see in Figure 3 -- put his arm right through the console. I wonder what kind of algorithm they are using that can be so good 99% of the time, but still let this kind of gross error happen.

Fig 3: A bug! In an A-list game!
Half Life 2 sample

In World of Warcraft on the other hand, it looks like the avatar is checked against a simple bounding shape and it's easy to get an avatar to stick its hand in a wall or stand in a plant. See Figure 4. Of course, keeping you away from plants would make it pretty hard to move in parts of the world!

Fig 4: What post? What plant?
World of Warcraft Sample

Fig 5: A sphere moving through triangles
sphere moving through triangles
After a bit of Googling, I found a writeup of collision detection by Kasper Fauerby (PDF) that didn't look hard to implement. It's got all the details, including the high school math, and sample code. What he does is wrap your moving object in an ellipsoid, then scale the coordinate space of the world so that this becomes a sphere with radius=1. The rest of the world is distorted, but this doesn't matter. He calculates the intersection points in the distorted world and then maps them back to the real world by inverting the scaling.

He then tests the sphere against all the triangles in the scene, as in Figure 5. His tests all return a distance along the movement vector until the sphere hits the triangle. He takes the closest hit, and uses that as the stopping point. With the hit point and the normal of the plane we hit, he can calculate the amount to slide (more on that below.)

Implementing this is easy, and would work when we get away from cubical landscapes. I started on it as shown in Figure 6. Unfortunately, you can't just intersect the moving sphere with the cube faces. You could get a situation like Figure 7, where the leading edge of the sphere (the bottommost point) does not touch any cube faces, but the body of the sphere does. So you need to test against the edges of the cubes as well. That would stop the sphere in midair as shown in Figure 8.

Fig 6: A sphere touching a cube face
sphere touching a cube face
Fig 7: A sphere missing the edges
sphere missing the edges
Fig 8: A sphere touching an edge
sphere touching an edge

Then I realized this is kind of pointless in my current world. If I had a blocky Minecraft-style avatar, the ellipsoid as a bounding shape isn't very good. The feet are going to stick out at the bottom along the sides. So here I am writing code to stop a falling sphere on the edge of a cube, and it's going to look stupid with a real avatar. It will stop in midair, part way down the side of the cube. Its feet will stick into the side of the cube. In block world terms, this is all wrong. It should be either standing on the top edge of the block, or fall to the next block.

So back to the world of blocks. We create a bounding box around the avatar, and using the same logic as with the sphere, find the first point along the movement path that hits a cube. See Figure 9. As before, face edges are still a problem. In Figure 10, the path still hits the cube, even though the block center point is beyond the edge of the cube face when the block hits.

Fig 9: Find the first cube we hit
find the first cube we hit
Fig 10: Watch those corners!
watch those corners

If you implement anything like this, there's one subtle point that's really essential. When we test the movement ray against a plane, we will frequently have the case that the origin point is imbedded in the plane, making the distance zero. This is because we stop at the plane when we hit it, and move along it when we slide. If we just use distance, we don't know if we're moving into or out of the plane. So in addition, we have to test if the plane is facing the same direction as the ray. If it is, then we are coming out of that plane, and don't test it for intersection.

If you skip this test, you can get all kinds of strange behavior, such as the avatar getting stuck in walls, or suddenly hitting the vertical planes of the cubes in the floor. I had it in my mind that this was just an optimization, and that I could cut down on the number of planes checked by using the visibility flags I put on all the cubes in Part 1. However, this isn't enough. Only by eliminating planes facing away from the movement ray can you avoid these spurious intersections.

In general, you have a problem with floating-point precision. If for any reason, the avatar strays to the opposite side of a wall (which has zero thickness, so this is easy), that wall will no longer be considered in the way of movement. Your avatar will break through the wall and continue on to the next obstacle. If this "wall" is actually the floor, it can drop through the bottom of the world. I've seen this in production games (such as World of Warcraft), so it's definitely something that you should pay attention to.

Sliding along a wall

Sliding along a wall when you hit it seems (to me, anyway) like it should be hard. In fact, it's easy. In Figure 11, we start at point A, travelling to point B. Along the way, we hit a wall and the final position from the collision detection is H. To slide, we simply take the vector from H to B (the part we wanted, but did not get), and project it back onto the plane of the wall we hit. The plane is represented by the hit point and the normal N. In the calculations, you won't even need the hit point. Just multiply the distance you still wanted to go by the wall normal, and subtract that from the target point B. That gets you the point S, which is your position after you slide.

It's important to note that the move from H to S is a new move for the avatar, and has to be checked with collision detection all over again. For example, in Figure 11, you are moving into a corner on a diagonal from A to B. The first hit is at H, and the projected sliding position takes you to S1. The second move, from H to S1 results in another hit and slide to S2. So collision detection continues until you've stopped hitting things.

A nice thing about this algorithm for sliding is that if you hit a wall at 90 degrees, you don't slide at all. In figure 13, you can see the same calculations on a 90 degree hit. The sliding calculation projects the H to B distance onto the wall, but that projection is right back where we hit, since the projection vector is at right angles to the plane. This is useful when gravity is pinning the avatar to the floor. We don't want to slide in that case.

Fig 11: Sliding along a wall
sliding along a wall
Fig 12: Hitting a corner
hitting a corner
Fig 13: A direct hit produces no slide
direct hit produces no slide

The Camera

Games have at least two modes for handling the mouse. In "shooter" mode, also used by Minecraft, moving the mouse turns the head. Press the forward key ("w") and you move in the direction you are looking. In "MMO" mode, such as in World of Warcraft, the screen has the usual desktop cursor. You can interact with tools and buttons and menus on the screen. To turn your head, you press and drag the mouse.

The world view is rendered from your "eye" or "camera" position. This is also different in the two modes. In shooter mode, the camera is in the center of your head. In MMO mode, it's usually above and behind your avatar. That can cause problems. Move the camera around and you could hit a wall or the floor. Not only would this render badly (see Figure 14), it could block your view of yourself or your opponents. To fix this, we also have to do some collision detection. Since we are just trying to see, not trying to move, it's enough to check if there are any blocks along the ray from the head to the camera. If so, we pull the camera distance in (temporarily) to the first collision point.

Fig 14: The camera shouldn't be inside a wall
camera shouldn't be inside a wall

This is kind of annoying, since it means that if you back up against a wall, the camera position will get closer and closer to your head. But since the alternative is to have your view blocked by the wall, we don't have much choice.

In the demo, you can hit F3 to switch between shooter mode and MMO mode. In "shooter" mode, you'll have a cross cursor. When you are in MMO mode, your avatar will appear and you'll have an arrow cursor. You can see your face by using press-and drag of the mouse to rotate the view around your head. All the movement keys are the same in shooter or MMO mode.

Finally, you'll notice a block border on nearby blocks that you look at. That's for when we add and remove blocks. In the next part...

The Demo

The new demo is at The Part 2 Demo. It has been tested on Windows 7, 32-bit and 64-bit, and Windows XP, 32-bit. 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. If you get an error message about needing "d3dx9_42.dll", you need to update your DirectX version. Go to Microsoft DirectX Update for a page that does that.

In the Part 2 user interface, we now have many more functions:

  • 'W' and up arrow - move forwards.
  • 'S' and down arrow - move backwards.
  • 'A' - move left.
  • 'D' - move right.
  • space - jump when walking
  • left arrow - turn left.
  • right arrow - turn right.
  • space and Page Up key - move up when flying.
  • 'X' and Page Down key - move down when flying.

  • Home key - toggle flying mode.
  • F1 - write statistics to the error log.
  • F2 - take a screen shot.
  • F3 - toggle "shooter" vs. "MMO" mode.

  • Hit Alt-Enter to toggle between windowed and full-screen mode.
  • Hit ESC to end the program.

In "shooter" mode (cross cursor), move the mouse to turn the head. There are no other mouse functions.

In "MMO" mode (arrow cursor), moving the mouse just moves the cursor. You can resize the window if you like. Drag the mouse to turn the head. Press both mouse buttons together to walk or fly in the direction of the cursor. Movement keys still work in MMO mode.

You will start in shooter mode, placed midair above the landscape, and in flying mode. Swoop around a bit, then hit "Home" to stop flying and start falling. Hit "F3" to see your avatar.

Note to programmers: The F1 key writes the graphics timing to the errors.txt log file. However, the version I'm releasing uses the "default presentation interval" in DirectX, which means you won't get more than 60 frames per second out of it (or whatever your display supprts). To get real times, find and uncomment #define GRAPHICS_TIMING in the file Framework/DXFramework.cpp That will switch to "immediate presentation interval" which should write graphics without waiting for the screen refresh.

The Source Code

Download The Part 2 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.


As of Part 2, here are the totals:

  Full Project   New for Part 2
TheGame lines 3,808 2,004
Framework lines   3,446 127
Utilities lines 4,325 0
Total 11,579 2,131

Coding hours 84.5 34.7
Writeup hours 18.6 9.45

Home       About Me       Contact       Downloads       Part 1    Part 3   

blog comments powered by Disqus