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;

}
\$\endgroup\$

closed as not constructive by Tetrad Jan 26 '12 at 7:18

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 '10 at 1:21
  • \$\begingroup\$ Done, community-ized. \$\endgroup\$ – gak Jul 22 '10 at 1:23
  • 3
    \$\begingroup\$ Screw that! just go with any and all code crafted by the great JC! \$\endgroup\$ – Adam Naylor Jul 22 '10 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 '10 at 17:24
  • 8
    \$\begingroup\$ Also note that it's not John Carmack's. \$\endgroup\$ – Kaj Jul 30 '10 at 6:05

11 Answers 11

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.

\$\endgroup\$
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)

\$\endgroup\$
  • \$\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 '10 at 6:05
  • 1
    \$\begingroup\$ True. That's why it's a gem. ;) \$\endgroup\$ – MrValdez Jul 22 '10 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 '10 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 '10 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 '10 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.

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

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

\$\endgroup\$
  • \$\begingroup\$ Almost works in C# (you need to declare a delegate type and insert at least one cast) \$\endgroup\$ – finnw Oct 11 '11 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 '16 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 '16 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

\$\endgroup\$
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.

\$\endgroup\$
  • 1
    \$\begingroup\$ That link is now broken, so it would help to have an explanation here. \$\endgroup\$ – finnw Oct 11 '11 at 17:34
  • \$\begingroup\$ Thanks. He's gone and changed his website again. I updated the link. \$\endgroup\$ – Anthony Oct 12 '11 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.

\$\endgroup\$
  • 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 '10 at 17:34
  • \$\begingroup\$ I think design patterns have their place. Not so much in games, though. \$\endgroup\$ – blissfreak Nov 14 '14 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 '14 at 5:42
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ It is, gosh! I've done lots of 3D and never really needed it. \$\endgroup\$ – Skizz Jul 29 '10 at 15:37
  • \$\begingroup\$ +1, it's the only way to go from x+y vector components to radians direction. \$\endgroup\$ – RCIX Jul 29 '10 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 '10 at 18:56
  • 6
    \$\begingroup\$ I wouldn't really call a bare standard library function a "gem". \$\endgroup\$ – user744 Jul 29 '10 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 '10 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.

\$\endgroup\$
  • 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 '10 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 '11 at 7:04
  • \$\begingroup\$ There's also "Some Old Hippy Came And Had Tripped On Acid" \$\endgroup\$ – blissfreak Nov 14 '14 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.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.