Slashdot Mirror
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."
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 )
(
So close and yet so far from the world's perfect ID number
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
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
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