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/.
mmm i think there was a topic talking about math books every programmer should read or something like that i dont really recall it ... but it had some nice things on it.... not sure if it was here or stackoverflow aswell lol
The PNPOLY algorithm: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
@Prix: you mean this one: http://gamedev.stackexchange.com/questions/1210/good-3d-math-theory-books ;)
@Michael yep you nailed it, i didnt remember if it was related but was something like that :)
Any 3D graphics development requires a decent understanding of linear algebra. Vector math tutorial for 3D Computer Graphics is by far the best resource for learning vectors and matrices. It is also interactive that each section has a test question to verify and seal the understanding of that topic.
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, and Vector normalisation are essential.
How do I move my game object? The novice might say:
"I know! I'll just do:"
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 because they represent rotations almost as space-efficiently as Euler angles, without suffering from Gimbal lock. Gimbal Lock begins when any Euler angle reaches a rotation of 90 degrees around any axis: you immediately lose a degree of freedom. Quaternions address this issue by adding a fourth dimension. If you stuck with Euler angles, you'd have to restrict one axis to never rotating more than ~89 degrees.
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 why you will need to know physics equations:
- Making a ball bounce (see: co-efficient of restitution)
- Make a ball move in a direction with 'x' newtons of force
- Make something have more or less friction so it will slide at a different speed
- 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.
For physics, Chris Hecker's articles on rigid body dynamics, including collision response and restitution, are marvellous: http://chrishecker.com/Rigid_Body_Dynamics
"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.
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.
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.
If you are going to be writing a physics engine then much more than a physics class is going to be needed, you are going to need to know numerical methods.
You don't actually need quaternions to avoid gimbal lock. If you build a rotation matrix using Right, Forward, Up vectors (view it as a change of basis) then you won't ever experience gimbal lock. Gimbal lock happens only when you use Euler angles.
If used wrong (e.g. rotation recalculated from euler angles each frame), quaternions don't make a difference. But if used right (storing the orientation and adding/multiplying a rotational delta quaternion calculated from e.g. an axis and angle) they make life much easier, e.g interpolating between matrices is not as easy as slerping a quat and lerping a translation vector (and, maybe, a vector/scalar for scale).
I would add Game Theory to this answer. When designing game mechanics it's important to evauluate equilibria and stability in order to make it more balanced and therefore more long-lived. If you think about additive famous games (expecially browser games and strategy games) you'll realize that they rely on some mechanics and without thinking about it the game will get boring soon.
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.
- 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.
Calculus is a huge field. Probably only a small amount of it is needed for game development.
@Noldorin yep. In most situations understanding the relationship between the derivative, acceleration, velocity, and position might be enough...but calculus is awesome.
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.
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.
@Jonathan: Agreed, that and numerical integration methods should be sufficient for most things.
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.
A very basic one is the Pythagorean theorem. Also known as the distance formula.
bare the edges of a right triangle and
cis the hypotenuse. This means that in order to find the length of a vector, you do this:
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.
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))`
Also great is understanding it in the context of the trig identity sin²(x) + cos²(x) = 1.
- 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
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.
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.
@Tetrad Doesn't wikipedia give you that? http://en.wikipedia.org/wiki/Dot_product#Definition.
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.
For more details on W component see famous: Do I need the 'w' component in my Vector class? and What does the graphics card do with the fourth element of a vector as the final position?
A firm grasp of
/. Without them, you're completely screwed.
I think we can all agree this isn't what the question was asking. (also you forgot %).
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.
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.
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.
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).
Why isn't this higher? Half the programmers I've worked with can't use sines and cosines for the life of them.
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.
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.
I think you've got `Boolean` and `binary` mixed up. Not sure they're absolutely necessary for game programming.
@Skizz, good point - fixed. (And another minor point, it is a *wiki* - nothing stopping you from changing it. :)
At the very least you'll need.
- 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.
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.
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
This appears extremely impractical to me. Do you think Starcraft or Warcraft 3 were balanced using a method like this? I don't think so, I believe it was iteration and playtesting, and constant patching.
Uh, they almost certainly were, the initial warcraft armies were modified duplicates of each-other that were probably created with payoff matrices designed to make them balanced overall. After that they may have simply built upon what they learned to tune things, but they probably had to do it again with starcraft to gets some reasonable level of balance now that three different armies were involved, and again when starcraft II units were added. Obviously you don't simply stop at the model, playtesting often shows emergent properties, but a payoff matrix is how you initially model complexity.
It was this: http://www.amazon.com/Game-Architecture-Design-New-Edition/dp/0735713634/ref=pd_sim_b_1 I wish that amazon version enabled searching inside the book, because it might be a great thing to reference in bits for this site. Though maybe the amazon in-book search doesn't work that way. Anyway, that's where they went over payoff-matrices, using warcraft as an example, and the advantage for managing complexity was so clear it made me an instant convert. That's no guarantee that Blizzard actually used that approach, but they're smart guys, so they probably had a mathematical solution...
... at least for a way of being able to understand the balance at a glance. Obviously you want to add testing to that as well. I actually bought the book on the strength of a smaller, cut down pamphlet that had awesome game related content, including discussion of the payoff matrix and rock-paper-scissors relationships and all kinds of great stuff, and was disappointed to find that the final book is a tome, and deals a lot with C++ programming (which is not my thing), as well as AAA title management problems. Everything in the cut down pamphlet was great, though.