Optimization Techniques for a 2D Engine
2022 · Team of 1
My final degree project, it is a small 2D engine written in C++ that can be executed in any Windows machine and can handle more than 10.000 entities interacting with each other in real time.
Description
The project is divided into four different versions where a specific optimization or group of optimizations is implemented, each version is tested against the previous one to ensure the improvement of each optimization technique.
The application itself is a minimal 2D engine that allows the user to add and remove asteroids from the scene. These asteroids collide and bounce off each other and the edges of the background.
It also has a UI panel to modify some aspects of the game-world and to show debug stats to check if the optimizations implemented are working as intended.
Versions
First Version - OOP
The first version of the project is the application coded with an object oriented approach. This version serves as the foundation and the optimizations of every version are applied gradually on top of this initial version.
The following diagram shows the structure of this version.
Second Version - ECS
The second version of the project is the implementation of an Entity-Component-System (ECS). It was a complete rework of how the entities' data is stored, accessed and modified, as well as the code regarding components.
The following diagram shows the structure of this version.
Third Version - Rendering Optimizations
The third version of the project consists of two rendering optimizations: frustum culling and batch rendering.
Frustum Culling or Camera Clipping is a rendering optimization with the primary focus of lowering the amount of data sent to the GPU. It does this by checking if an object to be rendered is inside the camera boundaries, in other words if it will actually be seen. If the object is outside the camera, it will not be rendered.
Batch Rendering is an optimization technique used to lower the amount of draw calls sent to the GPU. Each draw call is a relatively slow operation so, instead of sending each entity separately to the GPU, we can group or batch them together and send them all at the same time to the GPU, which will lower the amount of draw calls and speed up the rendering phase of the application.
The following graph shows the improvements of this version with respect to the previous one. Note that this optimization is mainly focused on the scene part of the application.
Last Version - Space Partitioning
The main optimization of this version is focused on improving the physics calculations with the implementation of a space partitioning algorithm.
As we can see in the previous graph, the physics system is the most time consuming part of the application. It takes so much time to compute because we are checking if an entity is colliding against every other entity, which results in a computational cost of O(N^2).
Space partitioning algorithms are one way of solving this problem, it consists of the process of dividing a space into non-overlapping regions and any point in the space can lie in exactly one of the regions. By dividing the space we can now check for collisions only between entities that lie in the same subspace, greatly reducing the amount of checks we have to do.
For this project I decided to implement a fixed-resolution grid where each division is of the same size. The size I chose was the same as the biggest asteroid that could be created so that they could only be inside a maximum of four sub-spaces at a given time.
Results
The following graph shows the comparison between all the versions and the gradual improvement after each optimization.
You can read the whole document with all the detailed information about the development of this project here.