Sunday, January 9, 2011

What math should all game programmers know?

Simple enough question: What math should all game programmers have a firm grasp of in order to be successful?

I'm not specifically talking about rendering math or anything in the niche areas of game programming, more specifically just things that even game programmers should know about, and if they don't they'll probably find it useful.

Note: as there is no one correct answer, this question (and its answers) is a community wiki.

Also, if you would like fancy latex math equations, feel free to use http://mathurl.com/.

From game development Tetrad

  • A very basic one is the Pythagorean theorem. Also known as the distance formula.

    a^2+b^2=c^2 where a and b are the edges of a right triangle and c is the hypotenuse. This means that in order to find the length of a vector, you do this:

    distance = sqrt( a^2 + b^2 )

    Another note of interest is that if you're just comparing distances, you don't have to take the square root (which can be relatively costly). That's why most frameworks have a "distance squared" or "length squared" function for their vectors.

    Ricket : I'm pretty sure I've read this somewhere else on this site before :)
    Tetrad : Sure, this post was inspired by that thread/comment.
    mmyers : I'm getting some déjà vu here... :)
    greyfade : More generally, the length of a vector is the square root of the dot product with itself. So, `sqrt(V dot V)` is its length. So, the distance between two points is: `sqrt((A-B) dot (A-B))`
    Joe Wreschnig : Also great is understanding it in the context of the trig identity sin²(x) + cos²(x) = 1.
    From Tetrad

  • The PNPOLY algorithm: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

    DFectuoso : Great one, this one is a must
    RCIX : Not sure why. Libraries can take care of this for you....
    coderanger : Most of the things mentioned in this thread can be handled my a library or engine, that doesn't mean you shouldn't learn them anyway.
    Skizz : I wouldn't say that `this one is a must` considering that polygon based games account for a small percentage of all games made (most games are written in Flash after all).
    coderanger : Not sure why you think a Flash game doesn't use polygons. Perhaps you are thinking that this is related to 3D programming, which is isn't (at least not directly). This is more generally used for things like collision detection.
    From coderanger

  • Binary and Hexadecimal numbering systems, and how to convert them to/from decimal numbers.

    Although you won't generally need to work with raw Binary numbers, they are frequently used for Flag variables, which require boolean logic and bit-shifting.

    Hex isn't quite as important (unless you want to process 0xDEADBEEF), but at a minimum, you'd want to recognize when they're being used, and why.

    Joe Wreschnig : If you can't read hex, you can't effectively program. Most bitwise constants in C and C++ are going to be specified as hex values.
    Skizz : I think you've got `Boolean` and `binary` mixed up. Not sure they're absolutely necessary for game programming.
    Cyclops : @Skizz, good point - fixed. (And another minor point, it is a *wiki* - nothing stopping you from changing it. :)
    From Cyclops

  • I dream of the day when game development is as data driven as art production. I don't see it anywhere on the horizon so for now knowing some math appears to be a necessity.

    Math is like technique, the more the better, as long as you can apply it.

    Here is the order of importance I see.

    • Arithmetic
    • Linear Algebra (with geometric interpretations)
    • Calculus (physics)
    • Combinatorics (randomized levels)
    • Probability (balancing)
    • Statistics (Bayesian esp. for AI)

    I could keep going. The more you know the better, but learning a bunch of math doesn't mean you will make a great game, but it can help.

    Noldorin : Calculus is a huge field. Probably only a small amount of it is needed for game development.
    Jonathan Fischoff : @Noldorin yep. In most situations understanding the relationship between the derivative, acceleration, velocity, and position might be enough...but calculus is awesome.
    Joe Wreschnig : Bayesian AIs tend to be unused for games because of comparatively large memory usage, poor debuggability and predictability, and a well-defined problem space. A good implementation of classic search with clever heuristics is usually (but not always) a better tool.
    Jonathan Fischoff : To me its not a particular Bayesian algorithm that I find important, but understanding the reasoning process as espoused by E. T. Jaynes. I don't think is anything inherently slow about Bayesian reasoning.
    Noldorin : @Jonathan: Agreed, that and numerical integration methods should be sufficient for most things.
    Rushyo : Statistics are wonderful when you're developing an AI, or just generally developing a management/tycoon game. On the other hand, I have no familiarity with calculus at all. I'd argue statistics and probability are essentially the same thing for learning purposes as the field of statistics stems from work on probability. It's very subjective.
    From Jonathan Fischoff

  • A firm grasp of +, -, *, and /.
    Without them, you're completely screwed.

    coderanger : I think we can all agree this isn't what the question was asking. (also you forgot %).
    RCIX : Other answers get voted up for this (basic arithmetic)....
    Joe Wreschnig : Not just basic arithmetic, but understanding how the operations all work in twos-complement, fixed point, and IEEE floating point environments. Without a firm grasp on why 0.1 * 3 != 0.3, or why -x might not be what you expect, you are screwed.
    From The Communist Duck
    • Vectors both 3D and 4D, and what the W component should be set to
    • Left-hand and right-hand coordinate systems, and which one your game is
    • The dot product, and what it's useful for
    • The cross product, and what it's useful for
    • Matrices, how they represent orientation and position and how you can combine them
    • Quaternions

    Even if you're not The Graphics Guy, you're going to use vectors and vector maths 80% of the time. They're the onions of our fun bolognese.

    Tetrad : This isn't a bad list, but I was hoping for a more descriptive answer. I.e. what the dot product formula is, what it means, and how it's useful.
    Jonathan Fischoff : @Tetrad Doesn't wikipedia give you that? http://en.wikipedia.org/wiki/Dot_product#Definition.
    Tetrad : Not for games specifically, no.
    Kaj : It does. It tells you the dot product is the cosine of the angle. That's all you need to know (and can know), as the application is still dependent on what you want to use it for. Orienting AI? You need the angle, so the dot is your friend. Rendering light? You need the angle. All that can be said is that it (dot product in this case) defines the cosine of the angle times length of vector a, times length of vector b. That is the knowledge that can be given. What part of it to use, and how, can't be told as the applications are infinite.
    From tenpn

  • Yeah, game programming tends to be pretty math-intensive. What math you need depends on what you're working on. Basic arithmetic is a must, of course, just as it is in all programming. Beyond that:

    Geometry is vital to any graphics work. If you want to display things on screen, you need to understand coordinate systems. And if you want to move them around in anything but the cardinal directions, you'll be completely lost without a solid grasp of sines, cosines and vectors (basic trig). And if you need to work in 3D, the geometry and trig requirements get a lot more complicated.

    If you want to model any sort of remotely realistic physics, you need calculus for that. (It's what drove Newton to invent calculus, afterall.)

    Any sort of probability calculations require knowledge of statistics and probability theory in order to get sane results without insane amounts of trial and error.

    There's probably a lot more, but that's what comes to mind just off the top of my head.

    Allan : +1 in my simple Flash games I use trig a lot.
    Mason Wheeler : I remember when my little brother tried to make a Bang-Bang game as a project for his high school VB class. He had everything worked out, except he had no idea how to make the cannonballs fly in an arc based on angle and power, because he hadn't taken Trig 1 yet. After I explained the basics, it worked just fine.
    Skizz : @Mason: No Trig needed for the arc, just use `s=u.t + a.t.t/2`. You need trig to get the initial velocity though (u).
    zaratustra : Why isn't this higher? Half the programmers I've worked with can't use sines and cosines for the life of them.
    Mason Wheeler : @Skizz: Yeah. You need trig to turn an angle and a power into an initial vector. After that you just need an animation loop and a gravitic constant.
    From Mason Wheeler

  • At the very least you'll need.

    • Algebra
    • Basic Geometry
    • Basic Trigonometry

    You'll also want to have at least a working knowledge of Vector operations, and you'll want to know what a Matrix is and what it can be used for, although the details won't be strictly necessary.

    If you'd like to get into graphics programming you'll need a hell of a lot more math knowledge, but doing general gameplay programming does not have to be so math intensive.

    From jessecurry

  • I'm surprised that no one mentioned Quaternions. I don't have a lot of experience with different engines but at least JME uses it everywhere and I got the impression that they're a pretty important concept.

    tenpn : er I mentioned quaternions.
    Raoul : Ahh, sorry, I missed it.
    Skizz : For the 1% of game programmers that write low level animation code in the rendering engine, quaternions are a useful tool. For the other 99% of game programmers, they're not really needed.
    From Raoul

  • There are many other forms of math that are useful, but at the absolute minimum you need to know these:

    • Algebra and Arithmetic

    These are pretty basic, but if you don't know these you won't have a chance at even being a programmer let alone a game developer.

    Objects in a game world are represented with vectors. A vector represents things like an object's position, look direction and speed. Vector math calculations such as the Dot Product, Cross Product, Vector normalisation are essential.

    How do I move my game object? The novice might say:

    "I know! I'll just do:" object.position.x++.

    No no no. You need to use a vector calculation. The object needs a position, direction and acceleration vector which you can use to move the object. If you do the novice thing, you'll get stuck in an unmaintainable mess, and how do you make it move in a direction not aligned with the world's XYZ axis?

    Main reason games use quaternions is to eliminate gimble lock. Gimble lock is that effect where when you move your mouse to look down, it will stop when you look directly down. Think about it, in games where you are in a space ship this would be pretty stupid if your camera stopped when you looked at the 'floor'.

    If you are going to be programming the math for physics responses in a game, then taking a physics class wouldn't have been a bad idea.

    Reasons will you need to know physics equations:

    1. Making a ball bounce (see: co-efficient of restitution)
    2. Make a ball move in a direction with 'x' newtons of force
    3. Make something have more or less friction so it will slide at a different speed
    4. Collision responses: What direction will the object rotate when I hit it 'here'?

    If you use a physics engine (or a game engine which has the physics engine inbuilt) then you can get away with knowing very little about physics. Still, it's quite good to know when you need to get your hands dirty because the physics engine isn't performing properly.

    tenpn : For physics, Chris Hecker's articles on rigid body dynamics, including collision response and restitution, are marvellous: http://chrishecker.com/Rigid_Body_Dynamics
    Andrew Russell : You mentioned quaternions but not transformation matrices??
    Joe Wreschnig : "Gimble [sic] lock is that effect where when you move your mouse to look down, it will stop when you look directly down...." Actually that is usually done for player sanity, and has nothing to do with gimbal lock.
    Skizz : It amazes me just how often quaternions are linked to gimble lock. I've written 3D games with no quaternions whatsoever and never had a gimble lock problem. If you really understand 3D maths and know what a gimble lock actually is, then you won't have that problem.
    Jason Kozak : Gimbal lock is actually caused by naive rotation with Euler angles (commonly Tait–Bryan angles: Yaw, Pitch, Roll). Alternative representations like Axis-Angle can also be used to prevent its occurrence. Quaternions however have the benefit of easy interpolation, and are generally preferred for that reason.
    From Brock Woolf

  • Making games is about bringing "real" life to virtual reality. It is better to know more about real world/universe than less :).. Math is only tool. And if You are making a plan, You have to put time for studying in plans too.

    EDITED: I saw some misunderstanding :).. I think that set of math acquirements what You need to rule, depends on concrete things what You want to describe. Nobody knows everything. And better way how to do it is. Not to learn everything on beginning, but learn little piece , use, learn, use etc. Then You can do it during development, if You have good plan.

    tenpn : How much real life is there in tetris?
    samboush : A lot of :). Tetris is about logical thinking under the presure. Like other logical games. It's about practising. More practising, more presure u can handle and still have fun from it. It seems like real life to me :)...
    Heath Hunnicutt : @samboush, you don't make sense when you fail to address the question fairly.
    samboush : @Heath Hunnicutt, You are right.
    Heath Hunnicutt : @samboush, I really respect that response.
    From samboush

  • No mentions of the foundational maths of computer programming? Graph theory, number theory, set theory, and concrete mathematics, usually all lumped together into painful and poorly-taught class called "discrete mathematics" at university.

    "Stupid bit tricks" save every kind of program time (and they're also usually equivalent to some string tricks and set tricks), graph types and traversals are used all over the place (even if you're just picking STL containers), and algorithmic complexity is key to optimization as languages get to higher levels.

    From Joe Wreschnig

  • I think the payoff matrix is a pretty essential tool. Games are often more fun when they approach some interesting zero-sum fair play balance, and payoff matrices help you quantify that in complicated cases. I guess this wikipedia article is as good as any, and gets the basic necessary concept across: http://en.wikipedia.org/wiki/Normal-form_game

    From Tchalvak

  • Besides sines and cosines (which 50-75% of programmers I've met didn't know how to use), learn the magical arc-tan function and how it can be used to get the angle of any vector.

    From zaratustra

  • Understand the dot product: If two vectors have about same direction, (theta < 90 deg), then the dot product is positive, or else, negative. It can be used to test whenever the player is in sight (assuming FOV is 90 deg).

    And generalize your 2D game to higher dimensions. (use vector calculations)

    If you can implement a 3D engine by yourself, you are good to go.

    From SHiNKiROU
Posted by Mu Cat at 12:24 AM

0 comments:

Post a Comment

Subscribe to: Post Comments (Atom)