Do you remember that game from the 90s, where you’d massacre a-hole Nazis in an attempt to escape a castle, and for some reason all the walls were the same height, and everyone was always looking directly at you? Yeah, I’m talking about Castle Wolfenstein 3-D, one of the earliest “3-D” games for MS-DOS, ported to a variety of other platforms. Why do I say “3-D” in quotes, you ask? Technically, it wasn’t 100% 3-D. Although everything was drawn in a way that looked 3-D, it was all represented as a 2-D grid. That’s why you never found anything above anything else and you couldn’t look up or down. This is generally referred to as pseudo-3-D or “2.5-D” technology. It wasn’t until Quake that true 3-D came to the first-person-shooter genre.
Have you ever wondered how they got Wolfenstein to render so quickly on such old computers? It was pretty simple, actually: they used a technique called “raycasting.”
First, think of the game as a 2-D grid, where each cell represents an optional cube, where each side is a wall. Now place a player in one of the empty cells, looking in some random direction. The question is, which walls are on screen and at what angle and distance should they be rendered? Wolfenstein’s process went a little something like this:
For each column on the screen…
- Generate an angle to project a ray towards. At the center of the screen, the ray should project perpendicular to the player. It should lean more towards the left the more left the column is and towards right the more right the column is.
- Project the ray until it hits the side of a cell. Repeat this until the cell has a cube in it.
- Calculate which column of the cube’s wall was hit, calculate its distance and render it to the screen at the current screen column with the appropriate stretching.
- Remember the distance of the wall rendered at that column of the screen in a so-called “z-buffer.”
Next, the sprites are rendered:
- Sort all of the sprites in order of distance.
- For each column of each sprite in closet-to-furthest order…
- Determine which point on the screen the sprite’s column would be drawn to.
- Ensure that the column actually exists on the screen (i.e. if it’s too far to the left or right).
- Ensure that the sprite column is not behind a wall via the z-buffer.
- If the previous two conditions are false, then draw the line with appropriate stretching.
Special thanks to Lode Vandevenne for his excellent tutorial on the subject. If you want to see exactly how to implement this technique yourself, his tutorial is a powerful resource.
So, this is all well and good, and I made my own Wolfenstein-style game engine this way. I had one problem with it though: it was a software renderer. Software renderers are inefficient and, by today’s video game standards, almost deprecated. So, I wanted to figure out how to bring this to OpenGL.
Thanks to id Software, who was nice enough to release the source code for the original Wolf3D along with their iPhone port, I discovered a cool way to do this. After a few minutes examining the iPhone port, I discovered that they continued to use a raycaster, but instead of rendering each wall as it was hit and drawing the sprites later, they kept a secondary grid that stated which cells were visible.
At the beginning of the process, every cell was marked as invisible. Then, whenever the raycaster passed over or collided with a cell, that cell was marked as visible. Afterwards, they would just go through each wall and sprite and render them if they were in one of these visible cells. They didn’t have to worry about what was in front of what because OpenGL automatically takes care of z-buffering.
Not only does this use hardware-accelerated graphics, but it also means that you don’t have to go through the rendering process for every single sprite in the game! If the sprite is not in a visible cell, it can be ignored completely. In the old algorithm, even if it was completely hidden by a wall you would have still had to check per-column.
I’ve begun the process of implementing this technique. For the software-rendered version I had used the Simple DirectMedia Layer, but for this I’m using Allegro 5.x. I’m using a modified version of the raycaster I built from Vandevenne’s tutorial, and it’s going pretty well. So far, I’ve managed to get a 2-D map to represent the visibility grid by highlighting cells that the raycaster hit. From what I can tell, it’s showing everything that can be seen and nothing else, exactly as it should. Here’s a video of me playing with it:
This game engine will become the basis of a retro, Wolfenstein-style video game I’m working on, code name CANINE (all-caps for awesomeness). Keep checking the blog or subscribe if you want to see how it goes. I’ll be posting about my progress and all of the cool little programming tricks I’m using on the way.