# Efficient way to check collisions for many objects

I am making a Bloons tower defense game and I came across a problem with regards to collisions. The way my code currently works is all the current bullets on the screen(could be potentially thousand) are stored in an array and all the balloons(could be in the hundreds) on the screen are stored in another array and every frame I loop through both arrays and draw each bullet/balloon. Now the problem is that I can't think of an efficient way to see if any bullet is colliding with any balloon every single frame when there are so many objects.

One thing I can thought of is looping through every balloon and then looping through every bullet to check if they are colliding, and it just doesn't seem like a good solution. The other solution I had was to blit all the balloons onto a surface and create a mask from that which I would use to check collisions however the problem that arises then is to determine the exact balloon object that was hit by the bullet in case of a collision and I can't think of any way to find that information from that mask. What would be the best way for me to implement this?

• Space_partitioning will be a good start. related: how-to-efficiently-do-one-to-many-collision-checks Jul 16, 2022 at 9:20
• Aside from the other suggestions, making sure your objects are close together in memory can reduce cache misses and improve the speed. Jul 16, 2022 at 12:06

Looping through the bullet array and the collider array is brute force way of doing it and will cost (at worst) Bullet * Collider amount of checks which can be very slow. Throwing multiple threads at the probably can make it a little better but overall it won't scale.

Here is a little list of things I can think of from my head you can do to speed things up in order of complexity (easiest to hardest):

## Collision shapes

Each collider usually has a shape which determines the amount of math needed to work if two are overlapping in space. Optimising this shape can lead to massive performance improvements (depending on what you are switching from). Circles are the cheapest to calculate, followed by squares, then convex hull (a mesh which doesn't go "in" at all), and actual meshes. It is often cheaper to have multiple circles represent something complex than a convex hull or even a square (if you have very optimised code).

If each bullet is a little circle and each enemy is a big circle all you have to check is if the distance between the centre points is larger than the combined radius of both circles, super fast check, great performance.

## Spatial partitioning

We know where all the enemies are and we know how big our play field is, so using that information we can divide the play field into squares (or rectangles) and then we'll keep a list of what is in each tile. When you then go to resolve a collision rather than looping through everything you do the following:

1. What tile is the centre point of my bullet?
2. Does my bullet collider go over the edge of the tile? (if so add each overlapping tile to the check tiles)
3. Loop though each enemy in the tile(s) and check if they collide, pick the most appropriate collision from there

This has the advantage that you only really care about the enemies in the same area where the collision is going to take place, the worst case is that you have to check 4 tiles but if you divide your play field into 100 tiles (this number will need a little fine tuning to your game) you still have a lot less total calculations.