Optimize Collision Detection with Broadphase and Narrowphase

[ecrinyildiz]

Is your feature request related to a problem? Please describe.

Collision detection in the current implementation involves checking all objects against each other within neighboring grid cells. While this reduces unnecessary checks compared to a naive implementation, it is still computationally expensive for large numbers of objects. As the game scales with more objects, the performance may degrade due to the increased number of narrowphase collision checks.

Describe the solution you'd like

Implement a two-phase collision detection system:

1. Broadphase

• Use spatial partitioning (e.g., grids, quadtrees, or sweep-and-prune) to efficiently reduce the number of potential collision pairs by filtering out objects that are far apart.
• Only objects that are close enough in the broadphase will proceed to the next phase.

2. Narrowphase

• Perform accurate collision detection for the filtered pairs from the broadphase.
• Use shape-specific algorithms (e.g., circle-circle, rectangle-rectangle, or SAT) to determine if objects collide and gather collision details like penetration depth and collision normals.

This system would significantly reduce the computational overhead while maintaining accuracy.

Describe alternatives you've considered

I have not considered any alternative solution.

Additional context

• The current implementation involves iterating over grid cells and their neighbors to check for potential collisions. While this is an improvement over brute force, it still performs redundant checks in some cases.
• A two-phase approach would allow us to further optimize the process by minimizing the narrowphase workload.
  Example of current collision resolve code snippet:

if (obj1->is_colliding_with(*obj2)) {
    obj1->on_collision(*obj2);
    obj2->on_collision(*obj1);
}

• Performance profiling or benchmarks could be useful to compare the new approach with the current system.