Tip:
Highlight text to annotate it
X
I play a lot of shooters, so getting screamed at by teenagers...that no longer makes me
go,"WTF?!?". My biggest WTF moments - that's when I crack open the game code and see that
it is lying to my face.
Sometimes those lies are artistic. Silent Hill used fog to cover up the fact they couldn't
render a full game world. And sometimes the lies get creative with hardware.
Fuse actually copied data to get space for its memory-hungry cinematics. It...uh...also
reminded us that Insomniac does so much better with pointy-eared, space mongoose shooters.
But that's a different story.
But my favorites? Oh, those are the lies that are literally written into the code. And do
you want to see the coolest of these. The one that hacked together the illusion of a
fully-lit, 3D world and literally had the developers themselves saying, "WTF?!?!"
Welcome to CompChomp the only show on the internets where our scripts don't ban you
for camping....but if you even think about spawn killing.
In the 90s, 3D gaming was fancy, new, barely charted territory. Now you had beefcakes and
bullets and bees and bubbles moving in the x, y and z direction. And in game programming
that meant that you had to wrap your mind around a vector with three components.
Do you know what else was moving around these 3D worlds? Light! Yeah, that's right. Light
with its rays doing that vector thing too.
And, you know what, that would just be one of those random curiosity things if you were
looking at a nice, rendered, 3D image....like this one. But, in games, we are literally
updating all of those vectors every single frame...let's say...uh...30 frames per second.
Now that is a lot of thinking to make your computer do. And 90s computers...they weren't
the smartest.
So let's say you are back in the 90's. You are back in the 90s! And you want to push
the limits and make your world look real. That is going to be 30 frames per second of
calculating every single angle that every piece of light bounces and reflects off around
your world. NBD...because even before the decade when the Prince was fresh, math had
already solved this problem. But unless you are a lag bot, and, no lag bots allowed, time
is actually something you just don't have a lot of between game updates.
OK, we are stuck in the 90s with bad hairdos, boy bands and a ton of light calculation.
Actually it was...it was heavy calculation.
You know what you're stuck with in the 90s also? Computers that can't handle that. So
what do you do? Huh? What are you gonna do?
So John Carmack and his team at id software, they were facing this very same problem while
working on Quake 3 Arena. Carmack? Yeah that's right. The Wolfenstein guy. The Doom guy.
The Quake guy. Look, I don't have a super high nerd quotient and my personal shooter
of choice is the kind with Claptraps and slot machines, but even I know who this guy is.
Math alert! I'm not gonna pull out the glasses, but you've been warned. The calculation to
come up with the inverse square root...that was kind of...too expensive for the computers
to do. So they had to come up with an alternative. The one thing id refused to do was give up
on those lighting effects. Failure was not an option.
One alternative they came up with was something called Newton's Method. It's really good at
refining a guess and getting it to a close approximation. But it takes around 5 or 6
rounds of refining. 5 or 6 rounds of guessing and refining the angle of every single light
beam hitting every single object in every frame. That's not gonna work either.
They actually had to get a bit...shifty...with their code. Bit shifty.
The way a floating point number is stored. Let's back up. There's a thing called a floating
point number, which, if you're not a programmer...actually, even if you are a programmer. It looks like
a regular number. The only difference is that it has some decimal stuff. And for light and
angles and movement, ya gotta have those more precise numbers.
When you're writing it into your code, a float looks pretty much exactly like you'd expect.
The way a computer was storing it though, that was...uhm...let's just say....a bit...different.
Bits.
So, you've got a beam of light and it is heading straight for the shiny metal barrel of your
sweet rocket launcher...slash...finger gun. And when that light hits that barrel, your
computer has to figure out where all of those beams are going to go before that update function
finishes running. And it has to do this, how many times? I've already told you this. 30
times per second. You're going to have time for one guess. One really, really, really
good guess.
OK. Look at this code. This code...this is literally how the guys at id did it. Ya don't
get it? Nobody gets it. Not even the guys at id get it. I don't get it. I'm confused!
We'll walk through it though. Don't worry.
Now let's go back to the floating point number. That's stored as a number times 2 to some
power. And when you manipulate that floating point number it can get pretty expensive.
Do you want to normalize the exponent and the mantissa after each calculation? We're
still trying to figure out what an exponent and a mantissa is. Mantissa. I like that word.
Taking the inverse square root is the same as dividing the power the number is raised
to by negative 2. Awesome, except dividing is still expensive. So how are you going to
do that without that floating point number?
So remember how I told you that floating point number was stored in a funny way? It's actually
that funny way of storing it that gives up the answer.
This...it's a computer. And any time you start digging deep enough into a computer, you find
that it stores things in bits. And in this case, it stores a floating point number in
two chunks - its mantissa and its exponent. And if you take those bits and you just shift
them one spot to the right...little shift em. It is actually the same thing as dividing
both of those chunks by two.
This isn't wholesome everyday code. And look! The guys at id knew it! Evil bit level hacking
indeed!
But this tiny bit of evil, it helped vanquish a costly foe - division. And it sped the whole
process up. But, I know what you're thinking to yourself. Didn't you say it was dividing
by negative 2? So, what? Multiply this by negative 1? C'mon you guys! I just told you...division
and multiplication are expensive! See Josh! I'm losing 'em here.
Kay...stick with me one more time. This is the thing. If we go back to those maths. Do
you know what is very similar to multiplying a number by negative one? It's subtracting
it from zero. It is actually the same darn thing.
If you remember though, your bit shift kind of messed with the mantissa too. So there
is one last hack. You pull a magic number out of thin air and that returns everything
to normal and leaves you with a changed exponent but the same mantissa.
Kay...look....don't look at me. I actually don't know how this works. The Quake guys
didn't know either. This right here. It is the original comment in the source code. WTF
indeed!
So look what we did. We replaced an expensive division and a multiplication with a bit shift
and a subtraction. That is so much cheaper. It is so much more 90s. We've got an extremely
close initial guess and with just a single round of Newton's method...we're good to go.
Understand this. No one is planning on launching a satellite into space with math like this.
But, it is definitely accurate enough to light an entire game arena without clunking that
90s PC behemoth. And that was the goal.
So for you gamers out there, maybe just take a moment, step back and appreciate all the
hard work that coders put into making your worlds look really awesome. And if you're
a coder, why don't you plan on keeping some of these dirty tricks up your sleeve so that
the next time you have to pull off the impossible, you'll be able to. Just...uh...don't tell
on me for telling you.
Chomp!