Jump to content
  • Advertisement
Sign in to follow this  
Antonym

List Problem

This topic is 3499 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.
	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);
				}
			}
		}
	}			

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 ^_^.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antonym
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 ^_^.


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 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 = 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)...

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!