jueves, 23 de mayo de 2013

Integration: Our Best Friend (Part 2)

In the previous part of this post, we covered some mathematical foundations behind the concepts of position, velocity and acceleration. We explained that velocity is the derivative of position and that acceleration is the derivative of velocity. We also saw that derivatives represent rates of changes, and therefore, velocity is the rate of change in position and acceleration the rate of change in velocity. If velocity is constant (i.e. acceleration is 0), the rate of change in position is constant, and the position would change linearly. If on the other hand acceleration $>$ 0 (but constant), velocity would grow linearly and position would grow quadratically (i.e. forming a curve). Figure 1 shows different possibilities: stationary objects (no velocity), uniform motion (constant velocity) and motion with constants acceleration.

Figure 1 (source: http://cnx.org)

The problem that tries to solve an integrator is how to figure out (fast and efficiently) the velocity from the acceleration and the position from the velocity (i.e. doing the inverse of derivatives). And why? Because in most games, the acceleration on an object is the only information that we have.

Actually, this is not completely true. The information that we usually have is the force applied to an object (due to a collision or a hit, for example). However, as the Newton's second law states: 'The acceleration of a body is directly proportional to, and in the same direction as, the net force acting on the body, and inversely proportional to its mass'. Mathematically, this can be represented as follows:

$F = m \cdot a$     (1)

Therefore, knowing the direction and magnitude of an applied force, we can figure out the acceleration from (1):

$a = \frac{F}{m}$     (2)


At this point, we know the acceleration. We may find two different situations here, depending on whether we have constant acceleration or not. 


Constant acceleration

When we have constant acceleration, we can simply move our minds back to high school times and apply the famous equations that models how position changes when there is constant acceleration, that is:


                                              $p = p_{0} + v_{0} \cdot t + \frac{1}{2} \cdot a \cdot t^{2}$  (3)

Then, we could simply update velocity for the next iteration:

$v = v_{0} + a \cdot t$  (4)

Formulas (3) and (4) are also integration formulas, but they don't approximate: they provide the real position and velocity values. Here, in a couple of comments, they call this type of integration a ballistic or parabolic integrator, even though I haven't found any other references or entries for these names. 

In any case, the point is that if we know that acceleration is constant, we can and should use these formulas, because they provide accurate results. Euler's integrator, however, accumulates errors over the time and if the time step is big, this error grows faster. Euler's integration uses the following formulas:
$p = v \cdot t$ (5)
$v = a \cdot t$  (6)

Let's see how we could implement both integrators in C.  

  int dt = 1; //time step  
  int position = 0, velocity = 0, acceleration = 10;  
  printf("Using physics formulas\n");  
  for (i = 1; i <= limit; i++) {  
  printf("Time %d: ", i);  
  position += velocity * dt + acceleration*dt*dt/2;  
  velocity += acceleration*dt;  
  printf("Position %d, Velocity %d\n", position, velocity);  
  }  
  printf("--------------------------------\n");  
  velocity = 0, position = 0;  
  printf("Euler integration\n");  
  for (i = 1; i <= limit; i++) {  
  printf("Time %d: ", i);  
  position += velocity * dt;  
  velocity += acceleration * dt;  
  printf(" Position %d, Velocity %d\n", position, velocity);  
  }  
  
If we execute the previous code, and we change the number of iterations we can see that the higher the number of iterations, the higher the error is (that is, error is accumulating in Euler's integration). Also, if we reduce the time step (dt), we can see how the Euler's error decreases, whereas it would increase in case of a bigger time step. If you carefully see the formulas, all of this makes sense. Notice that the only difference between the 'accurate' integration and Euler integration is the position update. The former includes more information (basically an extra multiplication by 0.5 * dt^2). The smaller dt, the less significant is the difference with Euler's. Also note that velocity update is exactly the same in both methods.

As a conclusion, there is no problem with constant acceleration, as we can achieve exact results. This becomes a little trickier in non-constant acceleration situations.

Non-constant acceleration

Many physics engines have to deal with non-constant acceleration. For example, consider a force on an object that is proportional to the velocity of the object, that is:


$F = -v$    (7)

This could model the air friction, for example. In this case, and because we always assume constant mass, we deduce from (2) that if the velocity changes, the acceleration changes. In these cases, we find a differential equation:

$a = \frac{dv}{dt} = \frac{-v}{m}$      (8)

It's a ordinary differential equation (ODE) because the equation of the velocity has the derivative of the velocity in it. Analytically integrating (i.e. with paper and pen and with exact results) ODEs is tough, but integrating them numerically is pretty straightforward. We have already seen the formulas of Euler integration (5 and 6), but let's re-write them again, this time considering a time step called $h$ (instead of $t$), using the differential notation and considering explicitly the iterations with a subscript:

$p_{n+1} = p_{n} + h \cdot \frac{dp_{n}}{dx}$     (9)
$v_{n+1} = v_{n} + h \cdot \frac{dv_{n}}{dx}$  (10)

Most integration methods follow the same pattern. They evaluate the derivative (remember, the slope) of the variable we want to figure out, and they step forward in time by a fixed amount, h, on the tangent line with that slope. In the next step, they evaluate the derivative at the new position to get a new slope, taking another time step. Chris Hecker gives a very good, graphical explanation of this process here

Of course, Euler will have the same problems we discussed previously, but at least if we choose a sufficiently small time step (as we may find in 60 frames/second games, where the time step is approximately 0.017 seconds), results are not that bad. However,  in physics-intensive games, where you need high accuracy, or in order to avoid inaccuracy problems due to drops in frame rates, you'll need other better integration methods, and that's what I'll cover in the last post.

Concretely, I will explain Runge-Kuta order 4 and Verlet methods. I'll also explain how I dealt with all this for the game I'm working on and I'll provide a list of references that were useful to me while writing these posts. Some of them will give you more mathematical insight. 

See you! 

sábado, 18 de mayo de 2013

Integration: Our Best Friend (Part 1)

In this post, which will be divided in three parts, I'll cover some basic maths that are required for most games. Concretely I'll cover a couple of numerical integration methods. For those of you who don't like maths, I'll advice you to give it a try, because I'll try to keep the explanations as simple as I can. Also, you should not be discouraged if you don't understand something: in the very end, you can (and probably will) use abstraction and use some physics library that includes what we're seeing here. However, as a recommendation, if you're serious about developing games, you should try to understand at least the most basic concepts, and I'll try to help you attain this. 

In the heart of any physics engine we can find the so-called integrator. The goal of an integrator is quite simple: given an acceleration on an object (or a force, as we will see), it calculates how the position is updated accordingly. And you will be wondering: why do I need this?

Well, in the very end, you will have something like this in your code:

object.setPosition(x, y); //Assuming a 2D game
object.draw(window); //It draws the object in the position set before onto the screen

But how is this position calculated? Of course, if the object is your character, the player's input will update the position. For example, you could do this:

if (input.isKeyPressed(RIGHT_KEY)) {
   x = x + 1;
}

If the right arrow is pressed, the x-position is advanced 1 unit or pixel. However, there may be other factors that have an influence on your character. For example, in any traditional platformer, we have to consider gravity. Gravity is an acceleration that pushes all the objects downwards in the y direction. So, if you want gravity to affect your character, you have to figure out the y position of you character from the acceleration induced by gravity after a period of time. Well, here is where an integrator is useful.

This first post will introduce the problem of integration. The second post will explain the Euler integration method, because it is the most simple one. Finally, the last post will describe two of the most widespread methods: Runge-Kuta order 4 (RK4) and Verlet. 

Derivatives or the rate of change

First of all, it is important to know the mathematical relationships between position and velocity, and between velocity and acceleration. (Note: I'm using the term velocity instead of speed because I'm assuming that velocity is a vector. That is, velocity implicitly includes a direction, whereas speed is just a scalar value representing an amount of movement).

Velocity is the derivative of position, and acceleration is the derivative of velocity. Derivatives are a way to measure rate of change of one variable with respect to another variable. Therefore, velocity represents the rate of change in position, and acceleration is the rate of change in velocity. 

For example, assume that the velocity is constant: let's say 5 pixels per second. Let's also assume that the object starts at position 100 along the X-axis (let's assume only one dimension for simplicity). So, after a second, the position of the object will be 105. After another second, the position will be 110, and so on. 

But what happens if we add acceleration to this scenario? Velocity will change also every second. For example, if we choose a constant acceleration of 10 pixels per second and we assume an initial velocity of 0, after one second, the velocity will be 10. After two seconds, the velocity will be 20, etc. And the position would change faster as the time goes by. 

Graphically, the rate of change at one point (i.e. the derivative at one point) corresponds to the slope of the tangent line at that point, as depicted in Figure 1.
Figure 1 (source: Wikipedia)

If velocity is constant (let's say 1), it means that the slope of the tangent line is 1 in every point of the position graph, that is, the position graph is a straight line (y = x), as shown in Figure 2.

Figure 2 (source: http://www.gcse.com)

On the other hand and following with the same example, the velocity graph would be a straight line at y=1 (i.e. without slope). This means that the slope at every point in the velocity graph is 0, meaning that there is no acceleration (it's normal, as we said that velocity is constant). Figure 3 shows the graph of the position (assuming an initial position of 0) (y=x) and the graph of the corresponding velocity (y=1). 

Figure 3 (source: http://www.ltcconline.net)

Maybe now, for those of you who know some maths, it is more clear why we're talking about integrators. Integration is the opposite to differentiation. If we wanted to figure out the velocity from the position, we should differentiate the position. But we want to do the opposite: we want to integrate velocity to figure out the position (and the acceleration to figure out the velocity). 

Analytical integration is usually a tough task. It comprises first finding a primitive and evaluate it over some interval. Sometimes finding such primitive is impossible. However, numerical integration (which is basically what we did in our previous example) is much easier. Numerical integration requires knowing some values for the derivative (e.g. velocity) at some points in time. We know that these values represent the slopes of the tangent lines at those points in time in the position graph.  What both Euler and RK4 do is stepping forward the position in time by a fixed amount, h, on that tangent line. How they do this will be the contents of the next part of this post.

Hope that at least the foundations are more or less clear, and don't hesitate to leave comments or suggestions (or error corrections if it's the case :)). 

See you soon!

jueves, 9 de mayo de 2013

AI with Neural Networks

Hi all!

Searching information about artificial intelligence for the game I'm working on, I came across this interview to Jeff Hannan, who used neural networks to implement the artificial intelligence in Colin McRae Rally 2.0. Hope that you enjoy and learn something new.

In posts-to-come, I'll further discuss different techniques to implement artificial intelligence, which is a fundamental component of any enjoyable game. But something that it's worth pointing out now is that we tend to think that the best AI is the one that makes it harder for the player. However, I personally believe that the best AI is the one that, as Hannan states, performs realistically. This a subtle but important difference to consider.

See you!

martes, 7 de mayo de 2013

Starting off!

So at last the moment has arrived when I'll tell something about the project I'm working on. The keyword here is 'simplicity'. I won't aspire to make a God-of-War-like 3D adventure game (in spite of how much I love this game). I have to be realistic. I'm just one person and I lack the necessary technical knowledge to program staggering 3D effects. Therefore the game must be simple, something I can be sure I'll be able to finish. Once I've done the first one, I'll probably feel like doing something more elaborated.

The game will be a classical 2D side-scrolling platform game. I think that this kind of games can be very fun, and they can be very profound too. If you don't believe me, just take a look at Blow's Braid. Also, you can ignore some intrinsic difficulties to 3D games, such as culling algorithms.

I'm currently in the process of making a small engine to support several features. In the following posts, I will be explaining these features in detail, as well as the difficulties I came across along the way. My idea is to cover each aspect of a typical game, from basic physics to artificial intelligence and graphics programming.

Regarding the technology, I'm using C++ as programming language and SFML in order to retrieve keyboard inputs and as render library. The choice is simple. I love C (as I read in one programming book lots of years ago, C is the language that God used to create the world; mmm... maybe this is the reason why there are so many buffer overflows...), and as far as I know, many current game engines use the Object-Oriented version of C, that is, C++. However, I must admit that it is not the easiest language if you've never faced a programming language before. I'd never recommend any aspiring game developer to begin with this language. I chose C++ because I already know enough C and Object-Oriented principles and patterns as a result of studying computer science. If you're new to programming though, I'd advice you to go for a more accessible language or game-making solution such as GameMaker.

As for the graphics library, you may find many out there. However, SFML seems to have an easy learning curve and builds upon OpenGL. For now, I'll use the abstraction with which SFML provides me (remember, abstraction is our friend), but in the future, I'd like to add some graphics programming by using vertex and pixel shaders, something that the library easily allows.

As a final comment, I'd like to add that the first game (my game in particular) might be a 'shitty game', but at last it'll be a game, 'my game', and you need to start off at some point anywhere. The following video shows advices for people wanting to become game developers. I found some comments challenging and inspiring. Remember, don't be afraid of simplicity. It's the natural path. Actually, I'd say it's the only possible path. 


viernes, 3 de mayo de 2013

How to make a game in 48 hours

I came across a time lapse video of a game making process for Ludum Dare, the name of which is Dream Fishing. For those who don't know it, Ludum Dare is a game making competition where developers must create a game in 48 hours. As you can see, the game author, Sophie Houlden, only took breaks to eat, have some short naps and watch some Anime.