   Collision Detection problem
  Hi,I am currently having a little problem with my collision detection. Basically I want to test between the bullets fired from a player's craft with an array of asteroids randomly generated. I have used STL list for both.What I did so far was just to test the X and Y positions of the bullet with the asteroids. But I think there is something wrong with the way I test them. Below are my code to further explain:[source lang = "cpp"]// the Asteroids where initialised earlier with:for(int i=0;i<OBJECTS;i++){pAsteroid->MoveTo(rand()%.GetScreenWidth()-SPS2Manager.GetScreenWidth()/2*MULT, (rand()%GetScreenHeight()-GetScreenHeight()/2*MULT), 1 + (rand()%200));AsteroidList.push_back(*pAsteroid);}//Asteroids Iteratorfor(AsteroidIterator=AsteroidList.begin(); AsteroidIterator != AsteroidList.end(); ++AsteroidIterator){AsteroidIterator->SetWidth(124);AsteroidIterator->SetHeight(124);AsteroidIterator->RenderPerspective();AsteroidIterator->MoveDeltaZ(5);if(AsteroidIterator->GetZ() > MAX_Z) {AsteroidIterator->MoveTo(rand()%.GetScreenWidth()-SPS2Manager.GetScreenWidth()/2*MULT, (rand()%GetScreenHeight()-GetScreenHeight()/2*MULT), 1 + (rand()%200));//AsteroidList.sort();}asteroidX = AsteroidIterator->GetX();asteroidY = AsteroidIterator->GetY();asteroidZ = AsteroidIterator->GetZ();}// Bullet Iteratorfor(BulletIterator=BulletList.begin(); BulletIterator != BulletList.end(); ){BulletIterator->SetWidth(16);BulletIterator->SetHeight(16);BulletIterator->RenderPerspective();BulletIterator->MoveDeltaZ(-15.5f);BulletIterator->MoveY();bulletX = BulletIterator->GetX();bulletY = BulletIterator->GetY();bulletZ = BulletIterator->GetZ();if( bulletZ < 300.0f ) // Depth where enemies spawn as well{BulletIterator = BulletList.erase(BulletIterator);}else ++BulletIterator;//printf("\n\nBullet Z = %f\n\n", depth); }I then test the values by doing if (bulletX == asteroidX) etc etc (bulletX and asteroidX are globals). This doesn't seem to be working as I am getting very random values from asteroidX. I am not really sure of how to perform the collision detection in this case.edit: I did some debugging and I found out that by my current method, the asteroids X,Y readout would be the one that hits the limit (before despawning) hence that is why I get erratic readings.Is there a way to lets say, first test all the asteroids on the same plane as the first (furthest) bullet fired, and then we test all the X and Ys of the roids on the same plane?Well I tried something like this :[source = lang "cpp"]for(int i=0; i<OBJECTS; i++){for(int p = 0; p < BulletList.size(); p++) {  if(pBullet.GetZ() == pAsteroid.GetZ() &&  pBullet.GetX() == pAsteroid.GetX()){printf("\n *************** BAM !!!!!!!!! **********************\n");}else printf("\n\n NO BAM!!!!!!!!!!!! \n\n"); }}Seemed to work for a while then the system locked. I think this is because of my bullet STL that has no fixed size?[Edited by - jonathanc on April 13, 2008 10:57:46 PM]
  Ok , so I tried to read the values of each instance in the Asteroid list by doing this :for(int i=0; i<AsteroidList.size(); i++){float temp1 = pAsteroid.GetX();printf("\n\n list:  :%d X:%f\n\n", i,temp1);}I noticed 2 problems though.1) The problem slows down, a lot. Achieving maybe 5fps.2) The readouts are weird. I get @=0, X = 480.000 but from =1 to [49] , I get X = 0 as readout. (I have 50 elements).Can anyone please tell me what I am doing wrong here :( I need to compare each (alive) elements of the list to another list so I can do some sort of a collision detection.edit: Hmm ok, so if I do AsteroidIterator->GetX(); it will point to the current element's X value, if I am not mistaken. But how do I "loop" through so I can point to all the elements value (to check if any satisfy a condition).[Edited by - jonathanc on April 14, 2008 12:52:34 PM];  First, comparing locations is a very weak form of collision detection. Bullets and especially asteroids are likely to be larger than just a dot and it's pretty easy to miss by just one single <insert measurement unit here>. Use a box-box or circle-circle collision detection method instead, depending on what best suits your game.Second, the 3 asteroidX = AsteroidIterator->GetX(); lines don't seem to have any usefull purpose, the same goes for the bullets part. After the loop, they will hold the positions of the last asteroid and bullet. What are these lines meant to accomplish?Third, if you store pointer-to-objects in a list, you'll need to access members with the -> operator. If you store objects in a list, you should use the . operator.Fourth, use a debugger for debugging. There are some pretty good ones available for free, and the time it takes to learn to work with one is a good investment. :)Fifth, you're mixing C++ and C. I assume you're unfamiliar with std::string, std::ostream and the like?Sixt, and that's a minor point, but it does affect your code readability, your style is inconsistent. Sometimes you're placing a { on the next line, sometimes on the same. Sometimes you surround a single line with {}, sometimes you don't. I think it'll help you in the long run if you keep your code consistent. At the very least it'll help the people you're going to work with. :)   ;  Hmmm finally managed to get my 2 lists done. They are :list<Sprite> BulletList;Sprite Bullet;list<Sprite>::iterator BulletIterator;list<Sprite> AsteroidList;Sprite Asteroid;list<Sprite>::iterator AsteroidIterator;for(AsteroidIterator=AsteroidList.begin(); AsteroidIterator != AsteroidList.end(); ++AsteroidIterator){AsteroidIterator->SetWidth(32);AsteroidIterator->SetHeight(32);AsteroidIterator->RenderPerspective();AsteroidIterator->MoveDeltaZ(5);if (AsteroidIterator->GetZ() > MAX_Z ) AsteroidIterator->MoveTo(((rand()%640)-320),((rand()%512)-256), 1 + rand()%200);}// resets the asteroids if it reaches the endfor(BulletIterator=BulletList.begin(); BulletIterator != BulletList.end(); ){BulletIterator->SetWidth(16);BulletIterator->SetHeight(16);BulletIterator->RenderPerspective();BulletIterator->SetVel(3.5f);BulletIterator->MoveDeltaZ(-15.5f);BulletIterator->MoveY();if( BulletIterator->GetZ() <200.0f ) // Depth where enemies start spawn as well// erase bullets if it reaches this point{BulletIterator = BulletList.erase(BulletIterator);}else ++BulletIterator;}AsteroidList.sort();Everything looks ok now but I have ran into a problem. How do I loop through both list and check collision detection between each of those two elements and also delete them off screen as appopriate? I have tried several methods but can't seem to get it right.My collision detection routine is a currently a member of class Sprite :bool Sprite::Collision(Sprite & r1, Sprite & r2){float halfw1 = r1.GetW()/2.0f;float halfh1 = r1.GetH()/2.0f;float halfw2 = r2.GetW()/2.0f;float halfh2 = r2.GetH()/2.0f;if((r1.GetX() + halfw1) < (r2.GetX() - halfw2)) return(false);if((r1.GetX() - halfw1) > (r2.GetX() + halfw2)) return(false);if((r1.GetY() + halfh1) < (r2.GetY() - halfh2)) return(false);if((r1.GetY() - halfh1) > (r2.GetY() + halfh2)) return(false);return(true);};  Ok so I was experimenting and I came out with something like this :list<Sprite>::iterator i_roids;list<Sprite>::iterator i_bullets;for(i_bullets = BulletList.begin();i_bullets = BulletList.end();i_bullets++){for(i_roids = AsteroidList.begin();i_roids = AsteroidList.end();i_roids++){if (Collision(i_bullets, i_roids) == true) {printf("COLLISION DETECTED!!!!!!!!\n\n");}}}Naturally I expected an error and it says :  no match for `_List_iterator<Sprite,Sprite &,Sprite *> & = _List_iterator<SpriteT,SpriteT &,SpriteT *>'I guess thats because my Collision function is expecting a pointer to an instance of class Sprite and not a list object. Basically what I want it do achieve something like : void PlayerBulAsteroidCol() // Collision Detection and Response for player bullet and asteroids{int i, j;for (i=0; i<MAX_BULLETS; i++){for (j=0; j<MAX_ASTEROIDS; j++){if (CollisionDetect(pBullets, asteroids[j]) == true){gScore+=20;InsertExplosion(asteroids[j]);pBullets.alive = false;}}}return;}This is what I wrote previously for a simple Windows game. But I am just kind of stuck when trying to apply it here. I know lists are just an improved version of an array but how do I modify/track its objects accordingly in my game loop?   ;  Ok more updates :PI have came up with something like this : bool CGame::BulRoidCol(){for(BulletIterator=BulletList.begin(); BulletIterator != BulletList.end(); BulletIterator++){for(AsteroidIterator=AsteroidList.begin(); AsteroidIterator != AsteroidList.end();AsteroidIterator++ ){float halfw1 = AsteroidIterator->GetW()/2.0f;float halfh1 = AsteroidIterator->GetH()/2.0f;float halfw2 = BulletIterator->GetW()/2.0f;float halfh2 = AsteroidIterator->GetH()/2.0f;printf("\nBulletX %.1f, Y:%.1f\n", BulletIterator->GetX() , BulletIterator->GetY() );printf("\nRoidX %.1f, Y:%.1f\n", AsteroidIterator->GetX(), AsteroidIterator->GetY());if((BulletIterator->GetX() + halfw1) < (AsteroidIterator->GetX()- halfw2)) return (false);if((BulletIterator->GetX() - halfw1) > (AsteroidIterator->GetX()+ halfw2)) return (false);if((BulletIterator->GetX() + halfw1) < (AsteroidIterator->GetX()- halfw2)) return (false);if((BulletIterator->GetX() - halfw1) > (AsteroidIterator->GetX()+ halfw2)) return (false);return (true);}}}Looks like its working but according to be debug screen its returning positive everytime I release a bullet.Now this could be that when collision occurs I do nothing so it kept on detecting for that current and roid...hence the spam.Is there anyway to modify this so it deletes both the bullet and asteroid from the list too? I tried a few methods but it crashed the system. I am assuming this is because I am adding + deleting elements in separate loops. (but the same element)I am currently calling this outside the bullet and asteroid lists (naturally it will crash if I call this function inside for the nested loops).   ;  In short what I am trying to achieve here is :1) loop through all the elements for both lists (at the same time)2) compare all the elements to see if they satisfy a condition3) if they do, grab the elements values, and then proceed to "delete" them from their prospective lists.4) update everything and loop again.Now I have tried several methods but that either crashes my program or doesn't delete the right elements :<My 2 lists are :A) Bullets list = push_back to list everytime user presses fire = if it reaches a boundary, delete it (I want to do collision detection here and delete it if pos)B) Asteroids list = the list is filled at start with random values   = currently if asteroid goes out of screen, randomly plant another one  = I want to compare each elements x,y,z to the bullets and if they collide, delete them from both lists.I know it sounds simple but I really can't figure it out :( And I am using lists for the sort function  because I have Z buffer as well that needs it for transparency etc etc.   ;  Looks like I am talking to myself but hopefully someone knows whats wrong :(I have something like this now:list<Sprite> BulletList;Sprite Bullet;list<Sprite>::iterator BulletIterator;list<Sprite> AsteroidList;Sprite Asteroid;list<Sprite>::iterator AsteroidIterator;// These two are extra iterators I use to loop both roids and bulletrslist<Sprite>::iterator i_roids;list<Sprite>::iterator i_bullets;//List 1for(AsteroidIterator=AsteroidList.begin(); AsteroidIterator != AsteroidList.end(); ){AsteroidIterator->SetWidth(32);AsteroidIterator->SetHeight(32);AsteroidIterator->RenderPerspective();if (AsteroidIterator->GetZ() > MAX_Z) {AsteroidIterator->MoveTo(((rand()%640)-320),((rand()%512)-256), 1 + rand()%200);}else AsteroidIterator++;}// List 2for(BulletIterator=BulletList.begin(); BulletIterator != BulletList.end(); ){BulletIterator->SetWidth(16);BulletIterator->SetHeight(16);BulletIterator->RenderPerspective();if( BulletIterator->GetZ() <200.0f ) // Depth where enemies spawn as well{BulletIterator = BulletList.erase(BulletIterator);}else ++BulletIterator;}// Note for List 2 I also add to it byif(player.fire = true){Bullet.MoveTo (ship.GetX(),(ship.GetY()-45), 800);BulletList.push_back(Bullet);}// This is the loop I used for Collision Detection// loops through bulletlist and asteroidlist but using i_bullets and i_roids to //iteratevoid CGame::BulRoidCol(){for(i_bullets=BulletList.begin(); i_bullets != BulletList.end(); ){for(i_roids=AsteroidList.begin(); i_roids != AsteroidList.end(); ){float bulletz = i_bullets->GetZ();   float roidz = i_roids->GetZ();float roidx = i_roids->GetX();float bulletx = i_bullets->GetX();float bullety = i_bullets ->GetY();float roidy = i_roids->GetY();if(bulletz<600 && bulletz>400){if(roidz<600 && roidz>400){i_bullets = BulletList.erase(i_bullets);i_roids = AsteroidList.erase(i_roids);}}else {i_bullets++;i_roids++;}}}}Its not the best collision detection algo atm but I just want to get the deletion correct. As usual, the program crashed when I do this :( Any ideas why?   ;  Heh, give the people on the forum a little time, perhaps. ;PAs to your problem, I suspect that the current crash (presuming that there isn't any new-ed memory in either of your bullet or asteroid classes that you're not properly dealing with) is due to your not updating your iterators after a deletion.  Note that you have it only incrementing the iterators if items are not deleted, which means, if I'm not much mistaken, that on the next run through the loop you will be attempting to use then-invalidated iterators.You didn't seem to be too far off in your previous version, however, by the looks of it.  I did see a few problems - "halfh2" was calculated using the asteroid iterator instead of the bullet iterator, you added the asteroid's half -width and -height to the bullet's position, and vice versa (perhaps, if I'm not mistaken in that, more descriptive names would have helped?), and only tested on the x-axis (it seems that you may have intended to test on the y-axis, but hadn't converted what seems to be code copied from the x-axis test), that I noticed.   ;Quote:Original post by ThaumaturgeHeh, give the people on the forum a little time, perhaps. ;PAs to your problem, I suspect that the current crash (presuming that there isn't any new-ed memory in either of your bullet or asteroid classes that you're not properly dealing with) is due to your not updating your iterators after a deletion.  Note that you have it only incrementing the iterators if items are not deleted, which means, if I'm not much mistaken, that on the next run through the loop you will be attempting to use then-invalidated iterators.You didn't seem to be too far off in your previous version, however, by the looks of it.  I did see a few problems - "halfh2" was calculated using the asteroid iterator instead of the bullet iterator, you added the asteroid's half -width and -height to the bullet's position, and vice versa (perhaps, if I'm not mistaken in that, more descriptive names would have helped?), and only tested on the x-axis (it seems that you may have intended to test on the y-axis, but hadn't converted what seems to be code copied from the x-axis test), that I noticed.ahoy!I do apologise if I sound edgy :S Been working through the night on this project and I really want to solve this problem :DWell, I actually have a version of this game using arrays. But now the game is a bit different hence sorting is very important so I don't overlap some of my sprites.Yes I noticed that I changed the detection routine. It's because I want to fix the STL lists before moving on , so I switched to a much simpler routine. I just post my updates and ideas along the way so I hope you don't mind the spam :DAnd about the iterator, this is the method I learnt for removing an item from the list. The only "obstacle" I see now is that there is no way to "actively" change the contents like I want to. It's obvious in my previous codes where you can only iterate through the list once and make changes (add/remove items) and if you try to do another iteration(even with different iterators) it would just crash the system :<Hmmm, isn't incrementing when items are not deleted correct? Or am i missing something here?