Jump to content

  • Log In with Google      Sign In   
  • Create Account

Problem with my Quadtree - converting from std::vector to std::set


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
10 replies to this topic

#1 Moonkis   Members   -  Reputation: 273

Like
0Likes
Like

Posted 29 June 2013 - 12:46 PM

I recently made a dynamic quadtree for moving objects for a game I'm creating. Initially i used the std::vector to contain all objects present in the current rectangle and after some optimization and fixing stack overflow it's now working perfectly with 1000+ moving objects.
 

 

However, a friend of mine told me ( or rather a chat ) that I should be using std::set rather than std::vector because it uses less alloc/moving/resizing-calls and has improved access time.

My naive approach was simply just change all std::vector operations to be std::set, change a few loops to use iterators instead of an integer and so forth. The code in it self is exactly "the same" as the one with vectors but for some reason it's crashing inside the "Quadtree::update()" method which simply updates the quadtree which contains moving objects.

The function looks like this:
 

void Quadtree::update() {
	if ( status == QuadStatus::BRANCH && hasLeafChildren() )
		merge();
	
	if(status == QuadStatus::LEAF) {
		for( auto it = objects.begin(); it != objects.end(); ++it) {
			if(!inBounds((*it)->getX(), (*it)->getY()) ) {
				GameObject* o = (*it);
				it = objects.erase(it); // THIS IS WHAT IS CAUSING THE CRASH!!!
				parent->addObject(o);
			}
		}
		return;
	}
	else
		for(int i = 0; i < 4; i++) {
			if(nodes[i] != nullptr)
				nodes[i]->update();
		}
}

Apparently it's the line "it = objects.erase(it)" that is making the program crash - here is the call stack:
 

 

0  0x00449a26  std::_Rb_tree_increment(std::_Rb_tree_node_base const*)    

1  0x004ceed6  std::_Rb_tree_const_iterator<GameObject*>::operator++  c:\\mingw-4.7.1\\lib\\gcc\\mingw32\\4.7.1\\include\\c++\\bits\\stl_tree.h  269
2  0x00403cca  Quadtree::update  C:\\Users\\Victor\\Documents\\CodeLite\\OneGameAMonth\\TinyQuest\\Quadtree.cpp  213
3  0x00403d58  Quadtree::update  C:\\Users\\Victor\\Documents\\CodeLite\\OneGameAMonth\\TinyQuest\\Quadtree.cpp  231
4  0x00403d58  Quadtree::update  C:\\Users\\Victor\\Documents\\CodeLite\\OneGameAMonth\\TinyQuest\\Quadtree.cpp  231
5  0x00401ad1  main  C:\\Users\\Victor\\Documents\\CodeLite\\OneGameAMonth\\TinyQuest\\main.cpp  79

I'm not entirely sure why ( I think it's an overflow ) but isn't std::set suppose to use LESS operations than an vector?


Kind regards, Moonkis



Sponsor:

#2 SillyCow   Members   -  Reputation: 849

Like
0Likes
Like

Posted 29 June 2013 - 02:07 PM

std:set does faster lookups for a specific object.

 

When you use a vector, which is basically an array, a lookup involves scanning the entire array. If you have 100 objects in the array, a lookup will take 100 operations (go over 100 objects until you find what you wanted).

Erasing is even worse, since in a vector, erasing something from the middle involves scanning the entire array to find it, and then copying the tail of the array over the "empty" space caused by deleting.

 

Sets implement either a "binary tree" or a "hash table" instead of an array (as vectors). They are able to do one item lookups and deletes very fast. The cost is that they take up more memory, and are slightly slower with other operations. But "erase a certain object" is much simpler than vectors.

If you want to understand exactly why, look up binary-trees and hash-tables on wikipedia. But your friend is basically right specifically regarding the "modeify/erase a specific item" operation. Which is exactly what you are doing here.

 

If you want to find out exactly what is causing the crash, run it in a debugger. I personally recommend Visual Studio, as it has excellent debug assertions on STL containers. You'll find your problem in 2 minutes.

 

also consider using an unordered set. If you don't need sorting, it should perform slightly better than an std::set.


Edited by SillyCow, 29 June 2013 - 02:13 PM.

My new android game : Enemies of the Crown

My previous android game : Killer Bees


#3 Cornstalks   Crossbones+   -  Reputation: 6994

Like
2Likes
Like

Posted 29 June 2013 - 02:28 PM

std:set does faster lookups for a specific object.

std::set is faster at determining if a specific object is in the set (because they're sorted, so a binary search can be done). However, for iterating over, std::vector is faster, because it's a contiguous block of memory that's more cache friendly. The thing is though, to lookup an object in a std::set doesn't make a lot of sense, because you have to pass it the object to look up (which means you already have the object to begin with...).
 

When you use a vector, which is basically an array, a lookup involves scanning the entire array. If you have 100 objects in the array, a lookup will take 100 operations (go over 100 objects until you find what you wanted).

It won't necessarily take 100. On average, it will take about 50 (assuming a randomly sorted array/vector and finding a random element (also assuming no duplicates)). Worst case is 100 comparisons. Best case is 1 comparison.

 

Erasing is even worse, since in a vector, erasing something from the middle involves scanning the entire array to find it, and then copying the tail of the array over the "empty" space caused by deleting.

Note that he's already iterating through the entire array, so the only extra cost of an erase() is the compacting of the data structure. In his case, there isn't really an added cost for finding the element to erase. Not necessarily. He has an iterator to the vector. Calling erase() is O(1). He's already iterating over the whole vector. The call to erase is not linear, though. It's constant time. [edit: that was embarrassing; thanks SiCrane]

 

Anyway, @Moonkis: unless I'm misreading/misunderstanding that stack trace, it's actually crashing on ++it. The problem is that erase() (for both vector and set) will return end() if you just erased the last element. Then the loop will try to ++it (before checking it != end()), which is undefined behavior. You need to check if it == end() (and NOT do ++it if it is).

 

Basically, this can be caused if your program follows this execution order:

  1. auto it = objects.begin()
  2. it != objects.end()
  3. execute loop body
  4. it = objects.erase(it); // Let's say you erased the last element and now erase() returns end()
  5. ++it // It will crash here, because it == end()!
  6. it != objects.end()
    1. Go to #3 if true
    2. Break out of the loop if false

 

The fact that it crashes with std::set and not std::vector is just dumb luck (or perhaps it's unlucky?). It's undefined behavior.

 

Also, for how your using objects, (assuming you aren't doing more with it), using std::vector will be faster. std::set is slower when it comes to iterating over, like you're doing in that loop. However, use the data structure that fits your needs best. If profiling reveals it to be too slow and problematic, then try to optimize.


[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#4 SiCrane   Moderators   -  Reputation: 9598

Like
1Likes
Like

Posted 29 June 2013 - 03:10 PM

Not necessarily. He has an iterator to the vector. Calling erase() is O(1). He's already iterating over the whole vector. The call to erase is not linear, though. It's constant time.

Only erase() at the end of a vector is O(1). The cost for erase() is proportional to how far from the end the iterator is, which means that repeated calls to erase() in a loop like this is quadratic. This is why the swap-and-pop idiom exists and why removing elements based on a condition from a vector is more efficiently done with remove_if().

#5 Cornstalks   Crossbones+   -  Reputation: 6994

Like
0Likes
Like

Posted 29 June 2013 - 03:13 PM

 

Not necessarily. He has an iterator to the vector. Calling erase() is O(1). He's already iterating over the whole vector. The call to erase is not linear, though. It's constant time.

Only erase() at the end of a vector is O(1). The cost for erase() is proportional to how far from the end the iterator is, which means that repeated calls to erase() in a loop like this is quadratic. This is why the swap-and-pop idiom exists and why removing elements based on a condition from a vector is more efficiently done with remove_if().

*facepalm*


[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#6 serumas   Members   -  Reputation: 718

Like
0Likes
Like

Posted 29 June 2013 - 04:04 PM

hi,

I am a littlebit out if space in this theme,but I can suggest you not to use quadtree for moving objects at all.

I want to suggest much simpler(smaller code, main code is about 50 lines) and faster (you dont need to update, remove and etc. operations for single object it goes automaticaly) aprouch that was created for game with lots of moving objects

 

testing app

http://serumas.gamedev.lt/temp/testing.zip

 

If you want I can share the code...


Edited by serumas, 29 June 2013 - 04:29 PM.


#7 BornToCode   Members   -  Reputation: 927

Like
0Likes
Like

Posted 29 June 2013 - 05:44 PM

The thing i do not understand is that you will have to iterate through all your objects anyway withing an node, so using an std vector works better in that especially when you can pre allocated how many objects can initially be store in each node. Another option is to increase your number of objects in each node but never decrease it and reuse them. So the tree node object container only grows and does not shrink. Also another thing you can do is keep track of removing indices in the tree whenever an object moves to a different node into a stack that is part of that node that tells one which node index was moved. So the next time something moves in, you can just grab the index from the stack and use that index into your vector to insert the new object. With that you end up with 0(1) insertion for any object.



#8 Moonkis   Members   -  Reputation: 273

Like
0Likes
Like

Posted 30 June 2013 - 08:47 AM

Anyway, @Moonkis: unless I'm misreading/misunderstanding that stack trace, it's actually crashing on ++it. The problem is that erase() (for both vector and set) will return end() if you just erased the last element. Then the loop will try to ++it (before checking it != end()), which is undefined behavior. You need to check if it == end() (and NOT do ++it if it is).

 

Basically, this can be caused if your program follows this execution order:

  1. auto it = objects.begin()
  2. it != objects.end()
  3. execute loop body
  4. it = objects.erase(it); // Let's say you erased the last element and now erase() returns end()
  5. ++it // It will crash here, because it == end()!
  6. it != objects.end()
    1. Go to #3 if true
    2. Break out of the loop if false

This did the trick, here is the altered code:
 

	if(status == QuadStatus::LEAF) {
		for( auto it = objects.begin(); it != objects.end(); ++it) {
			if(!inBounds((*it)->getX(), (*it)->getY()) ) {
				GameObject* o = (*it);
				it = objects.erase(it);
				parent->addObject(o);
				if ( it == objects.end() ) break;
			}
		}
		return;
	}

Problem is, I don't understand why "if ( it == objects.end() ) break;" is needed!

If the objects.erase() returns "end()" the for-loop should catch it before increasing the iterator, why doesn't it?



#9 SiCrane   Moderators   -  Reputation: 9598

Like
2Likes
Like

Posted 30 June 2013 - 09:06 AM

The condition for a for loop is checked after the increment. If you translate a for loop into a while loop:
for (a; b; c) {
  body
}
becomes
{
  a;
  while (b) {
    body
    c
  }
}


#10 Paradigm Shifter   Crossbones+   -  Reputation: 5374

Like
1Likes
Like

Posted 30 June 2013 - 09:21 AM

 

Anyway, @Moonkis: unless I'm misreading/misunderstanding that stack trace, it's actually crashing on ++it. The problem is that erase() (for both vector and set) will return end() if you just erased the last element. Then the loop will try to ++it (before checking it != end()), which is undefined behavior. You need to check if it == end() (and NOT do ++it if it is).

 

Basically, this can be caused if your program follows this execution order:

  1. auto it = objects.begin()
  2. it != objects.end()
  3. execute loop body
  4. it = objects.erase(it); // Let's say you erased the last element and now erase() returns end()
  5. ++it // It will crash here, because it == end()!
  6. it != objects.end()
    1. Go to #3 if true
    2. Break out of the loop if false

This did the trick, here is the altered code:
 

	if(status == QuadStatus::LEAF) {
		for( auto it = objects.begin(); it != objects.end(); ++it) {
			if(!inBounds((*it)->getX(), (*it)->getY()) ) {
				GameObject* o = (*it);
				it = objects.erase(it);
				parent->addObject(o);
				if ( it == objects.end() ) break;
			}
		}
		return;
	}

Problem is, I don't understand why "if ( it == objects.end() ) break;" is needed!

If the objects.erase() returns "end()" the for-loop should catch it before increasing the iterator, why doesn't it?

 

 

That looks wrong to me, if you erase something the iterator is incremented twice. You want to get rid of ++it from the for(;;) line and add else ++it; if the if statement is not entered.

 

EDIT: Like so... (and the check for .end() isn't needed either now)

if(status == QuadStatus::LEAF) {
		for( auto it = objects.begin(); it != objects.end(); /* no-op */) {
			if(!inBounds((*it)->getX(), (*it)->getY()) ) {
				GameObject* o = (*it);
				it = objects.erase(it);
				parent->addObject(o);
                                // This line is no longer necessary, either
				//if ( it == objects.end() ) break;
			}
                        else
                        {
                                ++it;
                        }
		}
		return;
	}

Edited by Paradigm Shifter, 30 June 2013 - 09:27 AM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#11 Cornstalks   Crossbones+   -  Reputation: 6994

Like
0Likes
Like

Posted 30 June 2013 - 09:57 AM

Note that it might be simpler to do something like this:
 
 
// Disclaimer: there might be some minor syntactic errors in this
// First define this functor (could also be a function, if parent can be accessed globally, which I'd be concerned about)
struct CheckInBounds
{
    Parent* parent; // Or whatever type "parent" really is
 
    CheckInBounds(Parent* p) : parent(p) {
    }
 
    bool operator()(const GameObject* o) {
        if (!inBounds(o->getX(), o->getY())) {
            parent->addObject(o);
            return true; // remove it
        }
        else {
            return false; // don't remove it
        }
    }
};
 
// Then, you can do something simple like this:
auto newEnd = std::remove_if(objects.begin(), objects.end(), CheckInBounds(parent));
objects.erase(newEnd, objects.end());

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS