24
\$\begingroup\$

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;

}
Improve this question
\$\endgroup\$
5
  • 6
    \$\begingroup\$ That's not really a question - at the very least, you might declare this a community wiki page... \$\endgroup\$
    – Rachel Blum
    Jul 22, 2010 at 1:21
  • \$\begingroup\$ Done, community-ized. \$\endgroup\$
    – gak
    Jul 22, 2010 at 1:23
  • 3
    \$\begingroup\$ Screw that! just go with any and all code crafted by the great JC! \$\endgroup\$
    – Adam Naylor
    Jul 22, 2010 at 15:39
  • 3
    \$\begingroup\$ 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/… ) \$\endgroup\$
    – Ricket
    Jul 28, 2010 at 17:24
  • 8
    \$\begingroup\$ Also note that it's not John Carmack's. \$\endgroup\$
    – Kaj
    Jul 30, 2010 at 6:05

11 Answers 11

Reset to default
25
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
14
\$\begingroup\$

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.

a^2 + b^2 = c^2
(source: mathurl.com)

or

alt text
(source: mathurl.com)

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

alt text
(source: mathurl.com)

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Well to be honest, Pythagorean math is used ALL over game code, especially engines, such as physics code, rendering code, AI. \$\endgroup\$
    – Nick Bedford
    Jul 22, 2010 at 6:05
  • 1
    \$\begingroup\$ True. That's why it's a gem. ;) \$\endgroup\$
    – MrValdez
    Jul 22, 2010 at 7:36
  • 4
    \$\begingroup\$ 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. \$\endgroup\$
    – mmyers
    Jul 22, 2010 at 14:34
  • \$\begingroup\$ @mmyers - Another wonderful thing: if you're working in x^2 space, the distance isn't just relative. \$\endgroup\$
    – Steven Evers
    Jul 22, 2010 at 15:44
  • \$\begingroup\$ 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. \$\endgroup\$
    – Ricket
    Jul 28, 2010 at 17:31
13
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
10
\$\begingroup\$

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?!?"

Improve this answer
\$\endgroup\$
8
  • \$\begingroup\$ Omg. The goggles! They do nothing! \$\endgroup\$
    – Raoul
    Jul 22, 2010 at 9:02
  • \$\begingroup\$ The nested "do-while" inside the "switch-case" always makes me blink. Even 20 years later... \$\endgroup\$
    – Andreas
    Jul 22, 2010 at 15:14
  • 1
    \$\begingroup\$ -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) \$\endgroup\$
    – bobobobo
    Oct 12, 2011 at 3:47
  • 1
    \$\begingroup\$ @JoeWreschnig why not? Memcpy will always be more readable, portable and probably more optimized. \$\endgroup\$
    – kaoD
    Apr 8, 2012 at 10:23
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – user744
    Apr 8, 2012 at 12:07
7
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Almost works in C# (you need to declare a delegate type and insert at least one cast) \$\endgroup\$
    – finnw
    Oct 11, 2011 at 17:41
  • \$\begingroup\$ 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? \$\endgroup\$
    – Peter Cordes
    Oct 3, 2016 at 15:31
  • \$\begingroup\$ 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). \$\endgroup\$
    – Peter Cordes
    Oct 3, 2016 at 15:34
5
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
5
\$\begingroup\$

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

Read the full article for an explanation.

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ That link is now broken, so it would help to have an explanation here. \$\endgroup\$
    – finnw
    Oct 11, 2011 at 17:34
  • \$\begingroup\$ Thanks. He's gone and changed his website again. I updated the link. \$\endgroup\$
    – Anthony
    Oct 12, 2011 at 3:30
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Iain
    Jul 22, 2010 at 17:34
  • \$\begingroup\$ I think design patterns have their place. Not so much in games, though. \$\endgroup\$
    – blissfreak
    Nov 14, 2014 at 4:37
  • \$\begingroup\$ @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. \$\endgroup\$
    – Steven Evers
    Nov 15, 2014 at 5:42
4
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ It is, gosh! I've done lots of 3D and never really needed it. \$\endgroup\$
    – Skizz
    Jul 29, 2010 at 15:37
  • \$\begingroup\$ +1, it's the only way to go from x+y vector components to radians direction. \$\endgroup\$
    – RCIX
    Jul 29, 2010 at 15:53
  • 1
    \$\begingroup\$ @RCIX: My point is that that transformation is unnecessary, i.e. (x,y) -> angle, there is a vector solution to any angle problem. \$\endgroup\$
    – Skizz
    Jul 29, 2010 at 18:56
  • 6
    \$\begingroup\$ I wouldn't really call a bare standard library function a "gem". \$\endgroup\$
    – user744
    Jul 29, 2010 at 21:33
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – RCIX
    Jul 30, 2010 at 18:50
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • 5
    \$\begingroup\$ 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. \$\endgroup\$
    – Asmor
    Nov 23, 2010 at 19:11
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – George Duckett
    Oct 12, 2011 at 7:04
  • \$\begingroup\$ There's also "Some Old Hippy Came And Had Tripped On Acid" \$\endgroup\$
    – blissfreak
    Nov 14, 2014 at 4:40
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged .