Fundamentals of Scrolling

Hi all!

After the last two posts on integration, I think that we can take a breath before finishing the hard physics stuff. So in this post I will talk about something that it is not that difficult to implement and is basic for any platform game (and many other games too): scrolling.

Most games, from the very beginning, have had some sort of scrolling. Scrolling consists of moving the scenario in such a way that your character is always visible, and usually, by the center of the screen. If this movement is on the horizontal axis, it is called 'horizontal scrolling', and if it takes place on the vertical axis, we would have 'vertical scrolling'. Most games use both of them.

Technically, however, it is more accurate to say that what we really move is the view along the level. That is, the idea is that we create a very big level (let's say 3000 x 3000 pixels) and then we set a view to our screen resolution, such as 1280 x 800 pixels. Then, we basically move this view (which you can think of as a rectangle) along the level in two dimensions, as depicted in Figure 1.

Figure 1.- View vs Screen Images. For scrolling, you move the view rectangle along the level rectangle

The way to achieve this in your game will obviously depend on the library or framework you are using. As I told you in this post, I will be using the SFML library, so the code explanations will be shown in C++ and using this library. However, the concept itself is the most important thing you should understand, and not any concrete technical implementation.

void LevelScreen::update(sf::Time elapsedTime) {

//We update all the objects in the screen
std::vector<Entity *>::iterator iter;
for(iter = gameObjects.begin(); iter != gameObjects.end(); iter++) {
        Entity *e = *iter;
        e->update(elapsedTime);
} 

//Now we update the view

//Horizontal scrolling

if (player->getPosition().getX() > SCREEN_WIDTH / 2) {
         view.move(player->getVelocity().getX() * elapsedTime.asSeconds(), 0);
}

//Vertical scrolling
if (player->getPosition().getY > SCREEN_HEIGHT / 2) {
        view.move(0, player->getVelocity().getY() * elapsedTime.asSeconds());
} 

}

Here, we basically update all the objects in the screen in the update method of the level (I'll give more details on the overall engine architecture in a following post). Then, we update the velocity of the view using the velocity of the player (the player variable holds a pointer to the player object). The update of the view will take place only if the player is located beyond the half of the screen in any dimension. Finally, in the draw method, we should set the view and draw the objects onto this view, as shown next:

void LevelScreen::draw(sf::RenderWindow &window) {

//Set the view to be used on the window (the window is where we draw the objects)
window.setView(view); 

//Draw the objects
std::vector<Entity *>::iterator iter;
for(iter = gameObjects.begin(); iter != gameObjects.end(); iter++) {
     Entity *e = *iter;
     e->draw(window);
}
}

This is the basic background you need in order to implement more advanced scrolling features, such as parallax scrolling. This technique will provide a higher feeling of realism with relatively little effort. I will explain how to implement it in the following post.

EDIT: you can go to the next post on parallax scrolling directly here. 

See you!

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! 

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!