The Technology Behind ID's Games

orac2 writes: "The current issue of IEEE Spectrum has an article on the groundbreaking technology behind iD Software's games, from the days of Commander Keen through to Return to Castle Wolfenstein. Graphics technologies covered include the original 2-D buffer trick that made side-scrolling games on the PC feasible, as well as the more modern Raycasting and Binary Space Partition Tree techniques. Carmack is quoted extensively."

Comments

Quake I / II

[Shamanin]

I read this in the IEEE spectrum. They kept mixing up the advances in Quake I with Quake II. They even refer to a picture of Quake II as Quake I. But, there was some interesting history nonetheless.

Excellent diagrams

[jukal]

This one is particularly good: about binary space partition tree.

Re:Excellent diagrams

[jtdubs]

Binary space partitioning trees proper have fallen out of use in games.

All BSP-based games now-a-days use Solid Leaf BSP trees, which are a variation of the original and have many more useful properties for games.

It is these trees and the sectors that they create that are used for determining portals.

If two sectors have the same portal then those two portals connect and can see eachother. If a portal has no pair, then it is a portal out in to infinite space and is hence a leak in your map. Assuming, of course, a map based on a single BSP tree.

Once you have portals, PVS generation is easy. And there you go, BSP and PVS.

A lot of modern research is shying away from BSP and PVS. They limit you to indoor spaces. Entirely different technology is required for outdoor scenes. And then special hacks and logic are needed to allow for seamless transitions between the indoor and outdoor worlds.

Some think that octrees with a form of occlusion culling might very well be better as they can represent both indoor and outdoor geometry without making any distinction between them. They are much harder to cull though as no handy PVS information is present and only more difficult methods exist such as Z-pyramids.

Others stick with BSP and PVS and use the one-sided portals that would normally represent leaks but instead in this case represent windows from the BSP into the terrain, and vice-versa. This combined with some extra lighting and shodow-volume information and you can have your lighting and transitioning between indoor and outdoor be seemless.

Anyway, just the ranting of a bored man at work.

Justin Dubs

Re:Excellent diagrams

[Buzz_Litebeer]

The problem is, is that BSP tree's cut a scene up into things that need to be rendered so only what a person can "see" is rendered.

take for example, if you were looking at a house from the outside, and all the windows were tinted dark, for all intents and purposes there is nothing in the house right?

This is because you cannot "see" anything inside of the house. Now lets take this a bit further, imagine you were looking down a hallway, and if you went to the end, turned right, then went forward, then turned right again, you would see something else, but before you went forward, and turned around the corner, you do not nececerrilly have to "see" whats around the corner, because essensially it does not exist.

this is what a BSP tree, and other pruning methods do, a bsp tree trys to break up a map or set of vertices in a way that allows the software to render only what you can see, and what you are about to see, this makes it so that the computer doesnt have to render a lot of extraneous stuff.

back to the house example, lets say you were rendering a house, and you defined every single possible item in the house as well (ie you could go into the house and look around), but you could see no objects from outside the house (imagine the house is a little box) so a BSP tree algorithm would take the scene, and if you were in some position outside of the house, it would not load all the vertices of the internal components of the house, but just load the vertices for the outside of the house and render them, so that the computer would not have to draw all the items in the house, items that you do not have to see. The smarter algorithms used in quake games for small rooms and small inside areas, will also load and draw things you could see "soon" ie, if you were walking down the hall, it would also render the next section of hall that you are coming up on when you got close to the hall. when you turned down the hall, and moved sufficiently far, or turned another corner, it would then remove those vertices from being rendered until you came back around again.

Now to why this causes problems for large outdoor scenes. this can be many reasons, many times if an outdoor scene is complex (ie has a lot of vertices) the game engine doesnt really have a lot of options on pruning what you see, and what you might see, so it causes slowdown because it draws EVERYTHING outside, regardless of if you can see it at the moment. if you have high render intensive items such as polygonal tree's it can truly slow the game down incredibly to render it, and causes other problems.

then open ended nature of outside areas, and having to draw skys can cause problems too. Its a pretty complicated subject, I hope someone can elaborate more, since I just got done (last semester) with a class that basically went over these concepts on inside spaces, I haven't full explored all the reasons for the problems of doing it outside, but thats what I am pretty sure of.

Buzz OUT.

Re:Excellent diagrams

[jtdubs]

No problem. This is a common question.

Here's the thing.

BSP trees work by breaking up the world into arbitrary convex hulls. This is good because you can render a convex hull that you are inside without worry about some of the triangles overlapping other ones.

In other words, take two cubes connected by a recangular hallway.

Theoretically the BSP tree could divide this into three sectors. One for each room, and one for the hallway. Each of these individual sectors is a convex hull.

So, if you are in the sector for a room you can just render that entire sector, without using a z-buffer or any kind of depth testing, and you don't have to worry about things overlapping. I mean, there is nowhere in a room where you can stand where the left wall and the floor will overlap.

See what I mean?

Now, while you are rendering the room you render it's portals. It has a portal connecting it to the hallway sector. So, you render the hallway's sector, clipped to the polygon that is the portal.

Then, while drawing the hallway you draw the sector connecting to the second room. So, you draw the second room, clipped to the portal leading from the hallway to that room, which is already clipped to the original portal.

So, we just drew the two rooms and the hallway, with no traingles overlapping.

This is exactly how the original portal-based renderers worked.

Now, why doesn't this work for outdoor scenes?

Imagine a large field with rolling hills. Now, try and find a convex hull. It's tough.

Imagine a hill shaped like a dome.

This dome forms a conCAVE hull. You can't break it down in to ANY convex hulls. So, every single triangle has to be part of it's own, unique, convex hull.

So, now every triangle in this hill is it's own sector. Our BSP tree is huge. And we have MILLIONS of portals connecting every triangle to the ones next to it.

This is HORRIBLY ineffient and slower than just brute force rendering.

So, to summarize. Indoor scenes tend to be easily decomposable into convex hulls. And hence work well with BSP trees and PVS. Outdoor scenes aren't. They tent to have a lot of concave areas.

So, hope that helps.

Justin Dubs

Truly impressive

[aengblom]

The truly breakthrough technology is that ID made it possible to spontaneously induce vomiting without noxious fumes! ;-)

ARRG (offtopic)
Editors please (as in pretty) fix this:

User types in comment and submits it (without subject). Is told to type in subject, but then is told "you have submitted to quickly." User loses comment because it is cleared from browser cache and slashdot doesn't put it in the error page.

( /offtopic )

Id didn't develop the Keen trick

[Junks Jerzey]

Good article, but the Commander Keen scrolling trick was old news by then. Lots of Apple II, Atari ST, and Amiga scrolling games did the same thing. Impressive? At the time, yes. But let's not get too carried away with giving Carmack credit for everything.

Re:Id didn't develop the Keen trick

[Anonymous Coward]

Umm.. The Amiga had a SuperBitMap mode where you could do smooth hardware scrolling without CPU, by having the copper(?) look at a memory range and a window to display with the ability to do transparancy. Although in this mode you were really limited in screen size and color pallets.
For those colorful games, you did need to pull tricks like this, but to match an EGA or CGA color list, you could use the copper to take care of it for you.

As far as I am concerned, Doom killed the Amiga.

Amiga???

[Anonymous Coward]

The Amiga, not the PC, pioneered almost all 2D neatness - even today, some features of the Amiga HW are unavailable on standard PC cards - particularly Amigaish smooth-scrolling. Most PC card 2D scrolling STILL sucks compared to Amiga scrolling... Why? I don't know. My theory is that while the Amiga scrolled by changing the pointers to where the screen was in memory, the PC dumb-copies entire screens. Amiga: economic 60Hz multidir in 1985. PC: brute-force 70Hz multidir in 1993. Wow.

Talk about NIH and wheel-reinvention...

Re:Amiga???

[mindriot]

My theory is that while the Amiga scrolled by changing the pointers to where the screen was in memory, the PC dumb-copies entire screens.

Well, that's what Id avoided on PC... (did you rtfa? :)) When EGA cards came up, they had enough graphic memory and functionality to change pointers... back then I tried this a little on VGA (320x200 tweaked mode giving four screens, and changing a pointer to scroll/switch screens for double-buffering).

The Amiga did of course have much better graphics hardware, including a blitter for fast graphics data transfer and accelerated drawing functions, (at that time) lots of video memory, and further hardware acceleration such as sprites support. And, also, support for bitplanar graphics modes, easing smooth scrolling.

book covering a few of those techniques

[r2r2]

you can read more about bsp trees and other graphics tricks on this wonderful online book written my Michael Abrash, an id software programmer: http://gpbb.dk.eu.org:81/
make sure you check the forewords by john carmack

Re:Commander Keen! w00t

[Baikala]

This part of the article is wrong.
That's not Commander Keen it's Dangerous Dave, and that's not Quake it's Quake II.

I know, I've played them all!

Lack of historical perspective...

[RatBastard]

*SIGH*.

Yes, the Amiga had smooth scrolling before anyone thought to do it on the PC. It took Carmack to do it simply because he was the first to do it. It wasn't all that hard, but someone had to do it first on the PC.

The important point that many people seem to be missing is the historical aspects of teh IBM PC. While the Amiga was developed with games and multimedia (and developed after the PC, I might add), the IBM PC was designed first as a smart 3270 terminal with the ability to run local programs, and then later slightly retooled to be a "business copmputer". The original PC came with a text-only dsiplay adapter and no ability to play anything but the most primitive of sounds. This was all done very much on purpose. IBM did not want the PC to be persieved as a game box, a toy. They wanted it to be seen as a work machine, an office computer to get work done on.

IBM didn't even develope the first graphics adapter for the PC, that was a small company called Hercules. Only after the runaway success of the Hercules card did IBM bother to develope the (weak and craptastic) CGA desplay.

IBM didn't put sound or music into the PC, either. That was done by Adlib, Creative Labs and Advanced Gravis.

Also of importance is the fact that the Amiga; the Atari ST, 400, 800, etc; the C64, Apple 2, etc... is that these system all shipped with fixed graphics adapters: an Amiga programmer knew that he had a display of XxY pixels and 4096 colors to play with, or the C64 programmer knew what his display was able to doi. In the PC wordld you had MDA, CGA, EGA, and VGA. Each generation of adapter brough new abilities to the PC and programmers had to decide which minimum technology level they were going to require.

So Carmak was the first to do smooth side scrolling on the PC? Someone had to be first. If nor John Carmack, it could have been Roberta Williams.

Say it with me now...!

[aztektum]

It's *id* Software. Not ID. Not iD. id. as in the psychology term.

id
Pronunciation: 'id
Function: noun
Etymology: New Latin, from Latin, it
Date: 1924
: one of the three divisions of the psyche in psychoanalytic theory that is completely unconscious and is the source of psychic energy derived from instinctual needs and drives.

Re:Softdisk

[John Carmack]

Here is an interesting bit of history:

Greed was built on the engine I wrote for Raven/Origin's Shadowcaster game, while the other Id guys were working on Spear of Destiny, the commercial Wolfenstein game.

The reason softdisk got the technology was that they were still making lots of noise about suing us for doing Keen while we were working at softdisk. Our original parting deal was that we were going to continue doing the Gamer's Edge games for a while, basically for free, as penance. We weren't savvy enough to get anything binding down on paper, so even when it was all wrapped up, there was room for twisting our arm a bit. (another trivia bit -- George Broussard at Apogee arranged to have Apogee produce one of the Gamer's Edge titles for us, so we could focus more on Wolfenstein).

We finally arranged a technology transfer of the latest engine code for free and clear severing of our ties. After they showed that just having the technology was not a guarantee of success, they had the nerve to come back and ask for more, but by then we were able to just tell them to go away.

BTW, Duke Nukem does not have a Softdisk heritage, it was by Todd Replogle (sp?), who was strictly Apogee-grown.

John Carmack

Softdisk v. Id

[Sean Clifford]

Unsubstantiated company rumor on the Duke thing, I guess. :)

I remember Al talking about the lawsuit and the source code. One poker night (which I played badly) Dan Tobias went on a long rant (suprise) about the whole ordeal. I share his opinion that moonlight code belonged to the programmer, not the company.

Absolutely nothing came of the source code. It sat in Jim's office unused.

Originality, creativity, etc

[John Carmack]

I was fairly pleased with how that article turned out - when I first heard about it, I dreaded seeing a trivialized simplification of the issues, but it turned out as representative as you can be in that space.

However, I really dislike discussions of the attribution of techniques to a particular programmer. Everything is derived from things before it, and I make no claims of originality. I would say that one of my talents is the ability to be aware of what sources are feeding into my work, and be able to backtrack to them. Also, there are always lots of other possible answers for any given problem that can be made to work. BSP vs sector list, Portals vs PVS vs scan line occlusion, tilted constant Z rasterization vs block subdivision vs background divides, etc. Looked at in the proper perspective, individual techniques just aren't all that important. Sometimes it sounds like "Dude, he INVENTED needle nose pliers!!!"

Heck, I somewhat deride the very concept of originality. Creativity is just synthesis without the introspection. Lots of people will catch on that and start a rant about how Id games aren't original, but they are missing the point - it is possible to set out and develop something that will be received as "original" without ever having an "original" idea spring into your mind.

The best way to get answers is to just keep working the problem, recognizing when you are stalled, and directing the search pattern. Many of the popular notions of innovation and creativity are in some ways cop-outs that keep people from being as effective as they could be. The little document I wrote about developing a part of the shadow algorithm for Doom that Nvidia has on their website was a pretty good example of my process. Don't just wait for The Right Thing to strike you - try everything you think might even be in the right direction, so you can collect clues about the nature of the problem.

John Carmack

Thousands of ZX spectrum games

[pommiekiwifruit]

prove you wrong there.

I have just been learning Z80 this last week, and damn it's a cool processor! And still for sale...