I was previously doing object-object tests like:
for(std::vector::iterator I=Objects.begin();I!=Objects.end();++I) { for(std::vector::iterator J=Objects.begin();J!=Objects.end();++J) (*I)->ObjectCollide(*(*J)); }and testing inside ObjectCollide() to ensure the object wasn't being tested against itself.
It occurred to me as I was having a nap on the sofa that each pair was being tested twice, first A to B, then B to A again.
Since ObjectCollide() moves both objects apart by the MSD and sets up both objects new velocities, the second check is redundant.
After messing about with some very silly ideas, such as each object maintaining a vector of pointers to objects already tested that it checked against at the start of ObjectCollide(), it occurred to me that given objects with the following indicies in the vector:
0 1 2 3 4
If 0 is tested against 1, 2, 3 and 4 then 1 only needs to be tested against 2, 3 and 4, 2 only needs to be tested against 3 and 4 and 3 only needs to be tested against 4. Thus all the pairs have been tested exactly once against each other.
So:
for(std::vector::iterator I=Objects.begin();I!=Objects.end();++I) { for(std::vector::iterator J=I+1;J!=Objects.end();++J) (*I)->ObjectCollide(*(*J)); }and my calls to ObjectCollide() for 80 objects drops from 6480 per frame to 3240 per frame.
Obvious really, in retrospect. Just shows what a good idea the occasional nap on the sofa can be.
Out of curiosity, I fed some numbers into Excel and this chart shows the shape of the curve of comparisions needed as the number of objects increases:
I guess there is probably a proper name for this sort of curve, but lacking any formal knowledge about this sort of stuff, I haven't got a clue. I suppose this chart represents the number of unique pairs within a set of N objects.
Anyway, the outcome is that now, on my pretty low end PC, I can now keep 60 fps with about 630 map polygons and a cool 100 polygons bouncing about. All without any kind of spatial indexing.
