Why Doom is Awesome: Binary Space Partitioning
ฝัง
- เผยแพร่เมื่อ 8 พ.ค. 2024
- Edit: I'm aware now that Doom didn't use affine texture mapping. I'm also aware that many of the games following Doom used portal based rendering, while still having files with a .BSP format.
Join the Discord: / discord
An exploration into how Doom's graphics work and how Doom affected the gaming industry back in 1993.
Chapters:
0:00 Preliminary explanation
0:53 Intro
4:30 Wolfenstein
8:00 Doom
25:37 Addendum
#Doom #Doom1993 #DoomBSP
Sources:
Doom visualization tool: github.com/proteal/DOOM-Vis
Headless Doom: github.com/jwhitham/DOOM
Node Building Video: • Doom E1M1 Nodes Building
www.pcmag.com/news/the-comple...
fabiensanglard.net/doomIphone...
web.archive.org/web/2015042121...
R Schumacher & Air Force Human Resources Laboratory. Training Research Division 1969, Study for applying computer-generated images to visual simulation, Air Force Human Resources Laboratory, Air Force Systems Command, Brooks Air Force Base, Tex.
Fuchs, H, Kedem, ZM & Naylor, BF 1980, ‘On visible surface generation by a priori tree structures’, ACM SIGGRAPH Computer Graphics, vol. 14, no. 3, www.cs.unc.edu/~fuchs/publicat....
Special Thanks:
ID Software
CoD Black Ops: Cold War
The Doom Community - เกม
This video was a kind of research project for me, and I appreciate your kind comments. In response to a couple of comments and things I've read, I need to make a few statements:
- I apologise profusely for the use of texture filtering in Doom.
- I'm aware that explaining triangles and planes is kind of obvious.
- I described recursion as a process repeating itself until an end is reached. This phrasing might give the wrong impression to some viewers. In programming, a recursive function is a function which calls itself.
- When I say "Raycasting means you’re able to draw only the surfaces which are in the players field of view", a better way of phrasing this would be "Raycasting grants you the ability to draw only the surfaces which are visible to the player".
- To the general audience, a 'float' data type is precise, in that it allows you to store small decimal numbers. This can be misleading. In programming, a float is quite imprecise as opposed to, say, a double.
- Some of the details of the axe and door story may be hazy.
- Apparently green and pissed wasn't ever a working title for Doom. It was the name of a pre-Wolf 3D game.
- Doom did not use affine texture mapping.
- A lot of 3D games following Doom didn't use it's BSP system. They often used different methods like portal based rendering. They still, however, used a BSP data type. Why? I'm not sure. That's why I'm lead to believe they have some extant features from Dooms BSP system. Could be an avenue for further research(unless somebody else already knows?).
My only gripe was you said the floors can be angled, which was not true for Doom. I can't remember if it was Heretic or Hexen where they first had that. Maybe Duke Nukem?
It's not that a float is less precise than a double. It's that, by their nature, both are imprecise. They can very rarely represent the exact value needed. I vastly prefer to use integers or rational numbers because they're always exact. Unfortunately, it can be really complex and annoying to represent a precise rational number when a calculation becomes too complex. This is especially true when you aren't doing symbolic math and your numbers are inherently not rational, such as square roots or transcendentals like pi. And so you end up resorting to approximations like float (or more precise approximations like double).
Now, I'm not sure how to get this across in your video., but the thing that makes float and double especially hard to work with without dedicated hardware is that they also include a magnitude component. The precision of a float can only be calculated with reference to its magnitude. So, you don't get a precision of 0.1 units, for example, if you're working with a float that represents a number that's larger than 10 million or so (or smaller than -10 million). But, with a float representing a number close to 1, you can get 6 or 7 digits of precision after the decimal point.
These facts make float and double in general a pain to use for a lot of things, even though they're the only reasonable choice sometimes. And they're definitely very slow without dedicated hardware, especially when compared to integers.
Honestly, I think you did a fairly good job. As a programmer, I would've liked a more detailed description of exactly how a BSP tree worked. But, you gave a really good outline for the level of explanation your video aimed for. And it does give me more to go on when I research more thoroughly how to code a BSP tree. It was also enough of an explanation to get a feel for why a BSP tree might only be efficient for certain styles of map.
Thank you.
A BSP structure has portals from one part of the tree to another part, so it can be general enough to do the same as portal based rendering. A pure BSP tree will cut up a lot of polygons, so like dividing your rooms first on a visible portal basis like doors can make things faster.
Quake has 5 degrees of freedom, not 6. You have the three translational degrees of freedom plus pitch and yaw. No roll, though.
@@Omnifarious0 To add to that, floats are near identical to integers as far as data goes. They are both sums of powers of 2, but integers do not have negative exponents like floats do. What makes float imprecise is that most sums will never equal the desired decimal number. They get as close as possible by adding many smaller numbers, which is where the double comes in. With more bits to include additional smaller numbers the final sum can be more accurate.
When Doom was released, the thing that amazed me most was - you could "go outside" and it had its own background that "acted right".
I thought the splash damage on the rocket launcher was super cool and that demons tried to eat you! But even cooler was that baddies killed on top of stairs would fall down them. But my favorite new thing about Doom was the way the lesser enemies would get exploded into slop from a rocket or a barrel. Going outside was soo cool, though. Episode 1 of Doom was amazing--still is!
I remember those exact feels!
I remember the feeling that I had when experiencing what you're talking about, and that truly was amazing, but I think just the fact that this game could run on my 386 was what astonished me most. I didn't think something like that was possible. There was absolutely nothing like it. It's like it broke all the rules of what a computer could do.
Who is bro quoting tho ⁉️⁉️⁉️🗣️🗣️⁉️
Thank you John Carmak, your programming and door smashing abilities are appreciated to this day
Honestly one of the best programmers of our time.
You spell his name wrong
@@examname9477 eldritch horror anomaly god John Carmack doesn't mind his name mispronounciation as long as it's not slandering his might
@@SpringDavid trye
@@SpringDavid LOL is that a Civvie reference?
The coolest thing is that John Carmackreleased the source code to Id's games 5 years after they were released. He _wanted_ people to learn from them. The stuff he did was revolutionary, but he wanted other people to learn to do things he hadn't thought of yet because it advanced what was possible and made the games better and more fun. He was always truly in it for the state of the art.
Without John Carmack I would have never started learning graphics programming or 3D. I've ha the privilege of being able to say it to him directly a time or two, but I'll say it again: Thanks John. You have no idea what it meant for me to be able to play around in the playground you built. Even if after several days debugging I literally woke up and realized I'd dreamed in Quake e1m4's textures. 🤣
I'm sure he is part of the reason, why modern game graphics programming community is so welcoming and shares a lot of information.
He alone advanced the gaming industry for decades in the span of about 10 years
Meanwhile studios like the guys who made shadow of Mordor/war patented their fucking nemesis system and pretty much killed any desire to replicate it
@@leofwulf268 John Carmack, David Braben and Ian Bell, Chris Sawyer. Nearly everything we have now is building on what those guys did. Probably shouldn't forget those who developed the early games for NES etc. as well. They all pioneered techniques to get "impossible" things out of the machines they had at their disposal.
also the fact that Doom can be run on EVERYTHING.
Their ability to craft games about chainsaws and demons using math never ceases to amaze
It's also insane that Carmack was able to find the scientific paper amongst many in at that time, understand that it can be actually adapted for a game, and then be able to use it.
Imagine people even found books in libraries without Google? Absolutely insane
@@kapsi I'm a proud owner of a library card for longer you even exist. You still have to know what book/paper you want to borrow, then you have to translate the included math into an algorithm, and moreover select one that is relevant to your problem. You won't fucking find a Doom algorithm in a The Catcher in the Rye.
**retarded gen Z noises**
Basically it comes down to how exntensive your knowledge is of maths. With the exception of polygon, everything mention is literally a mathematic: binary, linear, trigonometry etc etc. so carmack knew the math involved but didn’t know if there were an off the shelf solution which he could use and adapt.
Maths is my weakest link… I attempted open gl programming back in my uni days and it just flew over my head. Just as this video does. Either you’re a math wiz or you aren’t.
Especially considering that many papers about algorithmic geometry are very theoretical, meaning they may be correct mathematically but can be incredibly hard or even impossible to implement correctly and efficiently in discrete computing. Talking out of experience.
The programming technology wasn't the only thing genius about DOOM. The level design, gameplay mechanics, art direction, character animation, sound effects and music was also inspired, so everything combined to create a unique, and captivating experience. It still hasn't gotten old.
I still play it every year. Doom 2 not so much lol
@@octagonseventynine1253 Custom WADS make it the real DOOM Eternal.
Agreed. I first played DOOM in 2015 to learn the origins before DOOM 2016 released. It was still captivating to me and a fun experience, despite only first playing it so long after release. It's one of the few games that have stood the test of time so well.
@@aliensoup2420 I think Hugo said that every WAD is cannon. Because Doomguy has been to countless dimensions over eons.
Yeah we all freaking know
Carmak is certainly one of the most amazing individuals geniuses during the rise of the PC gaming generation. He and Romero’s work will live on in gaming lore for generations to come.
Carmack is god.
Thank you John Carmack- not only did I play Doom on coop with my dad back in the day; but had the exact same blast playing coop with my son decades later- the gameplay is still superb. After the Fall on VR is the closest I’ve come to loving a game so much since Doom. A masterpiece.
I'm doing that in the modern era
Wholesome. This game has connected generations.
Im 15 and absolutely love this game.
I remember the first time I connected by Modem in a coop game with my brothers friend, who was using my brother in laws computer just a few houses away. It was such an amazing feeling to actually connect by modems and have another live player in Doom. I was maybe 13 at the time but remember it perfectly He of course turned and killed me and said he could not hep it.
I could not believe it all worked.
I was hooked on Doom2, I played competitively and went to Dm95 at Microsoft the first computer gaming tournament in 1995.
Naylor taught game programming at UT Austin when I went to school there. I was in love with Quake and was so excited to be taught by the author of the BSP trees paper. After first talking with him, I took his 101 course and sat in on his 201 course concurrently, doing the 201 projects for my 101 class. None of my friend understood the extreme honor I felt to learn about bsp trees from Naylor himself. It was an exciting time for me.
Man that's cool. I've had lectures from people who are outstanding in their field, and it always surprises me how "normal" they are when talking about the stuff they know about.
Out of curiosity, what did you go on to do?
Thats like studying kung fu under Bruce Lee. Congrats to you.
@@romerogoon software eng. Never really ended up in game dev... closest thing was a q4 mod that never got popular. Currently at Google - work on natural language ML.
@@RobbyNeale nice one, well done! Good luck in the future!
You can't imagine how amazing those days were for a 14y old. In late 1993 my mind was blown multiple times. September: Jurassic Park, October: 2nd Reality by Future Crew, December: DOOM by id Software - _thank you John Carmack_. After that I knew the PC was here to stay and the following years will only get better. BBS warez/demo scene, 3DFX, Fast Tracker 2, the PSX, CD burners, 3DStudio4, SGI, Alpha RISC, Linux, MP3 and one awesome game after the next ... 1993-1997 were awesome.
I had a similar track, BBS operator and coder in 1982. Assembler serial port drivers and file transfers to get every bit out of a 1.79 Mhz Atari 800. I worked as a tech for Tandy and we were building Doom boxes that could get higher framerates instantly when the game came out. I built a portable PC MP3 player for DOS and Windows in a toolbox that slid under the seat of my F150 truck, just for kicks and grins. The iPod came out later in a few years. I loved the code and logic of how this stuff works. I went on to do corporate field service and ended up at Intel Labs testing hardware chipsets, the pxe boot rom, and drivers for network cards.
Mega Team Fortress came out as a mod for Quake and some of the coders in Quake C left comments about revamping the sound system and doing things to "the build engine".. Some of them ended up at Valve and put some of Carmack's stuff in the Build engine. Why fix it if it's not broken as they say?
Well, the miles sound system and Valve went on to make Team Fortress Classic and Half life.
I have a modified quake C Mega TF server than can play Half Life maps. Just a few logical switches on how the platforms, buttons and elevators work.
Xavior was instrumental in making a COOP versus monsters version of Mega TF that allows one to play Wolf 3D, Doom 1 and 2 maps, and even some converted Quake 2 and 3 maps.
Fuck yeah, man
Yeah... It was amazing back then. If we were in front of a computer. Everyone hated us to their guts, just because we were computer freaks.
@@TheMechanator Very cool! You were involved in a bunch of pretty interessting areas during your life, man. ..I got a love-hate with PXE though, never works when it's important ;)
Gravis Ultrasound and Sound Blaster.
For programmers interested in knowing more: Bisqwit made a really nice video on how the DOOM rendering works and a reimplementation in Basic and C.
Look for it as "Creating a Doom-style 3D engine in C".
After watching this video I really can imagine how the set of stairs with the armor on the top in Doom's first map is an impressive technical showpiece. It's strange how we can forget how revolutionary this game really is.
The hitboxes do have vertical values. It's the renderer that breaks when you angle the camera upwards, so the game uses auto aim instead.
To add to this, the game does check the height of enemies for things like missiles and bullets, because calculations for these kinds of objects are much less taxing. Enemies also obey their height when it comes to what ceilings they can fit under, so you never see enemies walking under a comically low ceiling. It was theoretically very possible for Doom to have mouselook, and later Doom engine games like Heretic and Hexen did support looking up and down.
Yes, fireballs can pass over your head for example.
Explosions are calculated in 2 dimensions, presumably for performance or convenience reasons.
@@richardg8376 The Icon of Sin (which I think is sequentially the very last Doom engine level that id software itself ever produced) seemed to throw shade at this, since the Carmack head inside the Icon's brain relies on 2D blast radius calculation to allow you to kill it with rockets.
The fact that hitboxes do have vertical limits is also the reason why no other weapon will work when firing into the Icon's brain.. only rockets do splash damage. Hitscan tracelines and projectiles will pass over the Carmack head.
@@cykeok3525 It's Romero's head. ;-)
@@MacJulian88 Crap, my bad.
Brain fart while typing, how could I misattribute those lovely long locks.
It's 30 years that I play the original version from time to time... it's just perfect
It's so insane that you can play it in a website. Used to play it in college classes.
I highly advise the vr mods for both Doom and quake to both of you. Both felt like religious experiences for me.
Just to note, not every sprite was created from photographs of custom sculptures. Some are photographs of various other objects, for example many of the weapon sprites being toy guns and the fist being a photo of one of the developer's hands. I believe a few were also completely hand-drawn such as Doomguy himself and the range of zombie enemies. I think my personal favorite goes to the Pinky, with legs being taken from a Jurassic Park dilophosaurus action figure and combined with a custom drawn torso.
There's one taken from the hanged corpse of Mussolini
Doomguy was a clay sculpture by Adrian Carmack. Then they drew over that to get the zombie, shotgun zombie, and chaingunner. The Cyberdemon and Baron of Hell were also models by Adrian. Then they contracted Gregor Punchatz to make latex models for the Spider Mastermind (which was also used as the base for the Arachnotron), Revenant, Arch-Vile, and Mancubus. The Cacodemon was based on a scan of the cover to an Advanced Dungeons and Dragons source book. The imp and pinkie were drawn from scratch, though with reference, like you said, to existing toys and models. The Pain Elemental was drawn over a mockup made from other sprites from Doom 1. I don't know about the Lost Soul.
As for the weapons, the hands and arms in the first person view were based on Kevin Cloud. The chainsaw was an actual chainsaw - they had problems with it leaking oil in the office! The rest were all toy guns, though sometimes used creatively and with edited details of course.
Textures came from all over, including those same toys, photos taken of stuff, stock images, and "Nightmares in the Sky", a coffee table book about gargoyles and grotesques. At least one texture was actually first used as a wall in Wolfenstein 3d, then was modified and used in Doom... then was modified again for use in Quake!
This video is absolutely brilliant, love the way you take into account chronology and reference things happening in specific years
Doom is such a ludicriously important game it's honestly kind of crazy how ahead of the curve it was back in the 90's.
crysis in 2ks
@@Sva010 Crysis didn't do much compared to Doom. Design philosophy, sound design, visual design, everything in Doom was cutting edge and incredibly influential. No other game looked or played like it at the time of it coming out. Crysis' game design was primitive, generic and pedestrian by comparison and didn't break any new grounds beyond physics simulation and the glaring graphical advancements.
@@papayer True technical (e.g. graphical details and good audio engine) crysis was ahead but that's it.
@@papayer It may not be a shooter, but Ultima Underworld deserves far more credit than it usually gets in these discussions. It had true 3D environments with free aiming and rooms on top of each other a few months before Wolfenstein 3D hit the market.
If anything, the game has grown even more impressive with age.
10:26 That's not affine texture-mapping, that's actually what is called y-shearing, the texture mapping still takes into account the perspective (depth).
Also I believe Quake did not have 6 degrees of freedom but 3.
6dof is moving X, Y, Z and rotating in the same - whilst quake only showed rotation along the up axis, it was certainly possible to pitch and roll also in the initial quake engine - they are just less useful in an FPS.
@@salmonmoose 6dof is actually having 6 free variables in the transform matrix. Quake did support pitch and yaw-rotations along X and Y, respectively.
I agree. Original PC Doom doesn't suffer from affine texture mapping warping because it does account for perspective correction. I'm pretty sure it even has subpixel accuracy
Quake doesn't let the player orient freely but it does utilize all 6 axes. You can translate X, Y, Z, you can rotate along yaw, pitch, and roll. Roll is acted on when you take damage or die.
I sense a distinct lack of respect for Descent and Descent II
I've known how special he was since reading Masters of Doom at a young age. still one of my favorites. Thank you John Carmack! you changed everything.
Thank you John Carmack, as an IT guy and gamer...I am really appreciating you diving into the actual code architecture, including the history. Thanks
I'm a programmer but I cannot imagine what can happen in a mind of someone like Carmack , simply a genius.
Thanks John Carmack
Have some ideas, and break everything down to simple chunks you can manage to implement. That's all that happens. :)
@@SnakeEngine Dynamic BSP of the mind?😂
He probably slapped it together, saw it was slow, and bought Knuth, Abrash, and every book on optimization.
@@nolan412 it's sad that few developers care about optimization these days since there are fewer limitations on data. At least some modern games are still optimized well like Doom Eternal. I was so happy that my jank near decade old gaming laptop could run that game and barely have to sacrifice on the graphics either.
@@markwilson4686 That's a lesson I learned getting old. Just wait five years. It and the hardware will be dollars, and you'll know if it's any good fun.
As a hobby game programmer, Im glad to see someone defining the basics real quick for the newbies out there. Programming can be such an elitist world sometimes. Seeing harmonious support like this is nice.
Also, it seems like graphics innovations get forgotten so easily over time, but gameplay innovations last forever. ( yet people are so addicted to graphics... )
For anybody else interested in game engine programming, check out Casey Muratori's Handmade Hero series.
aye makes it a bit easier to understand
You could have told me it was magic and I would have nodded along just as convinced as I was to this video. I don’t fully grasp these concepts but I suddenly feel smarter thank you.
It's remarkable to this day that Doom was designed to run on dos. It was such an efficient game and ran on just about anything.
Still does. I have had it run on multiple versions of the rasp berry pi. Some had to be compiled, some run out of the box.
@@nosuchthing8..Isn't it like a meme at this point? I've seen videos of people running Doom on car dashboard consoles and fridges. Hell, I think someone even ported it to an old TI graphing calculator
It's been a meme for over 15 years. I think the Crysis joke was a play on "Will it Run Doom?" When I was in high school
@@danem2215 I think its more of the ying to the crysis yang. Doom running on low end hardware has been a thing since the 90s.
To not only run on DOS, but the fact that it ran well on a 386 is just bonkers.
BSP is also often used in procedural generation of levels. I use it in my roguelite game to divide the whole map up into rooms that satisfy a certain size criteria and don’t overlap. Combining it alongside other generation techniques (waveform collapse, Poisson distribution, cellular automata, etc) can yield some pretty interesting and varied maps.
i'll subscribe if you do tutorial
Sounds fishy.
the two parts about Carmack i love is he is a rocket scientist, and made three (if you count wolfenstein 3d) revolutionary 3d engine types when he was only in his 20's.
Bro, commander keen was revolutionary in the way it did scrolling on a PC, besides the 3 you mentioned there is also quake 2 and 3 who were less revolutionary but still top notch for their time and Doom 3 who only got surpassed graphically by a game in 2008 I forgot the name.
@@felipegomes6312 RAGE?
@@prshadowcat rage came out in 2011
@@felipegomes6312 crysis.
@@Wabajak13 crysis doesn't count haha
8:58 small correction, the enemies vertical hit box is limited to the size of the sprite but the enemies collision box is infinitely tall.
Holy shit this video should be split over a semester of a Game Programming degree.
I can only imagine the euphoria that those guys felt whenever they overcame each of those mathematical hurdles. There is nothing more joyous than devising a solution to a problem and seeing it work. I feel quite envious.
Doom invented the stuff you learn at a pace not much faster than one would learn about them in class.
Carmack no doubt deserves a lot of credit for his vision, hard-work, creativity and technical genius, but MICHAEL ABRASH is the UNSUNG GENIUS behind the scenes that helped to push through many of the difficult rendering and optimization challenges that made Quake and other 3D FPS possible. All built on the shoulders of giants who came before them.
Yeah I feel like this is similar to how popular media always makes the claim that Isaac Newton 'singlehandedly invented calculus'. Like, no... Newton didn't even discover the fundamental theorem of calculus. He didn't put it on rigorous footing. Sure he was an absolute visionary who was able to formulate many novel ideas, but giving him credit for the entirety of calculus is absurd, and it just speaks to the scientific illiteracy of the general public, and to the tendency people have to paint scientists as otherworldly savants, rather than ordinary people who have a strong passion and work ethic.
@@Onoesmahpie Exactly. Both Gottfried Wilhelm Leibniz and Isaac Newton co-invented Calculus while standing _on the shoulders of giants._
@@MichaelPohoreski Yes, I think the phrase "standing on the shoulders of giants" carries significant weight though, which must be explored if we are to have an accurate understanding of history (or at least one of the few avenues of history that isn't an embarrassing, bloody, trial-and-error, hateful, ignorant mess) Newton and Leibniz basically gathered known information and compiled it in the form of a published manuscript (a nontrivial labor at the time, of course) adding significant contributions along the way; in particular Newton used the fundamental theorem ingenuously by applying integration and differentiation to physical objects' trajectories, an entirely novel approach at the time.
The above two were certainly revolutionary geniuses, I could of course go into Leibniz's larger breadth of mathematical work, and his conception / invention of the early calculator. But to say they invented calculus is a bit silly. Calculus was developed over centuries, or to be honest millennia. The names of early pioneers who studied integration, differentiation, or of the person who first discovered the fundamental theorem, are typically cursory glances in a textbook that most students will never even crack open anyway, which I think is sad, especially when we give Newton, whose actual accomplishments (he built the first reflecting telescope for fuck sake, which revolutionized the field of astronomy!) certainly stand on their own, all the credit for calculus. It's an insult to Newton and to those who actually did 'invent' or 'discover' nontrivial aspects of calculus, and I think it discourages students from wanting to learn math because they think they have to be some sort of House-esque savant to contribute meaningfully to mathematics which is historically speaking not at all true. Math is a slow process, discoveries are made piecewise by geniuses who go unknown to popular culture, but whose names I believe deserve all the glory with which we endow celebrities who do fuckall for society and in many cases actively make society worse by pushing scams, harmful religion / pseudoscience, etc... .
@@Onoesmahpie Brilliant read, thank you.
@@Onoesmahpie Or does it speak to the absolute unnecessity of attributing accomplishment? Credit and celebration seems so far removed from the right attitude towards math and science and probably contributed a lot to the miserable inner workings of academics.
Great video! I've never quite understood the rendering process to Doom until now. This video belongs in a museum! Thanks a lot 🙏
This video was top notch. Gave me a deeper appreciation for the process and progression of that process. Thank you
Great vid, mate! Just as a fun fact about John Carmack smashing down that door: Actually Romero was the one that got locked in his own office! Then he just called Carmack over to obliterate the door with a custom battle axe.
the Hero Axe of +1 splintering lolz
Romero: help me Carmack, you're my only hope
Carmack: CARMACK SMASH!! [breaks door]
lolz
Had to chuckle in the video when he said "he devised a brilliant solution" (for getting out of the locked office) Given what had been said previously, I was expecting something along lines of "he used his superior programming skills to hack into the buildings security to unlock all the doors ..." instead he took an axe to smash up the door! 😂
I heard it was because Romero locked himself inside because he played so much Doom and was lacking work on the next project or whatnot, so John took an axe to his door to snap him out of it. Romero was a really really good player back then
As I am, apparently, obligated to point out some inaccuracies from the video, here are a couple I noticed 😺
09:00 - The enemies actually do have a vertical size, just like any other "Thing" in doom and other games using the same engine (Like Hexen or Heretic). You can actually observe this during gameplay, when a projectile, like a rocket or a fireball, passes over objects and enemies. Enemies and the player couldn't vertically stack or jump over eachother, however, but I imagine this was a deliberate design choice, rather than a technical limitation. The argument I often hear that the enemies have infinite height is that when you shoot at them, you still hit them regardless if they're higher or lower than you, but in actuality, vertical autoaim is indeed a deliberate mechanic they coded into the game.
10:20 - While Affine Texture Mapping can result similar rendering issues, this isn't actually the reason why the vertical looking looks so weird. Doom didn't have affine texture mapping, because it didn't use triangles to render its surfaces, instead, to render textures on walls and flats (ceilings and floors) they used separate, unique rendering techniques for each, which I won't go into detail about here. The weird vertical distortion was actually a side effect of the way they achieved the vertical look in the first place, which was by simply shifting the entire render area up and down. When You look up or down in Marathon, any of the old Build engine games or even Doom source ports that use software redering, if you look closely, you'll notice that all of the walls stay completely vertical on the screen. if you remove all the ui stuff, like the hud and weapon sprites, it'll just look like the screen is scrolling vertically.
Could you link a resource that goes into detail on the texture rendering techniques on walls and flats?
In Heretic and Hexen you can actually fly
> The enemies actually do have a vertical size, just like any other "Thing" in doom and other games using the same engine
Which is why only rockets could be used to kill the Icon of Sin, right?
Other projectiles would just pass over the hitbox of the decapitated Carmack head on a spike.
Explosions had 2D calculations for their blast radius, which is what allowed rockets hitting the back wall to damage it.
I created a dehacked style tool in 1995, which set player height to zero in the game. As result walls were still impassable but you could go through locked doors. So yes, height variables were real.
@@cykeok3525 Its a decapitated Romero not Carmack lol.
Really cool stuff, thank you! Fascinating to see how far back the origins of modern graphics goes.
powerful and based
This was such an overdue homage to John Carmac and his early accomplishments.
You've outlined and explained the coding evolution of 3D in a way that was clear and easy to understand. (a markerd improvement over slogging through early 80's techpost blogs).
Well deserving of a subscription. Kudos.
Awesome and most informative vid made on these early rendering technologies. By clearly explaining the issues we are brought much closer to the actual creative process. This vid is in a class of its own. Thankyou.
This is a great video, thanks. It is the first time that I've seen this approach being explained in such a way that it is easily understandable.
Thank you John Carmak, breaking down doors both metaphorically and physically.
This is underrated.
You sure? At one point it had more downloads than windows
This is fascinating and super educative. Thank you so much!
Nice job man. I love the way you illustrated how the scenes are rendered.
I have to tip my hat to the incredible amount of work and effort with editing put into this video,
With Examples and Overlays to show what means what
If there weren't visual examples, I would have absolutely no idea what is happening. It goes a long way
Thank you Jonh Carmak! thank you ShreddedNerd
I really want to see videos like this moooooore
Great video! thanks for creating and sharing it with us!
Bilinear filtering in Doom is a crime against humanity.
what's that?
@@mrosskne It's a filter that makes pixels get blurry when you get close, instead of showing the blocky huge pixels in their full glory
How about anisotropic filtering? Bilinear is SO 1996.
@@TheWarmotor how about no filtering
@@traumatizedgeworth How old are you, sir? I remember when I bought my first gen Voodoo card with 4megs of dedicated video memory, would run GLQuake at 640x480! Not having to see blocky textures on every surface like a software renderer, it was the first step toward photorealism in games and a big deal. These days kids play minecraft and low-poly with pixellated planes is an aesthetic choice, they don't know how good they have it.
Thank you to the benevolent and hyper intelligent trans dimensional being known to us as John Carmack, for in his mercy allowing the human race to continue to exist.
or did he?
What is the time, CV-11?
@@KipcreateGaming that was so last year the time is cv12 silly🤣🤣🤣🤣🤣🤣
He also made our childhoods incredibly rich. End 90s and early 00s was such a rush!
Shame about Greasy Randy Fucking Pitchford though 😕 😒 🤣
Excellent vid, thanks. Brings back some great memories playing Wolfenstein and Doom back in the day.
Loved this, and I really appreciate your hard work here. Not sure why it just now popped up in my feed. Went to school to make games and while I do enterprise coding instead today, I still like to hit it up on the side. Carmack is STILL a legend and I loved your accessible deep dive you mad here.
shocked and appalled that someone would describe floats as "very precise decimal numbers"
Appalled, you and me both.
@@someguy2016 It's so precise that it's showing you the true nature of that very large 0.
Your vids always educate me in some way. Glad I subscribed.
absolutely love these types of videos, awesome work man!
fascinating, thanks so much for pulling this together
Wow this is actually really well researched, great vid
Interesting topic! Didn’t know Doom was that influential
Doom is still a living legend, bud. The original games are still better than most new shooters now.
It's probably more influential than that even.
Doom and Quake were revolutionary for coding. You'll still find Quake code in new games.
@@markwilson4686 the lights in half life: alyx use the same flickering pattern coded in by id
Everywhere you look you can see the eternal influence of Doom and Quake.
You have done an amazing job in explaining this, thank you!
Nice overview! I worked at several games companies include Maxis, EA, and Sierra-Online in the early 90s. I saw the transition as it happened.
This was definitely a big video with a lot of work put into it, I learned some pretty interesting stuff; good job! And thank you, John Carmack
BSP trees can also be found in the 3D models in the FreeSpace series of games, and in the first two Descent games. (the levels in Descent 1 and 2 don't contain BSP trees, but the 3D models for the missiles, player ship and robots do have BSP trees)
similarly, Star Fox on the SNES uses BSP trees for its 3D models (and before Doom's shareware episode was released lol)
@@monkybros One of the first BSP tree builders for Doom levels that was publicly available was in fact written by the guys that worked on Star Fox, too. Colin Reed and Dylan Cuthbert created the program simply called "BSP". Before that the only other one was the one integrated into DEU, by Raphael Quinet, who had to repeat all of Carmack's research himself in order to understand it.
Phenomenal work done here - I also didn't understand much of the technical stuff but the explanation and presentation was extremely well done and much appreciated. I can thank John Carmack with the others, but we also should thank you for your meticulous efforts to our collective benefit.
Thank you, John Carmak! Thank you as well for this wonderful video!! I really enjoyed it!
17:22 💀💀💀
Aside from that - the real history from Carmack, in a recent interview - I think the one with Lex - was that he implemented BSP when he had to port Wolfenstein to the SNES. So it's a small detail but in a scholarly technical history sense it should probably be referenced.
The string variable of the value "Sneed" at the start of the video should've been your heads-up to click off before hearing an edgy joke.
Thank you, John Carmack! If only modern devs cared about optimization half as much as you did!
amen
Thank you John Carmak
and thank you ShreddedNerd for producing this worthy TH-cam footage.
And finally, thank you to my late brother for wasting his (and my) youth on this wonderful game that you bring back so many memories of as you play it on screen whilst I watched this. I can literally recall exact scenes and times that I played this game co-op with my brother whom I miss so much.
When he died I stopped playing computer games for many years (probably 10).
(And don't worry about the recursion thing. It pissed me off for about 4 seconds.)
This was an excellent video and I appreciate your dedication to explaining the technical terms such that laymen could understand.
It really helped me put a perspective on how I should go about explaining technical stuff to people outside of my industry.
Thank you John Carmack, you have always been an inspiration for me. My life changed when I first saw Wolfenstein3D on PC.
Seeing a nodebuilder in action did the trick for me. Using DooM Builder for so long (as you did for demo purposes here) and always wondered why the node builder was the only thing that really complained or mattered. Being basically the very foundation of the rendering engine, that makes sense now to me!
Thank you John Carmak, And thank you for this video, its given me some ideas to solve a problem I'm trying to solve
Thank you John Carmack! So excited to see what you do with VR and AR over the next few years!
I've been trying to figure out why I couldn't understand how bsp would work, and it was a single sentence no one thought to include when they explained it. The partitions are already made, and they aren't generated. Thank you. This is a very well-made video, and I will continue to watch the rest of it despite finding what I was looking for.
Thank you John Carmack! Who knew such badassery would owe its existence to math. You've been a treasure to this industry, brother!
this was incredibly fastinating! just...incredible! it really shows the genius of carmac and why doom will run on anything
This video was super informative and so well made I simply couldn't stop watching it! It's amazing how for rendering technology has come.
Thank you, John Carmack for the FPS revolution!
Dude this was epic, fantastic work - Thankyou!!!
I’m 49 and been into FPS games forever. My first one was “Battlezone” on Atari 2600 in 1982. My “pinnacle” was playing professional PUBG Mobile in live tournaments for team “Gold” in Bali.
I remember playing very early Doom on my cousins computer in the mid 90’s.
Noone asked you old man
The genius of John Carmack will always be a door-smashing one for the gaming industry. Never shall we take it for granted.
Thank you John Carmak, you truly are a wizard of programming
OH MY GOD, the way they rendered the original Wolfenstein is GENIUS
Great video. You have a talent for communicating and teaching such technical topics. You did really great work with this video. Thank you for sharing it with the world.
As for the subject, itself, I am always amazed to learn the origin and circumstances of what become ubiquitous and commonplace ideas. Those were some seriously smart, resourceful, and driven people. Thanks again for sharing their story.
awesome video. when i first subbed after seeing halo content, i would have never imagined watching a video like this from the same channel. well done, i remember why i have notis for this channel.
Man, John Carmack literally pushed gaming and programming quantum leaps forward for all of us
Honestly, overall a good and basic description, even for a computer science major, and professional software developer like myself. Was interesting to learn about their rendering algorithm, as well as raycasting (I knew the basics, but never looked into it).
I'm lucky to have been around and programming since the early 90s (started on an Amiga, then I got a Tandy 1000 RLX with a whooping 4MB of ram and a 286 10Mhz!) I still remember the black magic we had to pull to get anything functioning. It's way different programming now and doesn't feel the same, in a way I do miss the massive amount of creative problem solving that went into optimising things to run at a workable speed it is a really good memory for me.
Oh I forgot to add that I had a couple of programs that took over 1 hour to compile in pascal!
@@DigitalViscosity Yeah, i kind of miss that on modern consoles. So many games are so unoptimized and just "deal with it," if they aren't optimized well.
I tried to program Wolfenstein3D in Pascal back in the days. I got two wireframe boxes, you could walk around them and in between, but if you went into one of them the program crashed, and I never found out why, so I started coding the texture rendering algorithm and it was so slow you could see the pixels got drawn. I was devastated O_o
@@b4ph0m3tdk9 Wolfenstein had some really extreme measures to make it go fast. It didn't just draw in vertical strips, which I assume you figured out. It also had a specialized assembly routine for each possible strip height, so when it was drawing them it would simply increment pointers and copy data.
But I would guess your program was slow because it was using some ridiculously overengineered SetPixel() function instead of simply writing bytes to a 2D array. Also, 16 color modes meant using planar graphics which meant a ridiculous amount of work to set one pixel, whereas with the 256 color mode you literally just had to set one byte.
This video was fantastic 👌 super interesting stuff. Thanks for the great content. I learned a lot!
Thank you John Carmak,
I didn't understand half of the video (basically everything in the 2nd half) but now I have something to do and will try to understand what is going on.
It's simplistic now but i remember being absolutely blown away by Wolfenstein 3D! Nothing like it existed at the time. The Doom came out and... HOLY CRAP! It was a great time to be alive
I agree, the difference between before and after Doom... was a shift only rarely rivaled. Doom was the Wayne Gretzky of FPS games.... sure there was others before, but *NONE* since have had the *GAP* of greatness they had.
I didn't know much about Wayne till I saw an ERB (epic rap battle of history) with him and tony hawk, and he dropped this line...
"You and I have so many world records between us... 184... that's plen-T-y of them....
*And I've set 183 of THEM!"*
I didn't believe it, sounded like a bit of an exaggeration.. so I did I quick youtube search and the first video that popped up was his "TOP 20 World Records".... Like... WTF!?!?!?
Like don't get me wrong Micheal Jordan was and most likely *_WILL REMAIN_* the greatest basket ball player to ever play the game... but the gap between MJ and everyone else is still *MUCH* closer than Wayne and any other hockey player. I mean seriously, you could just imagine a potential stat for the game, and odds are... He has the record for that stat by a country mile.
Sorry, just have to give Wayne his credit since I was so ignorant him for so long. The man was the Alexander The Great of Hockey.
If that's the case maybe rethink having a 20 year old woman as your profile pic
@@aguenter Why? Just curious. I've never understood why some people think that as a person gets older they are somehow supposed to *NOT* be attracted to or appreciate the beauty of a Healthy Mature woman.
@@James-iu2km Yes, clearly you haven't understood that, which is why you think "the beauty of a Healthy Mature woman" is reasonable sequence of words to come off of the fingertips of a 40+ year old man. So from one to another...gross, dude.
@@aguenter LMAO... I'm not 40+, so quit *PRETENDING* you know things you don't, that a far worse problem as it makes you capable of doing things without due *_REASONING._* You know that thing where you use logic, evidence, and *THINKING.* You really should try it some time as it's the primary source of humanity's accomplishments these past few millennia.
Furthermore, you did nothing to support your claim. That which can be asserted without evidence, can be dismissed without evidence. I *genuinely* wanted to give you a chance to explain, but clearly you're not interested in that as much as stroking your own ego and reassuring *YOURSELF* that you couldn't possibly be wrong. You know there's a whole world that exists outside and independent of you right? You are not the center of the universe, no matter how "special" your mother said you were.
Painter's Algorithm was being used by 3D games even into the early 2000s. The Playstation, 3DO and Saturn didn't have a z buffer. It's crazy that in the early 90s Doom was using a far more optimized algorithm. The N64 and Dreamcast were the first consoles with z buffers but even in 96-98 they made the graphics pipeline expensive.
Honestly if you had a camera on a track you could design the game using the Painter's Algorithm.
A lot of 3D games used Z sorting on the Playstation which is why you had polygons popping in and out on 3D characters like Resident Evil lol
Nope, you have popping in all games (including today) because that is an optimization technique. Does not have relation to z sort.
@@anonimo89479 ; You're referring to asset/texture streaming, which results in pops as higher LODs are streamed to GPU. What OP is describing is when two overlapping triangles are sorted by-triangle and rendered with no depth sort/check. The overlapping fragments that are written can change based on viewing position, resulting in popping. When rendered with a depth-buffer, or any other method that can sort by-fragment, only the furthest overlapping fragments will be discarded. This is still a problem in modern times, because it only works well for opaque surfaces. You can observe this behavior in a lot of transparent surfaces in games (which is why many games elect to heavily restrict transparency in their pipeline), and one of the solutions is sorting by-fragment via atomic textures.
Thank you John Carmack! Youre contributions are appreciated!
Great video!
Subbed, thank you, brilliantly made!
Thank you John Carmack, and thank you for creating this video!!!! I feel like a tinny grain of sand compared to these titans of the gaming history....
Can you do a video like this on the Build engine? I can't find any good videos explaining how that engine works (specifically, what makes it different). I know it doesn't use BSP trees the same way that Doom does, since you can view the levels live in the editor and even edit within the levels from a 1st person perspective. If Build is using some sort of BSP tree, then it must either be doing the math on the fly or else using a different method altogether.
The best explanation I've found came from a guy who was demonstrating how to write a "Doom-like" engine in C. It sounds like the way Build works is basically by treating every sector as its own independent space with what Doom would call a "linedefs" treated more like portals to another sector, and only blocking the view when those linedefs have been defined as an impassable barrier and given a texture.
But I would really like a more cohesive breakdown of how Build specifically works. He started out explaining the basics of raycasting, then explained that BSP trees and all the pre-processing used by the Doom engine was a totally unnecessary complication on modern hardware and made testing and map editing a pain in the ass, and then switched to making the engine more like Build, but with a lot of stuff missing from the explanation. Or, at least, it was explained from a lower-level coding/ mathematic perspective and not a higher level way like you're doing. Plus his goal is to make an engine _"like"_ Doom or Build, not to actually explain how either engine actually works, and I feel like his video was really more of a tutorial for how to make a basic 3D engine by using existing engines as examples.
John Carmack _rightfully_ gets so much credit for his contributions to not just gaming, but computer science as a whole. But I think it's important to remember that Ken Silverman wrote the precursor to Build in highschool and was contracted by Apogee by his first semester of college to produce the Build engine itself, and that engine got used in _way_ more commercial games than Doom ever did and was much more technologically advanced. It's probably fair to say that Silverman was able to leverage faster hardware and by many accounts I've read the Build engine is kind of a janky mess, but, damnit, it _works._ I think that Build contributed _a lot_ to the gaming industry and had functionality that few other contemporary engines had and apparently did it by some absolutely bonkers code fuckery, and I just want to have that fuckery explained to a chimp like me instead of just having to take the word of random people's forum posts saying so :P
Edit: heres the link if anyone is interested. It's not a bad video, just not really what I was looking for: th-cam.com/video/HQYsFshbkYw/w-d-xo.html
With SLADE you can sort of edit Doom levels in 1st person as well.
This is my best guess from what I've read, though I have not read the source code.
You divide the map into fully convex sectors. The neat thing about fully convex sectors is that you can draw the walls, floor and ceiling in any order, because they cannot overlap (you don't draw the walls that face away from the player). Sectors are linked via shared wall sections called portals.
You can draw it all with a recursive algorithm. You start in the sector where the player is in, with a viewport covering the whole screen. You draw the walls, floor and ceiling in any order you like. For portals, the drawing function calls itself, except it draws the sector seen through the portal, and the viewport is the portal. Because everything is clipped to the viewport, including portals, there is no overdraw with respect to level geometry, and only visible sectors are considered at all during the rendering process.
Sprites probably get drawn last, within the recursive function, with the painters algorithm.
See the books "Game Engine Black Book: Doom" and "Game Engine Black Book: Wolfenstein 3D".
@@jimtrela7588 I've looked through those books a bit, but that's still not BUILD AFAIK.
this was good research dude. went everything from the algorithms to the history. really neat. thanks for showing how you made the graphics and stuff. i really like the story of BSP and doom and stuff. quake uses bsp for so many things. thats one hell of a complex engine. carmack has the biggest brain in the world
Pleasant to listen to in the background. Had a laugh a few times. Well done guy
Thank you John Carmac, for your meme-worthy intellect. Oh, and for gifting us one of the greatest games ever made, that too.
I just got ALL Doom games from the Quake on sale, and I've been replaying the classic Dooms, and have to say they gawd quite well. They're still great experiences with tons of great levels, though enemies and tons of replayability.
Thankyou John Carmack and thankyou ShreddedNerd! I appreciated your tying of important game milestones to important music milestones, although my knowledge back then of id and apogee were somewhat scrambled at the time, it was a while before I realized that commander keen and wolfenstein 3d were connected! I do remember Doom floppy discs and the absolute mania surrounding the game but I wasn't very internet-connected so I didn't pick up on the whole multiplayer culture that dates from then on.
Great video man, I really enjoyed it.
I remember waiting many hours sometimes for the BSP file to finish compiling on my Source maps. If you ran your map in the source engine without the BSP being cooked first your map would run like shit.
Very interesting and informative. Honestly, he was a genius.
I was curious, around 10:50 you show off what seems to be a mod in doom which allows you to look up and down, is there a mod which allows you to play the game like this from start to finish? Also, great oratory skills as always, keep the great vids coming 👍🏼
Thanks, I was using GZDoom.
GZdoom,it isnt a normal mod,its whats known as a sourceport,after john carmack released the source-code of doom under the GPL,contributes rushed to improve on the engine,making replacements for the engine with improvements.
Mouselook is a thing on most source ports; it's just that it doesn't look too good in software rendering unless you're used to it. Source ports also limit the mouselook view pitch to 90 degrees so the game doesn't look horrendous, though GZDoom automatically removes that limit on hardware-accelerated rendering mode.
Thank you for the walk in the past + 3D game math lesson. It's been a fascinating experience. More!