Jump to content
• Advertisement
• entries
743
• comments
1924
• views
583213

# Interesting

93 views

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.

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.

## Recommended Comments

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

#### Share this comment

##### Link to comment
Quote:
 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
Apologies, it's been a hectic week :-)

Ho ho ho.

## 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
• Advertisement
• ### Blog Entries

• 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!