# What are your favourite game-specific coding gems? [closed]

I'll start off with John Carmack's the Fast Inverse Square Root in Quake III:

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;

}

• That's not really a question - at the very least, you might declare this a community wiki page... Jul 22, 2010 at 1:21
• Done, community-ized.
– gak
Jul 22, 2010 at 1:23
• Screw that! just go with any and all code crafted by the great JC! Jul 22, 2010 at 15:39
• By the way, do note that there's a more accurate "magic number" to use in the fast inverse square root function: 0x5f375a86 ( en.wikipedia.org/wiki/… ) Jul 28, 2010 at 17:24
• Also note that it's not John Carmack's.
– Kaj
Jul 30, 2010 at 6:05

mapValue function:

float mapValue( float inVal, float inFrom, float inTo, float outFrom, float outTo )
{
float inScale = (inFrom != inTo)
? ( ( inVal - inFrom ) / ( inTo - inFrom ) )
: 0.0f;
float outVal = outFrom + ( inScale * ( outTo - outFrom ) );
outVal = (outFrom < outTo )
? clamp( outVal, outFrom, outTo )
: clamp( outVal, outTo, outFrom );
return outVal;
}


It takes a value, converts it to a proportion within a range, and then scales that relative to another range. Like a double-lerp.

You can use it to normalise stuff:

float minDamage = 0.0f; float maxDamage = 300.0f;
float normalisedDamage = mapValue(damange, minDamage, maxDamage, 0.0f, 1.0f);


Or you can convert from one range to another:

float brakeStrength = mapValue(timeToCollision,
0.0f, 10.0f, // seconds
1.0f, 0.2f // brake values
);


Notice in the second example that the out range is a different order to the in range.

It doesn't look like much, but I use this little fella all over the place.

I still can't believe how many times I've used the Pythagorean Theorem in my game code. To me, this simple formula is a gem in game development.

(source: mathurl.com)

or

(source: mathurl.com)

and when only relative distance matters it can be used without expensive square root operation

(source: mathurl.com)

• Well to be honest, Pythagorean math is used ALL over game code, especially engines, such as physics code, rendering code, AI. Jul 22, 2010 at 6:05
• True. That's why it's a gem. ;) Jul 22, 2010 at 7:36
• An interesting variation is when you only care about the relative distances. Then you can skip the potentially expensive sqrt call and simply compute distance2 = x^2 + y^2. Jul 22, 2010 at 14:34
• @mmyers - Another wonderful thing: if you're working in x^2 space, the distance isn't just relative. Jul 22, 2010 at 15:44
• Thank you for mentioning the relative distance bit. I have seen way too many unnecessary square root operations, just as people using A* when they should be using something less exact. Jul 28, 2010 at 17:31

The biggest one from me was reading about Scott Bilas's GameObject system. Even though I don't use a database system like he does, it stopped me making 6 level inheritance trees and got me creating a component system which is much more manageable and reusable.

I have to go with Duff's Device. It was the first block of code that literally made my jaw drop. "You can do that?!?"

• Omg. The goggles! They do nothing! Jul 22, 2010 at 9:02
• The nested "do-while" inside the "switch-case" always makes me blink. Even 20 years later... Jul 22, 2010 at 15:14
• -1. I don't like this one. Its not very useful today (you would use memcpy instead, if you want other people to be able to read your code) Oct 12, 2011 at 3:47
• @JoeWreschnig why not? Memcpy will always be more readable, portable and probably more optimized.
– kaoD
Apr 8, 2012 at 10:23
• @kaoD: Because memcpy is not equivalent to Duff's device - it doesn't matter how "readable, portable, and probably more optimized" it is if it doesn't do the same thing! Modern CPU pipelines will probably do better without Duff's device than with it because of branch prediction and instruction caching, but that has nothing to do with memcpy.
– user744
Apr 8, 2012 at 12:07

A small C/C++ snippet from a game I helped write many years back:

(fill ? FillRect : DrawRect) (x, y, w, h, colour);


On my first game (this) I needed to access more than 1Mb of RAM, and, this being before the internet took off, I had no documentation for XMS and EMS that DOS apps used to access the extra RAM.

So, I ended up using a small 'backdoor' that featured in the 386 with regard to the segment registers. Normally, in real mode, the address was calculated as seg*16+off which limited you to 1Mb.

However, you could switch to protected mode, set up a segment to address 4Mb, switch back, and provided you didn't write to the segment register (which was OK since DOS only used the 8086 segment registers), you could access the whole 4Mb as a flat address space. Flipping back to real mode was necessary if you wanted to use the DOS services.

There weren't many DPMI extenders available either.

• Almost works in C# (you need to declare a delegate type and insert at least one cast) Oct 11, 2011 at 17:41
• You mean with 32-bit addressing modes in real mode? (i.e. requiring an address-size prefix). Are you sure it was necessary to set up a segment descriptor, and that it didn't actually use segment register as the normal 16*FS + whatever? I didn't think segments even had limits in 16-bit mode, just the base address (16 * their value), so couldn't you just set FS to something in 16-bit mode, and use [fs:esi] or whatever to access whatever you wanted? Oct 3, 2016 at 15:31
• I haven't tried this, or written any real code for 16-bit mode, just 32 and 64 bit asm, but it sounds weird. Hmm, plausible though. Modern CPUs definitely cache segment stuff internally, and only re-load those caches when you write to segment regs, so maybe that's how it kept the protected-mode base+limit (if that's actually what happened, and you weren't just using the 4MB starting at 16*FS). Oct 3, 2016 at 15:34

Personally I'm a big fan of the Mersenne Twister for predictable random numbers, especially if you need to create a several differently seeded instances of Rand

http://en.wikipedia.org/wiki/Mersenne_twister

Here's one mentioned by Chris Crawford (and apparently used by Atari) which he calls 'A Graphics Trick':

LDA FIRST
EOR SECOND
AND CONTROL
EOR SECOND
STA OUTPUT


• That link is now broken, so it would help to have an explanation here. Oct 11, 2011 at 17:34
• Thanks. He's gone and changed his website again. I updated the link. Oct 12, 2011 at 3:30

For some reason, people often underrate the power of design patterns in games. I've seen nearly every single GoF pattern applied with success to games.

• One of the things I like about games programming is getting away from the standard GoF way of "correctness" and just focussing on pure lovely speed! That said, I've seen a lot of bad implementations of MVC in games which do more harm than good.
– Iain
Jul 22, 2010 at 17:34
• I think design patterns have their place. Not so much in games, though. Nov 14, 2014 at 4:37
• @blissfreak: There's nothing special about game programming that makes it some kind of wild west where patterns aren't common. They are ridiculously common and here are some examples. Nov 15, 2014 at 5:42

Math.atan2() is extremely useful (along with all of trig).

• It is, gosh! I've done lots of 3D and never really needed it. Jul 29, 2010 at 15:37
• +1, it's the only way to go from x+y vector components to radians direction.
– RCIX
Jul 29, 2010 at 15:53
• @RCIX: My point is that that transformation is unnecessary, i.e. (x,y) -> angle, there is a vector solution to any angle problem. Jul 29, 2010 at 18:56
• I wouldn't really call a bare standard library function a "gem".
– user744
Jul 29, 2010 at 21:33
• @Skizz: Maybe for 3d, but i know of no other way to take a normalized vector and extract a radians direction value. Which as a good deal of value in 2D games.
– RCIX
Jul 30, 2010 at 18:50

To add to the pythagorean gem above...
I always tell people that for 3d programming they need only know:
- a^2 + b^2 = c^2
- soscastoa (sin = opposing side / sloped side, cos = attached side / sloped side, tan = opposed side / attached side)
- a . b = |a| * |b| * cos alpha
- a * b = |a| * |b| * sin alpha * unit vector
It can solve pretty much any 3d (or 2d) problem you encounter in game development - 4 rules.
Sure, there are nicer ways, but this can solve em all - I should know, I'm a hack that based a career on em.

• re:soscastoa I think most people know that as sohcahtoa (replacing 'sloped side' with the more specific, if admittedly more obscure, 'hypotenuse'). Flows off the tongue easier, and I think thus easier to remember. Nov 23, 2010 at 19:11
• I'll always prefer 'The Old Arab Sat On His Camel And Howled', since secondary school (high school age) it's been imprinted on my brain. Oct 12, 2011 at 7:04
• There's also "Some Old Hippy Came And Had Tripped On Acid" Nov 14, 2014 at 4:40

One of my favorites is the assembly language version of 'Life', and the whole description of optimizing it, in "The Zen of Code Optimization" by Michael Abrash.

I'd recommend any of his books to anyone looking for coding gems.