Jump to content
  • Advertisement
  • entries
  • comments
  • views


Sign in to follow this  


Just made quite an interesting discovery.

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.


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.
Sign in to follow this  


Recommended Comments

Original post by jjd
It's a quadratic function. In particular, y = x(x-1)/2.

Cheers. I thought there must be a well defined formula.

By the way, I don't see your Christmas avatar yet, jjd [smile].

Share this comment

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!