i'm going to use a few terms throughout this video that not everyone might understand a plane is a mathematical term for a square or rectangle this is mostly the walls ceiling and floor vertices are the corners of said planes the singular being vertex polygons are another term for surfaces derived from computer science rather than maths it's going to be used interchangeably with plane to do something recursively means a process must repeat itself over and over until an end goal is met to solve a problem a data type is a way data is classified in programming
for example a string which words or series of letters and int which is an integer a typical number there are different kinds of numbers as well such as float for precise decimal numbers and long for well long numbers of the total size of the games industry today around 20 percent at games within the shooter genre around a fifth of games in this 300 billion dollar industry are shooters most of them being first-person shooters the amount of money generated by and riding on the success of this singular genre in this industry is stupefying the first person
shooter has developed early on was a huge departure from every other kind of game that existed at the time games at the time pc games especially were often slow or methodical the personal computer platform was known for careful and considered games turn based strategy grand rpgs with a slowly unfolding world often times these games would be indistinguishable from a spreadsheet action was the realm of console gaming platformers were the most immediate real-time action-packed games available and besides notable games like duke nukem and commander keane people didn't really play those kind of action games on pc
this was until the advent of the first person shooter suddenly people were hit with this visceral representation of violence they represented something which films could not you inhabit a world through the lens of the character you were closer to the action hero than ever before in any medium in history what is widely agreed upon as the first first-person shooter ever is maze war developed in 1973 that's the same year britain joined the european union dark side of the moon was released and the united states announced it would withdraw from vietnam it was developed for nasa
computers by steve colley greg thompson and howard palmer it was constructed with simple wireframe graphics people had the idea of adding multiple players using networking then connecting over the arpanet then it took off we saw other first person shooter games after that point spasm or space him in 1974 battlezone for arcades in 1980 besides these few examples for the majority of the decades following its inception the first person perspective was known mostly for its association with the role-playing genre for example games like ultima now first person shooting did technically exist but you were merely shooting
projectiles at your friends you weren't inhabiting your character you weren't the action hero fighting bad guys that was until wolfenstein 3d id software was founded in 1991 by four former soft disc employees john and adrian carmack no relation they just happened to have the same name tom hall and john romero this was the same year the soviet union fell carmack is going to be more important later on they originally began with a mario clone named dangerous dave before the company was officially founded this was mainly to show off the beginnings of john carmack's technical wizardry
encoding an efficient 2d side-scrolling graphics renderer the early 90s when everything was a dark and edgy statement the satanic inversion between pc and console was no exception pc graphics using software rendering were terrible john carmack developed his adaptive tile refresh for the pc to compete with the raw computational power of the super nintendo a true beast adapted tar refreshment that slightly more of the game world could be included in the screen buffer just outside of view this meant they could render smooth 2d scrolling it also made the sprite animations independent from screen scrolling this little
bit of code magic powered their games including the commander keen series the commander keen series was spread through shareware with subsequent episodes releasing over the next year or so for purchase from apogee their publisher this shareware model would be important because it would be used in their subsequent games speaking of subsequent games wolfenstein 3d began development in 1991 it would use the raycasting technique earlier employed in id's catacomb 3d raycasting was a rendering technique necessitated again by the limited processing power of pcs at the time pc master race just can't stop losing pcs almost all
used software rendering rather than a dedicated graphics chip the shareware model involved getting the game on as many pcs as possible raycasting was the solution to help them do this raycasting allowed their game to run on basically any pc raycasting means you're able to draw only the surfaces which are in the player's field of view this helped massively in saving processing power but how does it work in effect a ray is cast from the player to the geometry to the nearest object blocking its path in wolfenstein none of the levels were truly 3d every level
was drawn out on a flat 2d plane the program scans horizontally checking that every pixel in the horizontal axis has something drawn in it there's nothing drawn in a position a pixel column will be drawn out this is simplified from the process of ray tracing where this process is done for every single pixel rather than every pixel column the distance between the viewer or the camera or player they are of the same meaning and the nearest piece of geometry is obtained the height of the pixel column is calculated using the distance from point of intersection
in the direction the player is facing it uses trigonometry to find this point of intersection this effectively allowed them to give the illusion of distance to render a 3d scene this makes the process of rendering 3d much easier as a line that line being distance from player to geometry directly transforms to a line that being the height of the rendered column this process is done multiple times every single second the planes in the scene had been texture mapped where an image is applied to a 3d surface when the columns are drawn they are really drawing
slices of these wall textures at different sizes the height of the column being drawn is smaller when the plane that being the wall is further away from you the textures are scaled appropriately to the size of the wall relative to the player this gave the world of wolfenstein so much believability for the time you were no longer just navigating wireframe mazes you were an action hero bj blaskowitz infiltrating a nazi castle the walls were adorned with flags of the german reich you felt closer to the world than ever before you were interacting with a true
3d space this process was however flawed in wolfenstein 3d there was no verticality at all no difference in elevation only the walls had texture the ceiling and floor had to be flat colors if they wanted texture on the ceiling and floor they would have had to add horizontal scan lines you were still ultimately navigating a maze a colorful maze with nazis in it but a maze nonetheless wolfenstein 3d was released in may 1992 the sequel's spear of destiny was released later in the same year while the rest of the id team was working on spear
of destiny john carmack the ascetic high priest of technology locked himself away to study he would brainstorm the revolutionary tech that would power their next massive game the next game that the rest of the team would start working on in september 1992 it would be something inspired by evil dead brutal and violent the name green and pissed was ultimately passed up for the much snappier doom doom would launch in 1993 the game would truly be able to transport you into a world the levels truly felt like places the architecture of doom consisted of supernatural science
facilities with geigeresque and hellish environments as well the enemies were a combination of horror and sci-fi with cybernetically enhanced demons the architecture over-the-top setting and violence was inspired by films such as evil dead and alien the floors could now be angled they could now have multiple levels with stairs and elevators pools of toxic fluid surrounded these risen platforms it was truly 3d but it wasn't really they were yet to achieve the full six degrees of freedom that john romero wanted this wouldn't happen until quake rooms couldn't be stacked on top of each other there was
no vertical aim the game was entirely played on the horizontal axis the thing is vertical aim was actually possible at the time they could have limited the enemy's vertical hitboxes to the size of the sprite but they didn't not because they couldn't but to save processing power you see doom was still using software rendering it's shareware model relied on getting their games on as many computers as possible like i said it was essentially the beginning of the free-to-play game model we have today they aimed for the ibm pc for machines running dos they had to
sell their game to university students and wages who were bored at work so they could run office tournaments they didn't calculate the enemy's vertical hitbox so that they could save memory they didn't want to give the enemies hitboxes a height value just have another factor to calculate all the levels were drawn on a 2d plane like wolfenstein just this time the map creator is quite different the ground is divided into sectors this will be very important later each sector has two associated values ceiling height and floor height well it has several associated values but those
are two important ones this is also why one room could not be placed above another and why every surface had to be made out of a flat square or rectangle another reason that vertical aim couldn't have worked is due to how the texture mapping worked one game that did have vertical aim and levels on top of each other before quake and not that long after doom was bungee's marathon and look what happens when you look up and down in that game the textures start to distort this is because the game like doom uses a fine
texture mapping this like many of the other methods was done to save memory on the processor by taking advantage of cpu caching basically what happens is that texture coordinates are linearly interpolated using screen space distance between vertices rather than the actual 3d in-engine distance between them the distance between points on a plane remains the same when you look up and down what this means is that perspective when looking up and down is not accounted for you know how pixels on a texture start to warp as you get closer what looks like a straight line from
far away begins to turn inward as closer pixels get larger while more distant pixels gets smaller this doesn't happen in doom because accounting for perspective is taxing on 90s computers you know how the game only draws things in columns to save processing time they'd have had to do vertical scans as well as horizontal scans newer ports of doom with newer rendering engines made for new hardware like gz doom obviously don't have this limitation as such they use more current texture mapping and don't have this issue but all of these concessions weren't enough john carmack's coding
brilliance met its most devious enemy yet stairs john romero came out with a really way out and strange idea on his early incarnation of e1 m2 yes he wanted to mix things up with the earth-shattering invention of stairs you see just raycasting alone wasn't enough to efficiently optimize the game raycasting saves memory by only rendering things which are visible to the player however surfaces on the inside of these stairs were visible to the existing algorithm thus they were drawn when they shouldn't have been you see for 3d rendering to not waste performance they need to
draw as few surfaces as few planes as possible this necessitates occlusion culling or visible surface determination or back face culling basically the renderer should only draw what is in the player's field of view there need to be absolutely no overdraw whatsoever adding height as a variable such as with romero's stairs requires a much more sophisticated algorithm than was present in wolfenstein and in id's existing rendering engine there are many different rendering algorithms out there it seems that we need to dip into the hypothetical algorithms to start drawing the literature for some better algorithms let's explore
some of the options there's the painters algorithm named so because like in a painting the background is rendered first with detail laid on top basically the polygons are sorted by their distance from the viewer and the more distant polygons are rendered first and the closest polygon is rendered last it is easily the most simple solution it was developed in 1972 the year mash started as an easy to implement solution for cad it also has the worst possible case for space complexity meaning it takes up as much memory as an algorithm possibly could every single service
in the field of view is drawn obviously this isn't a good fit it's more of an example from the early days of exactly what not to do there's also warnock's algorithm john warnock was the founder of adobe and this algorithm originated in his doctoral thesis in 1969 the year man landed on the moon and in the court of the crimson king was released essentially it recursively subdivides the screen into four parts what this means is it splits the screen into four windows and splits each window into four smaller windows it does this again and again
until each window is trivial to render meaning it has only one or zero polygons present the algorithm also checks if multiple polygons are within one window if the closest polygon covers the whole window then it is drawn this is more efficient than painter's algorithm as it renders front to back but it's still not very well suited it will eventually keep subdividing to a ridiculous degree to the point where a window is smaller than a pixel yet this ain't a good fit for a game you could do a z-buffer for every pixel you want to draw
check if there's anything in front of it doing a check on every single pixel yeah there's no chance in hell the final solution does kinda use a zed buffer but it doesn't do that check on every single pixel it finds a much more efficient way to do it no in order to truly revolutionize not just gaming but 3d graphics forever our protagonist john carmack needs to go to a much more inspired source something that hadn't actually been implemented before something he just read in a white paper just a concept yes how common is it in
gaming to see people run into optimization issues and seek out a white paper to solve their problem because nobody else had done it before yes that's carmack for you we need a renderer that would draw objects closest to the player to furthest away until every pixel was written to that had no overdraw the solution was in a 1980 white paper that's the same year genesis released the reclaimed album duke where they really came into their own i really didn't understand any of their work this 1980 white paper by bruce naylor was given the humble title
on visible surface generation by a priori tree structures it described a rendering model we know as binary space partitioning or bsp for short this was the method that would change gaming for years this wasn't the first time binary space partitioning was alluded to a 1969 study by the air force of the good old us of a alluded to the use of partitioning 3d scenes to solve the visible surface problem the study was conducted to determine the viability of 3d for flight simulation we can thank the armed forces of the united states for giving us doom
they explored using a matrix to track which objects are occluded these of course wouldn't do so well as the size of the matrix would need to be the square of the number of objects in a scene that wouldn't scale very well it wasn't until 1980 that binary space partitioning was properly realized in the white paper that would reach john carmack alongside its core tenant the binary tree but what is binary space partitioning anyway well the name gives you a clue is partitioning space in a 3d environment this is done using a bsp tree what is
a bsp tree you may ask in computer science a tree is a data structure used as a mathematical model for displaying certain data types it's separated into nodes with parent nodes that have child nodes bsp uses binary trees binary essentially meaning two a binary tree is a tree where there are two or less child nodes stemming from any given parent from any node there are never more than two child nodes this is as opposed to a non-binary tree which is the tree that has dyed hair and a gender studies degree the data stored in the
nodes of the binary tree are the sub sectors of the map subsectors being smaller parts of those map sectors i spoke about earlier remember each map is designed on a flat 2d map editor with each sector having associated height values the genius is that the map is sliced up via binary space partitioning after the map is built all the hard work is done when the map is created rather than by the processor at run time while the player is playing the game the map is already split already partitioned when the player loads it reducing processing
needed at run time to create the binary tree a root node is established covering the whole map after this the map is recursively subdivided along every plane until only convex sub-sectors are left the sectors are carved into smaller sub-sectors the entire map is essentially cut into along every single wall every time the map is cut in half the two halves are added as nodes at the bottom of the tree by the end you're left with a tree where each node at the bottom of the tree represents a distinct sub sector remember this tree is entirely
conceptual it doesn't actually exist so long as the planes don't move vertical movement is accepted from this because vertical movement is a separate value the same bsp tree can be used doom's bsp tree generation was done after levels were complete and would search for the best possible tree that being the one that generates the fewest binary tree nodes a binary search is performed to determine what sector the player is in a binary search is when an array of pre-sorted data is searched through by continually halving said array a search through a binary tree is by
its nature a binary search because every time you go down a node you're removing half of the possibilities after the player's sector is determined using this binary search the subsectors are then sorted by their distance from the player closest to furthest the tree is iterated through to determine which planes to draw the horizontal scan lines from raycasting are still used to track the parts of the screen that have been drawn over this way they are able to render front to back and ensure that there is no overdraw when each node is passed over in the
iteration a few things are checked has that area already been painted over if so don't bother drawing it when a plane a polygon or wall is drawn it is akin to a curtain being drawn left to right to unveil an area so to speak whenever a curtain is seen by the player it is unveiled from closest to the furthest to be exact it's the closest 256 walls that are displayed remember how height of the pixel columns drawn on screen depended on distance from the player for doom this required determining the angle of both ends of
every wall relative to the player's field of view in the early 90s most processors didn't have dedicated floating point capability this is a float in programming if you've ever heard of that basically a data type for very precise decimal numbers the doom engine had to use binary angle measurements which avoid floats and used a lookup table to determine the x-coordinates a lookup table is essentially a cheat sheet instead of the process of doing the maths itself it just looks up the answer in this lookup table they also use these angles for backface culling with a
simple and elegant piece of mathematics backface culling basically means the renderer doesn't draw the inside of every polygon it only draws the part on the outside that you actually see the walls are rendered first as pixel columns from front to back then the ceilings and floors using pixel rows the objects such as barrels and enemies are rendered from the furthest to the closest the ceilings and floors are determined using vis-plane underscore t or vis planes these planes were determined using height values within each sector vis-planes are not constrained to single sectors and will be continuous
provided they all possess the same height illumination and textures pixel rows are drawn top to bottom one final thing you may wonder about doom's graphics is why are all the enemies just pictures facing towards you probably something to do with them being what we call front-facing sprites they're rendered last and like i said furthest to closest that's the opposite order to the geometry they are just pictures taken from the data files and projected onto screen of course there are a range of pictures the one that is drawn depends on the player's location relative to the
enemy and the direction the enemy is facing the enemies do actually have a full 3d hitbox the pictures as most fans know are actually from real pictures taken of sculptures made by the artists so john carmack was faced with the fierce issue in the problem of visible surface determination he had to find a solution that was both incredibly fast and very accurate bsp doesn't completely solve the visible surface determination problem but it is one of the most reliable and efficient methods of optimization it saw massive acceptance bsps were evolved and made their way into quake's
dramatically improved game engine when they took on michael a brash and finally figured out the full six degrees of freedom from there it was in every fps and i mean all of them half-life and half-life 2 every source game counter-strike to left for dead the halo series used it you know the scarab from halo 2 is actually a bsp object yes it's a moving piece of level geometry many would say it's a sign of carmax genius that he took an idea from concept to mainstream solution he did all this crazy work in between supercharging ferraris
and becoming a judo master you know one time he got locked inside a building instead of say waiting for security or calling a locksmith he devised a brilliant solution he'd likely gone to a renaissance fair earlier where he bought a medieval battle-x so naturally he smashed down the door with his mighty axe he was rich so he could afford to get the door fixed he truly is a unique figure in the gaming industry and you can see why he's so highly respected if you made it this far comment thank you john carmack the use of
bsp trees has begun to be replaced over the last few years developers instead opt for things like static measures with more powerful hardware now they could afford some level of overdraw other methods give artists more creative freedom and a much quicker workflow bsp often leads to the distinct blocky look that many old games had one could certainly argue that these technical limitations are what gave source maps in early 2000s maps in general their distinct charm their soul with stark and distinct architectural choices some magic is truly lost in busy modern day maps many new games
have actually tried to go back to recreating these older cleaner more distinct visuals bsp is still occasionally used today in prototyping levels for games quickly blocking them out it's of course still used in games such as counter strike go this was a big video and naturally took a bit of research which i've provided links to in the description if i got anything wrong please feel free in fact feel obligated to call me out in the comments like join the discord server and subscribe with notifications on to join the nerd army and become a sigma male
thanks for watching goodbye hey guys instead of the usual meme i just want to add a little addendum here this video really was a lot of work for me if you didn't understand this video entirely that's fine because to be honest i didn't understand entirely going in and i still don't fully understand it if you saw anything in this video that was factually incorrect please do not hesitate to correct me in the comments to contact me as well as that there were actually some tools that i was trying to get running to visualize some of
the graphics rendering this includes the doom vism and headless doom which i've included both of the githubs in the comments section i've also included every source i used in this video was specifically helpful during this video was this article by fabian sunglad i definitely recommend checking it out if this interested you at all please check out these sources for further reading thank you and goodbye
