Predefined FPS (Frames Per Second) value for your game loop

In the last decades tons of inks have been spent in articles about how to achieve a constant value for FPS in a game loop.

But why add another headache in the game development process? Why to time it? Why not just leave things run as quick as the CPU can and forget about on-purpose delays and timing?

The main reason is that you have to make sure that the game has the same tempo independent of the power of the CPU and if possible to synchronize the game loop with the refresh rate of the display. Imagine that your hero is at the leftmost bound of the scene and as you hit the right arrow key then he is at the rightmost edge in no time.

Another reason it that once we know the FPS then this is the key for defining the step for x, y direction (and even z in a 3D environment). You know the width of your scene, you know in how much time your hero has to walk all this distance(completely up to you) as if his way was free of obstacles, and if you also know how many frames he walks in a second, then you are a simple division away from setting a correct step (…not exactly …but I will discuss it in another article)

Particularly nowadays where mobile gaming rules the galaxy it is most important to find a way to stabilize on-the-fly the FPS value because you don’t know in the creation time of the game in what hardware configuration the game is going to run. Of course if you write games for an a priori known hardware (as example, if you are an iPhone-developer) then you can experiment in the development time and find the correct values so to put them hardcoded in your source code.

Of course if the game logic is implemented in a terrible way then you have to take other medicine and return later in this tutorial.

Please read first the wrong way for achieving a constant FPS value: It says that...
...if you want to have in your game, let’s say, 25 frames per second (FPS) then you have to add a delay of 1000/25 = 40 milliseconds at the end of every game cycle.

This approach is absolutely wrong because it doesn’t take into consideration:
1) the execution time of one cycle of your game loop.
2) the time that the delay() or sleep() function needs to execute itself.

And, you may ask, what if alone the execution time covers completely the optimal value for the delay? Can you in this case ignore the delay(X milliseconds) function? No! A delay() or sleep() function must be there even with a minimum value in its argument so that the CPU can give time and resources to other threads as well(Input, Display, System threads, etc).

So, a first conclusion for what will follow is that the delay time in unknown in the initialization process and thus we have to keep a variable for this:

int       iGameThreadDelay   = 1;

and change this value on-the-fly according to the everytime calculated FPS value. You will decide for a new value every 1 second.
So, we introduce a variable called lTimer, initialized before going into the while(gameRunning) loop and in every cycle we check if the difference with the current time is greater or equal(the best) than 1000 milliseconds (= 1 second).
And this “1-second-has-passed” moment is the best opportunity to get the cycles performed in this interval (then, FPS=cycles). The variable lGameCycles is increase by 1 in every iteration of the game loop and we can compare this value with the desired one to decide if the delay time has to be increased or decreased. Of course, there must a check for this delay time not to take values less than 1.

Here is a game loop in pseudo language. You can easily find the libraries of the language you use to get the current time in milliseconds and for letting a thread go to sleep mode for some milliseconds.

final static int FPS = 30;
Timer = GetCurrentTimeInMillis();
// better, if you initialize it from a precalculated value
iGameThreadDelay = 1;

// will be set to zero every (almost) 1 sec
lGameCycles = 0;
while ( gameRunning == true )
{   
   lGameCycles++;        
   // ....   
   // Game logic here   
   // ....        
   if ( GetCurrentTimeInMillis() - lTimer >= 1000 )   
   {      
      if ( lGameCycles > FPS )      
      {         
         // if too many FPS, then increase the delay         
         iGameThreadDelay++;      
      }      
      else // ...decrease the delay ...      
      {         
          // ... making sure that the minumum value is 1
          if ( iGameThreadDelay > 1 )              
          {            
                iGameThreadDelay--;         
          }      
      }      
      lGameCycles = 0;      
      lTimer = GetCurrentTimeInMillis();   
   }   
   delay ( iGameThreadDelay );
}

Inaccurate can occur when the difference of the current time and the saved one (in the previous ‘second’) is > 1000 milliseconds. This can be happened while in the k iteration of the loop the difference is let’s say 998 milliseconds and of course in this case the flow doesn’t enter the if (CurrentTimeMillis() - lTimer >= 1000 ) section and right after this in the k+1 iteration(the next) have already been spent 80ms for the execution of the game logic then the calculated difference will be 998 + 80 = 1078 milliseconds.


This value can be stored somewhere and be used in the next game session because – and I have to admit it – using this approach and starting the iGameThreadDelay from 1, it may take a few seconds for the game mechanism to calculate the best value and some players may experience bizarre movements in these few seconds. Thus, by storing it somewhere, it will happened only for the very first time the game is start.

Exactly the same logic can be applied on platforms where a time scheduler executes periodically a callback function (like iPhone & Android).

Collision detection by detecting ...no-collision

What can destroy your game? A bad collision detection algorithm that either returns error results or it is slow or both of them. What if you have hundreds of objects in a scene that have to be checked for collisions using an algorithm hungry for CPU resources?

In this tutorial I am presenting a way that I believe covers the needs of the 90% of the game developers. I am showing you how to perform very quick collision detection in 2D assuming that every object that carry collision dynamics in your game universe can be consider either as a rectangle or as a circle.

If there are special reasons to perform collision detection between objects that are of any kind of shape then you can approach them by splitting them in rectangles/circles or ...re-thing if you really need all this geometry. And if you finally decide to proceed with this then after you have prayed and sacrificed to Zeus...

... you have to befriended with trigonometry but remember: Never call trigonometric functions (sin(x), cos(x), tan(x), etc). Create instead (use this excel spreadsheet) an array (or more) with all possible angles that your game uses and get from there whatever you need.

Checking if two rectangles DO intersect can lead to a complex system of inequalities that has to be checked one-by-one, no escape, no 'break's, no 'return's, for each pair of objects, in each cycle of the game loop.

I don't even want to reproduce here the nightmare of such an inequalities system. Just take a pencil and a (large) piece of paper and draw all possible relative positions of two objects to understand the underlying complexity.

Instead of doing this it is much simpler to find whether two objects DO NOT collide at all. See the sketches bellow. There are only four cases:

To understand the simplicity, I want you to forget for one moment that there are programming languages in this world. Staring at these four pictures it makes sense that if you detect that you belong to one of these cases, then there is absolute no reason to check the remaining cases and you simply return with a result like COLLISION_NO. But if you end up by realizing that you are not in any case of them then only one result remains for you to accept: COLLISION_YES

And exactly this is the logic that I am going to implement. So, assume we have two rectangles A and B and call (x, y) the coordinates of the upper left corner. By knowing also the width and the height of each rectangle we can easily detect all other sides of it. It is very easy to get width & height in the loading procedure of the (image-)resources since almost every graphics library offers functions like getWidth() and getHeight() for its supported images.

So, I am repeating the sketch above by adding in each case the algebraic condition

Picture 1
A.x + A.width < B.x

Picture 2
A.x > B.x + B.width

Picture 3
A.y + A.height < B.y

Picture 4
A.y > B.y + B.height

Now, pack these conclusions in a function, let's call it “getCollisionResult”, that takes two rectangles as arguments and returns COLLISION_NO or COLLISION_YES that can be (#)defined as integers(0 or 1) , booleans(false or true) or whatever other primitive type you like.

result getCollisionResult ( rectangle A, rectangle B)
{   
   // picture 1   
   if ( A.x + A.width < B.x ) // 1 math operation (addition), 1 comparison
      return COLLISION_NO;      
   // picture 2   
   if ( A.x > B.x + B.width )      
      return COLLISION_NO;      
   // picture 3   
   if ( A.y + A.height < B.y )      
      return COLLISION_NO;      
   // picture 4   
   if ( A.y > B.y + B.height )      
      return COLLISION_NO;      

   // reaching at this point means that the rectangles overlap
      return COLLISION_YES;
}

As you see with a little luck you can end up a cycle of the game loop by doing very few CPU-operations for performing collision detection between two rectangles, 4 at the worst case plus 4 comparisons. There is another implementation of this function to reduce the operations to 2 but I leave it as an exercise for you.

This is not the main function that is going to realize your wishes when a collision is detected, but it is a helper function instead. The main function would look like this

result_type HandleCollision( )
{   
   for ( i = 0; i < objectsInGame; i++ )   
   {      
      for ( j = i+1; j < objectsInGame; j++ )//why j=i+1 ???      
      {         
         // before proceeding with checking for a collision,
         // see if these objects don't even need to be checked.
         if  ( checkObjects(obj[i],obj[j] ) == true)
         {            
            if (getCollisionResult(obj[i].rect,obj[j].rect)
                                         == COLLISION_YES)            
            {               
               // ...do whatever you want.            
            }         
         }       
      }  // END for ( j = ... )   
   } // END for ( i = ... )
}

What happens now if your have circles?Then also in this case you can use the function getCollisionResult by passing to it the rectangles that contain these circles. But it may be not accurate enough since it is possible to fall in this case:

The solution for this is to add another argument in the getCollisionResult function so that also the kind of the shapes is known now to the function. So, if the four “if”s are passed without returning NO, then the rectangles collide and only from now on is the best time to check the circles themselves by applying in our calculations the following lemma from the Euclidean geometry:Two circles collide only if the distance of their centers is less or equal to the sum of their radius as it can be seen in the following picture:

But given the centers (cx1,cy1) and (cx2,cy2) of two circles with radius r1 and r2 respectively the distance d between the centers is

And to check if our circles are far away from each other then it has to be check if

To strike the CPU with a square root is not the most gently you can do to it. It is a heavy operation and could lead to unnecessary delays. To avoid this take the square of the above relationship and you finally have to check this inequality:

where there is no square root. After all these, dive into coding and extend the function getCollisionResult like this:

...
radius_A = (A.width)/2;
radius_B = (B.width)/2;
...

result getCollisionResult ( rectangle A, rectangle B,
                            int shape )
{   
   // picture 1   
   if ( A.x + A.width < B.x ) 
      return COLLISION_NO;      
   // picture 2   
   if ( A.x > B.x + B.width )
      return COLLISION_NO;
   // picture 3
   if ( A.y + A.height < B.y )
      return COLLISION_NO;
   // picture 4
   if ( A.y > B.y + B.height )
      return COLLISION_NO;

   // reaching at this point means that the rectangles overlap
   if ( shape == CIRCLE )
   {      
      centerA_x = A.x + radius_A;
      centerA_Y = A.Y + radius_A;
      centerB_x = B.x + radius_B;
      centerB_y = B.y + radius_B;   
   }      
   distance_square = (centerA_x - centerB_x)^2 +
                     (centerA_y - centerB_y)^2;
   if ( distance_square > (radius_A + radius_B)^2 )
      return COLLISION_NO;

   return COLLISION_YES;
}

As it is clear when looking into the if ( ...CIRCLE ) section it would be very painful for the CPU to consider from the beginning the two circle-objects as circles and proceed directly with the if ( shape == CIRCLE ) section. At least do it once the container-rectangles collide which is extremely lighter to find it out.Of course you can optimize this new variation of the function getCollisionResult but I leave it as an exercise.