We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
unique_copy (output.begin(), output.end(), std::back_insert_iteratorstd::string(_justDialogue), [](char a,char b)
=> a = -30 , b = -128
The value comes in like this, and there's an error here
I'm going to use a few terms throughout this video that not everyone might understand.
2 00:00:06,719 --> 00:00:10,960 A plane is a mathematical term for a square or rectangle.
3 00:00:10,960 --> 00:00:14,560 This is mostly the walls, ceiling and floor.
4 00:00:14,560 --> 00:00:19,519 Vertices are the corners of said planes, the singular being vertex.
5 00:00:19,519 --> 00:00:23,519 Polygons are another term for surfaces derived from computer science rather than maths.
6 00:00:23,519 --> 00:00:26,519 It's going to be used interchangeably with plane.
7 00:00:26,559 --> 00:00:31,160 To do something recursively means a process must repeat itself over and over until an
8 00:00:31,160 --> 00:00:33,399 end goal is met to solve a problem.
9 00:00:33,399 --> 00:00:37,079 A data type is a way data is classified in programming.
10 00:00:37,079 --> 00:00:43,000 For example, a string, which are words or a series of letters, and int, which is an
11 00:00:43,000 --> 00:00:44,960 integer, a typical number.
12 00:00:44,960 --> 00:00:50,200 There are different kinds of numbers as well, such as float for precise decimal numbers,
13 00:00:50,200 --> 00:00:53,039 and long for, well, long numbers.
14 00:00:53,039 --> 00:01:02,039 Of the total size of the games industry today, around 20% are games within the shooter genre.
15 00:01:02,039 --> 00:01:07,760 Around a fifth of games in this $300 billion industry are shooters, most of them being
16 00:01:07,760 --> 00:01:09,480 first person shooters.
17 00:01:09,480 --> 00:01:14,379 The amount of money generated by and riding on the success of this singular genre in this
18 00:01:14,379 --> 00:01:16,359 industry is stupefying.
19 00:01:16,359 --> 00:01:21,200 The first person shooter as developed early on was a huge departure from every other kind
20 00:01:21,200 --> 00:01:23,560 of game that existed at the time.
21 00:01:23,560 --> 00:01:28,159 Games at the time, PC games especially, were often slow or methodical.
22 00:01:28,159 --> 00:01:34,040 The personal computer platform was known for careful and considered games, turn-based strategy,
23 00:01:34,040 --> 00:01:37,520 grand RPGs with a slowly unfolding world.
24 00:01:37,520 --> 00:01:41,240 Often times these games would be indistinguishable from a spreadsheet.
25 00:01:41,240 --> 00:01:43,600 Action was the realm of console gaming.
26 00:01:43,600 --> 00:01:47,640 Platformers were the most immediate real-time action-packed games available, and besides
27 00:01:47,640 --> 00:01:52,340 notable games like Duke Nukem and Commander Keen, people didn't really play those kind
28 00:01:52,340 --> 00:01:54,319 of action games on PC.
29 00:01:54,319 --> 00:01:57,319 This was until the advent of the first person shooter.
30 00:01:57,319 --> 00:02:01,299 Suddenly people were hit with this visceral representation of violence.
31 00:02:01,299 --> 00:02:03,599 They represented something which films could not.
32 00:02:03,599 --> 00:02:06,439 You inhabit a world through the lens of the character.
33 00:02:06,439 --> 00:02:10,920 You are closer to the action hero than ever before in any medium in history.
34 00:02:10,920 --> 00:02:16,199 What is widely agreed upon as the first first person shooter ever is Maze War, developed
35 00:02:16,199 --> 00:02:20,799 in 1973, that's the same year Britain joined the European Union, Dark Side of the Moon
36 00:02:20,799 --> 00:02:24,199 was released, and the United States announced it would withdraw from Vietnam.
37 00:02:24,199 --> 00:02:28,759 It was developed for NASA computers by Steve Colleade, Greg Thompson and Howard Palmer.
38 00:02:28,759 --> 00:02:31,679 It was constructed with simple wireframe graphics.
39 00:02:31,679 --> 00:02:36,120 People had the idea of adding multiple players using networking, then connecting over the
40 00:02:36,120 --> 00:02:37,120 ARPANET.
41 00:02:37,120 --> 00:02:38,120 Then it took off.
42 00:02:38,120 --> 00:02:40,799 We saw other first person shooter games after that point.
43 00:02:40,800 --> 00:02:46,600 Spasm or Space Sim in 1974, Battlezone for arcades in 1980.
44 00:02:46,600 --> 00:02:51,520 Besides these few examples, for the majority of the decades following its inception, the
45 00:02:51,520 --> 00:02:56,000 first person perspective was known mostly for its association with the role playing
46 00:02:56,000 --> 00:02:58,320 genre, for example games like Ultima.
47 00:02:58,320 --> 00:03:03,520 Now, first person shooting did technically exist, but you were merely shooting projectiles
48 00:03:03,520 --> 00:03:04,520 at your friends.
49 00:03:04,520 --> 00:03:08,439 You weren't inhabiting a character, you weren't the action hero fighting bad guys,
50 00:03:08,439 --> 00:03:11,359 That was until Wolfenstein 3D.
51 00:03:11,359 --> 00:03:17,000 id Software was founded in 1991 by four former soft disk employees, John and Adrian Carmack,
52 00:03:17,000 --> 00:03:21,240 no relation they just happened to have the same name, Tom Hall and John Romero.
53 00:03:21,240 --> 00:03:24,000 This was the same year the Soviet Union fell.
54 00:03:24,000 --> 00:03:26,340 Carmack is going to be more important later on.
55 00:03:26,340 --> 00:03:31,199 They originally began with a Mario clone named Dangerous Dave before the company was officially
56 00:03:31,199 --> 00:03:32,199 founded.
57 00:03:32,199 --> 00:03:35,560 This was mainly to show off the beginnings of John Carmack's technical wizardry, encoding
58 00:03:35,560 --> 00:03:38,560 an efficient 2D side scrolling graphics renderer.
59 00:03:38,560 --> 00:03:43,780 The early 90s, when everything was a dark and edgy statement, the satanic inversion
60 00:03:43,780 --> 00:03:46,539 between PC and console was no exception.
61 00:03:46,539 --> 00:03:49,560 PC graphics using software rendering were terrible.
62 00:03:49,560 --> 00:03:54,900 John Carmack developed his adaptive tile refresh for the PC to compete with the raw computational
63 00:03:54,900 --> 00:03:58,599 power of the Super Nintendo, a true beast.
64 00:03:58,599 --> 00:04:02,240 Adaptive tile refresh meant that slightly more of the game world could be included in
65 00:04:02,240 --> 00:04:04,640 the screen buffer, just outside of view.
66 00:04:04,640 --> 00:04:07,360 This meant they could render smooth 2D scrolling.
67 00:04:07,360 --> 00:04:11,400 It also made the sprite animations independent from screen scrolling.
68 00:04:11,400 --> 00:04:16,120 This little bit of code magic powered their games, including the Commander Keen series.
69 00:04:16,120 --> 00:04:20,520 The Commander Keen series was spread through shareware, with subsequent episodes releasing
70 00:04:20,520 --> 00:04:24,340 over the next year or so for purchase from Apogee, their publisher.
71 00:04:24,340 --> 00:04:29,280 This shareware model would be important because it would be used in their subsequent games.
72 00:04:29,280 --> 00:04:33,200 Speaking of subsequent games…
73 00:04:33,279 --> 00:04:36,879 Wolfenstein 3D began development in 1991.
74 00:04:36,879 --> 00:04:42,199 It would use the raycasting technique earlier employed in id's Catacomb 3D.
75 00:04:42,199 --> 00:04:47,079 Raycasting was a rendering technique necessitated again by the limited processing power of PCs
76 00:04:47,079 --> 00:04:48,079 at the time.
77 00:04:48,079 --> 00:04:51,319 PC master race just can't stop losing.
78 00:04:51,319 --> 00:04:55,800 PCs almost all used software rendering, rather than a dedicated graphics chip.
79 00:04:55,800 --> 00:05:00,879 The shareware model involved getting the game on as many PCs as possible.
80 00:05:00,879 --> 00:05:03,079 Raycasting was the solution to help them do this.
81 00:05:03,079 --> 00:05:07,479 Raycasting allowed their game to run on basically any PC.
82 00:05:07,479 --> 00:05:11,740 Raycasting means you're able to draw only the surfaces which are in the player's field
83 00:05:11,740 --> 00:05:12,740 of view.
84 00:05:12,740 --> 00:05:15,000 This helped massively in saving processing power.
85 00:05:15,000 --> 00:05:16,000 But how does it work?
86 00:05:16,000 --> 00:05:21,519 In effect, a ray is cast, from the player to the geometry, to the nearest object blocking
87 00:05:21,519 --> 00:05:22,519 its path.
88 00:05:22,519 --> 00:05:25,839 In Wolfenstein, none of the levels were truly 3D.
89 00:05:25,839 --> 00:05:28,799 Every level was drawn out on a flat 2D plane.
90 00:05:28,800 --> 00:05:34,120 The program scans horizontally, checking that every pixel on the horizontal axis has something
91 00:05:34,120 --> 00:05:35,120 drawn in it.
92 00:05:35,120 --> 00:05:39,480 If there's nothing drawn in a position, a pixel column will be drawn out.
93 00:05:39,480 --> 00:05:43,699 This is simplified from the process of ray tracing, where this process is done for every
94 00:05:43,699 --> 00:05:46,600 single pixel, rather than every pixel column.
95 00:05:46,600 --> 00:05:51,040 The distance between the viewer, or the camera or player, they all have the same meaning,
96 00:05:51,040 --> 00:05:53,439 and the nearest piece of geometry, is obtained.
97 00:05:53,439 --> 00:05:58,400 The height of the pixel column is calculated using the distance from point of intersection
98 00:05:58,400 --> 00:06:00,880 in the direction the player is facing.
99 00:06:00,880 --> 00:06:04,440 It uses trigonometry to find this point of intersection.
100 00:06:04,440 --> 00:06:09,240 This effectively allowed them to give the illusion of distance, to render a 3D scene.
101 00:06:09,240 --> 00:06:14,620 This makes the process of rendering 3D much easier, as a line, that line being distance
102 00:06:14,620 --> 00:06:20,560 from player to geometry, directly transforms to a line, that being the height of the rendered
103 00:06:20,560 --> 00:06:21,560 column.
104 00:06:21,560 --> 00:06:24,480 This process is done multiple times every single second.
105 00:06:24,560 --> 00:06:29,360 The planes in the scene had been texture mapped, where an image is applied to a 3D surface.
106 00:06:29,360 --> 00:06:34,560 When the columns are drawn, they are really drawing slices of these wall textures at different
107 00:06:34,560 --> 00:06:35,560 sizes.
108 00:06:35,560 --> 00:06:40,319 The height of the column being drawn is smaller when the plane, that being the wall, is further
109 00:06:40,319 --> 00:06:41,319 away from you.
110 00:06:41,319 --> 00:06:45,879 The textures are scaled appropriately to the size of the wall, relative to the player.
111 00:06:45,879 --> 00:06:49,319 This gave the world of Wolfenstein so much believability for the time.
112 00:06:49,319 --> 00:06:52,839 You were no longer just navigating wireframe mazes.
113 00:06:52,839 --> 00:06:57,959 You were an action hero, BJ Blazkowicz, infiltrating a Nazi castle.
114 00:06:57,959 --> 00:07:00,920 The walls were adorned with flags of the German Reich.
115 00:07:00,920 --> 00:07:03,199 You felt closer to the world than ever before.
116 00:07:03,199 --> 00:07:06,240 You were interacting with a true 3D space.
117 00:07:06,240 --> 00:07:08,500 This process was, however, flawed.
118 00:07:08,500 --> 00:07:13,279 In Wolfenstein 3D, there was no verticality at all, no difference in elevation, only the
119 00:07:13,279 --> 00:07:16,800 walls had texture, the ceiling and floor had to be flat colours.
120 00:07:16,800 --> 00:07:20,680 If they wanted texture on the ceiling and floor, they would have had to add horizontal
121 00:07:20,680 --> 00:07:21,680 scanlines.
122 00:07:21,680 --> 00:07:24,079 You were still ultimately navigating a maze.
123 00:07:24,079 --> 00:07:27,879 A colourful maze with Nazis in it, but a maze nonetheless.
124 00:07:27,879 --> 00:07:31,319 Wolfenstein 3D was released in May 1992.
125 00:07:31,319 --> 00:07:34,960 The sequel, Spear of Destiny, was released later in the same year.
126 00:07:34,960 --> 00:07:39,560 While the rest of the id team was working on Spear of Destiny, John Carmack, the ascetic,
127 00:07:39,560 --> 00:07:42,560 high priest of technology, locked himself away to study.
128 00:07:42,560 --> 00:07:47,199 He would brainstorm the revolutionary tech that would power their next massive game,
129 00:07:47,199 --> 00:07:51,480 the next game that the rest of the team would start working on in September 1992.
130 00:07:51,480 --> 00:07:56,079 It would be something inspired by evil dead, brutal and violent.
131 00:07:56,079 --> 00:08:02,040 The name, Green and Pissed, was ultimately passed up for the much snappier Doom.
132 00:08:02,040 --> 00:08:08,000 Doom would launch in 1993, the game would truly be able to transport you into a world.
133 00:08:08,000 --> 00:08:10,620 The levels truly felt like places.
134 00:08:10,660 --> 00:08:16,100 The architecture of Doom consisted of supernatural science facilities, with Giger-esque and hellish
135 00:08:16,100 --> 00:08:17,740 environments as well.
136 00:08:17,740 --> 00:08:23,060 The enemies were a combination of horror and sci-fi with cybernetically enhanced demons.
137 00:08:23,060 --> 00:08:27,959 The architecture, over the top setting and violence was inspired by films such as Evil
138 00:08:27,959 --> 00:08:29,180 Dead and Alien.
139 00:08:29,180 --> 00:08:34,620 The floors could now be angled, they could now have multiple levels with stairs and elevators.
140 00:08:34,620 --> 00:08:38,120 Tools of toxic fluid surrounded these risen platforms.
141 00:08:38,120 --> 00:08:40,220 It was truly 3D.
142 00:08:40,220 --> 00:08:41,540 But it wasn't really.
143 00:08:41,540 --> 00:08:46,180 They were yet to achieve the full 6 degrees of freedom that John Romero wanted.
144 00:08:46,180 --> 00:08:47,899 This wouldn't happen until Quake.
145 00:08:47,899 --> 00:08:51,700 Rumours couldn't be stacked on top of each other, there was no vertical aim, the game
146 00:08:51,700 --> 00:08:54,779 was entirely played on the horizontal axis.
147 00:08:54,779 --> 00:08:58,560 The thing is, vertical aim was actually possible at the time.
148 00:08:58,560 --> 00:09:02,860 They could have limited the enemies' vertical hitboxes to the size of the sprite, but they
149 00:09:02,860 --> 00:09:03,860 didn't.
150 00:09:03,860 --> 00:09:06,620 Not because they couldn't, but to save processing power.
151 00:09:06,620 --> 00:09:09,779 You see, Doom was still using software rendering.
152 00:09:09,819 --> 00:09:13,939 This shareware model relied on getting their games on as many computers as possible, like
153 00:09:13,939 --> 00:09:14,939 I said.
154 00:09:14,939 --> 00:09:18,740 It was essentially the beginning of the free to play game model we have today.
155 00:09:18,740 --> 00:09:22,980 They aimed for the IBM PC, for machines running DOS.
156 00:09:22,980 --> 00:09:27,480 They had to sell their game to university students and wagies who were bored at work
157 00:09:27,480 --> 00:09:29,500 so they could run office tournaments.
158 00:09:29,500 --> 00:09:33,860 They didn't calculate the enemies' vertical hitbox so that they could save memory.
159 00:09:33,860 --> 00:09:38,419 They didn't want to give the enemies' hitboxes a height value, just have another factor to
160 00:09:38,419 --> 00:09:39,419 calculate.
161 00:09:39,459 --> 00:09:43,059 These levels were drawn on a 2D plane, like Wolfenstein.
162 00:09:43,059 --> 00:09:46,099 Just this time, the map creator is quite different.
163 00:09:46,099 --> 00:09:50,659 The ground is divided into sectors, this will be very important later.
164 00:09:50,659 --> 00:09:55,139 Each sector has two associated values, ceiling height and floor height.
165 00:09:55,139 --> 00:09:59,099 Well, it has several associated values, but those are two important ones.
166 00:09:59,099 --> 00:10:03,339 This is also why one room could not be placed above another and why every surface had to
167 00:10:03,339 --> 00:10:06,339 be made out of a flat square or rectangle.
168 00:10:06,340 --> 00:10:10,500 Another reason that vertical aim couldn't have worked is due to how the texture mapping
169 00:10:10,500 --> 00:10:11,500 worked.
170 00:10:11,500 --> 00:10:16,060 One game that did have vertical aim and levels on top of each other, before Quake and not
171 00:10:16,060 --> 00:10:19,420 that long after Doom, was Bungie's Marathon.
172 00:10:19,420 --> 00:10:22,820 And look what happens when you look up and down in that game.
173 00:10:22,820 --> 00:10:25,379 The textures start to distort.
174 00:10:25,379 --> 00:10:29,379 This is because the game, like Doom, uses affine texture mapping.
175 00:10:29,379 --> 00:10:34,780 This, like many of the other methods, was done to save memory on the processor by taking
176 00:10:34,779 --> 00:10:37,139 advantage of CPU caching.
177 00:10:37,139 --> 00:10:43,699 Basically, what happens is that texture coordinates are linearly interpolated, using screen space
178 00:10:43,699 --> 00:10:49,699 distance between vertices, rather than the actual 3D in-engine distance between them.
179 00:10:49,699 --> 00:10:54,000 The distance between points on a plane remains the same when you look up and down.
180 00:10:54,000 --> 00:10:58,379 What this means is that perspective when looking up and down is not accounted for.
181 00:10:58,379 --> 00:11:02,240 You know how pixels on a texture start to warp as you get closer?
182 00:11:02,240 --> 00:11:07,639 It looks like a straight line from far away begins to turn inward as closer pixels get
183 00:11:07,639 --> 00:11:11,399 larger, while more distant pixels get smaller.
184 00:11:11,399 --> 00:11:17,279 This doesn't happen in Doom, because accounting for perspective is taxing on 90s computers.
185 00:11:17,279 --> 00:11:21,539 You know how the game only draws things in columns to save processing time?
186 00:11:21,539 --> 00:11:25,840 They'd have had to do vertical scans as well as horizontal scans.
187 00:11:25,840 --> 00:11:32,080 Newer ports of Doom with newer rendering engines made for new hardware like GZDoom obviously
188 00:11:32,920 --> 00:11:33,920 don't have this limitation.
189 00:11:33,920 --> 00:11:37,960 As such, they use more current texture mapping and don't have this issue.
190 00:11:37,960 --> 00:11:40,720 But all of these concessions weren't enough.
191 00:11:40,720 --> 00:11:45,560 John Carmack's coding brilliance met its most devious enemy yet.
192 00:11:45,560 --> 00:11:46,560 Stairs.
193 00:11:46,560 --> 00:11:51,720 John Romero came out with a really way-out and strange idea on his early incarnation
194 00:11:51,720 --> 00:11:52,720 of E1M2.
195 00:11:52,720 --> 00:11:58,720 Yes, he wanted to mix things up with the earth-shattering invention of stairs.
196 00:11:58,720 --> 00:12:03,600 You see, just raycasting alone wasn't enough to efficiently optimise the game.
197 00:12:03,600 --> 00:12:07,680 Raycasting saves memory by only rendering things which are visible to the player.
198 00:12:07,680 --> 00:12:12,519 However, surfaces on the inside of these stairs were visible to the existing algorithm.
199 00:12:12,519 --> 00:12:15,320 Thus, they were drawn when they shouldn't have been.
200 00:12:15,320 --> 00:12:20,360 You see, for 3D rendering to not waste performance, they need to draw as few surfaces, as few
201 00:12:20,360 --> 00:12:21,840 planes as possible.
202 00:12:21,840 --> 00:12:27,639 This necessitates occlusion culling, or visible surface determination, or backface culling.
203 00:12:27,679 --> 00:12:33,319 Basically, the renderer should only draw what is in the player's field of view.
204 00:12:33,319 --> 00:12:37,080 There need to be absolutely no overdraw whatsoever.
205 00:12:37,080 --> 00:12:43,080 Adding height as a variable, such as with Romero's stairs, requires a much more sophisticated
206 00:12:43,080 --> 00:12:49,000 algorithm than was present in Wolfenstein, and in id's existing rendering engine.
207 00:12:49,000 --> 00:12:53,240 There are many different rendering algorithms out there, it seems that we need to dip into
208 00:12:53,240 --> 00:12:58,680 the hypothetical algorithms to start trawling the literature for some better algorithms.
209 00:12:58,680 --> 00:13:00,440 Let's explore some of the options.
210 00:13:00,440 --> 00:13:04,120 There's the painter's algorithm, named so because, like in a painting, the background
211 00:13:04,120 --> 00:13:07,000 is rendered first with detail layered on top.
212 00:13:07,000 --> 00:13:10,960 Basically, the polygons are sorted by their distance from the viewer, and the more distant
213 00:13:10,960 --> 00:13:14,759 polygons are rendered first, and the closest polygon is rendered last.
214 00:13:14,759 --> 00:13:17,399 It is easily the most simple solution.
215 00:13:17,399 --> 00:13:24,159 It was developed in 1972, the year MASH started, as an easy to implement solution for CAD.
216 00:13:24,159 --> 00:13:29,399 It also has the worst possible case for space complexity, meaning it takes up as much memory
217 00:13:29,399 --> 00:13:31,819 as an algorithm possibly could.
218 00:13:31,819 --> 00:13:34,639 Every single surface in the field of view is drawn.
219 00:13:34,639 --> 00:13:37,120 Obviously, this isn't a good fit.
220 00:13:37,120 --> 00:13:41,399 It's more of an example from the early days of exactly what not to do.
221 00:13:41,399 --> 00:13:43,039 There's also Warnock's algorithm.
222 00:13:43,240 --> 00:13:47,439 John Warnock was the founder of Adobe, and this algorithm originated in his doctoral
223 00:13:47,439 --> 00:13:52,879 thesis in 1969, the year man landed on the moon and In the Court of the Crimson King
224 00:13:52,879 --> 00:13:53,879 was released.
225 00:13:53,879 --> 00:13:57,899 Essentially, it recursively subdivides the screen into four parts.
226 00:13:57,899 --> 00:14:01,839 What this means is it splits the screen into four windows and splits each window into four
227 00:14:01,839 --> 00:14:02,959 smaller windows.
228 00:14:02,959 --> 00:14:08,000 It does this again and again until each window is trivial to render, meaning it has only
229 00:14:08,000 --> 00:14:10,719 one or zero polygons present.
230 00:14:10,720 --> 00:14:14,960 The algorithm also checks if multiple polygons are within one window.
231 00:14:14,960 --> 00:14:19,040 If the closest polygon covers the whole window, then it is drawn.
232 00:14:19,040 --> 00:14:23,440 This is more efficient than Painter's algorithm as it renders front to back, but it's still
233 00:14:23,440 --> 00:14:25,160 not very well suited.
234 00:14:25,160 --> 00:14:30,800 It will eventually keep subdividing to a ridiculous degree, to the point where a window is smaller
235 00:14:30,800 --> 00:14:31,800 than a pixel.
236 00:14:31,800 --> 00:14:34,399 Yeah, this ain't a good fit for a game.
237 00:14:34,399 --> 00:14:38,180 You could do a z-buffer for every pixel you want to draw, check if there's anything in
238 00:14:38,180 --> 00:14:39,180 front of it.
239 00:14:39,180 --> 00:14:40,740 And check on every single pixel?
240 00:14:40,740 --> 00:14:42,740 Yeah, there's no chance in hell.
241 00:14:42,740 --> 00:14:47,700 The final solution does kinda use a z-buffer, but it doesn't do that check on every single
242 00:14:47,700 --> 00:14:50,780 pixel, it finds a much more efficient way to do it.
243 00:14:50,780 --> 00:14:51,780 No.
244 00:14:51,780 --> 00:14:57,820 In order to truly revolutionize not just gaming, but 3D graphics forever, our protagonist,
245 00:14:57,820 --> 00:15:03,340 John Carmack, needs to go to a much more inspired source, something that hadn't actually been
246 00:15:03,340 --> 00:15:04,960 implemented before.
247 00:15:04,960 --> 00:15:06,960 Something he'd just read in a white paper.
248 00:15:06,960 --> 00:15:07,960 Just a concept.
249 00:15:07,960 --> 00:15:13,019 Yes, how common is it in gaming to see people run into optimization issues and seek out
250 00:15:13,019 --> 00:15:17,259 a white paper to solve their problem, because nobody else had done it before?
251 00:15:17,259 --> 00:15:19,139 Yes, that's Carmack for you.
252 00:15:19,139 --> 00:15:23,720 We needed a renderer that would draw objects closest to the player to furthest away until
253 00:15:23,720 --> 00:15:27,580 every pixel was written to, that had no overdraw.
254 00:15:27,580 --> 00:15:32,879 The solution was in a 1980 white paper, as the same year Genesis released the reclaimed
255 00:15:32,879 --> 00:15:36,580 album, Duke, where they really came into their own.
256 00:15:37,960 --> 00:15:45,820 This 1980 white paper by Bruce Nailup was given the humble title, On Visible Surface
257 00:15:45,820 --> 00:15:49,060 Generation by Apriori Tree Structures.
258 00:15:49,060 --> 00:15:55,460 It described a rendering model we know as Binary Space Partitioning, or BSP for short.
259 00:15:55,460 --> 00:15:58,700 This was the method that would change gaming for years.
260 00:15:58,700 --> 00:16:02,300 This wasn't the first time Binary Space Partitioning was alluded to.
261 00:16:02,300 --> 00:16:08,520 A 1969 study by the Air Force of the good ol' US of A alluded to the use of partitioning
262 00:16:08,520 --> 00:16:12,000 3D scenes to solve the visible surface problem.
263 00:16:12,000 --> 00:16:17,340 The study was conducted to determine the viability of 3D for flight simulation.
264 00:16:17,340 --> 00:16:21,380 We can thank the armed forces of the United States for giving us doom.
265 00:16:21,380 --> 00:16:24,900 They explored using a matrix to track which objects are occluded.
266 00:16:24,900 --> 00:16:29,160 These of course wouldn't do so well as the size of the matrix would need to be the square
267 00:16:29,160 --> 00:16:31,760 of the number of objects in a scene.
268 00:16:31,759 --> 00:16:33,620 That wouldn't scale very well.
269 00:16:33,620 --> 00:16:39,200 It wasn't until 1980 that Binary Space Partitioning was properly realized in the white paper that
270 00:16:39,200 --> 00:16:43,860 would reach John Carmack alongside its core tenant, the binary tree.
271 00:16:43,860 --> 00:16:46,740 But what is Binary Space Partitioning anyway?
272 00:16:46,740 --> 00:16:48,779 Well, the name gives you a clue.
273 00:16:48,779 --> 00:16:52,080 Is partitioning space in a 3D environment?
274 00:16:52,080 --> 00:16:54,939 This is done using a BSP tree.
275 00:16:54,939 --> 00:16:57,100 What is a BSP tree you may ask?
276 00:16:57,100 --> 00:17:02,040 In computer science, a tree is a data structure used as a mathematical model for displaying
277 00:17:02,040 --> 00:17:03,560 certain data types.
278 00:17:03,560 --> 00:17:08,720 It's separated into nodes with parent nodes that have child nodes.
279 00:17:08,720 --> 00:17:13,279 BSP uses binary trees, binary essentially meaning two.
280 00:17:13,279 --> 00:17:18,759 A binary tree is a tree where there are two or less child nodes stemming from any given
281 00:17:18,759 --> 00:17:20,559 parent, from any node.
282 00:17:20,559 --> 00:17:23,380 There are never more than two child nodes.
283 00:17:23,380 --> 00:17:28,160 This is as opposed to a non-binary tree, which is a tree that has dyed hair and a gender
284 00:17:28,160 --> 00:17:29,320 studies degree.
285 00:17:29,320 --> 00:17:34,800 The data stored in the nodes of the binary tree are the sub-sectors of the map.
286 00:17:34,800 --> 00:17:39,640 Sub-sectors being smaller parts of those map sectors I spoke about earlier.
287 00:17:39,640 --> 00:17:45,360 Remember, each map is designed on a flat 2D map editor, with each sector having associated
288 00:17:45,360 --> 00:17:46,600 height values.
289 00:17:46,600 --> 00:17:51,880 The genius is that the map is sliced up via binary space partitioning after the map is
290 00:17:51,880 --> 00:17:52,880 built.
291 00:17:52,880 --> 00:17:58,580 Hard work is done when the map is created, rather than by the processor at runtime while
292 00:17:58,580 --> 00:18:00,340 the player is playing the game.
293 00:18:00,340 --> 00:18:06,180 The map is already split, already partitioned when the player loads it, reducing processing
294 00:18:06,180 --> 00:18:07,840 needed at runtime.
295 00:18:07,840 --> 00:18:12,980 To create the binary tree, a root node is established covering the whole map.
296 00:18:12,980 --> 00:18:19,460 After this, the map is recursively subdivided along every plane until only convex sub-sectors
297 00:18:19,460 --> 00:18:20,460 are left.
298 00:18:20,480 --> 00:18:24,120 The sectors are carved into smaller sub-sectors.
299 00:18:24,120 --> 00:18:28,900 The entire map is essentially cut in two along every single wall.
300 00:18:28,900 --> 00:18:33,799 Every time the map is cut in half, the two halves are added as nodes at the bottom of
301 00:18:33,799 --> 00:18:34,840 the tree.
302 00:18:34,840 --> 00:18:40,400 By the end, you're left with a tree where each node at the bottom of the tree represents
303 00:18:40,400 --> 00:18:42,000 a distinct sub-sector.
304 00:18:42,000 --> 00:18:45,539 Remember, this tree is entirely conceptual.
305 00:18:45,539 --> 00:18:47,500 It doesn't actually exist.
306 00:18:47,519 --> 00:18:52,920 So long as the planes don't move – vertical movement is accepted from this because vertical
307 00:18:52,920 --> 00:18:57,960 movement is a separate value – the same BSP tree can be used.
308 00:18:57,960 --> 00:19:03,480 Doom's BSP tree generation was done after levels were complete and would search for
309 00:19:03,480 --> 00:19:09,000 the best possible tree, that being the one that generates the fewest binary tree nodes.
310 00:19:09,000 --> 00:19:13,240 A binary search is performed to determine what sector the player is in.
311 00:19:13,259 --> 00:19:18,660 A binary search is when an array of pre-sorted data is searched through by continually halving
312 00:19:18,660 --> 00:19:19,660 said array.
313 00:19:19,660 --> 00:19:24,740 A search through a binary tree is, by its nature, a binary search, because every time
314 00:19:24,740 --> 00:19:29,079 you go down a node, you're removing half of the possibilities.
315 00:19:29,079 --> 00:19:33,859 After the player's sector is determined using this binary search, the sub-sectors
316 00:19:33,859 --> 00:19:38,279 are then sorted by their distance from the player – closest to furthest.
317 00:19:38,279 --> 00:19:42,279 The tree is iterated through to determine which planes to draw.
318 00:19:42,299 --> 00:19:47,220 The horizontal scanlines from raycasting are still used to track the parts of the screen
319 00:19:47,220 --> 00:19:48,859 that have been drawn over.
320 00:19:48,859 --> 00:19:53,619 This way they are able to render front to back and ensure that there is no overdraw.
321 00:19:53,619 --> 00:19:57,859 When each node is passed over in the iteration, a few things are checked.
322 00:19:57,859 --> 00:20:00,019 Has that area already been painted over?
323 00:20:00,019 --> 00:20:02,339 If so, don't bother drawing it.
324 00:20:02,339 --> 00:20:08,660 When a plane, polygon or wall is drawn, it is akin to a curtain being drawn left to right.
325 00:20:08,720 --> 00:20:14,200 To unveil an area, so to speak, whenever a curtain is seen by the player, it is unveiled
326 00:20:14,200 --> 00:20:16,040 from closest to the furthest.
327 00:20:16,040 --> 00:20:20,759 To be exact, it's the closest 256 walls that are displayed.
328 00:20:20,759 --> 00:20:26,240 Remember how height of the pixel columns drawn on screen depended on distance from the player?
329 00:20:26,240 --> 00:20:32,120 For Doom, this required determining the angle of both ends of every wall, relative to the
330 00:20:32,120 --> 00:20:33,440 player's field of view.
331 00:20:33,440 --> 00:20:38,580 In the early 90s, most processors didn't have dedicated floating-point capability.
332 00:20:38,599 --> 00:20:41,599 This is a float in programming, if you've ever heard of that.
333 00:20:41,599 --> 00:20:45,359 Basically a data type for very precise decimal numbers.
334 00:20:45,359 --> 00:20:51,659 The Doom engine had to use binary angle measurements, which avoid floats, and used a lookup table
335 00:20:51,659 --> 00:20:54,000 to determine the x coordinates.
336 00:20:54,000 --> 00:20:56,960 A lookup table is essentially a cheat sheet.
337 00:20:56,960 --> 00:21:02,359 Instead of the processor doing the maths itself, it just looks up the answer in this lookup table.
338 00:21:02,359 --> 00:21:08,559 They also used these angles for backface culling, with a simple and elegant piece of mathematics
339 00:21:08,559 --> 00:21:14,379 Backface culling basically means the renderer doesn't draw the inside of every polygon.
340 00:21:14,379 --> 00:21:18,099 It only draws the part on the outside that you actually see.
341 00:21:18,099 --> 00:21:23,339 The walls are rendered first as pixel columns from front to back, then the ceilings and
342 00:21:23,339 --> 00:21:25,819 floors using pixel rows.
343 00:21:25,819 --> 00:21:31,500 The objects such as barrels and enemies are rendered from the furthest to the closest.
344 00:21:31,500 --> 00:21:37,599 The ceilings and floors are determined using visplane underscore t, or visplanes.
345 00:21:37,600 --> 00:21:41,900 Plains were determined using height values within each sector.
346 00:21:41,900 --> 00:21:46,940 Visplanes are not constrained to single sectors, and will be continuous provided they all possess
347 00:21:46,940 --> 00:21:50,600 the same height, illumination and textures.
348 00:21:50,600 --> 00:21:53,180 Pixel rows are drawn top to bottom.
349 00:21:53,180 --> 00:21:59,080 One final thing you may wonder about Doom's graphics is why are all the enemies just pictures
350 00:21:59,080 --> 00:22:00,780 facing towards you?
351 00:22:00,780 --> 00:22:04,880 Probably something to do with them being what we call front-facing sprites.
352 00:22:04,880 --> 00:22:08,980 They're rendered last, and like I said, furthest to closest.
353 00:22:08,980 --> 00:22:11,340 That's the opposite order to the geometry.
354 00:22:11,340 --> 00:22:16,340 They are just pictures, taken from the data files and projected onto screen.
355 00:22:16,340 --> 00:22:18,840 Of course, they're a range of pictures.
356 00:22:18,840 --> 00:22:24,020 The one that is drawn depends on the player's location relative to the enemy, and the direction
357 00:22:24,020 --> 00:22:25,500 the enemy is facing.
358 00:22:25,500 --> 00:22:29,040 The enemies do actually have a full 3D hitbox.
359 00:22:29,040 --> 00:22:34,260 The pictures, as most fans know, are actually from real pictures taken of sculptures made
360 00:22:34,259 --> 00:22:35,400 by the artists.
361 00:22:35,400 --> 00:22:41,519 So, John Carmack was faced with a fierce issue in the problem of visible surface determination.
362 00:22:41,519 --> 00:22:46,759 He had to find a solution that was both incredibly fast and very accurate.
363 00:22:46,759 --> 00:22:53,000 BSP doesn't completely solve the visible surface determination problem, but it is one
364 00:22:53,000 --> 00:22:56,900 of the most reliable and efficient methods of optimisation.
365 00:22:56,900 --> 00:22:59,039 It saw massive acceptance.
366 00:22:59,039 --> 00:23:04,339 BSPs were evolved and made their way into Quake's dramatically improved game engine
367 00:23:04,339 --> 00:23:09,819 when they took on Michael Abrash and finally figured out the full six degrees of freedom.
368 00:23:09,819 --> 00:23:15,220 From there, it was in every FPS, and I mean all of them.
369 00:23:15,220 --> 00:23:16,859 Half-Life and Half-Life 2?
370 00:23:16,859 --> 00:23:17,859 Every Source game.
371 00:23:17,859 --> 00:23:19,819 Counter-Strike to Left 4 Dead.
372 00:23:19,819 --> 00:23:21,500 The Halo series used it.
373 00:23:21,500 --> 00:23:24,579 You know the Scarab from Halo 2 is actually a BSP object?
374 00:23:24,579 --> 00:23:27,980 Yes, it's a moving piece of level geometry.
375 00:23:27,980 --> 00:23:33,039 Many would say it's a sign of Carmack's genius that he took an idea from concept to
376 00:23:33,039 --> 00:23:34,839 mainstream solution.
377 00:23:34,839 --> 00:23:41,839 He did all this crazy work in between supercharging Ferraris and becoming a judo master.
378 00:23:41,839 --> 00:23:44,519 One time, he got locked inside a building.
379 00:23:44,519 --> 00:23:49,759 Instead of, say, waiting for security or calling a locksmith, he devised a brilliant solution.
380 00:23:49,759 --> 00:23:54,759 He'd luckily gone to a Renaissance Fair earlier, where he bought a medieval battle axe.
381 00:23:54,759 --> 00:23:58,779 Also, naturally, he smashed down the door with his mighty axe.
382 00:23:58,779 --> 00:24:01,539 He was rich so he could afford to get the door fixed.
383 00:24:01,539 --> 00:24:07,379 He truly is a unique figure in the gaming industry, and you can see why he's so highly
384 00:24:07,379 --> 00:24:08,379 respected.
385 00:24:08,379 --> 00:24:12,019 If you made it this far, comment, thank you John Carmack.
386 00:24:12,019 --> 00:24:17,700 The use of BSP trees has begun to be replaced over the last few years.
387 00:24:17,700 --> 00:24:20,740 Developers instead opt for things like static meshes.
388 00:24:20,740 --> 00:24:25,620 With more powerful hardware now, they can afford some level of overdraw.
389 00:24:25,620 --> 00:24:30,400 Other methods give artists more creative freedom and a much quicker workflow.
390 00:24:30,400 --> 00:24:36,420 BSP often leads to the distinct blocky look that many old games had.
391 00:24:36,420 --> 00:24:41,839 One could certainly argue that these technical limitations are what gave source maps and
392 00:24:41,839 --> 00:24:45,720 early 2000s maps in general their distinct charm.
393 00:24:45,720 --> 00:24:47,079 Their soul.
394 00:24:47,079 --> 00:24:54,079 With stark and distinct architectural choices, some magic is truly lost in busy modern day
395 00:24:54,079 --> 00:24:55,399 maps.
396 00:24:55,399 --> 00:25:01,119 Many new games have actually tried to go back to recreating these older, cleaner, more distinct
397 00:25:01,119 --> 00:25:02,119 visuals.
398 00:25:02,119 --> 00:25:07,639 BSP is still occasionally used today in prototyping levels for games, quickly blocking them out.
399 00:25:07,639 --> 00:25:11,279 It's of course still used in games such as Counter Strike Go.
400 00:25:11,279 --> 00:25:16,000 This was a big video, and naturally it took a bit of research, which I've provided links
401 00:25:16,000 --> 00:25:17,539 to in the description.
402 00:25:17,539 --> 00:25:23,960 If I got anything wrong, please feel free, in fact feel obligated, to call me out in
403 00:25:23,960 --> 00:25:24,960 the comments.
404 00:25:24,960 --> 00:25:31,359 Like, join the Discord server and subscribe with notifications on to join the nerd army
405 00:25:31,359 --> 00:25:33,000 and become a sigma male.
406 00:25:33,000 --> 00:25:34,799 Thanks for watching, goodbye.
407 00:26:03,000 --> 00:26:24,680 Bye.
The text was updated successfully, but these errors were encountered:
No branches or pull requests
unique_copy (output.begin(), output.end(), std::back_insert_iteratorstd::string(_justDialogue),
[](char a,char b)
=> a = -30 , b = -128
The value comes in like this, and there's an error here
srt
1 00:00:00,000 --> 00:00:06,719I'm going to use a few terms throughout this video that not everyone might understand.
2
00:00:06,719 --> 00:00:10,960
A plane is a mathematical term for a square or rectangle.
3
00:00:10,960 --> 00:00:14,560
This is mostly the walls, ceiling and floor.
4
00:00:14,560 --> 00:00:19,519
Vertices are the corners of said planes, the singular being vertex.
5
00:00:19,519 --> 00:00:23,519
Polygons are another term for surfaces derived from computer science rather than maths.
6
00:00:23,519 --> 00:00:26,519
It's going to be used interchangeably with plane.
7
00:00:26,559 --> 00:00:31,160
To do something recursively means a process must repeat itself over and over until an
8
00:00:31,160 --> 00:00:33,399
end goal is met to solve a problem.
9
00:00:33,399 --> 00:00:37,079
A data type is a way data is classified in programming.
10
00:00:37,079 --> 00:00:43,000
For example, a string, which are words or a series of letters, and int, which is an
11
00:00:43,000 --> 00:00:44,960
integer, a typical number.
12
00:00:44,960 --> 00:00:50,200
There are different kinds of numbers as well, such as float for precise decimal numbers,
13
00:00:50,200 --> 00:00:53,039
and long for, well, long numbers.
14
00:00:53,039 --> 00:01:02,039
Of the total size of the games industry today, around 20% are games within the shooter genre.
15
00:01:02,039 --> 00:01:07,760
Around a fifth of games in this $300 billion industry are shooters, most of them being
16
00:01:07,760 --> 00:01:09,480
first person shooters.
17
00:01:09,480 --> 00:01:14,379
The amount of money generated by and riding on the success of this singular genre in this
18
00:01:14,379 --> 00:01:16,359
industry is stupefying.
19
00:01:16,359 --> 00:01:21,200
The first person shooter as developed early on was a huge departure from every other kind
20
00:01:21,200 --> 00:01:23,560
of game that existed at the time.
21
00:01:23,560 --> 00:01:28,159
Games at the time, PC games especially, were often slow or methodical.
22
00:01:28,159 --> 00:01:34,040
The personal computer platform was known for careful and considered games, turn-based strategy,
23
00:01:34,040 --> 00:01:37,520
grand RPGs with a slowly unfolding world.
24
00:01:37,520 --> 00:01:41,240
Often times these games would be indistinguishable from a spreadsheet.
25
00:01:41,240 --> 00:01:43,600
Action was the realm of console gaming.
26
00:01:43,600 --> 00:01:47,640
Platformers were the most immediate real-time action-packed games available, and besides
27
00:01:47,640 --> 00:01:52,340
notable games like Duke Nukem and Commander Keen, people didn't really play those kind
28
00:01:52,340 --> 00:01:54,319
of action games on PC.
29
00:01:54,319 --> 00:01:57,319
This was until the advent of the first person shooter.
30
00:01:57,319 --> 00:02:01,299
Suddenly people were hit with this visceral representation of violence.
31
00:02:01,299 --> 00:02:03,599
They represented something which films could not.
32
00:02:03,599 --> 00:02:06,439
You inhabit a world through the lens of the character.
33
00:02:06,439 --> 00:02:10,920
You are closer to the action hero than ever before in any medium in history.
34
00:02:10,920 --> 00:02:16,199
What is widely agreed upon as the first first person shooter ever is Maze War, developed
35
00:02:16,199 --> 00:02:20,799
in 1973, that's the same year Britain joined the European Union, Dark Side of the Moon
36
00:02:20,799 --> 00:02:24,199
was released, and the United States announced it would withdraw from Vietnam.
37
00:02:24,199 --> 00:02:28,759
It was developed for NASA computers by Steve Colleade, Greg Thompson and Howard Palmer.
38
00:02:28,759 --> 00:02:31,679
It was constructed with simple wireframe graphics.
39
00:02:31,679 --> 00:02:36,120
People had the idea of adding multiple players using networking, then connecting over the
40
00:02:36,120 --> 00:02:37,120
ARPANET.
41
00:02:37,120 --> 00:02:38,120
Then it took off.
42
00:02:38,120 --> 00:02:40,799
We saw other first person shooter games after that point.
43
00:02:40,800 --> 00:02:46,600
Spasm or Space Sim in 1974, Battlezone for arcades in 1980.
44
00:02:46,600 --> 00:02:51,520
Besides these few examples, for the majority of the decades following its inception, the
45
00:02:51,520 --> 00:02:56,000
first person perspective was known mostly for its association with the role playing
46
00:02:56,000 --> 00:02:58,320
genre, for example games like Ultima.
47
00:02:58,320 --> 00:03:03,520
Now, first person shooting did technically exist, but you were merely shooting projectiles
48
00:03:03,520 --> 00:03:04,520
at your friends.
49
00:03:04,520 --> 00:03:08,439
You weren't inhabiting a character, you weren't the action hero fighting bad guys,
50
00:03:08,439 --> 00:03:11,359
That was until Wolfenstein 3D.
51
00:03:11,359 --> 00:03:17,000
id Software was founded in 1991 by four former soft disk employees, John and Adrian Carmack,
52
00:03:17,000 --> 00:03:21,240
no relation they just happened to have the same name, Tom Hall and John Romero.
53
00:03:21,240 --> 00:03:24,000
This was the same year the Soviet Union fell.
54
00:03:24,000 --> 00:03:26,340
Carmack is going to be more important later on.
55
00:03:26,340 --> 00:03:31,199
They originally began with a Mario clone named Dangerous Dave before the company was officially
56
00:03:31,199 --> 00:03:32,199
founded.
57
00:03:32,199 --> 00:03:35,560
This was mainly to show off the beginnings of John Carmack's technical wizardry, encoding
58
00:03:35,560 --> 00:03:38,560
an efficient 2D side scrolling graphics renderer.
59
00:03:38,560 --> 00:03:43,780
The early 90s, when everything was a dark and edgy statement, the satanic inversion
60
00:03:43,780 --> 00:03:46,539
between PC and console was no exception.
61
00:03:46,539 --> 00:03:49,560
PC graphics using software rendering were terrible.
62
00:03:49,560 --> 00:03:54,900
John Carmack developed his adaptive tile refresh for the PC to compete with the raw computational
63
00:03:54,900 --> 00:03:58,599
power of the Super Nintendo, a true beast.
64
00:03:58,599 --> 00:04:02,240
Adaptive tile refresh meant that slightly more of the game world could be included in
65
00:04:02,240 --> 00:04:04,640
the screen buffer, just outside of view.
66
00:04:04,640 --> 00:04:07,360
This meant they could render smooth 2D scrolling.
67
00:04:07,360 --> 00:04:11,400
It also made the sprite animations independent from screen scrolling.
68
00:04:11,400 --> 00:04:16,120
This little bit of code magic powered their games, including the Commander Keen series.
69
00:04:16,120 --> 00:04:20,520
The Commander Keen series was spread through shareware, with subsequent episodes releasing
70
00:04:20,520 --> 00:04:24,340
over the next year or so for purchase from Apogee, their publisher.
71
00:04:24,340 --> 00:04:29,280
This shareware model would be important because it would be used in their subsequent games.
72
00:04:29,280 --> 00:04:33,200
Speaking of subsequent games…
73
00:04:33,279 --> 00:04:36,879
Wolfenstein 3D began development in 1991.
74
00:04:36,879 --> 00:04:42,199
It would use the raycasting technique earlier employed in id's Catacomb 3D.
75
00:04:42,199 --> 00:04:47,079
Raycasting was a rendering technique necessitated again by the limited processing power of PCs
76
00:04:47,079 --> 00:04:48,079
at the time.
77
00:04:48,079 --> 00:04:51,319
PC master race just can't stop losing.
78
00:04:51,319 --> 00:04:55,800
PCs almost all used software rendering, rather than a dedicated graphics chip.
79
00:04:55,800 --> 00:05:00,879
The shareware model involved getting the game on as many PCs as possible.
80
00:05:00,879 --> 00:05:03,079
Raycasting was the solution to help them do this.
81
00:05:03,079 --> 00:05:07,479
Raycasting allowed their game to run on basically any PC.
82
00:05:07,479 --> 00:05:11,740
Raycasting means you're able to draw only the surfaces which are in the player's field
83
00:05:11,740 --> 00:05:12,740
of view.
84
00:05:12,740 --> 00:05:15,000
This helped massively in saving processing power.
85
00:05:15,000 --> 00:05:16,000
But how does it work?
86
00:05:16,000 --> 00:05:21,519
In effect, a ray is cast, from the player to the geometry, to the nearest object blocking
87
00:05:21,519 --> 00:05:22,519
its path.
88
00:05:22,519 --> 00:05:25,839
In Wolfenstein, none of the levels were truly 3D.
89
00:05:25,839 --> 00:05:28,799
Every level was drawn out on a flat 2D plane.
90
00:05:28,800 --> 00:05:34,120
The program scans horizontally, checking that every pixel on the horizontal axis has something
91
00:05:34,120 --> 00:05:35,120
drawn in it.
92
00:05:35,120 --> 00:05:39,480
If there's nothing drawn in a position, a pixel column will be drawn out.
93
00:05:39,480 --> 00:05:43,699
This is simplified from the process of ray tracing, where this process is done for every
94
00:05:43,699 --> 00:05:46,600
single pixel, rather than every pixel column.
95
00:05:46,600 --> 00:05:51,040
The distance between the viewer, or the camera or player, they all have the same meaning,
96
00:05:51,040 --> 00:05:53,439
and the nearest piece of geometry, is obtained.
97
00:05:53,439 --> 00:05:58,400
The height of the pixel column is calculated using the distance from point of intersection
98
00:05:58,400 --> 00:06:00,880
in the direction the player is facing.
99
00:06:00,880 --> 00:06:04,440
It uses trigonometry to find this point of intersection.
100
00:06:04,440 --> 00:06:09,240
This effectively allowed them to give the illusion of distance, to render a 3D scene.
101
00:06:09,240 --> 00:06:14,620
This makes the process of rendering 3D much easier, as a line, that line being distance
102
00:06:14,620 --> 00:06:20,560
from player to geometry, directly transforms to a line, that being the height of the rendered
103
00:06:20,560 --> 00:06:21,560
column.
104
00:06:21,560 --> 00:06:24,480
This process is done multiple times every single second.
105
00:06:24,560 --> 00:06:29,360
The planes in the scene had been texture mapped, where an image is applied to a 3D surface.
106
00:06:29,360 --> 00:06:34,560
When the columns are drawn, they are really drawing slices of these wall textures at different
107
00:06:34,560 --> 00:06:35,560
sizes.
108
00:06:35,560 --> 00:06:40,319
The height of the column being drawn is smaller when the plane, that being the wall, is further
109
00:06:40,319 --> 00:06:41,319
away from you.
110
00:06:41,319 --> 00:06:45,879
The textures are scaled appropriately to the size of the wall, relative to the player.
111
00:06:45,879 --> 00:06:49,319
This gave the world of Wolfenstein so much believability for the time.
112
00:06:49,319 --> 00:06:52,839
You were no longer just navigating wireframe mazes.
113
00:06:52,839 --> 00:06:57,959
You were an action hero, BJ Blazkowicz, infiltrating a Nazi castle.
114
00:06:57,959 --> 00:07:00,920
The walls were adorned with flags of the German Reich.
115
00:07:00,920 --> 00:07:03,199
You felt closer to the world than ever before.
116
00:07:03,199 --> 00:07:06,240
You were interacting with a true 3D space.
117
00:07:06,240 --> 00:07:08,500
This process was, however, flawed.
118
00:07:08,500 --> 00:07:13,279
In Wolfenstein 3D, there was no verticality at all, no difference in elevation, only the
119
00:07:13,279 --> 00:07:16,800
walls had texture, the ceiling and floor had to be flat colours.
120
00:07:16,800 --> 00:07:20,680
If they wanted texture on the ceiling and floor, they would have had to add horizontal
121
00:07:20,680 --> 00:07:21,680
scanlines.
122
00:07:21,680 --> 00:07:24,079
You were still ultimately navigating a maze.
123
00:07:24,079 --> 00:07:27,879
A colourful maze with Nazis in it, but a maze nonetheless.
124
00:07:27,879 --> 00:07:31,319
Wolfenstein 3D was released in May 1992.
125
00:07:31,319 --> 00:07:34,960
The sequel, Spear of Destiny, was released later in the same year.
126
00:07:34,960 --> 00:07:39,560
While the rest of the id team was working on Spear of Destiny, John Carmack, the ascetic,
127
00:07:39,560 --> 00:07:42,560
high priest of technology, locked himself away to study.
128
00:07:42,560 --> 00:07:47,199
He would brainstorm the revolutionary tech that would power their next massive game,
129
00:07:47,199 --> 00:07:51,480
the next game that the rest of the team would start working on in September 1992.
130
00:07:51,480 --> 00:07:56,079
It would be something inspired by evil dead, brutal and violent.
131
00:07:56,079 --> 00:08:02,040
The name, Green and Pissed, was ultimately passed up for the much snappier Doom.
132
00:08:02,040 --> 00:08:08,000
Doom would launch in 1993, the game would truly be able to transport you into a world.
133
00:08:08,000 --> 00:08:10,620
The levels truly felt like places.
134
00:08:10,660 --> 00:08:16,100
The architecture of Doom consisted of supernatural science facilities, with Giger-esque and hellish
135
00:08:16,100 --> 00:08:17,740
environments as well.
136
00:08:17,740 --> 00:08:23,060
The enemies were a combination of horror and sci-fi with cybernetically enhanced demons.
137
00:08:23,060 --> 00:08:27,959
The architecture, over the top setting and violence was inspired by films such as Evil
138
00:08:27,959 --> 00:08:29,180
Dead and Alien.
139
00:08:29,180 --> 00:08:34,620
The floors could now be angled, they could now have multiple levels with stairs and elevators.
140
00:08:34,620 --> 00:08:38,120
Tools of toxic fluid surrounded these risen platforms.
141
00:08:38,120 --> 00:08:40,220
It was truly 3D.
142
00:08:40,220 --> 00:08:41,540
But it wasn't really.
143
00:08:41,540 --> 00:08:46,180
They were yet to achieve the full 6 degrees of freedom that John Romero wanted.
144
00:08:46,180 --> 00:08:47,899
This wouldn't happen until Quake.
145
00:08:47,899 --> 00:08:51,700
Rumours couldn't be stacked on top of each other, there was no vertical aim, the game
146
00:08:51,700 --> 00:08:54,779
was entirely played on the horizontal axis.
147
00:08:54,779 --> 00:08:58,560
The thing is, vertical aim was actually possible at the time.
148
00:08:58,560 --> 00:09:02,860
They could have limited the enemies' vertical hitboxes to the size of the sprite, but they
149
00:09:02,860 --> 00:09:03,860
didn't.
150
00:09:03,860 --> 00:09:06,620
Not because they couldn't, but to save processing power.
151
00:09:06,620 --> 00:09:09,779
You see, Doom was still using software rendering.
152
00:09:09,819 --> 00:09:13,939
This shareware model relied on getting their games on as many computers as possible, like
153
00:09:13,939 --> 00:09:14,939
I said.
154
00:09:14,939 --> 00:09:18,740
It was essentially the beginning of the free to play game model we have today.
155
00:09:18,740 --> 00:09:22,980
They aimed for the IBM PC, for machines running DOS.
156
00:09:22,980 --> 00:09:27,480
They had to sell their game to university students and wagies who were bored at work
157
00:09:27,480 --> 00:09:29,500
so they could run office tournaments.
158
00:09:29,500 --> 00:09:33,860
They didn't calculate the enemies' vertical hitbox so that they could save memory.
159
00:09:33,860 --> 00:09:38,419
They didn't want to give the enemies' hitboxes a height value, just have another factor to
160
00:09:38,419 --> 00:09:39,419
calculate.
161
00:09:39,459 --> 00:09:43,059
These levels were drawn on a 2D plane, like Wolfenstein.
162
00:09:43,059 --> 00:09:46,099
Just this time, the map creator is quite different.
163
00:09:46,099 --> 00:09:50,659
The ground is divided into sectors, this will be very important later.
164
00:09:50,659 --> 00:09:55,139
Each sector has two associated values, ceiling height and floor height.
165
00:09:55,139 --> 00:09:59,099
Well, it has several associated values, but those are two important ones.
166
00:09:59,099 --> 00:10:03,339
This is also why one room could not be placed above another and why every surface had to
167
00:10:03,339 --> 00:10:06,339
be made out of a flat square or rectangle.
168
00:10:06,340 --> 00:10:10,500
Another reason that vertical aim couldn't have worked is due to how the texture mapping
169
00:10:10,500 --> 00:10:11,500
worked.
170
00:10:11,500 --> 00:10:16,060
One game that did have vertical aim and levels on top of each other, before Quake and not
171
00:10:16,060 --> 00:10:19,420
that long after Doom, was Bungie's Marathon.
172
00:10:19,420 --> 00:10:22,820
And look what happens when you look up and down in that game.
173
00:10:22,820 --> 00:10:25,379
The textures start to distort.
174
00:10:25,379 --> 00:10:29,379
This is because the game, like Doom, uses affine texture mapping.
175
00:10:29,379 --> 00:10:34,780
This, like many of the other methods, was done to save memory on the processor by taking
176
00:10:34,779 --> 00:10:37,139
advantage of CPU caching.
177
00:10:37,139 --> 00:10:43,699
Basically, what happens is that texture coordinates are linearly interpolated, using screen space
178
00:10:43,699 --> 00:10:49,699
distance between vertices, rather than the actual 3D in-engine distance between them.
179
00:10:49,699 --> 00:10:54,000
The distance between points on a plane remains the same when you look up and down.
180
00:10:54,000 --> 00:10:58,379
What this means is that perspective when looking up and down is not accounted for.
181
00:10:58,379 --> 00:11:02,240
You know how pixels on a texture start to warp as you get closer?
182
00:11:02,240 --> 00:11:07,639
It looks like a straight line from far away begins to turn inward as closer pixels get
183
00:11:07,639 --> 00:11:11,399
larger, while more distant pixels get smaller.
184
00:11:11,399 --> 00:11:17,279
This doesn't happen in Doom, because accounting for perspective is taxing on 90s computers.
185
00:11:17,279 --> 00:11:21,539
You know how the game only draws things in columns to save processing time?
186
00:11:21,539 --> 00:11:25,840
They'd have had to do vertical scans as well as horizontal scans.
187
00:11:25,840 --> 00:11:32,080
Newer ports of Doom with newer rendering engines made for new hardware like GZDoom obviously
188
00:11:32,920 --> 00:11:33,920
don't have this limitation.
189
00:11:33,920 --> 00:11:37,960
As such, they use more current texture mapping and don't have this issue.
190
00:11:37,960 --> 00:11:40,720
But all of these concessions weren't enough.
191
00:11:40,720 --> 00:11:45,560
John Carmack's coding brilliance met its most devious enemy yet.
192
00:11:45,560 --> 00:11:46,560
Stairs.
193
00:11:46,560 --> 00:11:51,720
John Romero came out with a really way-out and strange idea on his early incarnation
194
00:11:51,720 --> 00:11:52,720
of E1M2.
195
00:11:52,720 --> 00:11:58,720
Yes, he wanted to mix things up with the earth-shattering invention of stairs.
196
00:11:58,720 --> 00:12:03,600
You see, just raycasting alone wasn't enough to efficiently optimise the game.
197
00:12:03,600 --> 00:12:07,680
Raycasting saves memory by only rendering things which are visible to the player.
198
00:12:07,680 --> 00:12:12,519
However, surfaces on the inside of these stairs were visible to the existing algorithm.
199
00:12:12,519 --> 00:12:15,320
Thus, they were drawn when they shouldn't have been.
200
00:12:15,320 --> 00:12:20,360
You see, for 3D rendering to not waste performance, they need to draw as few surfaces, as few
201
00:12:20,360 --> 00:12:21,840
planes as possible.
202
00:12:21,840 --> 00:12:27,639
This necessitates occlusion culling, or visible surface determination, or backface culling.
203
00:12:27,679 --> 00:12:33,319
Basically, the renderer should only draw what is in the player's field of view.
204
00:12:33,319 --> 00:12:37,080
There need to be absolutely no overdraw whatsoever.
205
00:12:37,080 --> 00:12:43,080
Adding height as a variable, such as with Romero's stairs, requires a much more sophisticated
206
00:12:43,080 --> 00:12:49,000
algorithm than was present in Wolfenstein, and in id's existing rendering engine.
207
00:12:49,000 --> 00:12:53,240
There are many different rendering algorithms out there, it seems that we need to dip into
208
00:12:53,240 --> 00:12:58,680
the hypothetical algorithms to start trawling the literature for some better algorithms.
209
00:12:58,680 --> 00:13:00,440
Let's explore some of the options.
210
00:13:00,440 --> 00:13:04,120
There's the painter's algorithm, named so because, like in a painting, the background
211
00:13:04,120 --> 00:13:07,000
is rendered first with detail layered on top.
212
00:13:07,000 --> 00:13:10,960
Basically, the polygons are sorted by their distance from the viewer, and the more distant
213
00:13:10,960 --> 00:13:14,759
polygons are rendered first, and the closest polygon is rendered last.
214
00:13:14,759 --> 00:13:17,399
It is easily the most simple solution.
215
00:13:17,399 --> 00:13:24,159
It was developed in 1972, the year MASH started, as an easy to implement solution for CAD.
216
00:13:24,159 --> 00:13:29,399
It also has the worst possible case for space complexity, meaning it takes up as much memory
217
00:13:29,399 --> 00:13:31,819
as an algorithm possibly could.
218
00:13:31,819 --> 00:13:34,639
Every single surface in the field of view is drawn.
219
00:13:34,639 --> 00:13:37,120
Obviously, this isn't a good fit.
220
00:13:37,120 --> 00:13:41,399
It's more of an example from the early days of exactly what not to do.
221
00:13:41,399 --> 00:13:43,039
There's also Warnock's algorithm.
222
00:13:43,240 --> 00:13:47,439
John Warnock was the founder of Adobe, and this algorithm originated in his doctoral
223
00:13:47,439 --> 00:13:52,879
thesis in 1969, the year man landed on the moon and In the Court of the Crimson King
224
00:13:52,879 --> 00:13:53,879
was released.
225
00:13:53,879 --> 00:13:57,899
Essentially, it recursively subdivides the screen into four parts.
226
00:13:57,899 --> 00:14:01,839
What this means is it splits the screen into four windows and splits each window into four
227
00:14:01,839 --> 00:14:02,959
smaller windows.
228
00:14:02,959 --> 00:14:08,000
It does this again and again until each window is trivial to render, meaning it has only
229
00:14:08,000 --> 00:14:10,719
one or zero polygons present.
230
00:14:10,720 --> 00:14:14,960
The algorithm also checks if multiple polygons are within one window.
231
00:14:14,960 --> 00:14:19,040
If the closest polygon covers the whole window, then it is drawn.
232
00:14:19,040 --> 00:14:23,440
This is more efficient than Painter's algorithm as it renders front to back, but it's still
233
00:14:23,440 --> 00:14:25,160
not very well suited.
234
00:14:25,160 --> 00:14:30,800
It will eventually keep subdividing to a ridiculous degree, to the point where a window is smaller
235
00:14:30,800 --> 00:14:31,800
than a pixel.
236
00:14:31,800 --> 00:14:34,399
Yeah, this ain't a good fit for a game.
237
00:14:34,399 --> 00:14:38,180
You could do a z-buffer for every pixel you want to draw, check if there's anything in
238
00:14:38,180 --> 00:14:39,180
front of it.
239
00:14:39,180 --> 00:14:40,740
And check on every single pixel?
240
00:14:40,740 --> 00:14:42,740
Yeah, there's no chance in hell.
241
00:14:42,740 --> 00:14:47,700
The final solution does kinda use a z-buffer, but it doesn't do that check on every single
242
00:14:47,700 --> 00:14:50,780
pixel, it finds a much more efficient way to do it.
243
00:14:50,780 --> 00:14:51,780
No.
244
00:14:51,780 --> 00:14:57,820
In order to truly revolutionize not just gaming, but 3D graphics forever, our protagonist,
245
00:14:57,820 --> 00:15:03,340
John Carmack, needs to go to a much more inspired source, something that hadn't actually been
246
00:15:03,340 --> 00:15:04,960
implemented before.
247
00:15:04,960 --> 00:15:06,960
Something he'd just read in a white paper.
248
00:15:06,960 --> 00:15:07,960
Just a concept.
249
00:15:07,960 --> 00:15:13,019
Yes, how common is it in gaming to see people run into optimization issues and seek out
250
00:15:13,019 --> 00:15:17,259
a white paper to solve their problem, because nobody else had done it before?
251
00:15:17,259 --> 00:15:19,139
Yes, that's Carmack for you.
252
00:15:19,139 --> 00:15:23,720
We needed a renderer that would draw objects closest to the player to furthest away until
253
00:15:23,720 --> 00:15:27,580
every pixel was written to, that had no overdraw.
254
00:15:27,580 --> 00:15:32,879
The solution was in a 1980 white paper, as the same year Genesis released the reclaimed
255
00:15:32,879 --> 00:15:36,580
album, Duke, where they really came into their own.
256
00:15:37,960 --> 00:15:45,820
This 1980 white paper by Bruce Nailup was given the humble title, On Visible Surface
257
00:15:45,820 --> 00:15:49,060
Generation by Apriori Tree Structures.
258
00:15:49,060 --> 00:15:55,460
It described a rendering model we know as Binary Space Partitioning, or BSP for short.
259
00:15:55,460 --> 00:15:58,700
This was the method that would change gaming for years.
260
00:15:58,700 --> 00:16:02,300
This wasn't the first time Binary Space Partitioning was alluded to.
261
00:16:02,300 --> 00:16:08,520
A 1969 study by the Air Force of the good ol' US of A alluded to the use of partitioning
262
00:16:08,520 --> 00:16:12,000
3D scenes to solve the visible surface problem.
263
00:16:12,000 --> 00:16:17,340
The study was conducted to determine the viability of 3D for flight simulation.
264
00:16:17,340 --> 00:16:21,380
We can thank the armed forces of the United States for giving us doom.
265
00:16:21,380 --> 00:16:24,900
They explored using a matrix to track which objects are occluded.
266
00:16:24,900 --> 00:16:29,160
These of course wouldn't do so well as the size of the matrix would need to be the square
267
00:16:29,160 --> 00:16:31,760
of the number of objects in a scene.
268
00:16:31,759 --> 00:16:33,620
That wouldn't scale very well.
269
00:16:33,620 --> 00:16:39,200
It wasn't until 1980 that Binary Space Partitioning was properly realized in the white paper that
270
00:16:39,200 --> 00:16:43,860
would reach John Carmack alongside its core tenant, the binary tree.
271
00:16:43,860 --> 00:16:46,740
But what is Binary Space Partitioning anyway?
272
00:16:46,740 --> 00:16:48,779
Well, the name gives you a clue.
273
00:16:48,779 --> 00:16:52,080
Is partitioning space in a 3D environment?
274
00:16:52,080 --> 00:16:54,939
This is done using a BSP tree.
275
00:16:54,939 --> 00:16:57,100
What is a BSP tree you may ask?
276
00:16:57,100 --> 00:17:02,040
In computer science, a tree is a data structure used as a mathematical model for displaying
277
00:17:02,040 --> 00:17:03,560
certain data types.
278
00:17:03,560 --> 00:17:08,720
It's separated into nodes with parent nodes that have child nodes.
279
00:17:08,720 --> 00:17:13,279
BSP uses binary trees, binary essentially meaning two.
280
00:17:13,279 --> 00:17:18,759
A binary tree is a tree where there are two or less child nodes stemming from any given
281
00:17:18,759 --> 00:17:20,559
parent, from any node.
282
00:17:20,559 --> 00:17:23,380
There are never more than two child nodes.
283
00:17:23,380 --> 00:17:28,160
This is as opposed to a non-binary tree, which is a tree that has dyed hair and a gender
284
00:17:28,160 --> 00:17:29,320
studies degree.
285
00:17:29,320 --> 00:17:34,800
The data stored in the nodes of the binary tree are the sub-sectors of the map.
286
00:17:34,800 --> 00:17:39,640
Sub-sectors being smaller parts of those map sectors I spoke about earlier.
287
00:17:39,640 --> 00:17:45,360
Remember, each map is designed on a flat 2D map editor, with each sector having associated
288
00:17:45,360 --> 00:17:46,600
height values.
289
00:17:46,600 --> 00:17:51,880
The genius is that the map is sliced up via binary space partitioning after the map is
290
00:17:51,880 --> 00:17:52,880
built.
291
00:17:52,880 --> 00:17:58,580
Hard work is done when the map is created, rather than by the processor at runtime while
292
00:17:58,580 --> 00:18:00,340
the player is playing the game.
293
00:18:00,340 --> 00:18:06,180
The map is already split, already partitioned when the player loads it, reducing processing
294
00:18:06,180 --> 00:18:07,840
needed at runtime.
295
00:18:07,840 --> 00:18:12,980
To create the binary tree, a root node is established covering the whole map.
296
00:18:12,980 --> 00:18:19,460
After this, the map is recursively subdivided along every plane until only convex sub-sectors
297
00:18:19,460 --> 00:18:20,460
are left.
298
00:18:20,480 --> 00:18:24,120
The sectors are carved into smaller sub-sectors.
299
00:18:24,120 --> 00:18:28,900
The entire map is essentially cut in two along every single wall.
300
00:18:28,900 --> 00:18:33,799
Every time the map is cut in half, the two halves are added as nodes at the bottom of
301
00:18:33,799 --> 00:18:34,840
the tree.
302
00:18:34,840 --> 00:18:40,400
By the end, you're left with a tree where each node at the bottom of the tree represents
303
00:18:40,400 --> 00:18:42,000
a distinct sub-sector.
304
00:18:42,000 --> 00:18:45,539
Remember, this tree is entirely conceptual.
305
00:18:45,539 --> 00:18:47,500
It doesn't actually exist.
306
00:18:47,519 --> 00:18:52,920
So long as the planes don't move – vertical movement is accepted from this because vertical
307
00:18:52,920 --> 00:18:57,960
movement is a separate value – the same BSP tree can be used.
308
00:18:57,960 --> 00:19:03,480
Doom's BSP tree generation was done after levels were complete and would search for
309
00:19:03,480 --> 00:19:09,000
the best possible tree, that being the one that generates the fewest binary tree nodes.
310
00:19:09,000 --> 00:19:13,240
A binary search is performed to determine what sector the player is in.
311
00:19:13,259 --> 00:19:18,660
A binary search is when an array of pre-sorted data is searched through by continually halving
312
00:19:18,660 --> 00:19:19,660
said array.
313
00:19:19,660 --> 00:19:24,740
A search through a binary tree is, by its nature, a binary search, because every time
314
00:19:24,740 --> 00:19:29,079
you go down a node, you're removing half of the possibilities.
315
00:19:29,079 --> 00:19:33,859
After the player's sector is determined using this binary search, the sub-sectors
316
00:19:33,859 --> 00:19:38,279
are then sorted by their distance from the player – closest to furthest.
317
00:19:38,279 --> 00:19:42,279
The tree is iterated through to determine which planes to draw.
318
00:19:42,299 --> 00:19:47,220
The horizontal scanlines from raycasting are still used to track the parts of the screen
319
00:19:47,220 --> 00:19:48,859
that have been drawn over.
320
00:19:48,859 --> 00:19:53,619
This way they are able to render front to back and ensure that there is no overdraw.
321
00:19:53,619 --> 00:19:57,859
When each node is passed over in the iteration, a few things are checked.
322
00:19:57,859 --> 00:20:00,019
Has that area already been painted over?
323
00:20:00,019 --> 00:20:02,339
If so, don't bother drawing it.
324
00:20:02,339 --> 00:20:08,660
When a plane, polygon or wall is drawn, it is akin to a curtain being drawn left to right.
325
00:20:08,720 --> 00:20:14,200
To unveil an area, so to speak, whenever a curtain is seen by the player, it is unveiled
326
00:20:14,200 --> 00:20:16,040
from closest to the furthest.
327
00:20:16,040 --> 00:20:20,759
To be exact, it's the closest 256 walls that are displayed.
328
00:20:20,759 --> 00:20:26,240
Remember how height of the pixel columns drawn on screen depended on distance from the player?
329
00:20:26,240 --> 00:20:32,120
For Doom, this required determining the angle of both ends of every wall, relative to the
330
00:20:32,120 --> 00:20:33,440
player's field of view.
331
00:20:33,440 --> 00:20:38,580
In the early 90s, most processors didn't have dedicated floating-point capability.
332
00:20:38,599 --> 00:20:41,599
This is a float in programming, if you've ever heard of that.
333
00:20:41,599 --> 00:20:45,359
Basically a data type for very precise decimal numbers.
334
00:20:45,359 --> 00:20:51,659
The Doom engine had to use binary angle measurements, which avoid floats, and used a lookup table
335
00:20:51,659 --> 00:20:54,000
to determine the x coordinates.
336
00:20:54,000 --> 00:20:56,960
A lookup table is essentially a cheat sheet.
337
00:20:56,960 --> 00:21:02,359
Instead of the processor doing the maths itself, it just looks up the answer in this lookup table.
338
00:21:02,359 --> 00:21:08,559
They also used these angles for backface culling, with a simple and elegant piece of mathematics
339
00:21:08,559 --> 00:21:14,379
Backface culling basically means the renderer doesn't draw the inside of every polygon.
340
00:21:14,379 --> 00:21:18,099
It only draws the part on the outside that you actually see.
341
00:21:18,099 --> 00:21:23,339
The walls are rendered first as pixel columns from front to back, then the ceilings and
342
00:21:23,339 --> 00:21:25,819
floors using pixel rows.
343
00:21:25,819 --> 00:21:31,500
The objects such as barrels and enemies are rendered from the furthest to the closest.
344
00:21:31,500 --> 00:21:37,599
The ceilings and floors are determined using visplane underscore t, or visplanes.
345
00:21:37,600 --> 00:21:41,900
Plains were determined using height values within each sector.
346
00:21:41,900 --> 00:21:46,940
Visplanes are not constrained to single sectors, and will be continuous provided they all possess
347
00:21:46,940 --> 00:21:50,600
the same height, illumination and textures.
348
00:21:50,600 --> 00:21:53,180
Pixel rows are drawn top to bottom.
349
00:21:53,180 --> 00:21:59,080
One final thing you may wonder about Doom's graphics is why are all the enemies just pictures
350
00:21:59,080 --> 00:22:00,780
facing towards you?
351
00:22:00,780 --> 00:22:04,880
Probably something to do with them being what we call front-facing sprites.
352
00:22:04,880 --> 00:22:08,980
They're rendered last, and like I said, furthest to closest.
353
00:22:08,980 --> 00:22:11,340
That's the opposite order to the geometry.
354
00:22:11,340 --> 00:22:16,340
They are just pictures, taken from the data files and projected onto screen.
355
00:22:16,340 --> 00:22:18,840
Of course, they're a range of pictures.
356
00:22:18,840 --> 00:22:24,020
The one that is drawn depends on the player's location relative to the enemy, and the direction
357
00:22:24,020 --> 00:22:25,500
the enemy is facing.
358
00:22:25,500 --> 00:22:29,040
The enemies do actually have a full 3D hitbox.
359
00:22:29,040 --> 00:22:34,260
The pictures, as most fans know, are actually from real pictures taken of sculptures made
360
00:22:34,259 --> 00:22:35,400
by the artists.
361
00:22:35,400 --> 00:22:41,519
So, John Carmack was faced with a fierce issue in the problem of visible surface determination.
362
00:22:41,519 --> 00:22:46,759
He had to find a solution that was both incredibly fast and very accurate.
363
00:22:46,759 --> 00:22:53,000
BSP doesn't completely solve the visible surface determination problem, but it is one
364
00:22:53,000 --> 00:22:56,900
of the most reliable and efficient methods of optimisation.
365
00:22:56,900 --> 00:22:59,039
It saw massive acceptance.
366
00:22:59,039 --> 00:23:04,339
BSPs were evolved and made their way into Quake's dramatically improved game engine
367
00:23:04,339 --> 00:23:09,819
when they took on Michael Abrash and finally figured out the full six degrees of freedom.
368
00:23:09,819 --> 00:23:15,220
From there, it was in every FPS, and I mean all of them.
369
00:23:15,220 --> 00:23:16,859
Half-Life and Half-Life 2?
370
00:23:16,859 --> 00:23:17,859
Every Source game.
371
00:23:17,859 --> 00:23:19,819
Counter-Strike to Left 4 Dead.
372
00:23:19,819 --> 00:23:21,500
The Halo series used it.
373
00:23:21,500 --> 00:23:24,579
You know the Scarab from Halo 2 is actually a BSP object?
374
00:23:24,579 --> 00:23:27,980
Yes, it's a moving piece of level geometry.
375
00:23:27,980 --> 00:23:33,039
Many would say it's a sign of Carmack's genius that he took an idea from concept to
376
00:23:33,039 --> 00:23:34,839
mainstream solution.
377
00:23:34,839 --> 00:23:41,839
He did all this crazy work in between supercharging Ferraris and becoming a judo master.
378
00:23:41,839 --> 00:23:44,519
One time, he got locked inside a building.
379
00:23:44,519 --> 00:23:49,759
Instead of, say, waiting for security or calling a locksmith, he devised a brilliant solution.
380
00:23:49,759 --> 00:23:54,759
He'd luckily gone to a Renaissance Fair earlier, where he bought a medieval battle axe.
381
00:23:54,759 --> 00:23:58,779
Also, naturally, he smashed down the door with his mighty axe.
382
00:23:58,779 --> 00:24:01,539
He was rich so he could afford to get the door fixed.
383
00:24:01,539 --> 00:24:07,379
He truly is a unique figure in the gaming industry, and you can see why he's so highly
384
00:24:07,379 --> 00:24:08,379
respected.
385
00:24:08,379 --> 00:24:12,019
If you made it this far, comment, thank you John Carmack.
386
00:24:12,019 --> 00:24:17,700
The use of BSP trees has begun to be replaced over the last few years.
387
00:24:17,700 --> 00:24:20,740
Developers instead opt for things like static meshes.
388
00:24:20,740 --> 00:24:25,620
With more powerful hardware now, they can afford some level of overdraw.
389
00:24:25,620 --> 00:24:30,400
Other methods give artists more creative freedom and a much quicker workflow.
390
00:24:30,400 --> 00:24:36,420
BSP often leads to the distinct blocky look that many old games had.
391
00:24:36,420 --> 00:24:41,839
One could certainly argue that these technical limitations are what gave source maps and
392
00:24:41,839 --> 00:24:45,720
early 2000s maps in general their distinct charm.
393
00:24:45,720 --> 00:24:47,079
Their soul.
394
00:24:47,079 --> 00:24:54,079
With stark and distinct architectural choices, some magic is truly lost in busy modern day
395
00:24:54,079 --> 00:24:55,399
maps.
396
00:24:55,399 --> 00:25:01,119
Many new games have actually tried to go back to recreating these older, cleaner, more distinct
397
00:25:01,119 --> 00:25:02,119
visuals.
398
00:25:02,119 --> 00:25:07,639
BSP is still occasionally used today in prototyping levels for games, quickly blocking them out.
399
00:25:07,639 --> 00:25:11,279
It's of course still used in games such as Counter Strike Go.
400
00:25:11,279 --> 00:25:16,000
This was a big video, and naturally it took a bit of research, which I've provided links
401
00:25:16,000 --> 00:25:17,539
to in the description.
402
00:25:17,539 --> 00:25:23,960
If I got anything wrong, please feel free, in fact feel obligated, to call me out in
403
00:25:23,960 --> 00:25:24,960
the comments.
404
00:25:24,960 --> 00:25:31,359
Like, join the Discord server and subscribe with notifications on to join the nerd army
405
00:25:31,359 --> 00:25:33,000
and become a sigma male.
406
00:25:33,000 --> 00:25:34,799
Thanks for watching, goodbye.
407
00:26:03,000 --> 00:26:24,680
Bye.
The text was updated successfully, but these errors were encountered: