list<object>::iterator it;
list<object>::iterator it2;
//Iterate through all objects in the list
for(it = gameObjects->begin(); it != gameObjects->end(); it++){
//For each member of the list iterate through all members and see if the current object being checked is in collision with any other
for(it2 = gameObjects->begin(); it2!= gameObjects->end(); it2++){
//Not if it's the same object
if(it2 != it){
if(it->pos.x < it2->pos.x + 16 &&
it->pos.x > it2->pos.x - 16 &&
it->pos.y < it2->pos.y + 16 &&
it->pos.y > it2->pos.y - 16){
//If object is in collision with another object remove object.
gameObjects->erase(it);
}
}
}
}
List Problem
Author
I tried to make something simple to detect collision in an asteroids-like game I am working on.
To begin with I made it so that all objects, the ship and every missile it fires became stored in a list. This here is the code to detect collisions in members of that list, with members of that list.
Basicly I tried to have it iterate through all members of the list for each member of the list and see if the object being currently checked was in collision with any other member of the list(except itself of course).
The problem is that whenever I test the program asoon as a collision occurs it crashes... I think it has to do something with removing a member of a list that is currenlty being iterated through..
It gives me this error message "Expression: list iterator not incrementable"
Any help/advice on how to fix/go around this please?
Thanks
Well I think when you delete the erase the object, you need to give a value to it again, because it loses its value.
Maybe have an iterator temp that is one before it, and after you delete it you set it to temp.
Maybe have an iterator temp that is one before it, and after you delete it you set it to temp.
Yes, you can't delete from a container that you're iterating through.
A quick way to solve it is to 'flag' that item for removal.
A quick way to solve it is to 'flag' that item for removal.
Author
Quote:Original post by sheep19
Well I think when you delete the erase the object, you need to give a value to it again, because it loses its value.
Silly me, it worked, such a simple solution thanks ^_^.
You are invalidating the iterator when you call erase() on it, so you can't it++. When you erase(), you will return an iterator to the next element. This will lead to all sort of logic funkiness that you have to deal with -- for example, your top for loop will now skip objects when you perform an erase. You will most likely need to change this to a while loop. Also, make sure you are not invalidating the second iterator in any way.
Quote:Original post by AntonymQuote:Original post by sheep19
Well I think when you delete the erase the object, you need to give a value to it again, because it loses its value.
Silly me, it worked, such a simple solution thanks ^_^.
Careful with this solution. First of all, the way you have the loop set up, you are doing too much work. By erasing the iterator, you were removing the value from being checked again. Since you are no longer removing the iterator, you will check A versus B, as well as B versus A. Perhaps this is your intention, as it will put BOTH objects in the list to be removed ... but if object A is colliding with B, we know that B is colliding with A.
This method has some benefits, however. In how you have it currently implemented, imagine the case where A is touching both B and C, but we check A versus B first, and remove A. A versus C will never get checked, so no collision will ever be detected. By not removing the item from the list, we ensure that all collisions are detected.
Basically, you probably want to do something like this:
list<object>::iterator it;list<object>::iterator it2;list<object> toRemove;//Iterate through all objects in the listfor(it = gameObjects->begin(); it != gameObjects->end(); it++){ //For each member of the list iterate through all members and see if the current object being checked is in collision with any other for(it2 = it+1; it2!= gameObjects->end(); it2++){ if(it->pos.x < it2->pos.x + 16 && it->pos.x > it2->pos.x - 16 && it->pos.y < it2->pos.y + 16 && it->pos.y > it2->pos.y - 16) { //If object is in collision with another object remove object. toRemove.push_back(*it); } }}for(it = toRemove->begin(); it != toRemove->end(); it++) { gameObjects.remove(*it);}This isn't particularly fast, though, as you have O(n), looping through each toRemove object, and O(m), looping through every game object, to see if it matches -- giving us O(mn). m will most likely be larger than n, giving us O(m) -- but still not too great. We can probably do better than linear...but this has more to do with your choice of data-structure for gameObjects. If gameObjects were a hash-table, implemented as a binary heap, you would get O(logn), which is a great improvement. If it is a hash-table, implemented with a reasonable hash-function, you would get O(1) for insert and delete. All of a sudden, O(nm) has become O(n)...
Author
I had a question, is this a good/decent way of detecting collisions or is it a reall bad/crappy means to an end?
Edit: Thanks by the way visage for all the info. Though I didnt understood this beyond the part that my method isn't fast :S.
'This isn't particularly fast, though, as you have O(n), looping through each toRemove object, and O(m), looping through every game object, to see if it matches -- giving us O(mn). m will most likely be larger than n, giving us O(m) -- but still not too great. We can probably do better than linear...but this has more to do with your choice of data-structure for gameObjects. If gameObjects were a hash-table, implemented as a binary heap, you would get O(logn), which is a great improvement. If it is a hash-table, implemented with a reasonable hash-function, you would get O(1) for insert and delete. All of a sudden, O(nm) has become O(n)...'
[Edited by - Antonym on December 15, 2008 8:00:12 AM]
Edit: Thanks by the way visage for all the info. Though I didnt understood this beyond the part that my method isn't fast :S.
'This isn't particularly fast, though, as you have O(n), looping through each toRemove object, and O(m), looping through every game object, to see if it matches -- giving us O(mn). m will most likely be larger than n, giving us O(m) -- but still not too great. We can probably do better than linear...but this has more to do with your choice of data-structure for gameObjects. If gameObjects were a hash-table, implemented as a binary heap, you would get O(logn), which is a great improvement. If it is a hash-table, implemented with a reasonable hash-function, you would get O(1) for insert and delete. All of a sudden, O(nm) has become O(n)...'
[Edited by - Antonym on December 15, 2008 8:00:12 AM]
Quote:
I had a question, is this a good/decent way of detecting collisions or is it a reall bad/crappy means to an end?
For an "asteroids-like game", the basic technique will probably work fine. It has scalability issues, but your game is unlikely to run into it.
Once you have it working, move on and improve the rest of your game. Don't waste time on something that works. If later on you run into speed issues, you can use a profiler to discover the bottlenecks and sort them out then.
I probably wouldn't hard code the constant 16 in there though. Are you 100% sure you are never going to introduce objects with different sizes?
Even if you are, consider this code:
class Object{public: // ... bool is_colliding(const Object &other) const { return (pos.x < other.pos.x + 16 && pos.x > other.pos.x - 16 && pos.y < other.pos.y + 16 && pos.y > other.pos.y - 16); }};for(it = gameObjects->begin() ; it != gameObjects->end() ; it++){ const Object &one = *it; for(it2 = it + 1 ; it2 != gameObjects->end() ; it2++) { const Object &two = *it; if(one.is_colliding(two)) { // ... } }}I think this would be easier to read. In addition, the "pos" member could be made private, maybe with a bit more work.
Then see if you can modify Object::is_colliding to use a width and height of the entities. You don't actually need to do much, you can simply add these functions to Object
class Object{ int width() const { return 16; } int height() const { return 16; } // ...};What this will have accomplished:
- Collision detection is removed from collision handling
- Removed Magic Numbers from the code, making it easier to understand.
- Can later easily add objects of different sizes by only modifying the width() and height() functions, not the collision detection code.
[Edited by - rip-off on December 15, 2008 10:23:10 AM]
Quote:
Though I didnt understood this beyond the part that my method isn't fast :S.
'This isn't particularly fast, though, as you have O(n) ...
This is Big O Notation. It is a common way of comparing algorithms. It focuses on the worst case running time of an algorithm on a input data set of some size. The size is assumed to be very large - because simple algorithms can often outperform more suitable ones on small data sets.
This is related to what I was saying in my above post: your game will probably have a small data set, so your simple algorithm will suffice.
Author
Thanks rip-off.
I don't recognize the & in 'const Object &one = *it;' though, what does it mean?
I have never used classes before.. Think it's a good time to start converting my structures into classes?
I don't recognize the & in 'const Object &one = *it;' though, what does it mean?
I have never used classes before.. Think it's a good time to start converting my structures into classes?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
