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?


1 Answer 1


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.

Quad Trees

Take what you made with spatial partitioning and nest the tiles, navigating this structure can be cheap depending on how it's layed out in memory (see Morton Codes) because you can reduce the cache misses on the CPU and effectively give easy patterns for the CPU to pick up on and pre-calculate your results before your program even asks for the result.

You can take this concept further with dynamic nesting of tiles so you can subdivide where there are more enemies into fine grain tiles (so you effectively have a limit on the amount of enemies in each tile), though this has some trade offs with either breaking Moron Code compatibility or creating large empty arrays. Depends on the implementation

GPU compute shaders

Your CPU will have somewhere between 4 and 32 cores while using them all is really good the best you can do is use all of them, meanwhile your most GPUs are able to process thousands of things at the same time. If your target platform and performance requirements allow you to this can be a really good speedup (if your going for mobile this most likely won't be a silver bullet for you).

They differ based on the rendering API your using and have some quirks but if you look around for compute shader tutorials and the theory behind it you can move all the collision checks to the GPU while the CPU goes other things while waiting for the results.

There are other ways and many methods yet to be thought up so this sort of thing is always getting new optimisations and techniques...


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .