/
02-quake-hack.txt
101 lines (72 loc) · 9.53 KB
/
02-quake-hack.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
HOW QUAKE TRICKED COMPUTERS INTO FAKING REAL-WORLD LIGHTING
illusion of fully lit world
not gonna give up lighting fx wanted
bouncing off every surface and etc
shiny metal barrel of sweet rocket launcher
alternatives:
shot of turning and blowing self up
shot of fighting in a different arena
ASSETS
X img: controller
X img: game code
X img: game code gets devious/snarky face
X anim: mist - fog to cover up world
X img: Fuse copies character data for space during cinematics
X img: pointy-eared space-mongoose (look left, right, snarky)
X vid: Quake footage teasing illusion of fully lit world
X (intro)
X img: in the 90s - floppy disk
X img: x -> y -> z*NEW* - were moving in the x, y and z directions
X img: light at center emanating in those 3 directions, too
X anim: nice rendered 3D image like this
X img: 6 frame sequence of light moving step by step and reflecting
X img: the Prince was still Fresh
X img: dj lighting pic for equation
X anim: inverse sqrt -> $ expensive -> no, TIME expensive!
X img: 90s computers that can't even handle light calculation
X img: John Carmack sequence of expressions and talking
X vid: Quake not going to give up lighting fx they wanted
X anim: Newton's Method on paper -> guess -> method -> refine
X vid: Quake light bouncing off every surface and reflecting
?text: draw light direction arrows show how crazy calculating all this is
X anim: floating point number -> example of one -> in code looks same
X vid: light heading to shiny metal barrel of sweet rocket launcher
X (vid: slow to show frames - gotta do this 30 frames a second)
X anim: floating point number
X img: outline of controller
X img: code - how they did it. don't get it? nobody does!
X anim: back to floating point -> stored as number x 2^some_power -> lots going on here
X anim: (cont'd) -> circle exponent and mantissa - normalize after calc? didn't think so
X anim: -> reshow invsqrt = number x 2ˆ(some_power/-2 <-THIS!) -> pulling hair out!
X anim: -> float funny storage -> 2 chunks mantissa/exponent
X anim: -> chunks shift right -> both sides divided n/2 * 2^(x/2)
X img: code - evil bit level hacking indeed
X anim: -> circle some_power/2 - wait needed to div by NEGATIVE two!
X text: 5*-1 = 0-5 - same darn thing
X text: circle mantissa (n/2) - messing with the mantissa too
X img: code - magic number restores mantissa -> zoom WTF comment
X vid: not launch satellite but good enough to light whole game world -> final outro
I play a lot of shooters. So getting screamed at by teenagers no longer makes me go WTF. My biggest videogame WTF's are when I pull open game code and see how it's lying to my face.
Sometimes those lies are artistic. Silent Hill used fog to cover up technical limitations of displaying a full town onscreen at once.
Some lies get creative with hardware. Fuse copied data to get enough space for its memory-hungry cinematics. It also reminded us that Insomniac does so much better with pointy-eared space mongoose-thing shooters. But that’s another story.
But my favorite are the lies literally written in code. And do you want to see the coolest of these tricks, one that hacked together the illusion of a fully lit world and literally had the developers themselves WTFing in their code comments?
[intro]
Welcome to CompChomp, the only show on the internets where our scripts don't ban you for camping. But if you spawn kill...
In the 90’s, 3D gaming was fancy, new, barely charted territory. Sexy stuff. Now beefcakes and bullets and bees and bubbles were moving in the X, Y and Z direction. In game programming, that meant wrapping your mind around a vector with 3 components.
But you know what else was moving around these 3D worlds? Light. Light with its rays doing the vector thing, too.
And that would be just a curiosity if you were looking at a nice rendered 3D image like this. But in games, we’re literally updating those vectors every frame, let’s say 30 frames per second. That’s a lot of thinking for your computer to do.
If you’re back in the 90s but you really want to push the limits and make your world look real, that’s 30 frames per second of looking at every light source and calculating every angle that light bounces and reflects around your world. No big deal, because even before the decade when the prince was still fresh, math already had an equation for that. It’s called the inverse square root. But don’t jump up out of your seats and cheer, because that equation is expensive. Computer expensive, meaning it didn’t cost stacks of cayush - it cost stacks of time. And unless you’re a lagbot, time is something we don’t have a lot of between game updates.
So now we’re stuck in the 90’s with a ton of light calculation - actually it was rather heavy. Hahaaa! Yeah, and you’re stuck with computers that can’t even handle that. What do you do? Huh?
Coders are problem solvers. You know, in some jobs you wake up and you’re like, ok I need to do this and this and this today. No. For us, it’s more like I have no idea how to do this today. Time to figure it out!
So John Carmack and his team at id software were facing this very same problem while working on Quake 3 Arena. Carmack? Yeah, the Wolfenstein guy, the Doom guy, the Quake guy. Look, I don’t have a super high nerd quotient and my shooter of choice is the kind with claptraps and slot machines, and even I know who this guy is.
The actual calculation to come up with the inverse square root was too expensive. So they needed an alternative, cuz they weren’t going to give up the lighting effects they wanted. That was NOT an option.
One alternative they thought of was Newton’s method, which is pretty good at refining a guess and getting a close approximation, however that generally takes like 5 or 6 rounds of refining that guess. 5 or 6 rounds of guessing and refining the angle of every light beam hitting every object every frame. That wasn’t gonna work. So they had to get shifty with their code. Bear with me here. The way a floating point number is stored. Wait, wait, wait. Let me back this truck up. There’s a thing called a floating point number. Which, if you’re not a programmer, honestly, even if you are, looks like a regular number with some decimal stuff. And for light and angles and movement, we need those more precise decimal numbers. When you’re writing it into your code, a float looks like you’d expect. The way the computer was storing it was a bit different. (? Hahaha. Bits. You might understand why I keep chuckling to myself in a moment. )
So you’ve got a beam of light heading straight towards the shiny metal barrel of your sweet rocket launcher. And when that light hits that barrel, your computer has to figure out where all those beams are going before that Update function finishes running and it has to do this 30 times per second. We only have time for one guess - a really, really good one so you only have to run Newton’s method once.
Look at this code. This is how they did it. You don’t get it? Nobody does! We’ll walk through it. Just a bit.
Back to the floating point number. That’s stored as a number times two to some power. And manipulating floating point numbers can be expensive. Do YOU want to normalize the exponent and mantissa after each calculation? I didn't think so. Well, taking the inverse square root is the same as dividing the power the number is raised to by negative two. But how do you do that without floating point numbers?
Remember that the number’s stored funny. And it’s that funny way of storing the number that gave up the solution. Obviously this is a computer, and, whenever you start looking low enough, you’ll see that computers store stuff in bits. And these bits represent that number in two chunks - its mantissa and its exponent. If you take those bits and you shift them one spot to the right, that’s actually the exact same thing as dividing both of those chunks by two. This isn’t wholesome everyday code, and look! They knew it! Evil bit-level hacking indeed. But this bit of evil helped vanquish that costly foe - division - speeding the whole thing up. Wait, but we need to divide by NEGATIVE two! So, what? Multiply this by negative one? WRONG! I just told you - multiplication is expensive! See, Josh! I told you this Quake math stuff would never work. I’m losing them!
Here’s the thing. Let’s go back to the maths. You know what is very similar to multiplying your number by negative one? Subtracting it from zero. It’s actually the same darn thing. But wait, your bit shift ended up messing with the mantissa, too. So one last hack - pull a magic number out of thin air that returns things to normal and just leaves you with a changed exponent. Don’t look at me. I don’t know how it works. But don’t feel bad. They didn’t know how it worked either! This is really the original comment in the source code. WTF indeed!
Look what we did. We replaced an expensive division and multiplication with a bit shift and a subtraction. Much cheaper. Much more 90’s. Now there’s an extremely close initial guess and with one round of Newton’s method they were good to go!
You wouldn’t want to launch a satellite into space with this, but it was accurate enough to light a whole game arena without lagging your clunky 90’s PC behemoth.
So if you’re a gamer, maybe step back to appreciate the hard work coders do to deceive you and keep your game world running awesome. If you’re a coder, maybe keep some dirty tricks up your sleeve for the next time you need to pull off the impossible. Just don’t tell on me for telling you. And whoever you are, get out there and code!
Chomp!