My collision is daftly slow - please help.
Hello. My Collision code is *very* slow I guess. The more objects I add the slower the game gets.
Collision:
I thought I'd be smart and check if an object 1): can move, and 2): moved since last frame. I thought it'd be a lot faster than actually checking each object each time if it collided with something.. What am I doing wrong?
Full code if you actually want to look.. http://pastebin.com/cZeK5fgF
end project .exe: http://www.filedropper.com/sfmlgame1
if you're willing to tell me a better way without reading go ahead - i don't blame you to sort out my code.
Collision:
|
|
I thought I'd be smart and check if an object 1): can move, and 2): moved since last frame. I thought it'd be a lot faster than actually checking each object each time if it collided with something.. What am I doing wrong?
Full code if you actually want to look.. http://pastebin.com/cZeK5fgF
end project .exe: http://www.filedropper.com/sfmlgame1
if you're willing to tell me a better way without reading go ahead - i don't blame you to sort out my code.
I tihnk you can change line 10 to
In other words, when checking object i, you only need to see if it collides with objects i+1 to N. That means you can remove
|
|
In other words, when checking object i, you only need to see if it collides with objects i+1 to N. That means you can remove
&& iteratorindex1 != iteratorindex2 at line 13, which means you don't need lines 9 or 13 at all.
What do you mean you only have to check i+1 to N? I don't understand.
I also don't understand that for loop. That will check if the current object isn't checking itself?
I also don't understand that for loop. That will check if the current object isn't checking itself?
Last edited on
You are doing something like:
for (x = 1 to 3)
for (y = 1 to 3)
if (collides( x, y ))
producing test collisions
1 1 (does object collide with itself?)
1 2
1 3
2 1 (already did this)
2 2 (self?)
2 3
3 1 (already did this)
3 2 (already did this)
3 3 (self?)
Change your loop:
for (x = 1 to N)
for (y = x+1 to N)
test...
The general rule is to reduce the number of collisions you need to test. If you have a lot of stuff on the screen, keep track of which 'quadrant' of the screen your object is in. After that, you can keep the testing down to only those things near it.
Hope this helps.
for (x = 1 to 3)
for (y = 1 to 3)
if (collides( x, y ))
producing test collisions
1 1 (does object collide with itself?)
1 2
1 3
2 1 (already did this)
2 2 (self?)
2 3
3 1 (already did this)
3 2 (already did this)
3 3 (self?)
Change your loop:
for (x = 1 to N)
for (y = x+1 to N)
test...
The general rule is to reduce the number of collisions you need to test. If you have a lot of stuff on the screen, keep track of which 'quadrant' of the screen your object is in. After that, you can keep the testing down to only those things near it.
Hope this helps.
Unless I'm blind that's not what it's doing? It only runs the second loop (and checks for collision) if the object from the first is moving AND is a tile. Your example is checking every object against every object for collision regardless of what type or if it's moving.
Last edited on
Generally for any collision detection algorithm you can reduce the required processing time by reducing the amount of objects it has to check.
There is a bunch of different techniques which one can use to do this which range from simply grouping objects so that they don't test for collisions that can't possibly happen (For example testing static objects which don't move against other static objects) all the way to complex techniques like using Quad-Trees to reduce the amount of collision checks for a certain entity.
Without knowing your what your current game/real-time system is and the details about what your collision detection needs it is hard to suggest the best path for you to take and to provide concrete examples on what you should do. But I will say look for simple ways of reducing the amount of objects you will need to run your actual collision detection algorithm on.
This could be something simple like knowing that your static trees that are part of your environment will never need to check for collision against other static trees.
Or maybe for every object you do a simple distance test first (By running a Bounding Sphere Check possibly) and only run your expensive but more precise collision detection algorithm on those objects which collided in the first test.
A lot of the time games do something similar to this. They first run less complex algorithms to "thin down" the number objects and then after that simple collision detection algorithm is run they will run a more complex and expensive algorithm to get more precision. For example Bounding Sphere/Bounding Box checks first then Pixel Perfect Checks after.
Then of course there is more complex systems to set up like Quad-Tree testing which divides you game screen in sections that can only contain a certain amount of objects (If the number of objects goes over that set amount it then splits up that section into 4 smaller sections). It will then only test for collisions for objects that are in the same section. There is plenty of information out there on how to implement Quad-Trees and that explain how they work better then I can.
But any way you can reduce the amount of times your collision detection algorithm needs to be run the faster it will get. Hopefully this helps give some idea.
There is a bunch of different techniques which one can use to do this which range from simply grouping objects so that they don't test for collisions that can't possibly happen (For example testing static objects which don't move against other static objects) all the way to complex techniques like using Quad-Trees to reduce the amount of collision checks for a certain entity.
Without knowing your what your current game/real-time system is and the details about what your collision detection needs it is hard to suggest the best path for you to take and to provide concrete examples on what you should do. But I will say look for simple ways of reducing the amount of objects you will need to run your actual collision detection algorithm on.
This could be something simple like knowing that your static trees that are part of your environment will never need to check for collision against other static trees.
Or maybe for every object you do a simple distance test first (By running a Bounding Sphere Check possibly) and only run your expensive but more precise collision detection algorithm on those objects which collided in the first test.
A lot of the time games do something similar to this. They first run less complex algorithms to "thin down" the number objects and then after that simple collision detection algorithm is run they will run a more complex and expensive algorithm to get more precision. For example Bounding Sphere/Bounding Box checks first then Pixel Perfect Checks after.
Then of course there is more complex systems to set up like Quad-Tree testing which divides you game screen in sections that can only contain a certain amount of objects (If the number of objects goes over that set amount it then splits up that section into 4 smaller sections). It will then only test for collisions for objects that are in the same section. There is plenty of information out there on how to implement Quad-Trees and that explain how they work better then I can.
But any way you can reduce the amount of times your collision detection algorithm needs to be run the faster it will get. Hopefully this helps give some idea.
Last edited on
Wow, that's a lot of useful information! I've heard about checking only what's on the screen (or in a given area), but then I'd have to "load" each level in different sections which sounds way too involving right now. (because I can't have other objects fall though the floor on parts of the level that isn't "loaded" yet.
Or I can do what you also said and use cheaper "collision" to see if any objects that can collide are close.
You said "For example testing static objects which don't move against other static objects" isn't that what I was doing? I make it so it only checks when the object isn't a "GameObject::tile" and it's moving.
Or I can do what you also said and use cheaper "collision" to see if any objects that can collide are close.
You said "For example testing static objects which don't move against other static objects" isn't that what I was doing? I make it so it only checks when the object isn't a "GameObject::tile" and it's moving.
Last edited on
The point we're trying to make is that you are using an n² iteration with expensive checks for every object you've got.
You need to thin it out -- use inexpensive checks and some state information to reduce the number of expensive checks you must do. Then, only when it is possible for something to collide do you need bother with the expensive tests.
You need to thin it out -- use inexpensive checks and some state information to reduce the number of expensive checks you must do. Then, only when it is possible for something to collide do you need bother with the expensive tests.
I'm sorry for being ignorant on this topic, Duoas, and I promise i'm not trying to be condescending, but isn't that what I'm doing? Isn't checking if an object is a certain type cheap? And AFTER that, checking if the object that isn't moving cheap as well before any actual collision is being calculated?
Last edited on
LOL, I haven't spent a whole lot of time with your code. But the problem is you are still checking every object with every other object.
Presumably you have only a relatively few xs compared to the number of objects, but you haven't really thinned the board by that much.
Can an x on the far left side of the screen collide with any of the ys on the right side of the screen? (Or, having run your game to see, can your blue box collide with anything not visible on the screen?)
Clearly no, but you are still testing every one for the possibility.
You should look into ways to limit the total number of collisions to those that are even remotely possible because they are in the general area of the moving object. Do this by dividing your map up into sections and keeping track of what section every object is in. (Obviously, only moving objects can change sections.) After that, only check to see if your moving object is colliding with objects in the same section (or sections) that it is in.
Hope this helps.
|
|
Presumably you have only a relatively few xs compared to the number of objects, but you haven't really thinned the board by that much.
Can an x on the far left side of the screen collide with any of the ys on the right side of the screen? (Or, having run your game to see, can your blue box collide with anything not visible on the screen?)
Clearly no, but you are still testing every one for the possibility.
You should look into ways to limit the total number of collisions to those that are even remotely possible because they are in the general area of the moving object. Do this by dividing your map up into sections and keeping track of what section every object is in. (Obviously, only moving objects can change sections.) After that, only check to see if your moving object is colliding with objects in the same section (or sections) that it is in.
Hope this helps.
All of that definitely does help! But I have a follow up question. Why does this have such an impact on my program already? Even 5 objects vs 10 objects it's a lot slower. How can computers can handle 3d collision but this makes it go so slow? Is the reason why it does that because it goes as fast as it can and basically kills itself performance wise? Or am I missing something? Even if I make it so it only checks around itself.. It'll still have to check more than a couple objects, right? But a couple objects are already making it terribly slow.
Which brings me to my next question.. Why does it make the pace of the game slower, not the actual frame rates? I know it doesn't have to do with drawling anything on the screen but I've never seen a game go "slower" in the sense that the speed of everything is slowed down.
Which brings me to my next question.. Why does it make the pace of the game slower, not the actual frame rates? I know it doesn't have to do with drawling anything on the screen but I've never seen a game go "slower" in the sense that the speed of everything is slowed down.
Last edited on
To be fair, I was wondering that when I played (briefly) with your game. (It was so slow I didn't try to move around much further than climbing halfway up that one wall a little to the right.)
While it does impact performance significantly, I'm not convinced this is the only issue.
Maybe if I get a chance I'll download your code and look at it.
While it does impact performance significantly, I'm not convinced this is the only issue.
Maybe if I get a chance I'll download your code and look at it.
|
|
By the way, GameObject destructor must be
virtual as you do have another virtual member function.Also, it may pay to separate the movable objects.
Wait a minute. Looking at your code, it appears that there is only one object that can move - the player. So why are you doing an N2 of all objects? Just see if the player has collided with any of the tiles.
Even with this change, what makes you think that the collision code is the problem? It looks like you are redrawing every object after every move, even if they move less than a pixel. Don't you only need to redraw the player?
GameObject needs a constructor that initializes loopcount, canjump and speed. Right now those members are uninitialized for Tiles.
Why do you have speed and velocity members? It looks to me like you should remove speed and use velocity.x in its place.
I may misunderstand the heart of the collision code but it seems odd to me. Here it is with my comments/questions. Note that I've created some references to make it less verbose:
Even with this change, what makes you think that the collision code is the problem? It looks like you are redrawing every object after every move, even if they move less than a pixel. Don't you only need to redraw the player?
GameObject needs a constructor that initializes loopcount, canjump and speed. Right now those members are uninitialized for Tiles.
Why do you have speed and velocity members? It looks to me like you should remove speed and use velocity.x in its place.
I may misunderstand the heart of the collision code but it seems odd to me. Here it is with my comments/questions. Note that I've created some references to make it less verbose:
|
|
Topic archived. No new replies allowed.