Walls II

Allow me to elaborate...

A square room (top down view)

Ok so this is a square room. It consists of four lines (walls). So in-game, we draw four quads (one is behind the camera so we can't see it):

Square room in Gloom: three walls are visible

Alright. So let's say we have two connected rooms:

Two rooms!

What we do now is we connect the rooms by cutting a hole in the far wall, based on the difference in ceiling- and floor heights between the two rooms.

Back wall now has an opening in it to connect the rooms

The interesting thing is that these two are the only possibilities: a wall, or a wall with a hole in the middle. Yet you can build very complex and interesting architectures using this system. Just look at the maps in Doom!

Walls

Here's what that previous scene looks like with walls (and a gun sprite) added in:



Almost like a 15 year old FPS! :)

Like I said, walls are pretty easy to make. A Doom level is basically a top down line-drawing, where each line is a wall. So to generate the walls you just create squares from floor to ceiling at each line. If the line divides two rooms then you punch a hole in it (like the little window in the video).

PS: Apparently Gloom is already a game, and it's a Doom clone as well. So I need a new name. Maybe "Mood"?

Triangulation

This could be a room in Doom!

Hit the first snag already. While the walls in Doom are ridiculously easy to create - they're just quads - the floors and ceilings of rooms can have many bizarre and arbitrary shapes.

I'm not sure how Doom rendered its floors and ceilings. If you forget a wall the ceiling kind of "spills" out. My guess is they use some scanline tricks.

Anyway, I'm not working on that low a level. All I do is send triangles to the GPU and let it do its magic. So that means I need to triangulate my floors. Which, apparently, is super difficult.

... Chazelle (1991) showed that an arbitrary simple polygon can be triangulated in O(n). However, according to Skiena (1997), "this algorithm is quite hopeless to implement."

Quite hopeless indeed!

So I started at the top of the chain with the hopeless algorithm and then moved my way down to less and less efficient ways until I hit the bottom with the "ear pruning" technique. It basically boils down to "pick a random corner and see if you can cut it off, otherwise pick a new one." One of the online powerpoint presentations I found mockingly called it the "naive solution" before failing to properly explain another method involving trapezoids. :/

Stuff that though! At least it works, check this out:



Oh and one cool thing about the Doom engine: because the floors are all perfectly level it's super easy to map a texture on them!

Introduction

So. Doom.

Doom's a great game. Not only was it a breathtaking graphical achievement at its time, the gameplay and design of Doom still hold up to this very day. Simple, yet surprisingly deep, like a modern day Shakespeare.

Truly, Doom is the Citizen Kane of gaming.

So yeah, I'm a fan. Played it to death. Used to make my own WADs for it. Revisited it on Xbox recently.

Then one day I woke up and thought: I can make this game. And that's exactly what I plan to do.


So why Doom, specifically?

Because Doom is awesome. But also because Doom is a perfect fit for a single programmer hobby game. The game was designed to run on hardware from 20 years ago. To make it work, Carmack and co put a lot of smart simplifications into the game. Those same simplifications make the game a lot easier to code than modern first person shooters, while the current hardware allows me not to worry too much about optimizations.

For instance:

• Doom levels can be designed with a 2D top down view, no need to have a 3D editor or create exporters for Max/Maya.
• Walls are always perfectly upright. Floors are always perfectly level. This makes collision detection and physics super easy!
• Objects are sprites instead of 3D models. Sprites are way easier to find/make than animated models.
• Doom geometry is sparse when compared to modern 3D games. Modern GPU's can probably render an entire level without breaking a sweat, saving me the hassle of programming visibility culling.

This blog will catalogue my successes and failures. Although writing a blog about something is the best way to lose interest, let us hope that there will be plenty of both.

XNADoom teaser trailer