Sign in to follow this  

I need some suggestions for my snail-slow collision detection

This topic is 4354 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm a beginner. I just wrote a class to do 2D collision detections. It worked, but was too slow. Could you please give me some suggestion to improve it? Thank you! My idea is: 1,Every sprite have a list of bounding circles. When checking two sprites, I first check the outermost circle which contains the whole sprite. Then if the outermost circles collide, I iterate the rest circles, each of which accuratly contains one part of the sprite. 2,I devide the whole map into 64X64 grids. Each grid has a list of sprite pointers. In the game loop, I move sprites, calculate the grids covered by the outermost bounding circle, and then add the pointer to these grids. The grids' indices are stored in sprite objects. It only needs 4 numbers: the left-bottom grid's and the right-top grid's indices (an (x,y) pair). 3,So when I need to check whether a sprite is hitting something, I just go through the grids coverd by the sprite, and, with each grid, go through the sprite list it holds. the code looks like: ------------------------------------------------------------------------------- clear_the_list_of_all_grids(); for(iterator i=sprite_list.begin();i!=sprite_list.end();++i) { i->move(time); calculate_the_grids_it_covered(i); } for(iterator i=sprite_list.begin();i!=sprite_list.end();++i) { go_through_the_grids_it_covered(i, &list_of_result); for(iterator j=list_of_result.begin();j!=list_of_result.end();++j) { do_something(j); } } ------------------------------------------------------------------------------- It only can reach about 70FPS when handling 50 sprites though it works correctly Is it a feasible idea? If it's bad, why? Is there any way to improve it? I'm not a native English speaker. I hope you can understand me.

Share this post


Link to post
Share on other sites
The basic idea sounds fine, but there are a lot of places things could be going wrong. Here are some random comments/questions:

1. Are you sure it's the collision detection that's slowing things down? How does it perform with 50 sprites and collision detection off?

2. You might do some visual debugging with the grid system. That is, have a couple of sprites move around, and draw the grid cells that they're touching in a different color. This should reveal any blatent bugs in the grid system. (I assume that when the sprite moves you're also removing the sprite reference from cells it no longer touches?)

3. If you're not doing this already, find a way to avoid duplicate intersection tests, that is, sprite A tests against sprite B, and then when it's B's turn it (redundantly) tests against sprite A.

There are some other things you could look into, but the above things would be a good place to start, I think.

Share this post


Link to post
Share on other sites
That is a good way of doing it

I understand the first bounding circle -- that's crucial, but the others need more explanation. Perhaps, that is not most efficient way to check for collision.

Don't forget to remove the sprite from grid cells, too.

Share this post


Link to post
Share on other sites
Are you using any square roots in your collision code? It can impact a little (especially if there are lots of them). Hope this helps,

JVFF

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
How big are your grids compared to your sprites?
Are your grids very very large, so that each one contains too many sprites?
Are your grids very small, so that each sprite covers many grids, and you have to check too many.

How do you decide if a sprite covers a grid or not? I hope you aren't doing anything expensive here.


-regarding jky's suggestion 3
easy way to avoid duplicate collision tests
do a pointer check
if(&A>&B) CollideCheck(A,B) else ignorecheck

Share this post


Link to post
Share on other sites
You might also want to output a the number of Collision checks performed each update (both collisions that hit and those that miss).
Might tell you if anything wierd is happening with more checks than expected. Might also tell you if you're wasting a lot of CPU time performing unecessary checks that keep returning misses

Share this post


Link to post
Share on other sites
to jyk:

1,Oh, YES! I'm the biggest fool in the world! I have tested it again, and the result is:
50 sprites with no collision detection: 58~62 FPS
with collision detection on: 50~57 FPS

It looks not bad. But I soon make another test: 500 sprites with nothing else but collision detection, and the FPS can only reach about 40. When the numbers of sprites come to 1000, I got 10 FPS...I am desponded so much.

It seems that I still need to find some way to improve it or a better method, any suggestions?

2,Yes, I have done that. I draw borders of grids, bounding circles, and a lot of sprites moving around.
I actually remove the sprite from the grids it no longer touches. Instead of removing sprites one by one, I clear all the cells before moving sprites. Because I found that all sprites may change their position between frames, which results that each grid with sprites on it has to repeat removing operations. If I do all removing in a round, it should be faster.

3,Yes, you are right. I found that, in some cases, such as two sprites are touching same grids, duplicate test will be done. Should I use a list to record sprites that have been checked for each sprite? It looks expensive. Any better methods?

4,No, I use squares, not square roots.
========================================================================
to JohnBolton:

For example, a object represent a man. The first circle in the list contain the whole man. And then, I store several circles, one only contains his head, another only contain his hand, and so on. Only if the first circles of two objects collide, I check the rest circles.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
How big are your grids compared to your sprites?
Are your grids very very large, so that each one contains too many sprites?
Are your grids very small, so that each sprite covers many grids, and you have to check too many.

How do you decide if a sprite covers a grid or not? I hope you aren't doing anything expensive here.


-regarding jky's suggestion 3
easy way to avoid duplicate collision tests
do a pointer check
if(&A>&B) CollideCheck(A,B) else ignorecheck


That's a problem that I have been thinking of. In the test, I just hard code the size of grids. Sprites using in test are 64X64 pixels, and the grids are 128X128 pixels. I think it won't too bad. But I still don't know how to decide the grid size. Do you have any ideas?

"if(&A>&B) CollideCheck(A,B) else ignorecheck"
It only works when A and B are in the same array...

Share this post


Link to post
Share on other sites
You can further reduce the checks done and handle a large volume of sprites if they aren't all visible on screen at a time. If so you can do a visibility check for each one. Then when you do collision, you simply ignore the sprites which are not visible. e.g... 1000 sprites in game, but only 50 on screen at a time. Thats 50 sprites to check collision instead of 1000.

Share this post


Link to post
Share on other sites
Quote:
Original post by Jorn Bloodyscalpel
"if(&A>&B) CollideCheck(A,B) else ignorecheck"
It only works when A and B are in the same array...


Nope: you just compare the memory position of two objects, independantly of the meaning of that position. So it works in any case! The only thing that could make it fail is if you are recreating objects A and/or B and their position in memory changes.

Have you tried finding how much the inner collision is costing you? When there are a lot of sprites, this might actually slow down. Maybe you should do a few tests without this inner collision detection?

I'd also encourage you to use a profiler, if you can.

Share this post


Link to post
Share on other sites
Quote:

Nope: you just compare the memory position of two objects, independantly of the meaning of that position. So it works in any case!


It might not work in every case or on every platform. Look at this.

Share this post


Link to post
Share on other sites
Quote:

Nope: you just compare the memory position of two objects, independantly of the meaning of that position. So it works in any case! The only thing that could make it fail is if you are recreating objects A and/or B and their position in memory changes.

Wowwww, you are right, it's so cool! I have never heard of it before. In flat memory, despite of DLL, it actually works.
Quote:

Have you tried finding how much the inner collision is costing you? When there are a lot of sprites, this might actually slow down. Maybe you should do a few tests without this inner collision detection?

The data used in test won't cause inner collision, though my program will.
Quote:

I'd also encourage you to use a profiler, if you can.

what's that, and how to use? Could you explain it more? Or a link may help.

Share this post


Link to post
Share on other sites
A profiler is a program that tells you where your program is spending most of its time. See, for example, gprof as a free/open-source profiler. Profilers help you determine what example is eating up all of your cycles, so you don't spend all your optimization time on irrelevant parts of your program. For example, currently for my program, I know that I'm spending most of my time doing collision detection, followed by drawing sprites to the screen. Thus there's no point in my optimizing, say, my input system.

Share this post


Link to post
Share on other sites

This topic is 4354 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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

Sign in to follow this