WOW! thankyou everyone for all your comments!
I think I will look into doing a grid type thing as that seems the fastest.
Actually no, it isn't. I've seen various benchmarks on collision detection routines and 2D grids are never at the top. For example oct-trees are faster. There is also a Wikipedia page on spatial partitioning
that you can look at. But it is significantly faster then your original brute-force approach.
A 2D grid is also relatively easy and straight forward to implement.
A few more remarks; unless you build in some sort of system to deal with this then you can't have Towers outside of the grid (i.e. offscreen). I also highly advise building an interface for your collision detection routine so you can easily implement a new algorithm. Also make sure you benchmark your algorithm (and it's optimizations) with real data. Otherwise you don't know if the optimizations help, or not. Also how will you deal with inheritance? Even if you choose not to you need to decide about what to do with this (i.e. everything is stored as a Tower).
A big issue for my own grid collision system was the high number of nodes and iterators used by the sets. I found when I had a thousand objects all constantly moving and intersecting against each other, it would be creating millions of objects per-second just to detect collisions. This caused the garbage collector to run ALOT
and so I've since optimized it to remove this.
Finally there is a bug in my code above, dividing by the grid width and height is incorrect. It should be dividing by the width and height of each cell in the array in pixels, not the number of elements in the array. You can see my full grid collision code here
. It's not perfect, but for now it's good enough.