Wikipedia: Making of Doom | Hacker News Reader

Wikipedia: Making of Doom

en.wikipedia.org

96 pointsolliesaunders32 comments

One really nifty piece of code that I associate id-software with is the 0x5f3759df hack. Though it was probably known before, Hakmem would be the first place to look.

I am sure there are many more such bit twiddling and magic number hacks, but nothing quite as useful to me than this magic to compute the reciprocal of a square root. The only other floating point operations that comes up this frequently in what I do are log and exp.

In my day to day coding (not that I code every day, far from it) I have nothing to do with game engines, yet inverse square root shows up in almost every corner (pun intended) in the vector manipulation code, for example in finding the cosine similarity between two documents.

Does not work for double precision, 64 bit, and nothing I write is so performance critical that it demands the use of this trick, but its still fun

    float Q_rsqrt( float number )
    {
        long i;
        float x2, y;
        const float threehalfs = 1.5F;
        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;
        i  = 0x5f3759df - ( i >> 1 );
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );
        return y;
    }

Taken from the wikipedia article http://en.wikipedia.org/wiki/Fast_inverse_square_root has the fuller story.

Yeah, this is really cool :) A favorite of mine is the xor-swap: While not useful in pratice for me, you can get quite stunned faces if you tell your friends, that a swap is possible without a third variable.

  x = x xor y
  y = x xor y
  x = x xor y

It's also possible to use addition and subtraction instead of xor.

FWIW, pretty much every 3rd (penultimate) year engineering student in India knows the xor-swap, I should think (only they might not call it that, because they've just memorised the procedure, and have very little idea why it works... /cynical)

This is one of the most common questions in 'technical interviews' when big IT companies are recruiting fresh grads.

(See http://www.allinterview.com/showanswers/17145.html)

I am not sure where your cynicism or contempt is coming from. There is not much to a deeper understanding of xor-swap. If one knows the xor truth table one knows why it works, and knowing the truth table is essentially an act of memorization. I hope they are exposed to digital logic way before 3rd year. On the other hand cases where this will not work in the current form, perhaps needs a somewhat deeper understanding of bit lay out. Say if one were to swap two unicode characters from void * pointers to them.

My cynicism (not contempt - I know that the students are under various sorts of pressures) stems from personal experience.

It's not much good explaining how simple it is to understand the xor-swap - it doesn't change the fact that the majority of engineering students go to the link like the one I posted, compile a list of questions and answers, and rattle off answers before the question is even completed in the interviews.

It's like knowing [any interesting method] can be used to accomplish a task, without knowing why said method works.

edit: I realise all this is OT, but I was downvoted for my earlier post and felt the need to defend it.

Am I the only one that thinks this would be a really BAD interview question? There'd be no way to tell if the candidate had memorised the answer or had worked it out on the fly.

To elaborate on its usefullness: An XOR-swap is only useful when you do not have space for a new pointer, otherwise, making a new temporary variable will on most processors be faster than XOR-swapping.

I would assume you need to be using regesters for three XOR's to be slower than a temperary variable.

been used in many-a-obfuscate-a-bug-contests for what happens when x == y.

I'm almost sad that this isn't useful on modern processors (thanks to an SSE instruction that computes this). It's just such a crazy math hack.

Worth reading: http://en.wikipedia.org/wiki/Masters_of_Doom

This is a great book. It basically goes over how the game industry was able to develop itself for the PC, which at the time people believed was only for work. The guys at I'd pioneered a lot of efficient technology whited allowed for games to even be playable on PCs.

+ one for this book. Excellent startup narrative.

+ one here too. Very good book, very nice narrative.

More fun Doom trivia on the origin of the (id)spispopd cheat code:

http://www.urbandictionary.com/define.php?term=idspispopd

The Smashing Pumpkins for their part continued to the joke by adding a sample from Doom to 'Where Boys Fear to Tread' on 'Mellon Collie and the Infinite Sadness'. The booklet contains the following credit: "Explosion from Doom courtesy of id Software, Inc and bobby prince Music""

This is a really great wiki entry. I was searching around after reading it and came across this pic from '92 which is really amazing: http://bit.ly/qxaxrC

Both Carmacks, Romero, Tom Hall, Kevin Cloud, etc in startup mode :D

I used to read their .plan's.... :o

Unshortened link: http://www.3drealms.com/bio/images/legacy_romero2.jpg

Why do people post bit.ly links in places where there is no char limit? Are people that conditioned by twitter?

I'm a data nerd and I like to see when people click on my links :) For example barely anyone clicked when I posted this on twitter vs. tons of exposure on HN: https://bitly.com/qxaxrC+

Dunno, I just enjoy keeping track of what I post and seeing what's popular, etc!

Fair enough, I guess I forgot about that. It's still a leap of faith to press a bit.ly link by paranoids like me. I should probably use an addon and forget about these.

Here's a video tour of their offices circa 1993, for those who haven't seen it. I think this is a cool look into the beginnings of the company and the (early) excitement surrounding Doom at the time.

http://www.youtube.com/watch?v=Q65xJfVkiaI

Haha great video! They're playing not completely finished Doom and sometimes it kicks them back to DOS with an error message like

File not found

Don't worry about "File not found"

Here is a 60min DOOM post-mortem by John Romero from the Game Developers' Conference.

http://www.gdcvault.com/play/1014627/Classic_Game_Postmortem...

If you look around the free section of the GDC site there are a lot videos about other classic games too

John Romero and Tom Hall, in fact.

It's quite an interesting talk - lots of people have interviewed John Carmack about the history of Doom, and he was certainly a core figure, but I enjoyed hearing a telling from outside the usual "id Software has been continuously successful for decades" frame of reference.

Gotta love the cool stop animated models they used for the sprites in the games, but here's the best bit that I didn't know:

(about the sources for some of the textures)"Among the more unusual sources, one texture was based on Adrian's snakeskin boots, and a bloody texture for the hell levels was created from a photograph of a wound on Cloud's knee"

Awesome. I thought the skin-wall textures in ep.3 were pretty gross. Eww! nerdscabs!

John Romero's blog has a lot of good content on the making of Doom and other classic id software games too: http://planetromero.com/

So, software invented on the NeXT includes Doom and the World Wide Web? Not bad for a failed platform.

If I remember well, the biggest problem with NeXT was that it was quite expensive! According to the "Master of Doom" book, Carmack pay around U$ 10,000 for one workstation in 1991.

And total non-sequitor (if you missed it the first time around):

How to burn a NeXTCube

http://simson.net/photos/hacks/cubefire.html

>and the editing tools were written in Objective-C.

I find this really interesting, Carmack's been using Objective-C long before he started his iPhone work.

Does that makes him a hipster?

I would pay decent money to see the movie remake, kickstarter anyone?

Reply on news.ycombinator.com