Higher-Order Fun

Game Design & Game Programming

Month: June, 2009

Math for game programmers 03 – Geometrical representation of vectors

In the previous post, we introduced vectors, and showed some very elementary uses for them. We presented them as a simple and convenient way to pack a number (3, in our case) of scalar values into a single object. Now, we’ll consider their geometrical representation, which will help you grasp them more intuitively. For simplification’s sake, we’ll use two-dimensional vectors for all our examples, but the same extends to 3D vectors.

Points

First, consider two points, A and B. A is located at (1, 2), and B is located at (4, 3) (If you are unfamiliar with the cartesian plane, points are represented as coordinate pairs in the form (x,y), so (1, 2) means that A is at x=1 and y=2), as shown in the following picture:

vectors_fig1As we’ve mentioned in the previous post, positions in space can be represented as vectors. So we would have a vector A and a vector B, each representing one of the points in the figure. But points are not the SAME as vectors! A vector should always be thought of as a “delta”, it’s merely an increment. Without a reference, it’s meaningless as a position. For points, we adopt the point (0,0) as our origin (represented by the letter O), so all points can be represented as a vector from the origin. Drawing our vectors as arrows, we get this:

vectors_fig2Consider it for a moment. If we have O=(0,0), and we add a vector A=(1,2) to it, you’ll get the point (0+1, 0+2) = (1,2), which is exactly our original point A. However, vector A by itself is merely an increment of 1 in x and an increment of 2 in y… As such, we could also represent it as:

vectors_fig4This might all sound confusing, but don’t worry, it’ll eventually “click” into place! If you don’t fully understand the concept now, don’t worry about it.

Addition and Subtraction

What if you took vector B and subtracted A from it? From our previous lesson, we know that B – A is simply (B.x – A.x, B.y – A.y), so, given that B = (4, 3) and A = (1, 2), B-A = (3, 1). Let’s call that vector “C”. If we do A + C, we should naturally get B back: (1, 2) + (3, 1) = (4, 3). If you remember that we said that vectors are merely offsets, then this means that we can represent C as the vector that takes “A” and turns it into “B”, as in the following picture:

vectors_fig3If you look to the axes, you’ll see that vector C (the orange vector) spans x from 1 to 4, meaning that its x component is 3 (4-1), and y from 2 to 3, meaning that its y component is 1 (3-2).

Length and Distances

The geometrical representation of vectors leads to a very intuitive way to understand one of their most important operations, length. The length of a vector (or magnitude) is simply its geometrical length! Take vector B, for example. It has a x component of 4, and a y component of 3. How can we get its length? The pythagorean theorem solves that for us: we simply take the square root of the sum of its squared components. For a 2D vector, length = sqrt(x²+y²). For a 3D vector, length = sqrt(x²+y²+z²), and so forth.

For example, the length of vector B is sqrt(3²+4²) = sqrt(25) = 5.

One immediate use for the length operation is to find distances. Say that you want to find the distance between points A and B. You subtract one from the other (order doesn’t matter), and take its length. In C++, that would look as simple as:


float distance = (a-b).length();

The reason why the order of the subtraction doesn’t matter is that (A-B) results in the opposite vector of (B-A), that is, a vector with the same length, but opposite direction. A-B results in (-3,-1), and B-A in (3,1). Both have a length of sqrt(10).

Math for game programmers 02 – Vectors 101

If you don’t already use vectors (and I mean vectors in the MATHEMATICAL sense, not in the “dynamic array” sense that languages like C++ or Java use), this is probably going to be the single most useful piece of math you can learn for writing games. It’s easy, efficient, and makes your code much shorter. In fact, provided that you’re using a language that supports definition of operators for user-defined types (like, say, C++ or Haskell), using vectors is going to be extremely intuitive and simple.

Motivation: The Ugly Code

Consider that you want to simulate some simple physics, such as an object accelerating in 3D space. We’re going to use the formulas Δs = v₀t + ½·a·t² and Δv = a·t (where s is the position, v₀ is the speed at the start, a is the acceleration, and t is the elapsed time). You might declare the object as something like this:


class PhysicsObject {
  public:
    float pos_x, pos_y, pos_z; // Position
    float vel_x, vel_y, vel_z; // Velocity
    float imass; // The inverse of the mass (1/m)

    void addImpulse(float force_x, float force_y, float force_z, float t) // t is time, in seconds
    {
        float halft2 = 0.5f * t * t;

        float accel_x = force_x * imass;
        float accel_y = force_y * imass;
        float accel_z = force_z * imass;

        pos_x += vel_x * t + accel_x * halft2;
        pos_x += vel_y * t + accel_y * halft2;
        pos_x += vel_z * t + accel_z * halft2;

        vel_x += accel_x * t;
        vel_y += accel_y * t;
        vel_z += accel_z * t;
    }
};

Not very pretty – there’s a lot of redundancy – whatever you do for one axis, you do for the other two. If only there was a way to do that all at once…

Enter vectors: The Pretty Code

Here’s the same code, but this time using a hypothetical 3d vector class:


class PhysicsObject {
  public:
    vector3f pos; // Position
    vector3f vel; // Velocity
    float imass; // The inverse of the mass (1/m)

    void addImpulse(vector3f force, float t) // t is time, in seconds
    {
        vector3f accel = force * imass;
        pos += vel * t + accel * (0.5f * t * t);
        vel += accel * t;
    }
};

Much shorter, isn’t it? You now have half as many lines to write, test and debug. Not only that, but they’re also simpler, and you avoid a whole class of “copy-paste but oops forgot to change a letter in one place” bugs. So, after all, what ARE these vectors? How do they work?

P.S.: If you’re using a language which does not allow you to define your own operators, the code above will get quite uglier… Java, I’m looking at you.

Defining vectors

If you go check Euclidean Vector at Wikipedia, you’ll see that it’s defined as a geometric object that has magnitude (length) and direction. For our purposes, while important to remember that definition, we’ll think of vectors as an n-tuple of a given type. In the example about, we have a 3-tuple (“a triple”) of floats. In other words, our definition would be something like this:


class vector3 {
  public:
    float x, y, z;

    inline vector3 operator + (const vector3 &param) const
    {
        return vector3(x + param.x, y + param.y, z + param.z);
    }

    inline vector3& operator += (const vector3 &param)
    {
        x += param.x;
        y += param.y;
        z += param.z;
        return *this;
    }

    inline vector3 operator * (float param) const
    {
        return vector3(x * param, y * param, z * param);
    }

    // Lots of other methods here
};

Basically, all it does (so far) is take basic arithmetic operators and apply them to 3 values, instead of just one. When you add two vectors, it adds each component – x to x, y to y and z to z. There’s also the “scale” operator, which is the multiplication by a scalar (a scalar is a non-vectorial number, like a float). When you multiply a vector by a scalar, you simply multiply all components by it. So, if you want to make your vector twice as big, just multiply it by 2.

That’s it! That’s the basic idea! Whenever you have two or more points and always want to perform the same set of operations on them, use a vector! In fact, most properties that apply to scalar numbers will also work here… If you happen to know that you need to multiply velocity by time to get a change in position, you can do that with vectors in just the same way you would with scalars.

When should you use vectors like this? Whenever it makes sense. If you’re passing along two or three values which all represent the same point, do yourself a favor and pack them in a vector. Not only will it be much harder to accidentally mix up stuff, your code will be shorter. Even if they aren’t a POSITION, they might still be represented by a vector – for example, the size of a rectangle is a vector where x is the width and y is the height. That way, if you have a vector representing the starting position of the rectangle, and a vector representing its size, you can easily find its ending position by adding them up.

But vectors are far more powerful than this. On the next article, we’ll explore other common operations done on them, such as length, normalization, dot product and cross product. You wouldn’t believe me if I told you just how damn useful those can be.

Math for game programmers 01 – Introduction

Here comes a harsh fact of life: game programming requires mathematics. One could say that programming IS, in a way, math, but you don’t really need to know math to write the vast majority of programs. Most of the time, you don’t need it to write parsers, to interact with databases, to validate data. Games, however, very often rely on mathematics. If you want objects to move across your world realistically, or if you want to draw things on the screen following certain geometric patterns, or if you want to check for collision between certain shapes, you need math.

But don’t despair! Even though I say “math”, what you ACTUALLY need is geometry. Luckily for us, geometry is probably the easiest part of mathematics! Now, I’m not saying that discrete mathematics, algebra and calculus are useless for writing games (or other sorts of programs), but geometry is the bread and butter of video game programmers.

An interesting thing that I did notice is that, despite my previous assertion, many game programmers do not actually know much geometry! This means that they’ll often do things in extremely laborious, buggy and verbose ways, when it could very easily be done with some basic grasp of geometry. For example, if you want to place several objects along an arc of circle, you COULD do it through trial and error, or place it in an image editing program (like Photoshop) and copying the coordinates, but it will be much easier if you simply use a parametric equation.

So I intend to write a few posts to explain, as clearly as I can, some topics that are important to game programming. These are the topics that I intend to cover:

  • Vectors
  • Parametric Equations
  • Vector bases
  • Basic Trigonometry
  • Matrices
  • Complex Numbers
  • Quaternions

While there are many basic and in-depth tutorials of all of the above topics on the Internet, explanations as to why the matter to game programmers and how to use them seem to be scarce, or left as an exercise to the reader. My goal is to make those topics easy to understand and put into use.

main = putStrLn "Hello world!"

Hello, my name is Rodrigo Monteiro, and this is my shining, brand-new blog. I have been a hobbist game designer and programmer for over a decade now, and have recently moved into the realm of professional game development. I am also creator of the “Aegisub” subtitling program, which is the de facto standard for anime subtitling, used by the vast majority of fansubbing groups worldwide. I intend to write thoughts and tutorials on game design, programming, and my recent musings with the development of games on functional languages (e.g. Haskell).