Optimizing a 2D Plataformer

Well, this is a never ending topic. There are a trillion ways to optimize a game. Not that Dogurai is a heavy game that needs to run at 900 FPS or would run at 5 fps in a bad PC. But, you know, it's always good to have something running smoothly.

So far, what takes more time to process on every frame of the current game is rendering. I'm using an old OpenGL 1.X with SDL2. As a side project, I'm porting the engine to run on 
modern OpenGL and be easy to port for new libraries (or even consoles; we might need that). I'm no specialist in OpenGL and I am still struggling to make it right, so this devlog will be on the logic side, especially collision.

As I was told in college, the process of collision detection is usually an operation with magnitude O^2 which means that for every object, a loop on every other object is needed. So, having 100 objects means 1000 collision checks. In Dogurai, most of the checks are based on rects.

But, you know, that is not always necessary.

In Dogurai, I created two types of object lists. Collision and Creature. So in that way, thinking we have 100 objects, but only 90 are collision blocks or platforms and the other 10 are the player with all creatures in a given map, there is no need to do a big O^2 operation. Collision blocks and platforms don't interact with each other, and neither do monsters, unless it is with the player.

That removed a HUGE part of all the branches needed to check the collision. Now, going further there is no need to check collision of the player on EVERY FRAME. If the player is not moving, there is no reason to check collision with the collision blocks (only with monsters). 

This is a screenshot of the game showing the collision box of everything:

All the collisions block were placed in the editor. Each on its grid, creating the ground and the ceiling. That can be improved, in Dogurai maps there are no slopes or curved blocks. We can take advantage of that by doing a merge on each tile side by side creating a single long block:

(Note the bottom ground is missing because it's a rendering optimization that removed it because it's too far)

Where before a level would easily have around 4000 collision blocks, this number is now less than 500. That's something!

Another improvement was made because of one of my decisions. The collision works based on the current speed multiplied by the delta time (the time between each frame), and sometimes a given object can be moving fast, or there can be some kind of frame spike due to a screen resize or something, which can cause an object to enter a little inside another. Having a player stick inside a wall is not good. Another thing that can happen is that the speed doesn't match the position exactly and the player stays 1 pixel away from the ground... That's basic collision in games. So I made a function to check if the collision happened, it adjusts the speed to "perfectly" match where the player should be. This is a little heavy compared to a single collision check. But it happens only on collision.
Okay, that's a little heavy but not that much. 

Now think about it. The game can be modded using Lua scripts. Most of these optimizations gave some juicy extra FPS... Using that in Lua would drain it. Collision check in a script language is terrible. So most of the functions are native and can be called without risking the performance. Yet the need might come to step through objects that might collide with the player. Based on that, I changed things so most of the collisions are managed by a function that returns a list of objects near the object.

Here is a gif. When a tile gets lit, it's because the collision is being checked and is considered near:

Using a cheap collision with low accuracy to detect near objects, then on only those (usually 2 or 4 objetos) the precise collision is checked. Also, handling 2~4 instances on a Lua script won't kill the frame rate of 300 fps.

And yes, that's only for the collision group. Overall, I reduced checks from 3000 to ~500 cheap ones and 2~4 medium-expensiveish ones.

There might be better ways. I am no master when it comes to optimizing stuff and some are really overkill yet those were super fun to make.