Optimizing Collision Detection
Author
It seems to me, even if you try to minimize the space in which you check, using an {oct|quad}tree or whatever, the best you can do for a collision detection algorithm between game objects is always O(n^2).
Short of the trivial "if(object1==object2) continue" are there any good optimizations to be made? I suppose I could omit objects that are not visible on the screen at the time in this project (2D Shootemup done in 3D) but there's going to be alot of bullets flying around...
Oh well, I haven't gotten that far yet, so I'll just have to see if it works well or not. No use pre-optimizing.
You need to throw out as many checks as you can. Spatial partitioning works good if you have A) many objects with B) an even distribution. If you have a hundred objects all packed into a tiny space (ala "Pikmin") it doesn't work as well. But here are some tricks i used:
- Never check for the same collision twice ( that is, A:B and B:A both )
- Only check object types for for which it makes sense ( bullets vs bullets usually does not make sense, so do not waste your time )
- Only check objects in the local area (spatial partitioning)
- Only check moving objects. Never check static non-movers against other non-movers (walls vs walls)
- Do a simple bounding box or sphere test before you do something more fancy like computationally expensive polygons or complex 3D volumes.
Using these simple tips, for a shooter game like Ikaruga you should be able to throw out at least 2/3 of the total n^2 checks, if not much more.
[Edited by - leiavoia on January 2, 2005 1:51:15 PM]
- Never check for the same collision twice ( that is, A:B and B:A both )
- Only check object types for for which it makes sense ( bullets vs bullets usually does not make sense, so do not waste your time )
- Only check objects in the local area (spatial partitioning)
- Only check moving objects. Never check static non-movers against other non-movers (walls vs walls)
- Do a simple bounding box or sphere test before you do something more fancy like computationally expensive polygons or complex 3D volumes.
Using these simple tips, for a shooter game like Ikaruga you should be able to throw out at least 2/3 of the total n^2 checks, if not much more.
[Edited by - leiavoia on January 2, 2005 1:51:15 PM]
One of the easiest ways that I've done is just to do a simple distance check. If you have a point for one object, and a point for another, check distance formula. I believe you can even eliminate the square root from it, because sqrts are generally expensive. But overall distance calculations are not expensive compared to per-polygon detection, so that's been one of the first and easiest optimizations to be made.
Another one was mentioned above; if all of your game objects are in the same list, that can hurt. As long as you only check things like bullets vs. everything else then characters vs. everything else, that's not nearly as bad. Checking wall v. wall is. =)
Another one was mentioned above; if all of your game objects are in the same list, that can hurt. As long as you only check things like bullets vs. everything else then characters vs. everything else, that's not nearly as bad. Checking wall v. wall is. =)
Some have already been said but I feel like a parrot today.
1) Do initial collisions between spheres. This is performed by calculating the distance between the two object's origin and seeing if it is less than the sum of the two radii. This can be further optimised by comparing the squared distance with the sum of the squared radii. This gets rid of the nasty square root.
2) You can reduce the amount of tests by half if you check each pair once. So, instead of:
You use
3) If the game only plays in 2D (even if rendered in 3D), then only check for collisions in 2D.
4) Divide the world into equal squares, and keep track of which square each bullet is in. Then you can perform a whole load of optimisations and find out some useful data:
4.1) If the distance between the two is greater than the size of the square then they can't possibly collide, so there's no need to start squaring radii.
4.2) If they are not in adjacent grids (including diagonals) then they can't collide (if they are in grids that are side by side then their radii might overlap).
4.3) If they are in the same grid then you know that there could be a collision
4.4) 4.2 is also handy for rendering. An off-screen grid that isn't next to an on-screen grid will never be seen, so don't bother rendering it.
5) Bullets should not collide with bullets, which will take a whack off the number of tests to perform. Powerups should only collide with ships and the scenary, and ships should collide with everything ;).
6) If possible, don't do any other tests apart from sphere-sphere as most shooters don't require anything more complex.
7) Don't use dynamic spacial partitioning. It will choke under bullet-hell shooters.
8) Put the bullets into a seperate array from the ships and other entities. That way you can ensure that no bullet is ever tested against another. It will require rendering 2 different arrays, but it'll be worth it.
9) If both objects are still then don't test them
10) I'm done.
++
1) Do initial collisions between spheres. This is performed by calculating the distance between the two object's origin and seeing if it is less than the sum of the two radii. This can be further optimised by comparing the squared distance with the sum of the squared radii. This gets rid of the nasty square root.
2) You can reduce the amount of tests by half if you check each pair once. So, instead of:
for (first_ent = 0; first_ent < MAX_ENTITIES; ++first_ent){ for (second_ent = 0; second_ent < MAX_ENTITIES; ++second_ent) { // Collision check }}You use
for (first_ent = 0; first_ent < MAX_ENTITIES; ++first_ent){ // Start from the one passed first_ent, as all previous ents have already been checked! for (second_ent = first_ent + 1; second_ent < MAX_ENTITIES; ++second_ent) { // Collision check }}3) If the game only plays in 2D (even if rendered in 3D), then only check for collisions in 2D.
4) Divide the world into equal squares, and keep track of which square each bullet is in. Then you can perform a whole load of optimisations and find out some useful data:
4.1) If the distance between the two is greater than the size of the square then they can't possibly collide, so there's no need to start squaring radii.
4.2) If they are not in adjacent grids (including diagonals) then they can't collide (if they are in grids that are side by side then their radii might overlap).
4.3) If they are in the same grid then you know that there could be a collision
4.4) 4.2 is also handy for rendering. An off-screen grid that isn't next to an on-screen grid will never be seen, so don't bother rendering it.
5) Bullets should not collide with bullets, which will take a whack off the number of tests to perform. Powerups should only collide with ships and the scenary, and ships should collide with everything ;).
6) If possible, don't do any other tests apart from sphere-sphere as most shooters don't require anything more complex.
7) Don't use dynamic spacial partitioning. It will choke under bullet-hell shooters.
8) Put the bullets into a seperate array from the ships and other entities. That way you can ensure that no bullet is ever tested against another. It will require rendering 2 different arrays, but it'll be worth it.
9) If both objects are still then don't test them
10) I'm done.
++
A simple possibility
Make up an array that is the size of your 2d grid
For each object (this is o(n)) Startup
for each cell an object occupies
Increment the array value for that cell
next cell
next object
Now you need to move things, what you do, is:
For the trailing edge of the object, you decrement its array value, and on the leading edge of the object, you incrememnt its array value.
Every time you increment an array value, you go
Test = array[index] & b11111110
Now if test is > 0 then you have a collision.
O(n) time complexity o(m) memory usage. Its ok. as long as you have small maps. (or else its possible, but it uses up more time to use a nearly fixed amount of memory, but you need to recreate it every frame, so...
o(n), in time complexity, the n is the number of moving objects. (when you don't have any moving objects this is exactly 0. no tests, just zip.)
With o(m) memory usage, m is the size of the map. it could be a room, building, or the entire map.
Its also possible to build overlapping maps, which you can cache. to get a good mix. but its harder, and takes time doing the calculations.
From,
Nice coder
Make up an array that is the size of your 2d grid
For each object (this is o(n)) Startup
for each cell an object occupies
Increment the array value for that cell
next cell
next object
Now you need to move things, what you do, is:
For the trailing edge of the object, you decrement its array value, and on the leading edge of the object, you incrememnt its array value.
Every time you increment an array value, you go
Test = array[index] & b11111110
Now if test is > 0 then you have a collision.
O(n) time complexity o(m) memory usage. Its ok. as long as you have small maps. (or else its possible, but it uses up more time to use a nearly fixed amount of memory, but you need to recreate it every frame, so...
o(n), in time complexity, the n is the number of moving objects. (when you don't have any moving objects this is exactly 0. no tests, just zip.)
With o(m) memory usage, m is the size of the map. it could be a room, building, or the entire map.
Its also possible to build overlapping maps, which you can cache. to get a good mix. but its harder, and takes time doing the calculations.
From,
Nice coder
Author
Everything in the game is part of the same class hierarchy, and every object has an identifier that identifies exactly what it is in the game. I was planning on using that, among other things, in collision detection, so that if the engine flagged a collision between two things, each of the things would know what the other thing was and could act accordingly. For simple example:
The eliminating B vs A once A vs B has been done is common sense, I can't believe that didn't come up to my mind yet. But I'll add that now, because it is very simple.
Collision detection is still a way in the future for my engine. Right now I'm working my way through the easier portions of the class hierarchy to get the interfaces right (Part of the family tree) and testing them out is a little bit fun sometimes...
Can't wait to get some interactivity though. A few months down the line, probably for something minimally playable.
Thanks for the tips, all.
void CPlayer::Collision(const CThing *COther){ switch(COther->TypeID) { // ... case TYPEID_MISSILE: DieAPainfulDeath(); break; case TYPEID_PLAYERBULLET: break; // don't let the player shoot himself in the foot // ... }}// ...void CMissile::Collision(const CThing *COther){ switch(COther->TypeID) { // ... default: Spawn(new CExplosion(...)); Flags|=FLAG_CULL; break; }}The eliminating B vs A once A vs B has been done is common sense, I can't believe that didn't come up to my mind yet. But I'll add that now, because it is very simple.
Collision detection is still a way in the future for my engine. Right now I'm working my way through the easier portions of the class hierarchy to get the interfaces right (Part of the family tree) and testing them out is a little bit fun sometimes...
Can't wait to get some interactivity though. A few months down the line, probably for something minimally playable.
Thanks for the tips, all.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
