Simple Collision Detection
I’m trying to come up with the logical routine for some very basic collision detection. The collision detection will be used to detect collision between many different sprites that are located through out the screen.
For example, I have a bullet that is traveling towards the top of the screen. There is also a small collection of enemy sprites staffing back and forth across the screen. My goal is to detect weather this bullet had made a successful collision with one of the sprites in the small collection.
My theories are:
1) Use global array of bullet sprites. Check collision against each sprite on screen with each bullet sprite.
2) Develop a way to organize sprites by position to perform look-ups for bullet sprite collision.
3) Use a cell system that checks collision for sprites with in the cell only.
The first theory seems pretty costly. The second theory would seem to take more effort then is needed. The third theory, however, seems to be easier to code and less hassle to deal with.
The cell system would be very similar to something a tile engine would use. I retrieve the cell the sprite is currently located in by dividing the sprite’s positional co-ordinates by the dimensions of the cell grid. Then check for collision against all other sprites with in this cell. The tricky part is figuring out with sprites are located with in that cell. So I would have to develop a way to organize the sprites similar to theory 2.
I would very much appreciate any suggestions from some of you that may have and idea of what I’m trying to accomplish here.
Well that strongly depends on how many bullet particles / enemies you''re planning to have active in memory at a time.
If there won''t be that many, I''d see no real drawback in using the first method (which can be optimized, still), since it is very easy to program.
I don''t quite get the main idea of the 2nd theory ... sounds pretty much like theory 1...
As to theory 3: sounds promising, but might (!) be total overhead (depending on the number of particles / enemies / movement speed of particles / enemies etc.). Do you want those cells to be like containers holding the enemies? If so, what happens on a "hand-over" from one cell to another? There''s pretty much you have to think about. Though it most possibly is faster than the first approach, you should definitely think about whether it''s practical to optimize that piece of code...
Just my 2 cents...
Indeterminatus
--si tacuisses, philosophus mansisses--
If there won''t be that many, I''d see no real drawback in using the first method (which can be optimized, still), since it is very easy to program.
I don''t quite get the main idea of the 2nd theory ... sounds pretty much like theory 1...
As to theory 3: sounds promising, but might (!) be total overhead (depending on the number of particles / enemies / movement speed of particles / enemies etc.). Do you want those cells to be like containers holding the enemies? If so, what happens on a "hand-over" from one cell to another? There''s pretty much you have to think about. Though it most possibly is faster than the first approach, you should definitely think about whether it''s practical to optimize that piece of code...
Just my 2 cents...
Indeterminatus
--si tacuisses, philosophus mansisses--
as mentioned, which way you go depends on how many collidable objects you have and how big your playing space is. If you have, oh, say, 100+ objects then it might be a good time do use space partitioning (BSP, Quadtrees, tiling system, etc). That way, objects only check other local objects. Your #2 and #3 are about the same. What you do is register each sprite/object as having residence in some "area" (tile, quadrant, sector, whatever you call it) of the game space. When doing collision detection, you only check other objects in that area. When you move objects, you remove them from the area and replace (in the same place or a new area) them after moving.
Remember that larger sprites can inhabit many areas at once if you use a simple grid system. That''s what Quadtrees are for. (don''t ask me about those though)
This all involves some overhead in the checking and moving phases though. If you only have a few objects, i would go with the brute force #1 method and check everybody against everybody else (tip: remember that ObjectA <-> ObjectB is the same as ObjectB <-> ObjectA, so don''t check both combonations or you just end up doing that much more math)
Remember that larger sprites can inhabit many areas at once if you use a simple grid system. That''s what Quadtrees are for. (don''t ask me about those though)
This all involves some overhead in the checking and moving phases though. If you only have a few objects, i would go with the brute force #1 method and check everybody against everybody else (tip: remember that ObjectA <-> ObjectB is the same as ObjectB <-> ObjectA, so don''t check both combonations or you just end up doing that much more math)
The area I would be dealing with is screen space only. The sprites do not move off the screen and neither does the playing field by any means. In other words; the screen resolution is the space to be partitioned. The number of sprite objects that would be on screen ranges from one to thirty, including the player sprite object but not including the bullet sprite objects.
I though of the tiling scheme as one of the best ways also. I’ve also come to realize the problem of sprite objects residing in two or more partitioned areas. For example, an object is placed at an origin (0,0) of all quadrants (similar to the X and Y planes). The sprite is now occupying four areas at once. This creates a problem performance wise.
Then again, because a bullet is traveling upwards, only the sprite objects in the top two quadrants would need to be checked for collision against the bullet. After all, how can two objects moving away from each other possibly collide?
The next step would be to exclude all objects that are not currently obstructing the path of the bullet’s velocity. So, unless an object is directly overhead or would soon be, it is not checked.
In theory, I believe that I can perform collision detections on all sprite objects semi-simultaneously. I should be able to do this by using the same conditional statements for all sprite objects. If one of the conditional statements failed, then the rest would fail also.
If ObjectA has a grater Y value then ObjectB, then there would be no need to check for other corresponding values either. If ObjectA has a lesser Y value then ObjectB, but has a lesser X value then ObjectA, then again, there is no need for continuing the collision detection checks. The logic for the collision detection needs to be set up in a similar manner described above. Using area checking would greatly decreases the number of sprite objects that would be potential candidates for the collision detection algorithm.
The area would need to be sub-divided into the proper levels that have the least multiple area residing problems accruing. This can be figured out on pencil and paper. I simple divide the number of cells horizontally and vertically by the corresponding position co-ordinates. I must save these co-ordinates for each sprite. Every time the sprite object is moved these cell co-ordinates are updates. I think this should partially eliminate the overhead required with quad-trees or any other expensive(memory efficiency) space partitioning algorithms.
The application that this collision detection is used for is something similar to SPACE INVADERS or Galaxian. I think quad-trees are over kill but I could be wrong. The though of using quad trees does inspire some interesting ideas though.
I though of the tiling scheme as one of the best ways also. I’ve also come to realize the problem of sprite objects residing in two or more partitioned areas. For example, an object is placed at an origin (0,0) of all quadrants (similar to the X and Y planes). The sprite is now occupying four areas at once. This creates a problem performance wise.
Then again, because a bullet is traveling upwards, only the sprite objects in the top two quadrants would need to be checked for collision against the bullet. After all, how can two objects moving away from each other possibly collide?
The next step would be to exclude all objects that are not currently obstructing the path of the bullet’s velocity. So, unless an object is directly overhead or would soon be, it is not checked.
In theory, I believe that I can perform collision detections on all sprite objects semi-simultaneously. I should be able to do this by using the same conditional statements for all sprite objects. If one of the conditional statements failed, then the rest would fail also.
If ObjectA has a grater Y value then ObjectB, then there would be no need to check for other corresponding values either. If ObjectA has a lesser Y value then ObjectB, but has a lesser X value then ObjectA, then again, there is no need for continuing the collision detection checks. The logic for the collision detection needs to be set up in a similar manner described above. Using area checking would greatly decreases the number of sprite objects that would be potential candidates for the collision detection algorithm.
The area would need to be sub-divided into the proper levels that have the least multiple area residing problems accruing. This can be figured out on pencil and paper. I simple divide the number of cells horizontally and vertically by the corresponding position co-ordinates. I must save these co-ordinates for each sprite. Every time the sprite object is moved these cell co-ordinates are updates. I think this should partially eliminate the overhead required with quad-trees or any other expensive(memory efficiency) space partitioning algorithms.
The application that this collision detection is used for is something similar to SPACE INVADERS or Galaxian. I think quad-trees are over kill but I could be wrong. The though of using quad trees does inspire some interesting ideas though.
yes, for your game a single all-vs-all check each frame would be okay i''d imagine. Just make sure your math is fast and that you don''t check objects to other objects for which it makes no sense (don''t check bullets to other bullets, unless of course you need to).
What some people do is set up two lists: passive and active objects. Check each active object against each passive and active object. Do NOT check each passive object (walls) to the passive objects. That immediately cuts the number checks down.
If you are doing space invaders, that makes it even easier. You have a few bullets times ~30 bad guys. That''s 100 checks on worst case. Not so bad. You do NOT need to check bad guys agaisnt themselves, nor bullets against themselves, so instead of ~30x30 = 900+ checks, you only have 100. Thats okay. IMHO don''t waste your time on space partitioning for this one.
What some people do is set up two lists: passive and active objects. Check each active object against each passive and active object. Do NOT check each passive object (walls) to the passive objects. That immediately cuts the number checks down.
If you are doing space invaders, that makes it even easier. You have a few bullets times ~30 bad guys. That''s 100 checks on worst case. Not so bad. You do NOT need to check bad guys agaisnt themselves, nor bullets against themselves, so instead of ~30x30 = 900+ checks, you only have 100. Thats okay. IMHO don''t waste your time on space partitioning for this one.
if you have bitmasks for enabling or disabling collisions between objects, it makes things a lot simpler, and not that slow.
for kind of space partitioning, you can sort the objects along an axis (say the Y axis), by their min-value along that axis. then you can do.
so, it''s the basic "test-it-all" algo, but with an extra check that cuts down quite a lot of tests.
you can sort objects along the X axis, and along the Y axis, creating two lists, then you ''intersect'' the two lists to find the pair of objects intersecting. But one list is usually enough.
enum eCollisionType{ ePlayer = (1<<0), eEnemyBullet = (1<<1), ePlayerBullet = (1<<2), eEnemy = (1<<3), eEnvironment = (1<<4), ePickups = (1<<5)};class CCollObject{public: bool ShouldCollide(const CCollObject& CollObject) const { return (m_eType & CollObject.m_eAcceptMask) && (CollObject.m_eType & m_eAcceptMask); }private: u_int m_eAcceptMask; eCollisionType m_eType;};
for kind of space partitioning, you can sort the objects along an axis (say the Y axis), by their min-value along that axis. then you can do.
// Object[] are sorted down the Y-axis by their Box''s Min cornerfor(int i = 0; i < NumSortedObjects; i ++){ for(int j = i+1; j < NumSortedObjects; j ++) { // Checks if box[j] is too far down the Y axis if (Object[j]->Min.y > Object[i]->Max.y) break; // test the X-components and see if the bounding boxes // overlap if (Object[j]->Min.x > Object[i]->Max.x || Object[i]->Min.x > Object[j]->Max.x) continue; // some more refined collision checks TestCollision(Object[i], Object[j]); }}
so, it''s the basic "test-it-all" algo, but with an extra check that cuts down quite a lot of tests.
you can sort objects along the X axis, and along the Y axis, creating two lists, then you ''intersect'' the two lists to find the pair of objects intersecting. But one list is usually enough.
Using two lists is initially the way I first viewed the solution to this problem. One sprite object list would contain only bullets and another would contain the player and enemy sprite objects. I wouldn’t have to check bullets against bullets, nor would I need to check enemy against enemy. But I would have to check enemy against player, but only if the enemy was in a certain logical state that it would be diving towards the player. Other wise, I just fallow what leiavoia and oliii suggested.
It makes very mush cense to avoid unnecessary checks for collision. But I need to have the state machine set up to where things are cooperative. For example, I would process all the logic for the enemies’ first then process the player and lastly the bullets. Each state in the state machine exits after it has been processed but also records data to aid the next round of processing. There should be two different types of bullets. The first type should be a bullet fired from an enemy and the second could be the bullet fired from the player. This way I’m not making 100+ checks against a bullet an enemy fired at the player when I only need to be making one.
It just seems not that the logic routines and state machine need to be set up so that they process thing smoothly and accurately. Thank you for all your input guys. I very much appreciate it.
It makes very mush cense to avoid unnecessary checks for collision. But I need to have the state machine set up to where things are cooperative. For example, I would process all the logic for the enemies’ first then process the player and lastly the bullets. Each state in the state machine exits after it has been processed but also records data to aid the next round of processing. There should be two different types of bullets. The first type should be a bullet fired from an enemy and the second could be the bullet fired from the player. This way I’m not making 100+ checks against a bullet an enemy fired at the player when I only need to be making one.
It just seems not that the logic routines and state machine need to be set up so that they process thing smoothly and accurately. Thank you for all your input guys. I very much appreciate it.
I have found that using the distance formula works much more better. I use the center of the sprite object and the bullets. Then I computer the distance between the two. If the distance is more then half the sprite object''s width a collision has occured. This formula works much better then simply checking X and Y values.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement