Computer graphics: Cast your rays

I'd be willing to bet money that you've played (or at least seen) some sort of generic dungeon-crawler game with high walls, repetitive textures, and a very basic 3D engine.

Looking at you, Dungeon Master

These games tend to end up with a cult following, but people generally aren't too impressed with the game itself; in a world where true 3D immersion is just baby steps away, blocky pseudo-3D dungeons aren't that cool. Not anymore, anyway. Go back about twenty years, though, and this was pretty high-level stuff. 

Remember the Wolfenstein games? You, the blocky hero, have to sneak through and out of a castle (or bunker), shoot Nazis, and save the day. The first two games, Castle Wolfenstein and Beyond Castle Wolfenstein, looked like this: 

I wasn't kidding when I said you were blocky

Then suddenly, in 1991, Wolfenstein 3D (the grandfather of 3D shooters) came out looking like this: 

Such depth!

It feels a whole lot like 3D (albeit unrealistic 3D), but it still ran on a 2D platform. All semblance of 3D in Wolfenstein 3D was faked using a technique called ray casting. Ray casting divides the map into a grid. Each entry on the grid can either be "wall" or "not wall." Then, for every vertical line in the player's field of vision, a ray is sent from the player out through that line until it hits a wall. 

Rays extend from the player (the green dot) to the wall (the blue squares)

The distance from the player to that wall is calculated, determining the displayed height of the wall (far-away things look little, etc.). This principle also applies to enemies -- the longer the ray from you to Herr Nazi, the smaller his sprite is scaled. There are a ton of subtleties to this (how do you determine how often to check for a ray-wall intersection? what about field of vision?) and lodev has a very detailed and clearly-written introduction to ray casting page here that can clear up some uncertainty (that's also where I got my grid image). 

With ray casting, faking 3D on a 2D platform became easy: the implementation is straightforward and the calculations were so easy that real-time ray casting could be done on a 286. Unfortunately, giantbomb.com is a buzzkill and pointed out all the things you can't do with ray casting: 

• Walls can be of only one height
• All cells are of the same width and height
• Walls must be one color per face
• The camera is unable to rotate on the x-axis (look up or down)
• There can be no cells above cells (e.g. the first and second floor of a building)
• Walls must be either perfectly horizontal or perfectly vertical

Those dungeon games are making sense now, right? Walls of one height? Check. One color? Grey goes with everything. Can't look up or down? Don't need to in a dungeon; it'll just be ceiling and floor. Perfectly vertical walls? No reason to make your dungeon fancier than that. 

If you're thinking of making a simple game, dungeon crawler or otherwise, ray casting is a good technique to know. It's a simple implementation, so you can spend more time thinking about a plot that doesn't suck. You can use the info at lodev to get started, or there are video tutorials from Unity3DStudent and Ravi Ramamoorthi (check that one out just for his voice).

Or if you're really lazy, I think The Raycasting Game Maker does most of the work for you.