Higher-Order Fun

Game Design & Game Programming

Tag: tutorial

Math for Game Programmers 05 – Vector Cheat Sheet

This is the long due fifth article in this series. If you aren’t comfortable with vectors, you might want to take a look at the first four articles in this series before: Introduction, Vectors 101, Geometrical Representation of Vectors, Operations on Vectors.

This cheat sheet will list several common geometrical problems found in games, and how to solve them with vector math.

Read the full article »

Multi-thread OpenGL texture loading

Those who have used OpenGL are probably aware that you can only invoke OpenGL procedures for a given context on the thread that currently owns it – usually, the main thread. This leads many programmers to assume that OpenGL is strictly single-threaded, and that no loading can be done on the background, inside some loader thread. This is not the actual case, and it’s actually fairly simple to work around this.

The key to multi-threaded OpenGL is in creating multiple contexts that share data between them. On Windows, it is done with the wglShareLists() procedure. On X and Apple APIs, it can be done during context creation (glXCreateContext() and aglCreateContext(), respectively). It boils down to creating a second context for the loader thread, and setting it to share data with the main context. This way, all data loaded on the second context will be available on the main one – you can just create a texture normally on the loader thread, and then glBindTexture() it on the main thread, for example.

On Windows/C++0x, the code looks like this:

void startLoader(HWND hwnd)
{
	// Assuming that this is the main thread
	HDC hdc = GetDC(hwnd);
	HGLRC mainContext = wglGetCurrentContext();
	HGLRC loaderContext = wglCreateContext(hdc);
	wglShareLists(loaderContext, mainContext); // Order matters

	boost::thread([=] () {
		wglMakeCurrent(hdc, loaderContext);
		runLoader();	// Your method for loading textures
		wglMakeCurrent(nullptr, nullptr);
		wglDeleteContext(loaderContext);
	});
}

Most APIs (such as Allegro, SDL, wxWidgets, etc) will provide you with a simple method of retrieving the window handle, which is all that you require to call the above procedure.

Note that you could create the context and share the lists inside the loader thread, but wglShareLists() must be called BEFORE anything is done on the main context, so the safest way is to do it on the main thread (otherwise, the new thread could take a while to run and be too late to do it).

IMPORTANT! I have observed that, on some cases (Windows 7 64, NVIDIA 320M), attempting to use a texture after it has been created (via glGenTextures()) but before its data finished uploaded (in this case, via glTexSubImage2D()) resulted in the texture being corrupted, and remaining corrupted even after it was uploaded. This will happen even if you wait for glTexSubImage2D() to return before using it on the main thread, since OpenGL is asynchronous. To avoid this problem, make sure that you glFinish() the loader thread before you attempt to use any textures initialized there.

Understanding the Game Main Loop

Video games are simply ordinary software – there’s nothing intrinsically special about them. However, they SEEM to behave in a very different way from your ordinary everyday applications – so much that many experienced programmers are at a complete loss when faced with the task of developing a game from scratch. This difference is mostly caused by game’s close ties to their main loop. In this article, we’ll examine what is the main loop, how it works, and why it’s important.

A simple model

How simply could we model a computer game? Let’s start by separating the game in two parts: the data inside the computer, and everything outside the computer. This might seem like a strange thing to say, but remember that games are, first and foremost, interactive software. So, outside the computer, we have (at the very least) the player. Inside the computer we have all sorts of data, but the most important is what we call the game state: it contains all the dynamic information of the game: the position of the player, monsters and camera; the current time; the score – in essence, everything that changes with time.

A computer game can then be understood as a system in which those two entities – player and game state – interact with each other according to a specific pattern of rules. The player inputs data into the system, and the system uses the game state to generate output to display to the player. This is not very different from ordinary applications, in which e.g. a click (input) might cause a dialog to show up (output). The difference is how that behaves in respect with time.

The Game Loop

Most applications are developed in a reactive way – your program just sits around waiting for the user to click something, and then it does something in response. There is a main loop behind your application as well, but it’s not important – it’s abstracted away. With games, your code is constantly being invoked, even in the absence of user input.

The pseudo-code for a video game will often look like this:

void GameClass::main() {
    init();
    runMainLoop();
    deInit();
}

The main loop looks something like this:

while (running) {
    processInput();
    updateGameState();
    drawScreen();
}

First, it reads input from the user and stores it somewhere. Here, it will check the keyboard, gamepad, plastic guitar and network message queues – basically, it will collect all information from the outside world.

After that, it will use that information to update the game state – depending on what conditions we have, they will have different results. For example, on the menu screen, detecting that the “down” arrow got pressed might increment the “currently selected menu item” variable, but the same input while on the game might instead trigger the “set player as moving down” flag. Note that the world update is invoked even if the user didn’t perform any input. This is a very important property of most video games.

Lastly, it will collect the current game state data to generate the output – it will figure out where the player and camera and everything else are, and generate an image to display on the screen. A more complicated game will also have to deal with other forms of output – audio and network, for example.

A More Sophisticated Main Loop

The loop pseudo-code above suffers from a major flaw: it will run at unpredictable speeds – on fast machines it might run thousands of times per second (which would be a waste), and on slow machines it might run on unacceptably slow speeds – perhaps only five updates per second or so. Besides the obvious issues, this makes the game much harder to program – it’s much easier to write your game logic when you know that you’ll have a fixed number of steps per second.

Consider this: the player presses the right arrow, and you store a flag containing that information. Now, on every step, regardless of any player action, you’ll move the player to the right by 1 unit in the game state (which, let’s say, corresponds to 1 pixel on the screen). If the game runs at 5 Hz (that is, 5 updates per second), the player will move VERY slowly. If it runs at 5000 Hz, he’ll be out of the screen before you can even see it!

A possible solution to this is to calculate the real time elapsed between two steps and use this information during the step. In practice, however, this makes the game development much harder and error prone. It will also make networking a true nightmare, and will essentially make reliable behavior (e.g. replays) impossible.

A much better solution is to fix the rate at which your game performs its updates. Most modern games use an internal clock of 60 Hz or 30 Hz. Let’s assume 60 Hz for our example. This means that, 60 times per second, your game will check the input from the player, update the game state, and try to display something on the screen. But how do we control that?

First, let’s consider the case of a very fast computer. In this case, before each iteration of the main loop, we’ll check if it’s time for the update. If it isn’t, we’ll simply wait (preferably yielding the time slice back to the operating system), without doing any processing.

In the case of a slower computer, things are trickier – we can’t skip on updating the game state, or the game will run in slow motion, so we must sacrifice the output – the screen rendering. On most games, screen rendering is the slowest part of the pipeline, meaning that most games WILL be able to run at 60 Hz given enough sacrifice on graphics. If not, then the game will be way too slow, and we have no choice but ask the player to get a better computer.

In pseudo-code, our new algorithm now looks somewhat like this:

while (running) {
    if (isTimeToUpdate()) {
        processInput();
        updateGameState();
        if (hasTimeToDraw()) drawScreen();
    } else {
        waitUntilItsTime();
    }
}

It’s simple, but it’s very similar to real game loops found in real games.

The Foundation

At this point, it should be clear that the vast majority of the game code will run inside the main loop – in a simple game, everything except for initialization and deinitialization. Also, that code is now separated in three functions: processing input, updating the game state, and rendering the screen. Since all three of them are controlled by the loop, it’s the foundation block of every game.

Having this foundation, your task of implementing a game has been reduced into three simpler and relatively independent tasks. The input you collect will be used on the state updating stage, and the state created by that step will be used to generate the output to the user, but they are each their own logically distinct operations, and how they interact with each other is now clear.

If you understand the topic discussed in this article, then all you have to figure out in order to make a (very) simple game is “how to read user input?”, “how to draw stuff on the screen?” and “how to keep track of my state and update it?”. None of those are, at a basic level, difficult, but they might be different from what programmers are used to coding.

On the next article, we’ll try to figure those things out and write an extremely simple real-time game using those concepts.

Math for Game Programmers 04 – Operations on vectors

Last time, we introduced vectors, and hopefully that introduction alone would be compelling reason to use vectors where it makes sense to. This time, we’ll discuss common operations associated with vectors, and their many uses. All of these operations are commonly found in vector operation libraries.

Length

Like we’ve discussed on the previous post, the length (or magnitude) of a vector is the square root of the sum of the squares of its components. So, if you have a 3D vector, its length is sqrt(x²+y²+z²). It is often represented by writing the vector inside ||s, that is, the length of vector v is said to be |v|.

For example, if we have the vector (4,2,4), we have:

length((4,2,4)) = |(4,2,4)| = sqrt(4²+2²+4²) = sqrt(36) = 6

Application example: If you have two points, you can find the vector between them and take its length to find the distance between the points.

Multiplication by scalar

You can multiply a vector by a scalar number (that is, a real number), which results in multiplying each component of the vector by that number. For example:

(0,-2,5) * 2 = (0,-4,10)

When you multiply a vector by a scalar, its direction is unchanged, but its length is multiplied by the scalar – for that reason, this operation is also called “scaling” the vector.

Application example: If you have an object moving with a vector representing its speed, you can adjust the speed without adjusting the direction by scaling the vector.

Normalization

By combining the two previous operations, we can “normalize” a vector. A vector is said to be normalized when its length is equal to 1. Since we can multiply any vector (except for (0,0,0)) by a scalar and therefore change its length to anything we want, we can normalize any vector by multiplying it by the inverse of its length.

In other words:

n = v * (1/|v|)

For convenience, many classes implementing vectors will define a “division by scalar” operator, so you could often just do this:

n = v/|v|

Application example: If you want a vector that represents a direction without a length, you usually want to use normalized vectors. It turns out, this is extremely common, and you will encounter normalized vectors very often.

Dot Product

Possibly the single most interesting operation on vectors, the dot product is very simple and versatile. It takes two vectors and returns a scalar number as the result, according to the following formula:

(a,b,c) . (d,e,f) = a*d + b*e + c*f

So, for example:

(2,-6,-10) . (1, 0, -1) = 2*1 + (-6)*0 + (-10)*(-1) = 2 + 10 = 12

It also has a different interpretation. Given two vectors v1 and v2, and let α be the angle between the two vectors, the dot product can be defined as:

v1 . v2 = |v1| * |v2| * cos(α)

This means that the angle between the two vectors can be determined like this:

α = arc cos( (v1 . v2) / (|v1| * |v2|) )

The formula above can easily be derived by isolating α on the previous equation. If the two vectors are normalized, then their lengths are one, and the dot product is simply the cosine of the angle between them.

One consequence of the cosine relationship is that the dot product can be used to determine the relative facing of two vectors. Let d be the dot product between two NORMALIZED vectors. Then:

v = 1: the two vectors face the exact same direction
0 < v < 1: the two vectors face roughly the same direction
v = 0: the two vectors are perpendicular
-1 < v < 0: the two vectors face roughly opposite directions
v = -1: the two vectors face exactly opposite directions

If you’re not interested in v=1 and v=-1 cases, then there is no need for the vectors to be normalized.

Applications: finding angles between vectors, projecting vectors into specific axes, determining whether a vector is facing the right direction, neutralizing a vector along a given axis, etc

Cross product

Similar to the dot product, but instead of taking two vectors and producing a scalar, the vector product takes two vectors and produces a third vector. It is defined as follows:

(a,b,c) x (d,e,f) = (b*f-c*e, c*d-a*f, a*e-b*d)

Similar to the dot product, the cross product also has an angular relationship,

|v1 x v2| = |v1| * |v2| * sin(α)

It’s important to note that while the dot product is also defined for 2D vectors, the cross product is only defined for 3D vectors. However, since it has useful properties even for 2D, a pseudo vector product can be defined for 2D vectors as follows:

(a,b) x’ (c,d) = a*d-b*c

This results in a scalar that is identical to what the “z” component of the result of extending the multiplication to 3D: (a,b,0) x (c,d,0) = (0,0,z)

A very important property of the cross product is that the cross between two vectors ALWAYS results in a vector that is perpendicular to the two original vectors (unless one of them was null). This makes the vector product extremely useful for calculating surface normal vectors – assuming that you can find three points on the surface, you can create the vectors v1 = (A-B) and v2 = (A-C), then n = v1 x v2, n’ = n/|n|.

An interesting use for the cross product (in particular, the 2D version) is that it indicates which direction a vector must rotate in order to face the same direction as the other vector, by taking the shortest path. Simply take the cross product between “current facing” and “desired facing” vectors, and the sign of the number (i.e. whether it’s negative or positive) will tell you which way to turn.

Applications: Finding normal vectors, finding turn directions, calculating torque, etc

These operations are some of the most basic things you can do with vectors. They will allow you to perform more complicated and interesting computations using vectors, so make sure that you understand them. We will use them very often in following lessons.

 

The fifth article in this series is now available here.

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 &amp;param) const
    {
        return vector3(x + param.x, y + param.y, z + param.z);
    }

    inline vector3&amp; operator += (const vector3 &amp;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.