# List Problem

## Recommended Posts

Antonym    179
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 on other sites
sheep19    494
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 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 on other sites
Antonym    179
Quote:
 Original post by sheep19Well 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 on other sites
choffstein    1090
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 on other sites
choffstein    1090
Quote:
Original post by Antonym
Quote:
 Original post by sheep19Well 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)...

##### Share on other sites
Antonym    179
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 on other sites
rip-off    10979
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 on other sites
rip-off    10979
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 on other sites
Antonym    179
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 on other sites
rip-off    10979
In C++, there is little difference between a struct and a class. The main difference is default member visibility.
struct Foo{   int foo;};class Bar{   int bar;};

In the above, the member foo is public and the member bar is private. This is because members in a struct are public unless you specify otherwise. Likewise, in a class members are private unless you specify otherwise.

The other difference has to do with inheritance. A struct defaults to public inheritance and a class to private inheritance. Private inheritance isn't often used though. This tends to be a minor point.

Other than that, class and struct are the same. You can declare member functions, constructors and destructors in either. You can derive a struct from a class and vice versa.

The difference is usually a style thing. Some people use the struct keyword when the type they are creating is a POD type. I use it in the above situation, and also for very small types (because the "public" keyword can be omitted).

The ampersand indicates a C++ reference. This means that one is an alias for *it. Remember that C++ places great emphasis on values. By omitting the ampersand you would be creating a copy of the Object instance. In general, we try to minimise copying when we can. Complex types like std::string (and possibly your 'Object' type) can be expensive to copy. A common rule of thumb is to use references unless the type is primitive.

This might explain it better.

##### Share on other sites
Antonym    179
What sort of copying? Primitive? Sorry it's just all this are new terms for me :S I seem to recall some of them from studying the language syntax but I've forgotten plenty...

##### Share on other sites
HomerSp    126
Primitive types are types that are built in. int, char, short etc.

##### Share on other sites
rip-off    10979
A copy is a copy.

With a reference, there are two names for the same thing in memory. With a copy, there are two things in memory.

##### Share on other sites
Antonym    179
A question that bugged me for a while that I just have been reminded of is, why constants? What is the difference between a constant integer and a normal integer for example?

##### Share on other sites
rip-off    10979
The terminology can be confusing.

- integer literals
- constant integers (like const <any other type>)
- integer constants

The first is the clearest. It refers to anywhere you write an actual number, like 42, in C++. The second is fairly clear. The last is a bit ambiguous, it could refer to either of the others depending on context.

Can you re-word your question in light of this? I am not really sure what you are asking. Are you asking about the const keyword in general, or is there something specific about integers that you are wondering?

##### Share on other sites
Antonym    179
the keyword in relation to data types

one more question, this

'const Object &one = *it;'

would mean one is a reference to a constant object which would be the value pointed by 'it'?

##### Share on other sites
rip-off    10979
Ah right... you were pretty clear, I just misread your question [smile]

const means "I cannot write through this alias". So a const int cannot be written to. The following will not compile:
const int x = 42;x = 13; // error

In practise, we only use const on integers when defining important, global constants.

With pointers and references, const becomes much more important. The ability to write to to the original variable could be the source of bugs. Here is some information about it.

A simple example, consider passing a string to a function. To avoid a copy, we pass a reference:
void frobnicate(std::string &ref){    // ...}

However, because "ref" is now an alias for the value in the calling code, if we accidentally modify ref inside the function then the calling code will see these changes! This is bad, because we only passed by reference to avoid a copy, not so the caller's value could be modified.

The solution is to mark the parameter as const too. This way frobnicate() cannot write to the reference. Most of the time passing a const reference is almost exactly the same as passing the parameter by value in terms of the logic in the function.

In general, C++ programmers mark references and pointers as const by default, unless you are 100% sure you want to allow writing through them. In the collision example earlier, I could have omitted the const qualifier, and nothing bad would probably happen. But better to be safe than sorry.

There is also the advantage that you can pass a temporary into a const reference, which you can't do with a non-const reference:
void foo( std::string &arg ) { /* ... */ }void bar( const std::string &arg ) { /* ... */ }int main(){    foo("hello"); // fails to compile    bar("world"); // will compile fine}

There was a typo in the example I gave. The is_colliding() function should be marked const too. I have corrected this now.

##### Share on other sites
randomizer    130
Quote:
 Original post by AntonymWhat sort of copying? Primitive? Sorry it's just all this are new terms for me :S I seem to recall some of them from studying the language syntax but I've forgotten plenty...

##### Share on other sites
Antonym    179
Thanks again and thanks for the suggestion but I don't want to get myself reading c++ books again. I've found that I learn way better from trial and error rather than reading books. I've tried studying plenty of material on c++ and look how sloppy I still am, most of what I currently know still came just recently by trying to make my programs through... trial and error.

Edit: And of course the excelent help from this forum ^_^.

##### Share on other sites
Antonym    179
I made modifications to the code... my brain is about to hit a meltdown.. The same problem has pop up again and I don't know why. Asoon as it compiles it crashes telling me an iterator can't be incremented. I can't see what's wrong with it this time.. help please...

list<object> gameObjects;list<object> removeObjects;void updateObjects(list<object>* gameObjects){		list<object>::iterator it;	list<object>::iterator it2;	for(it = gameObjects->begin(); it != gameObjects->end(); it++){		const object &one = *it;		for(it2 = it + 1 ; it2 != gameObjects->end() ; it2++)		{			const object &two = *it2;			if(isColliding(one,two))			{				removeObjects.push_back(*it);			}		}	}	for(it = removeObjects.begin() ; it != removeObjects.end() ; it++){		gameObjects->erase(it);	}	return;}bool isColliding(const object &one, const object &two){	return(one.pos.x < two.pos.x + two.width &&		   one.pos.x > two.pos.x - two.width &&		   one.pos.y < two.pos.y + two.height &&		   one.pos.y > two.pos.y - two.height);}

##### Share on other sites
rip-off    10979
You have 3 for loops, you only need two. Also, this is incorrect:
for(it2 = it2++ ; // ...

Read visage's post again, paying careful attention to the variables used.

##### Share on other sites
Antonym    179
Oops for that, caught it soon and removed it, the problem is still present.

I tried changing the it2++ to it + 1 and it gave me more error messages :S..

1>c:\documents and settings\david\mis documentos\visual studio 2005\projects\dungeon\dungeon\logic.cpp(116) : error C2784: 'std::_String_iterator<_Elem,_Traits,_Alloc> std::operator +(_String_iterator<_Elem,_Traits,_Alloc>::difference_type,std::_String_iterator<_Elem,_Traits,_Alloc>)' : could not deduce template argument for 'std::_String_iterator<_Elem,_Traits,_Alloc>' from 'int'
1> c:\archivos de programa\microsoft visual studio 8\vc\include\xstring(438) : see declaration of 'std::operator +'
1>c:\documents and settings\david\mis documentos\visual studio 2005\projects\dungeon\dungeon\logic.cpp(116) : error C2784: 'std::_String_const_iterator<_Elem,_Traits,_Alloc> std::operator +(_String_const_iterator<_Elem,_Traits,_Alloc>::difference_type,std::_String_const_iterator<_Elem,_Traits,_Alloc>)' : could not deduce template argument for 'std::_String_const_iterator<_Elem,_Traits,_Alloc>' from 'int'
1> c:\archivos de programa\microsoft visual studio 8\vc\include\xstring(298) : see declaration of 'std::operator +'
1>c:\documents and settings\david\mis documentos\visual studio 2005\projects\dungeon\dungeon\logic.cpp(116) : error C2784: 'std::reverse_iterator<_RanIt> std::operator +(_Diff,const std::reverse_iterator<_RanIt> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'int'
1> c:\archivos de programa\microsoft visual studio 8\vc\include\xutility(1809) : see declaration of 'std::operator +'
1>c:\documents and settings\david\mis documentos\visual studio 2005\projects\dungeon\dungeon\logic.cpp(116) : error C2676: binary '+' : 'std::list<_Ty>::_Iterator<_Secure_validation>' does not define this operator or a conversion to a type acceptable to the predefined operator
1> with
1> [
1> _Ty=object,
1> _Secure_validation=true
1> ]

##### Share on other sites
rip-off    10979
std::list isn't a random access container. This means that you can't use operator + with iterators from std::list. You could change to a different container, like std::vector<>. Alternatively, something like this:
for(it = gameObjects->begin(); it != gameObjects->end(); it++){    const object &one = *it;    it2 = it;    // skip the current element    ++it2;    for(/* nothing here */ ; it2 != gameObjects->end() ; it2++)    {        // ...    }}

##### Share on other sites
Zahlman    1682
Quote:
 Original post by AntonymI've found that I learn way better from trial and error rather than reading books.

Don't you think your experience in this thread (and, for that matter, the need to start it in the first place) kind of contradicts that evaluation? :)