Wolfenstein 3D's map renderer

[@jamesgrimwood1285]

See kids, this is why you need to learn Pythagoras and trig at school. Those normal vectors won't calculate themselves ;-)

[@crestfallensunbro6001]

James Grimwood Pythagoras Theorem has become somewhat of a meme I'm my maths class, with great effort going into using it as much as possible and the first suggestion for solving every problem is usually Pythagoras.

[@dhkatz_]

@youtubeShadowBan Lets hope if you ever get a job, they don't look at your social media

[@drown_666]

@youtubeShadowBan it is not triggering me at all, but your wording and the racist videos just speak for themselves and tell me alot about you as a person. Have a nice day.

[@mdejoss1311]

Ah, good quote..

[@marcopozzi522]

I now that math is important but that is why some people developed libreries that with some easy functions can automatically do the raycasting or the raytracing 🧐

[@3DSage]

...I just posted my own raycaster video and fun tutorial! I love how you made your video :)

[@EpicTyphlosionTV]

My algebra teacher would be proud

[@N00BT00BX]

this is trigonometry

[@ProBarokis]

lol

[@2flip]

I can't believe there was no floating point at this time. Really respect them.

[@boltstrikes429]

As advanced as wolfenstein's engine is, I find it just makes Doom more impressive. Doom's engine is so much more sophisticated than Wolfenstein, it's actually insane to think only one and a half years passed between Doom's release and Wolfenstein 3D's release

[@daishi5571]

@etresevo It helped that that they were targeting a much higher system specification.

[@robertforster8984]

@@daishi5571 Not really. i486 instead of a i386.

[@trashcanman6649]

@@robertforster8984 Well a 486dx2 is certainly a lot faster than a 386dx40

[@demgreens]

@@robertforster8984 Wolfenstein's code is 16-bit; id was targeting 286s. As a side note, it was going to be a 16 color EGA game until late in it's development.

[@jonsnow8543]

It’s also a lot harder to go from 0 to 1 than it is to make a feature reach version 2+

[@mahj]

Great video, but please make your graphics a bit bigger. You’re barely using 30% of the available space. On a cell phone, this does not help.

[@MattGodbolt]

Mahj thanks for your feedback. Definitely will use bigger graphics in future. Sadly KZbin won't let me edit a video, only replace it...hopefully you can find a way to zoom to see these.

[@MattGodbolt]

An Enemy thanks for your constructive comment. I'd rather not replace. I'll consider adding another with a more zoomed view

[@panguin7803]

An Enemy, People like you discourage new creators and old ones alike from making fresh and innovative content. I hope you're proud of yourself.

[@ragnarokofborg]

@Panguin > "An Enemy, People like you discourage new creators and old ones alike from making fresh and innovative content. I hope you're proud of yourself." I assume from context that "An Enemy" is a screen name for a previous comment, to which "Panguin"'s comment is a reply. But what was that comment? I only see 3 replies to "Mahj"'s constructive comment about the video only using 30%. Was it deleted, or did YT delete it on it's own, or sort it into God-Know-Where in the comment "stream/blizzard/whatever-the-heck-comment-"discussion"-forums-these-days-are-called". I'm confused..

[@fluent_styles6720]

Panguin People like them rather help new and old creators improve the quality of their content, helping them to communicate information easily to their audience, increasing their retention. So they should be proud of themselves

[@GraveUypo]

this just makes me appreciate how powerful even a 286 is. for a person to calculate one frame of wolfeintein by hand with pen and paper it might take a whole week and that little ancient cpu did it in real time. just wow.

[@sdsdfdu4437]

Whole week is an overestimate. Might take a couple minutes. But yeah your point is still valid, computers are crazy

[@gorgolyt]

@@sdsdfdu4437 You think it would take you "a couple of minutes" to compute an entire frame? Are you sure about that?

[@sdsdfdu4437]

@@gorgolyt Yes, we're talking about wolfenstein3d here.

[@gorgolyt]

@@sdsdfdu4437 Wow. You're quite dumb, aren't you? It's still 128 pixels across. So you have to do all of the calculations in this video in about one second. 😂 And that's just the first step, ignoring the vertical textures.

[@sdsdfdu4437]

@@gorgolyt Jesus fine, so it'll take an hour or two.

[@jacks2782]

This is precisely the kind of video I was hoping existed. I've been dissecting old FPS games. Thank you so much for making this. Know that it is greatly appreciated.

[@TheVopi]

Everytime I see godbolt I know I'm in for a great time. It's insane how topically everything you post/dev is to me at the time. When I was writing an emulator you did a talk at GOTO. When I was writing a compiler you made godbolt. And now I'm tinkering with primitive 3d graphics and here we are. Thanks for everything Matt really appreciate everything you do. Alot of what determined me wanting to go into a CS degree was stuff you've done. Thanks! PS shout-out to Chicago

[@MattGodbolt]

TheVopi wow, thanks for the wonderful support! Very much appreciate your kind words. It's just lucky coincidence I've done things that are helpful to you :-). Great to hear though. And indeed, shouts to Chicago. You should check out the Chicago Open Source Open Mic Meetup, or the Chicago C++ user group if you're into such things!

[@TheVopi]

Matt Godbolt I will! Thank you!

[@the7th494]

How do you get a degree in Counter-strike?

[@TBrianOnline]

I don't know anything about advanced math but I was always curious how they made 3D without actual 3D objects. It's really genius, especiallyl since developers at that time had to overcome so many limitations, it's mindblowig. Thanks for the explanation!

[@jimboli9400]

Thanks for this video, life saver. I was programming a fps game in python using sockets and pygame for fun at school. I kept wondering why I got the fish eye effect until i realised I was not calculating rays with respect to the perpendicular 'p' i.e. 'd'. Great video and really well explained

[@piggypiggypig1746]

This was easy to understand, that is until 2 minutes into the video when my brain failed me.

[@frayedsanity]

agreed, I'm fried. I wished I paid more attention in math at school! DAMMIT!

[@SummonerArthur]

Same here

[@KRAFTWERK2K6]

now THAT was well elaborated in a very detailed way. Thank you Matt!

[@ian_b]

Back in 1984, I was 18, and it was the first year (83-84) that my school was offering a Computer Studies O Level, so I did it along with A Levels my last year of 6th form. Never one to be sensible, I decided one of my three projects (the other two were a version of Missile Command in BASIC (heh) and an "address book") would be a program to draw 3D graphics. It's only looking back now that really it's amazing I achieved anything at all. It drew wireframes, and there was no internet and no books on computer graphics available so I had to work it all out myself, and I remember long hours with pencil and notebook trying to work out how to do it. Your mention of learning Trigonometry with "SOHCAHTOA" brought back memories of that. We never learned the acronym though. In the end my program did work. It could draw simple wireframes. My maths led me to a strange implementation where I had something like a vanishing point but at a fixed distance and objects with negative coordinates appeared beyond it, but getting bigger again the further away they were. I don't needless to say have the source code now so precisely what I did I don't know. I feel quite proud to have got that far though. The machines were British school standards- Research Machines 380Z and 480Z, with a networked floppy disk pack of 4 drives. Which felt like something from Star Wars. At home, I had a ZX81. 3D graphics of any kind were a long way beyond it...

[@greenaum]

Except for 3D Monster Maze!

[@ian_b]

@@greenaum Indeed, how could I forget that? :)

[@raptoress6131]

I love the videos where someone more knowledgeable explains the algorithms used in old games and software.

[@barichm0]

If a Wolf3D map has the edges exposed, you can look and go outside the level. In the north and south directions, the wall data repeats. In the west and east directions, it is from other areas of memory, which results in a bizarre world of mixed up blocks, doors, and empty spaces.

[@henrycgs]

I implemented something very similar to this recently, without even hearing of raycasting before. I did it using ASCII in command line, and then moved on to actual pixels. It was really laggy, however. I was simply moving my rays thousands of very small steps in the direction of the walls. It also had that strange fisheye effect you mentioned. Nonetheless, It was quite fun to make!

[@rambles2727]

When i was a kid i looked at these games and thought how crazy intelligent it all looked. That there are people who understand it. And now that i can understand it it just impresses me even more than it did before.

[@upyours2707]

This video has the charme of old educational material and does the job just as precise in a calm yet engaging way. Thank you! Subbed!

[@benjaminfoo9270]

Extremely underrated youtube-channel - keep up the good work, the followers will come :)

[@elektra81516]

I'm actually going to try and implement something like this inside a more primitive game engine. Maybe even inside a command line using ASCII. Thanks for the detailed explanation!

[@Sevendogtags]

If you do decide to do this, please remember to post an update here. Would be cool to see, Thanks!

[@Stefan-pd9sl]

Somebody took it even further an created a Raycasting engine in factorio kzbin.info/www/bejne/bZ25cnmZeb1nm68

[@mariogamer929]

To be fair, even in the 90s, game engines did exist. But they were often incredibly specific to one project because you can't waste any resources.

[@maelstrom2313]

Look up raycasting tutorials. I wrote a raycasting engine in Java last year following one of those. I even added a custom feature to render animated GIF textures. It's super cool and crazy easy to build a simple game engine.

[@rjhelms]

This video hints at the genius of the Wolf3D code, but actually implementing a ray tracer really drives the point home. Even on modern hardware, it's not trivial to get the same performance that id software managed to squeeze out of a 286!

[@davidt939]

6:14 and 6:31 no, when stepping to the next cell you have to add +1 or -1 to the initial computation dx/tan(θ) or dy/tan(θ), as you correctly describe later based on source code.

[@capt_fruit]

thanks, I read an article on this but it took this video for the concept to really sink in.

[@edminchau811]

There is an effort to port Wolf3D to the Commander X-16, an 8 bit 65c02 based machine. Casting all of these rays is time consuming, and complicated by the lack of assembly language commands to do multiplication on 65c02. I found a way to significantly reduce the number of rays cast. Rather than casting rays one column at a time from one side of the screen to another, the screen is first broken up into groups of columns of pixels. There are 304 columns on the screen, so rays are cast to column 0, column 256, column 288, and column 304 (note this column is just off the right side of the screen and not rendered). This breaks up the screen into a group of 255 uncalculated columns, a group of 31, and a group of 15. For each of the rays cast, there are several values saved in RAM: the map block hit, the face of that block (N,S,E or W), the X-intercept or Y-intercept (whichever applies for that face), and the distance in the direction the player is facing. For all the so-far-uncalculated pixel columns, the high byte of that distance is set to 255. For the rest of the columns we do not immediately cast a ray. Instead, we first check to see if the high byte of the distance is still 255. If it isn't, then we skip the column and move to the next one on the list. However, if it is 255 then we look to the left and the right of this column, to find the closest column to the left which has already been calculated and the closest column to the right which has already been calculated. The order we test the pixel columns, the left pointer, and the right pointer can be stored in three precalculated arrays. The first array is the column to test {0,256,288,304,128,64,192,32,96,160, 224, 16, 48, 80,112,144,176, 208, 240, 272, 8, 24, 40, 56...} . The second array is the column already tested to the left {65535,65535,65535,65535,0,0,128, 0, 64, 128, 192, 0, 32, 64, 96, 128...} and the third array is the column already tested to the right {65535,65535,65535,65535, 256, 128, 256, 64, 128, 192, 256, 32, 64, 96, 128, 160...}. After the first four entries, the left-side entries are the largest number lower than the current column before it in the first list, and the right-side entries are the lowest number higher than the current entry in the first list. The column to test next is just the midway point of the largest remaining untested range, from left to right. So the next column to test is 128. To the left we've already calculated column 0 and to the right we've already calculated column 256. Here's where the magic happens: do the column to the left and the column to the right both hit the same map block on the same side? If they do, then we don't need to cast the rays between them. We can just do a linear interpolation on the x-intercept/y-intercept value and on the distance value, as every column of pixels between two that hit the same block and face will be evenly spaced between them. So we just subtract the value for intercept on the left from the value for the intercept on the right to get an intercept range constant, and subtract the value for the distance on the left from the distance on the right to get a distance range constant. Then we add the left value to some fraction times that constant, a different fraction for each column of pixels. Since the difference between the column number of the right one and the left one is always a power of two, we're always interpolating 1, 3, 7, 15, 31, 63, 127, or 255 columns of pixels. It's trivial to keep track of which interpolation routine to use, and the number of calculations in interpolation (two subtractions once for the entire range, plus two multiplication subroutine calls and two additions for each column in the range) is about the same as just the final step of raycasting: converting delta x, delta y, and beta into a distance. On average, this reduces the number of rays that need to be cast down to approximately 305/(log(305)/log(2)) or 37 rays, more or less; about 87% reduction in rays cast on average. If you're standing close to and facing a wall, only the first four rays need to be cast and all the rest can be interpolated.

[@suvetar]

Absolutely fascinating stuff, not just the code tricks but it gives a kind of insight into the brain of John Carmack too! ... That guys brain has got so many groves it has its own Hausdorff dimension! I would love to see a Javascript simulation of these algorithms working, especially that cunning Square-Root hack!

[@rfdave3980]

Wolfenstein was so awesome. I was so addicted to it. I moved on to Doom then Heritc then Hexen. Hexen was my favorite. Awe so many wonderful memories. Thanks for the video. (liked)

[@djrphotography]

The explanation in this video is so articulate and easy to follow.

[@the7th494]

This is sarcasm

[@FullFledged2010]

Now imagine the amount of calculations in a modern game. Mind boggling🙌

[@pasijutaulietuviuesas9174]

Which is why you have abstraction and automation. In other words - engines.

[@ct275]

@@pasijutaulietuviuesas9174 he said calculations.. not how hard it was to code. If anything the engine adds more things to calculate.

[@pasijutaulietuviuesas9174]

@@ct275 I know that, I also was specifically referring to calculations. Automation and abstractions reduce the amount of calculations the developers need to make themselves. For example, if you want to find the sum of two integers, you perform a calculation - a+b. You want to find a quotient, you perform a calculation - a/b, where b=/=0. Soon, you find that you require to find the sum and quotient so often that you define functions - sum(a, b) and division(a,b). Later, you need to find averages, so you use your functions - division(sum(a,b)). You find that you need to find averages quite often, so you define a function for it - average(a,b). The more and more you automate and abstract your operations, the less calculations you need to perform. The computer still performs every single calculation, but the video shows how developers THEMSELVES needed to perform these calculations in order to make it happen. Nowadays, you download an engine full of APIs and plugins, you barely need to perform as many calculations. That's the point I'm making.

[@briankarcher8338]

If you haven't looked into it, you have no idea, haha. Even something simple like a shader is incredibly complex. You have lighting (multiple light sources mind you), texture mapping, even various techniques to pick from. PBR for example. So you need to calculate Metallic, Glossiness, etc. Diffusion, Specular. Fresnel. Just to draw one dot on the screen.

[@krozareq]

Knowing how to optimize code is still very important. Even a game with relatively low graphical fidelity can bring down the FPS if someone doesn't know what they're doing. Even high fidelity modern games can vary a lot in performance due to someone really understanding GPUs and CPUs at low level in their code. A problem is we rely on frameworks and advancing hardware to take up the slack. But software has not advanced anywhere near as much as hardware has. We still rely on a lot of frameworks and libraries with code written decades ago. There's also a lot of room for software optimization in machine learning ("AI").

[@mohammedjawahri5726]

This is amazing, why is youtube showing me this 3 years too late

[@DashieDasher]

Our geometry teacher taught SOHCAHTOA as "Some Old Hippy Caught Another Hippy Tripping On Acid".

[@screamsinrussian5773]

@@rodri_gl how the hell did you reach that conclusion

[@rodri_gl]

@@screamsinrussian5773 through Pythagoras'.

[@screamsinrussian5773]

@@rodri_gl makes sense

[@ThumbsTup]

Same

[@samferngamerhd4204]

I live on Brazil and my math teacher told us SOHCAHTOA too. It's so cool it's the same tip on another country.

[@white_mage]

matt: explains how wolfenstein 3d's engine works me: ikr is crazy

[@AlbertDongler]

Brilliant! Thanks for putting this together. Absolutely fascinating :-)

[@RobertFisher1969]

It’s interesting to finally learn how similar & different my own attempt at raycasting back-in-the-day was. I don’t think I ever realized the proper way to eliminate the fish-eye effect. I think I ended up with something much more complex. I also remember that I adapted the Bresenham algorithm for drawing lines for the scaling routine.

[@greenaum]

There is a way of eliminating fish-eye, Doom uses a specific technique to do it. Buggered if I can remember how! Doom is actually really similar to Wolf3D. One secret of Doom's speed, is that all walls are dead vertical. No slanting walls at all, just straight up 'n' down. You probably wouldn't notice that unless you knew to look for it. There's a few little genius shortcuts like that, that give the illusion of a world with much more freedom to the level design than there actually is. Doom is drawn as vertical strips from top to bottom. Starts at the ceiling, down to any wall, then maybe some more ceiling and wall. Then eventually starts hitting floor and wall partway down each column. Each point on the map in Doom has one floor height and one ceiling height. No floors above other floors. No bridges, no multi-storey buildings. Though there's some bits that look that way particularly in Doom II. The real genius (well, some of it, there's a lot of genius) in Doom is setting up compromises where the machine could generate each frame fast enough, while having more freedom of level design than the simple flat grid of Wolf 3D. The second part, is designing levels that hide those compromises so it looks like there are less limits than there really are.

[@Elrinth]

Hi! I think when I've watched this video a couple of times I'll be able to make a renderer. I plan on using it in my current project. We'll see!

[@Levelworm]

This tells how proficient Carmack as a programmer about 3 years into professional game programming, starting from a couple of Ultima spin-offs (Shadowforge and Wraith for Apple ][) in 1989. Jeez that guy is a beast and he probably programmed non-stop 12 hours 7 days.

[@walkern.picker3893]

I clearly remember the night I downloaded it off of Compuserve. While standing in the cell, I hit the cursor key to spin around and thought "We're not in Kansas anymore". Some of the other tricks your noticed straight away was using flat images for the "rewards" and other items you collected during play. The movable walls were another great trick. Thanks for the "maths" explanation.

[@greenaum]

Gets a bit too trigonometric a bit too quick. It might be easier if you actually drew in the triangles, when you talk about SOHCATOAH. People are much better at understanding maths visually, usually, as shapes, human brains work better with concrete examples than abstract theory. I'm sure to you it's all the same thing cos you learned it so long ago you don't even think about it any more, but an important part of teaching something is knowing where the learner's brain is at, and bridging the gap between that, and understanding.

[@programaths]

Depends what you want to achieve. Abstract material is transferable while reified material is not. As an example, a common caveat in teaching fractions is using cake and pies. It's very visual and most student can understand that taking two of four parts is the same as taking one of two parts. Going for cake to pie then to enumerable objects is a real struggle. But with practice, student end up building a simple model...which doesn't transfer well! That shows when student are asked to convert a fraction into a real number. Struggle comes back as they didn't internalize that it is a division in the first place and that they are simply asked "do the division". It's also why most adults struggle with ratio. (Problems like "It take 100 hours for 100 people to build 100 houses. How how long does it take for one person to build one house ?") When taught using abstract concept, it takes much more time for students to grasp. But once they do, they can solve any problems involving cake, pies and jugs and even convert fraction into reals. This is not taught that way because people do not need to have profound knowledge and it's OK most people struggle with ratio all their life. It's the practical side which won. But it also limit discoveries we are making. The same with reading has been observed. People lack vocabulary and are not proficient at reading because syllabic reading has been abandoned for the global method. Global method works through repetition. Through a lot of reading, students remember words and even expressions. The issue is that it obfuscate patterns within words. Again, pragmatism won. People seldom use words like "hydrophobic", so it's fine if they have to look it up. Schools "dumbed down" because there is not enough resources, but demand increased. Even 30 years ago, you could end up in a one to one session or in very small group with the teacher. It was also quite normal to have hours of preparation work between two lessons and be interrogated from the get go! What you can do, and that's what I did in the past, is explore and illustrate by yourself. It's very different because your anchor is the abstract subject and not the other way around. But again, starting with abstraction makes everything seems way heavier. But that's the weight of real knowledge!

[@agma]

It's funny to stumble upon a video by the guy who made the Compiler Explorer. Thanks for giving the tools and ideas for tinkering! =) And thanks for the notes on self-modifying and self-generating code: made me really want to dig into Wolf3D's internals Why does the fisheye effect occur with the naive hit distance calculation? Geometric intuition suggests that everything should be ok if you choose field of view correctly

[@MattGodbolt]

I obviously didn't explain myself well about the fisheye. Field of view doesn't come in to it. Imagine a wall directly 10 feet from you. If you were to take a photo, the wall would appear in the photo as a rectangle, right? No fish eye. However, if you measured the distance from your eye to the wall directly in front of you you'd get (say) 5 feet. But it's further to the left and right edges of the wall, maybe 7 feet away (depending on how long the wall is). If you scaled the left hand as 7 feet away, the middle as 5 feet away and the right as 7 feet you'd draw something like a fish-eye wall. So -- the takeaway is, the scaling distance can't be the straight-line distance from the eye to the object, but rather the perpendicular distance away from a plane at the screen. I hope that's (maybe) a bit clearer! I've seen engines use the straight-line distance and then "fudge" it to undo the fisheye effect instead of calculate it properly as Wolf does. Changing the field of view only changes the angles between each ray cast out, it doesn't create or remove the fish eye effect (although if you have a very large field of view you see something similar).

[@agma]

@@MattGodbolt thanks, got it! But what if I aim not to simulate a flat non-distorted picture, but to make the screen "transparent"? In this setup the source of the rays matches the viewer's position, and the virtual screen FOV matches the real one. Will the straighforward approach be more appropriate then? And why isn't it used in game engines? Too narrow FOV? What I want to overcome by this approach is the unnatural view stretching. It's noticeable when you rotate the camera: everything looks way smaller in the center of the screen than on its periphery (yay, I know the reason of this warping now)

[@kentlofgren]

8:24 this is what makes it extra good. thx for sharing.

[@techeadache]

Good and unstructured code. It works but it is insane. It applies 16-bit arithmetic on 32-bit words. It is not portable because it requires an old C compiler that defaults to unsigned comparisons. There should be a disclaimer.

[@kentlofgren]

@@techeadache woaaa did you just use _knowledge_ to elaborate on my initial argument!! O_O :-)

[@techeadache]

@@kentlofgren I think a lot of people will try to implement this craziness on a different compiler. Ofcourse without knowing that (-dx) means static_cast(static_cast((1L

[@dosmastrify]

This is really cool, matt

[@footballCartoon91]

@11.05 if I am not mistaken.. one lone coder perform this (calculate p) the easier way.. first initialize player position at the midpoint of the map for example if the map is 16x16 we initialize the player position as: float playerX=8.0f float playerY=8.0f so p is 8.0

[@damarino1]

This is the older video and I don't know if there was a comment on the following issue... At the time stamp 04:55, you are showing that "dx" is the distance of the starting point from the LEFT side of the square field. But at the time stamp 06:20, "dx" is suddenly the distance from the RIGHT side of the square field. Which "dx" is used in the final equation? Left or right side "dx"?

[@tornghost]

This needs to be presented as a 70s Open University programme, wearing a kipper tie and drawing on a blackboard.

[@skilz8098]

Next up, making the 6502 by hand as they did in the 70s!

[@NiloRiver]

Today is much more easier. Respect even more this guys. Todays devs are not math genius like this.

[@dustmighte]

Super concise and easy to follow!

[@the7th494]

Sarcasm.

[@curcumin417]

Excellent video. Thank you for the interesting and clear explanation of Wolf-3D's ray-casting, wall-rendering technique, such that even I, a non-coder, found it enlightening.

[@thulinp]

ID software took this several steps further with the followup game Doom , featuring much richer 3D map rendering, while still not requiring any 3D rendering or math coprocessor, although they needed more CPU power.

[@MattGodbolt]

thulinp absolutely. I have plans to cover Doom and Quake too :)

[@SweetHyunho]

thulinp If today's engines were this efficient, wouldn't movie-like games run smoothly on ten years old hardware?

[@totara3463]

Sounds exciting! Can't wait to see how Id Software pulled off such a great 3d engine for Quake

[@kangarht]

define 3d rendering ? all rendering happens in 2 dimensions. hence you are plotting pixels on a screen.

[@SerBallister]

@@SweetHyunho Today's engines are very efficient, the whole area of realtime rendering is advancing all the time, what makes you think they aren't optimised ?

[@codename_v]

If you are interested for more information, I recommend the book of Fabien Sanglard he describes in a very descriptice language the whole magic of Wolf3D. The whole engine, not only the rendering. Loved reading it and looking forward for his next book about Doom. Love your awesome vid about rendering of Wolf3D too @Matt! A pictures worth a thousand words. A video is worth a thousand pictures. Looking forward for your further videos!

[@khangdao8119]

Thanks for recomending the book, but I can't find the chapter in the book that describes the engine of wolf3d, can you help?

[@nixel1324]

I'd be really interested in seeing that fisheye effect you mentioned at 3:38.

[@MCSteve_]

Just search up "raycasting fisheye effect." It just looks like the player is looking through a fish bowl. When facing and far from a wall, the lines (top and bottom) slowly converges at the ends of the screen; this is more apparent when the Fov is relatively wide.

[@callsignseth7679]

Check out the coding train Livestream for a demonstration of that on P5 js kzbin.info/www/bejne/Y2fMepZsYr5goc0

[@rszec]

@@callsignseth7679 The middle section of the stream of Daniel is about 3D representation of ray casting and the fish eye effect when we don't take in consideration this geometrical adjustments.

[@mattj2217]

Ultima Underworld and I think Catacomb Abyss both have this issue.

[@shifter65]

There's a picture of the effect in the book "Game Engine Black Book Wolfenstein 3D" by Fabien Sanglard.

[@axpanos]

I'm sorry but I can't follow this, can you please explain why yIntercept is equal to ( y + dy + dx/tan(θ) ) ? I thought since the space between the Vertical Intercepts is [-dx * tan(θ)], shouldn't it be equal to ( y + dy - dx*tan(θ) ) ?

[@Clairvoyant81]

I'm sorry, but this has become sort of a pet-peeve of mine (especially with all the videos about real-time raytracing around these days): Raycasting is simply the process of "firing" (or casting) a ray from one position in one direction into a scene and checking what it hits. That's all there is to it. It's still in use in almost every single game you play today, for example to check what enemy a bullet hits. In itself, it has about as much to do with rendering as a hammer has to do with building a house. Raytracing generally describes algorithms that use raycasting to render an image. Everything beyond that is not included in the terms on their own. Two other things I noticed: 1. You're only using about a quarter of the screen. I imagine that's a bit annoying for people watching this on a smaller device. 2. The step done around 12:35 might have been easier to follow if you circled the terms replaced by delta X and delta Y in the equation for p. Still, very nice and to the point explanation of the algorithm.

[@MattGodbolt]

Thanks for the comments. You're not the first to point out my mistakes here :). If I were to redo things, I'd use more of the screenspace and make clearer the definition of what ray casting is.

[@barrybathwater4877]

hammers have a lot to do with building houses, Lol

[@Clairvoyant81]

@@barrybathwater4877 Well... yeah... they are definitely used while building houses, but using a hammer does not mean you're building a house... which was the point.

[@barrybathwater4877]

@@Clairvoyant81 using the toilet means you squeeze poopies out

[@realcygnus]

I'm pretty sure that either when or VERY shortly after that game came out I had a 386-sx 33 MHz with a separate external FPU I got a few weeks later, 2-4 MB RAM & a 40MB(lol) Hard Drive. & I felt Boss because of it. I am more certain that I had that same system for playing Doom. NO Q these things were like literal magic at the time. id/Carmack are Legends imo, I'm sure these things were ripe for discovery & implementation but he/they were the 1st to do it in a way that reached millions. I used to do modem to modem deathmatches with my uncle. But imho Quake was thE defining moment in history where everything really came together for 1st person 3D multiplayer gaming.

[@Roxor128]

Don't forget Ken Silverman. Cloned Wolf3D as a teenager to make Ken's Labyrinth, then went on to make the BUILD engine that powered Duke Nukem 3D, Shadow Warrior, and Blood plus a number of less well-known games in the mid-1990s, and which got a revival for Ion Fury in 2019.

[@realcygnus]

@@Roxor128 Yup, I haven't really seriously gamed since but the evolution of technology has been almost as interesting as the the tech itself.

[@timog7358]

great explanation

[@F0r3v3rT0m0rr0w]

i will use this, thank you!

[@techleontius9161]

2D plane world... 2D raytracing... Modified 1D image (image in one line) vision... Looks like it's what 2D creatures would see.

[@haph2087]

well, what a 2D creature would see indexed against another 2D plane of textures.

[@puppergump4117]

Actually it's a 1d image with 2d projection.

[@phillippi2]

It should be noted; Ken Silverman's Build Engine could actually do room-over-room tracing, even though it was primarily a raycasting engine. I'm not exactly sure how it worked, except that doorways and windows that you could pass through worked by teleporting the player to different places in the map.

[@navithefairy]

The build engine wasn't geometrically correct though, try looking up and you will see everything looks distorted!

[@Roxor128]

@@navithefairy It's the same trick used by Rise Of The Triad: treat the view like it's really tall and slide the screen up or down, then render the bit that'll actually appear. Unlike a proper perspective-correct 3D rendering, it will keep the walls dead-vertical when you look up and down, whereas a proper rendering will have them turn into diagonals.

[@OnlyBadJoke]

Thanks man it helps a lot

[@FalconComic]

Definitely one of the better explanations I've heard, nice job! This is a little unrelated, but are you the guy that made the Godbolt compiler explorer?

[@MattGodbolt]

Jakob thanks for the kind words. I am indeed the same chap :)

[@greenaum]

Not as many Godbolts in the programming world as you might've thought, funny old world eh?

[@khangdao8119]

Can you make a video which explains how sprites are added in?

[@MattGodbolt]

Great idea, thanks. I don't know if I will have time in the near future. There's a great book on this subject if that's your thing though

[@khangdao8119]

@@MattGodbolt oh, what's the book name?

[@MattGodbolt]

@@khangdao8119 game engine black book: Wolfenstein 3D by Fabien Sanglard

[@khangdao8119]

@@MattGodbolt thanks for recommending

[@robertforster8984]

I don’t know. I remember Wolfenstein running pretty poorly on a 286. You would want a state of the art i386 to play Wolfenstein well.

[@blakegriplingph]

Plus around that time, the 486 was generally available anyway.

[@technoguyx]

The use of the square grid to leverage CPU power was pretty genius on id's behalf. I wonder how was the trig handled without floating point arithmetic?

[@rich1051414]

It was built into the compiler, they didn't even need to think about it, but of course, it is always better to avoid using floating point, as doing floating point math without an FPU is expensive.

[@MattGodbolt]

I think I explain in the video (it's been a a while...) - everything used fixed-point arithmetic with look-up tables to handle the trig functions.

[@adamp9553]

It's really 2D with depth projection for the x/y map. No height changes whatsoever.

[@c0d3_m0nk3y]

It's actually not that hard when you think about it but coming up with it in 1992 when nobody has done it before is the actual achievement. I was 15 at that time and it took me years to figure out how it works. There was no stackoverflow that you could consult at that time.

[@Domarius64]

Now I see why Carmack was so resistant to adding "push-walls" when John and Adrian pestered him to. That breaks the grid stepping. I wonder how he went about it in the end?

[@nickwallette6201]

Good point. Maybe it used 2D sprite tricks to move it further away by just decrementing its height and width.

[@SerBallister]

@@nickwallette6201 You could fudge the intercepts on tiles that contain the shifted wall.

[@shifter65]

If still curious, checkout the "Game Engine Black Book Wolfenstein 3D" by Fabien Sanglard. There's a section talking about how it was done

[@Domarius64]

@@shifter65 thank you!

[@____________________________.x]

Well I didn’t understand that (sitting here munching breakfast), but it looked really interesting, so I’ll definitely watch it again

[@sky-persuitofwonder]

trig is a high school subject.

[@____________________________.x]

IndiiSkies - And I’ve studied Engineering at Degree level you little snot nosed spod, but that doesn’t mean I can design a bridge before I’ve even drunk my coffee.

[@denoww9261]

@@____________________________.x yikes

[@LKRaider]

IndiiSkies - and its been 20 years since I last used any of this.

[@____________________________.x]

@Tommy Hopps - actually, zero tolerance for numpties is generally how we all turned out.

[@gnoath5684]

Personally, I always thought that the fisheye effect was much more desirable than the "corrected" version that has become standard for the simple practical reason is that you can play with a higher FOV with the simple distance renderer and not have the central focal point in the middle of the screen be so small, and the edges be so big. I really wish more renders kept the simpler distance render for that simple reason alone. It makes it easier to see when playing.

[@briankarcher8338]

The fisheye effect didn't increase FOV. FOV stayed the same, the walls just scaled incorrectly.

[@imnotlmao]

Amazing video!

[@figfox2425]

I am amazed by the 118 down thumbs... This video is gold !

[@goauld88]

13:07 why is the height constant/p? Isn't the apparent size of an object arctan(size / distance)? Is it just an approximation that works fine?

[@MattGodbolt]

I think the angle subtended is that, but the height itself is inversely proportional to distance alone.

[@trickysoft]

Love it Matt :)

[@tomp2008]

a 286 with no floating point was certainly NOT "state of the art" in 1992!

[@MichaelPohoreski]

Tom P. Agreed. I still have my 386SX-16 from 1990. A 486DX2 was state of the art in 1992!

[@danpowell806]

It wasn't 'state of the art', but it was met the minimum system requirements.

[@robertforster8984]

I think he met to say i386.

[@SteamPunk96]

fantastic video, very informative. thanks for making this

[@khangdao8119]

Great video!, I have a question : at 5:09, we can already find the coordinate of the first horizontal intersection. But in raycasters, we need to check both horizontal and vertical intersections. The question is, in that case, how do we find the x,y coordinate of the first vertical intersections?

[@MattGodbolt]

At 6:19 I show the first vertical intersection. I wasn't clear: there's also a dispatch on which of the four quadrants the ray is being cast on, which sets the scene for which direction to check first.

[@ropespopes1395]

There were far more powerful processors in 1993 than a 286. We were up to 486 pushing into pentiums. There were also graphics cards at that time.

[@Roxor128]

Wolf3D came out in 1992. Doom came out in 1993. My family got a 486DX/33 with 8MB of RAM in 1993. You could just barely run Quake on it (if you call getting single-digit fps with the sound breaking up "running"). Cost AUD$4000, which is about double that in today's money. Hardware was expensive. Hardly surprising that ID targeted older stuff like the 286 for Wolf3D and the 386 for Doom. 3D accelerated graphics cards were a mid-1990s thing. The first ID Software game to get support for them was Quake 1 with the GLQuake update, but Quake 1 started off with software rendering only. Quake 2 still came with a software renderer, and it wasn't until Quake 3 in 1999 that they were common enough that ID dropped software rendering entirely. The original Unreal from 1998 also includes a software renderer (and a pretty impressive one at that, as it dithers the environment textures to fake bilinear filtering, which I've never seen in any other engine), but later games using the engine don't bother to include it.

[@3ombieautopilot]

Cool vidoe. You have a badass last name, man

[@zylascope]

Great video thanks. :)

[@RagbagMcShag]

I have 1920x1080 pixels on my screen And I am watching a guy explaining a ~500x500 pixel graphic about rendering a game from the 90s in a way that makes it run on a toaster This, my friends, is the peak of evolution.

[@mandataruu8685]

math and gometry is the secret of theory behind hardware, cpu and memory

[@torokati44]

Another high quality video with excellent explanation, as usual with your content. Thank you! One small note though: the graphics were perhaps a bit too small, the lines thin and faint, and the annotations a bit tiny. On mobile, I could see them fairly okay, but someone with a smaller screen and/or less good vision could have a hard time. And especially thanks for adding captions (to whoever created them, if it was submitted, and not made by you), on top of your already clear and understandable speech!

[@MattGodbolt]

Thank you for the feedback! I'm still learning how to best record these, and getting the screen zoomed up appropriately is something I just worked out how to do! Sorry the diagrams suffered from being too small here!

[@Rand0081]

Yes, there is a class of programmers which simplify their formulas, finding interesting shortcuts in complex math algorithms. And then there is your business software colleague, the one who converts a number to a string to check if it is positive.

[@Zentauri77]

I actually expected the raycasting routine to be written in assembly.

[@monad_tcp]

(we don't use self-modifying code anymore... sadly, but that's why we use self-generating code !)

[@chillzwinter]

This game alone is what made me realize practically overnight that it was now safe to abandon my Amiga 500, and enter the world of PC's.

[@waynegalen1538]

I disagree with calling a 286 "state of the art" for 1992. Commonly available, and a good target system to develop for? Yes, but the 386's and 486's had already been out for a few years by then.

[@shomz]

Yeah, and not to mention the gaming beast that came out in '87 - Amiga 500.

[@Saturn49YT]

Agree. The 486 was introduced in 1989, it was actually a bit old by 1992 - the 486DX2-66 was top of the line in 1992. The Pentium was released in 1993. 386s were still around but fading away. 286s were pretty rare and while Wolf-3d may have run on one, it didn't run particularly well.

[@heriblandt]

Wolfenstein 3d has always fascinated me. For the longest time I have wanted to understand how it was made and after this video... I still don't. That is not the video's fault. I was never good at math. Its a start though and thanks for that. I feel like there could have been some more information on screen once the explainations started. The drawings were great but some supporting text maybe. Just a thought.

[@daifee9174]

Im pretty new to the programming, but wouldn't that be much easier to cast every ray from a diferrent point on a line perpendicular (facing player in 90°degrees angle, imagine that like letter "T" player is the leg "|" and those lines will be casted from points on that "-" part) to the player (can it potentially lead to orthographic perspective? - and if so, would it matter in the first place? ) or cast those lines from the same point and then shorten those lines in the middle (lines closer to the middle would get shorten by the higher value ) to compensate for the fish eye effect Please correct me if im missing something

[@MattGodbolt]

Not sure; what equation would you use to shorten the lines in the middle?

[@daifee9174]

@@MattGodbolt first of all, i would let the player face the wall at 90° degrees angle, thus all the rays should be ideally the same length, which they will never be because of the fish eye effect. I would measure lengths of all rays, and then I would basicaly try to find out if that length progression from shortest to the longest ray can be represented by some mathematical function (like parabola or something) and then I would try to aplly reversed version of that mathematical function which would potentially cancel the fish eye effect. But in this part of world its late night right now as I'm writting this very so maybe I'm saying nonsence.

[@MattGodbolt]

@@daifee9174 if you're casting every ray from a different point on the perpendicular...what angle are you casting? It doesn't seem to matter if you cast them from the player's position, or a point on the plane. Then the "reversed version of the mathematical function" is distance dependent, and it needs to be calculated. There are engines out there that do this, but the "reverse transform" is more expensive than avoiding it in the first place :)

[@daifee9174]

@@MattGodbolt If I would cast rays from diferrent points on the line, they would have to be perpendicular to that line. Im not sure if my poor english can accurately describe what I mean, so I'll show it on letters again. It would be like"•E" player is that "•" and that perpendicular line is the vertical part of letter E and rays casted from that line are like those 3 horizontal parts of letter E

[@daifee9174]

So angle of every casted ray would be 90°

[@balazsszilveszter9454]

I had a 386DX 40Mhz then, I clearly remember that it didn't run well at full screen even on that machine. I was quite jealous for the 486DX2 66Mhz because Wolf3D ran perfectly on that, but not with the 386... on 12Mhz 286, there is no way to talk about well-running Wolf3D at all, if it is close to the full screen :D Not mentioning Doom, what was awfully slow at full res. on my 386, strong compromising needed to play. With a 486DX2 it was much more playable...

[@gavinbrichardson]

I did a project on explaining this exact thing about a month before this was made. Research for it was extremely difficult. This would have been "very useful"

[@O_Mercurial]

Dude.. I learned a lot with this! Thanks for making it!

[@JiosX]

John Romero and John Carmack are fucking geniuses.

[@ehsanamini8501]

a detailed code review would be much appreciated.

[@repogamesstudio2366]

nice explanation, thx

[@deux2k]

There's a mistake in the definition of raycasting and raytracing. In raycasting you fire a ray for every pixel on the screen and stop when the ray intersects an object, in raytracing you fire a ray for every pixel on the screen and when the ray intersects an object you fire another ray from the point of intersection and into the direction in which your ray is be reflected by the object, and you repeat this action until your ray intersects the light source, thus tracing a ray of light from the camera and to the light source. In raycasting color of a pixel on the screen is determined by the color of the object at the point of intersection between it and the corresponding ray you cast and maybe the distance. In raytracing, the color of the pixel is determined by the color of an object as it is lit. The renderer in Wolfenstein 3D does even less than a normal raycasting algorithm would because it is only capable of rendering a certain kind of scene with a certain kind of camera: You can't look up or down and the floor and ceiling are always the same color, so the renderer only needs to cast one ray for every column of pixels, like it was said in the video, to determine how far a wall is. And, since the only other type of object on the scene is a billboard/sprite that always faces the player, raycasting is only needed to render the wall textures.

[@KuraIthys]

Your definitions aren't correct either. Raycasting is tracing a single ray PER COLUMN (or row, in theory) of pixels, and determines the point at which this intersects a surface. - you then use this to determine what column of a texture should be drawn, and the distance to determine the length of the line. (and in more advanced raycasting engines, some kind of lighting parameters.) That's raycasting. Raytracing also doesn't do what you think it does either. It traces a ray from each pixel and looks for an intersection with an object. If it's a fully reflective surface, it then traces a line based on the angle of incidence and repeats the process until it hits the bounce limit set by the renderer. It doesn't trace until it hits a lightsource, rather when it hits a surface, it traces a line to each light source, determines the angle to the surface of that specific light source at the point of intersection, and uses that to determine the lighting contribution. What you're calling Raytracing is a process called Path Tracing. What you're calling Raycasting is, to my knowledge a non-existent algorithm. What Wolfenstein does is how Raycasting is described in every book I've ever read on the subject.

[@clonkex]

@@KuraIthys Tbh I would argue that there's no real between raycasting and raytracing. In all these ray-based algorithms, you take a ray, trace/cast/fire/whatever it in some direction until it hits something, and then do something with the result. We need better names to differentiate between all the different rendering algorithms based on rays.

[@404_profile_not_found]

"In 1992, the state of the art was a 12 MHz 286"... And yet I had a 33MHz 386 in 1991. I must have purchased my computer from a time traveler.

[@olyohalia8514]

In 1992 I think that I had a 486 ^^ But hey, that was a great video anyways !

[@monad_tcp]

things weren't so fast and I guess that changed by country

[@olyohalia8514]

@@monad_tcp Im pretty sure that in 92-93 I had a 486 dx2 66. Edit : I mean It lasted for so long that it's like my actual i5 2500k from 2011, I don't think I'll forget it ^^

[@stupidsimple272]

You are a saint

[@Ehal256]

Interesting and easy to follow video. Any chance of a video covering the Doom renderer? :)

[@krozareq]

It ran well on my IBM Clone 8088. Well, until I used the map editor to create a room full of bosses... that brought it to its knees.

[@bhargavvoleti2647]

I'm pretty curious about the self-modifying code of the ray casting loop. How was it even done? And was this common practice when writing tight loops? It's seriously cool to think about, but in hindsight, I can see how much of a pain in the ass it could be for someone who doesn't know about it.

[@MattGodbolt]

I'm not sure how common it was, but Wolfenstein did it here: github.com/id-Software/wolf3d/blob/05167784ef009d0d0daefe8d012b027f39dc8541/WOLFSRC/WL_DR_A.ASM#L235 patched the `jge` etc :)

[@bhargavvoleti2647]

Wow, that was way simpler to understand that I thought it would be. Guess I'll be reading the wolfenstien source code this weekend.Amazing video as usual!

[@thulinp]

The technique is fairly common in assembly code, which forces a fair level of spaghettification anyway. The speed critical bits like 3D rendering would be where you invested in assembly coding, which is far slower to develop.

[@danpowell806]

There's a better way to calculate how large the column of pixels for the wall should be than calculating the normal distance. Calculate the square of the normal distance, and use that directly.

[@OCPyrit]

I'd like to know how the lookup tables work and how the precision works with fixed point numbers.

[@MattGodbolt]

Something like this: instead of having 360 degrees in a circle, have 256 of them. Prepare (for eaxmple) a table of sin() by having sin(0/256), sin(1/256), sin(2/256)... etc. Now you can get sin(angle) by looking at entry "angle" in the sin table. For the entries: we know that sin() ranges between -1 and +1. So, we use a signed number between -128 and 127 to mean -1 to +1: we store (sin(angle) * 128)) in our tables, as an integer. So now we have a 256-byte table of sin. To multiply by sin(angle), we take a number like "150" and multiply it directly with the sin value. Then we shift it down by 7 (to account for the 128-scaled sin()). That way we get an answer in the right domain. Later you can note that there's a close relationship between sin() and cos(), and can reuse parts of the table. tan is a little trickier, as is tan-1. But hopefully this gives a little taste!