Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » More efficient way to capture mouse position?

This thread is locked; no one can reply to it. rss feed Print
More efficient way to capture mouse position?
Mishtiff
Member #15,776
October 2014

EDIT: Mainly the GetObjectsAt and CheckCollisions methods

#SelectExpand
1//GetObjectsAt() 2vector<GameObject*> Quadtree::GetObjectsAt( double x, double y ) 3{ 4 if ( isLeaf ) { 5 return objects; 6 } 7 8 vector<GameObject*> returnedObjects; 9 vector<GameObject*> childObjects; 10 11 if ( !objects.empty() ) 12 returnedObjects.insert( returnedObjects.end(), objects.begin(), objects.end() ); 13 14 for ( int n = 0; n < NodeCount; ++n ) { 15 if ( nodes[n].contains( x, y ) ) { 16 childObjects = nodes[n].GetObjectsAt( x, y ); 17 returnedObjects.insert( returnedObjects.end(), childObjects.begin(), childObjects.end() ); 18 break; 19 } 20 } 21 22 return returnedObjects; 23}

#SelectExpand
1//CheckCollisions 2bool GameObject::CheckCollisions(GameObject *otherObject) 3{ 4 float oX = otherObject->GetX(); 5 float oY = otherObject->GetY(); 6 7 int obX = otherObject->GetBoundX(); 8 int obY = otherObject->GetBoundY(); 9 10 if( x + boundX > oX - obX && 11 x - boundX < oX + obX && 12 y + boundY > oY - obY && 13 y - boundY < oY + obY) 14 return true; 15 else 16 return false; 17}

Hope this gives some insight.

pkrcel said:

1. I meant profiling...
2. structuring your code better would help a lot in sharing & understanding for people which might look upon your code...
3. At the very least, a buch of conveniently placed (as in when calling a fnction or traversing a loop iteration) "debug" printf with timestamps might help.

1a. Now i understand your suggestion. I have tried using std::cout for timestamps, where i call the current time and track how long it takes to get through a loop. Would you like me to place this back in and check how long some loops are taking?

2a. Ill try to clean it up as to help others understand and not get lost. Since it is my code, I understand it fully, but I will be sure to make it more readable for not only you guys, but for others who look at it for learning.

3a. refer to 1a.

Aikei_c said:

1. some quad trees may actually slow down performance instead of improving it...
2. Also note, if you have any static objects which never move, you don't need to rebuild a quadtree for them every tick, you need to add them just once...

1a. I understand what you mean. I do know that my quad tree does not destroy the quadrants that were made in the last loop. This meaning that if it broke itself down into 10 quadrants, on the next iteration, all of the quadrants from before will be cleared, but the leaves and branches are never reset. I Imagine that could cause some unnecessary looping in the tree search (maybe not actually).

2a. Yeah i currently do not add the static units to the tree at all (since im not worried about collisions with them at this moment). The only units that are added to the quad tree are the ships that move.

Trent Gamblin
Member #261
April 2000
avatar

I don't know what "objects" is in your code, but I assume it's all objects? Your code adds ALL objects repeatedly for every node that x, y is in. That's why smaller divisions gets slower, it's adding all objects multiple times. You need to rewrite the GetObjectsAt method, doesn't make any sense. A quadtree is supposed to track each object and which quad they're in and then add only the objects in a specific section to the values it returns. Whenever an object moves, it's quadrant is adjusted if needed.

Aikei_c
Member #14,871
January 2013
avatar

Boost has a nice spatial partitioning module which you can adapt to your needs. It's pretty fast and doesn't even require linking, it's headers only.
http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/spatial_indexes/introduction.html
http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/spatial_indexes/rtree_quickstart.html

Mishtiff
Member #15,776
October 2014

I don't know what "objects" is in your code, but I assume it's all objects? Your code adds ALL objects repeatedly for every node that x, y is in. That's why smaller divisions gets slower, it's adding all objects multiple times. You need to rewrite the GetObjectsAt method, doesn't make any sense. A quadtree is supposed to track each object and which quad they're in and then add only the objects in a specific section to the values it returns. Whenever an object moves, it's quadrant is adjusted if needed.

objects refers to anything that is a collide-able object. As of right now, i am only adding ships to the quad-tree. Later ill make other objects collide-able.

As for the GetObjectsAt() method: I did not write any of the quadtree code. I was fortunate enough to find a post where someone had made a adaptive quadtree.
link: http://veendeta.wordpress.com/2012/10/26/algorithm-adaptive-quadtree/
It could be that i do not understand it well enough to use it correctly, but i think i have a pretty good idea. Also, in the comments at the bottom of that page, she talks about creating a function that checks an area around a unit rather than passing a point.

The current usage does work, however. as it breaks down into smaller pieces, each object is in only 1 node. so every node that is higher than the "leaf" node is empty, until it hits the leaf. I did some of the printing for it, and it is returning the correct amount of units that are in the area (unless i'm misunderstanding what you mean).

Aikei_c said:

Boost has a nice spatial partitioning module which you can adapt to your needs.

This seems great, but looking over it has me a bit confused. I'm still learning as much as i can in C++, so some of this seems out of my depth.

Trent Gamblin
Member #261
April 2000
avatar

Not so sure you were fortunate. When I look at this:

if ( !objects.empty() )
    returnedObjects.insert( returnedObjects.end(), objects.begin(), objects.end() );

You've just added every single object to the list that's returned. Then a little further down, you add every single object again, multiple times. What am I missing?

pkrcel
Member #14,001
February 2012

I can't speak for the implementation, but I GUESS that if it's not a leaf node it should not have objects in itself.

So we're basically looking at a bunch of dead code.

IIF on the other hand, the non-leaf node contains objects...

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

Trent Gamblin
Member #261
April 2000
avatar

Ok then, I'm not sure. I can't tell anymore about it without seeing the whole code, but rather than do that I would learn about profiling as pkrcel suggested.

EDIT: The fact that the class is called QuadTree to me implied the whole tree, if it's a node then "Node" would be a better name.

Mishtiff
Member #15,776
October 2014

You've just added every single object to the list that's returned.

right, i see where you are confused. Essentially this code runs through each quadtree level until it hits a level that STILL has objects in it. This may clear it up for you a bit:

#SelectExpand
1void Quadtree::AddObject( GameObject *object ) 2{ 3 if ( isLeaf ) { 4 objects.push_back( object ); 5 bool reachedMaxObjects = ( objects.size() == numObjectsToGrow ); 6 if ( reachedMaxObjects ) { 7 createLeaves(); 8 moveObjectsToLeaves(); 9 isLeaf = false; 10 } 11 return; 12 } 13 14 for ( int n = 0; n < NodeCount; ++n ) { 15 if ( nodes[n].contains( object ) ) { 16 nodes[n].AddObject( object ); 17 return; 18 } 19 } 20 21 objects.push_back( object ); 22} 23 24void Quadtree::createLeaves() 25{ 26 nodes = new Quadtree[4]; 27 nodes[NW] = Quadtree( left, (left+right)/2, top, (top+down)/2, numObjectsToGrow ); 28 nodes[NE] = Quadtree( (left+right)/2, right, top, (top+down)/2, numObjectsToGrow ); 29 nodes[SW] = Quadtree( left, (left+right)/2, (top+down)/2, down, numObjectsToGrow ); 30 nodes[SE] = Quadtree( (left+right)/2, right, (top+down)/2, down, numObjectsToGrow ); 31 32 33} 34 35void Quadtree::moveObjectsToLeaves() 36{ 37 for ( int n = 0; n < NodeCount; ++n ) { 38 for ( unsigned int m = 0; m < objects.size(); ++m ) { 39 if ( nodes[n].contains( objects[m] ) ) { 40 nodes[n].AddObject( objects[m] ); 41 objects.erase( objects.begin() + m ); 42 --m; 43 } 44 } 45 } 46}

In addObjects() we add all objects into the quad tree. if the quadrants hits the maximum units, it subdivides, creating the leaves and clearing itself of any objects in the currently level, but adding them to the next level down.

so in the getObjectsAt() function, every node that is (!isLeaf) will be empty for objects, and even though it seems that it is constantly adding objects, technically the objects in the higher level quadrants are empty.

pkrcel said:

So we're basically looking at a bunch of dead code.

Like i said before, im learning this stuff as i go, so i have no idea how to just pass over the dead code directly to the isLeaf quadrant.

Talking about getObjectsAt() again, ill go through what i think it does, and you can correct me if im wrong.

if the quadrant is a leaf, return all objects in the leaf. else, create two vectors to store data.

if(!objects.empty()) add to returnedObjects. however, this should always be empty because we move objects down the leaves and erase where they were before.

then in the for loop here, we find what node contains x,y and continue to traverse the tree until we find a leaf, and add those objects to the returned objects.

Trent Gamblin
Member #261
April 2000
avatar

Alright. What is numObjectsToGrow set at? Is that the value that when set low causes slowness? It shouldn't be really low. It'll be faster to check collisions with 10 objects than to loop through a ton of nodes. Also how many objects are there in total (so I don't have to read to find it?)

Mishtiff
Member #15,776
October 2014

no problem trent :)

i currently have numObjectsToGrow set at 20. ive tried different variances, the lower the worse it is, the higher the better (to a point... like 40). total objects currently is 200. i would like to get it to where it can run a maximum of 500. if this is not possible, i am 100% ok with just running 250-300.
But this is all end game, if i can get past this problem. as of now, im running 100-200 ships and its causing my frames to drop to around 30 (from 60)

Trent Gamblin
Member #261
April 2000
avatar

Well I don't feel like doing a full analysis of the quadtree but I don't think 500 objects is unreasonable at all, depending on system specs a little bit. FWIW in my game I don't even have a full blown quadtree, I just have a grid I put objects into. It's very simple, just divide each area into 100x100 (or whatever) grid array and check objects in [x][y] in the array. In total there are probably up to a couple thousand objects in some areas and it runs on an old netbook and even a Raspberry Pi. So this leaves me questioning the efficiency of the quadtree implementation you're using. Again, I'd have to do a full analysis of it to figure out what's slow OR profile it but since you're the one who already is set up to build the project, you could profile it. What compiler are you using? I've done profiling with GCC-based compilers but I believe it doesn't work well on Windows. I've also used the profiler from Software Verify (which is insanely expensive, but you can get a free trial) which works with GCC/MSVC built code on Windows. If you're not using Windows than GCC-based profiling is easy to set up. If you're using MSVC then Google for profiling for that, I'm sure there are free ways to do it, probably without installing anything extra. I've even heard of free profilers that work on GCC-based code for Windows so Google for that also.

pkrcel
Member #14,001
February 2012

I'm not a spatial indexing expert but there's really something I don't grasp in this quadtree implementation.

Namely, in addobject there's something like this:

void QuadTree::AddObject(GameObject* object){
   if (isLeaf) {
      //ad objs and split quadrant if reached a max obj threshold then..
   return;
   }
   //otherwise:
for (each child node){
//recursively check if node contains object add object to that node and then //in ANY other case??? *** objects.push_back(object) // should we ever end here? I surely hope not }

I agree with Trent that right now we should look into the Quadtree implementation: my impression is that there might be some unnecessary object loading into returned vectors and you end up doing definitely too many collision checks.

Or might be that you're rebuilding the tree from scratch for each object and things get exponentially heavier even for a small set of objects.

But I'm just speculating, eh. :P

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

Trent Gamblin
Member #261
April 2000
avatar

Seems that it adds those objects if they don't lie within the quadtree, and then returns them where I mentioned earlier. Check to see if that last line, objects.push_back(object) ever gets run.

Mishtiff
Member #15,776
October 2014

Well I don't feel like doing a full analysis of the quadtree but I don't think 500 objects is unreasonable at all...
...What compiler are you using?

i am currently using visual studio 2012 on windows.
Thinking of it now, i have been so focused on using this quad tree, because i thought that cleaning up my code with it would be more efficient, that i forgot that my old system actually worked much better.

what i did before was create 12 quadrants in the display area and update each ship based on what quadrant they are in. then i would test each ship for collision in their quadrant. the problem with this was that it cause a TON of extra, messy code. but it did work MUCH better. the other thing that made this hard to use was that if every single ship was in the same quadrant, i had no idea what to do to split it up (since i was just using lists, without the adaptive quadtree implemented.)
If you would like to see an example of what i am talking about let me know and ill post the previous code. It sounds like what you are talking about with the 100x100 grid, but Im not sure i fully understand what you mean by it.

pkrcel said:

I'm not a spatial indexing expert but there's really something I don't grasp in this quadtree implementation.

Looking over what you are referring to:
AddObject()
if(isLeaf) put the ship into object list in this leaf, if the max size is hit, create new leaves and move the objects to the leaves while removing them from this tier of the tree.

for(nodecount) this only runs if the last part was false
check which sub node contains the gameobjects point, then add it to that quadrant.

as for the last part:

//in ANY other case??? ***
objects.push_back(object) // should we ever end here? I surely hope not

I have no idea why this is here, and i agree... it should never get to this code. i have it commented out now in my program and it seems not to effect it at all.

Aikei_c
Member #14,871
January 2013
avatar

Last comment on the page you linked says there are mistakes in the code and provides a link to a corrected version.

Mishtiff
Member #15,776
October 2014

Yeah aikei, I did see that. I tried to implement his changes, but they caused the program to crash constantly. Essentially the change he did was cause the program to delete all sub nodes on quad.clear(). However when I tried using the code, I would get code block errors. I can redo the changes and tell you exactly what happens if you like.

pkrcel
Member #14,001
February 2012

This is intersting.

Looking at the edits Saduino put in the Quadtree implementation I can't see why you're getting errors, BUT it cleaned the AddObject code and put a needed delete[] for the sub nodes.

Also, you're rebuildng the quadtree each timer tick assuming quad points to the Root node: without that delete[] you end up with unneeded leaves in the tree (and possibily duplicate ones? CreateLeaves just uses new[] each time, is there some kind of memory leak?)

Also, why is this called "adaptive" if it just rebuilds every frame? ...nothing wrong I assume since it shouldn't cost that much rebuilding it, even thou standard memory allocation is kinda slow.

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

Mishtiff
Member #15,776
October 2014

Pkrcel- that is what I thought as well. I figured that adding the delete [] nodes would be beneficial because you are resetting the tree. The current way it is set up, it never deletes the nodes after the clear... so that means that all of the nodes that were created in the previous are just sitting around for nothing...
when I added the delete, it gave me a code block error. It's my assumption that when it runs through the clear function, it also deletes the top most nodes, which in turn cause the program to crash when it tries to add new items to the top most nodes that have just been deleted (since they are never redeclared). I think you are correct in saying that there could be a memory leak issue.

The only reason, I believe, that it is considered adaptive is because it adapts it's quadrants to the number of units. In her previous posts on her site she created another tree that doesn't change due to units in the area.I understand why youre saying you don't understand why it's considered adaptive since it's constantly clearing and rebuilding...

Aikei_c
Member #14,871
January 2013
avatar

I will show you how you can use boost RTree for your purposes. First of all, you need to start using vectors, as I showed you earlier:

#SelectExpand
1struct Vec2 2{ 3 float x,y; 4 5 Vec2(float a_x, float a_y) { x = a_x; y = a_y; } 6 7 Vec2 operator+(const Vec2 &right) const 8 { 9 Vec2 ret; 10 ret.x = x+right.x; 11 ret.y = y+right.y; 12 return ret; 13 } 14 //same for operator-, operator*, operator/ 15 Vec2 operator+(float right) const 16 { 17 Vec2 ret; 18 ret.x = ret.x + right; 19 ret.y = ret.y + right; 20 return ret; 21 } 22 //same for operator-, operator*, operator/ 23 ... 24};

Then, you need to define a rectangle class which contains its lower left and bottom right points, as well as its center and size, just in case:

#SelectExpand
1struct Rect 2{ 3 float size; 4 Vec2 center,topLeft,bottomRight; 5 6 Rect(Vec2 a_center, float a_size) 7 { 8 size = a_size; 9 SetCenter(a_center); 10 } 11 12 SetCenter(const Vec2& newCenter) 13 { 14 center = newCenter; 15 topLeft = center - size/2; 16 bottomRight = center + size/2; 17 } 18};

Now, each of your actors will store its position as a rectangle, along with other things:

class Actor
{
   Rect boundingBox;
   ...
public:
   const Rect& GetBoundingBox() const { return boundingBox; }
   const Vec2& GetPosition() const { return boundingBox.center; }
   void SetPosition(const Vec2& newPos) { boundingBox.SetCenter(newPos); }  
   ...
};

When you move your actor, you set its new position with the SetPosition() method. You could also define a MovePosition() method which will add argument vector to the center of the bounding box, instead of replacing it:

void MovePosition(const Vec2& moveBy) { boundingBox.SetCenter(boundingBox.center+moveBy); }

This is how you can move your actor:

Actor* actor;
Vec2 positionChange(2, 1);
actor->MovePosition(positionChange);

or

actor->MovePosition(Vec2(2,1));

Now you have a bounding box for each of your objects, which should dynamically change every tick. Now we need to register your new classes with boost so they could be used for boost RTree instead of internal boost classes:

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/register/point.hpp>
#include <boost/geometry/geometries/register/box.hpp>
#include <boost/geometry/index/rtree.hpp>

//first agrument is the name of your 2D vector class, second - value type used for vector coordinates by your class, and then names of variables or methods used to access x and y coordinates respectively.
BOOST_GEOMETRY_REGISTER_POINT_2D(Vec2,float,cs::cartesian,x,y);

//first argument - name of your rectangle class, then name of your point class and names of your variables or methods used to access to top left and bottom right points of the rectangle respectively
BOOST_GEOMETRY_REGISTER_BOX(Rect,Vec2,topLeft,bottomRight);

Now, let's proceed to RTree. You could create a permanent RTree and then clear() it and insert() actors as needed, however, according to the manual, packing algorithm which involves bulk loading of all objects at the same time, is much more effective, and it is used when using a specific RTree constructor, so we will probably be better off destroying and creating our RTree each tick.

So, somewhere in your code you define RTree and declare a pointer to it. I assume you will store pointers to Actors in the RTree:

namespace bgi = boost::geometry::index;

struct AreRTreeValuesEqual;
struct GetRTreeIndexable;

//8 is the number of actors per node. you could try and specify a different number.
typedef bgi::rtree<Actor*, bgi::quadratic<8>, GetRTreeIndexable, AreRTreeValuesEqual> RTree;

RTree* pRTree = NULL;

I forward declared AreRTreeValuesEqual and GetRTreeIndexable function objects just to show you that you need to at least declare them before defining RTree. GetRTreeIndexable() takes a pointer to Actor (the first argument of the bgi::rtree template specified above) and must return a const reference (`const &`) to an indexable, that is, your bounding box. AreRTreeValuesEqual() should return true if two Actor* values passed are equal or not (I'm not sure if default functors are adequate for pointer comparison, so I decided to write my own implementation just in case). Here it is:

#SelectExpand
1struct AreRTreeValuesEqual 2{ 3 bool operator()(Actor* v1, Actor* v2) const 4 { 5 return v1 == v2; 6 } 7}; 8 9struct GetRTreeIndexable 10{ 11 typedef const Rect& result_type; 12 result_type operator()(Actor* v) const 13 { 14 return v->GetBoundingBox(); 15 } 16};

Now, let's assume you have a vector of actors somewhere:

std::vector<Actor*> actors;

At the start of every tick you do this:

if (pRTree)
   delete pRTree;
pRTree = new RTree(actors.begin(),actors.end());

This will create an RTree of all your objects. Let's proceed to queries. Let's say you want to check if any actors are collided with the current one:

Actor* currentActor;
std::vector<Actor*> results;
//find all actors intersecting with the current one and insert results into the "results" vector:
pRTree->query(bgi::intersects(currentActor->GetBoundingBox()),std::back_inserter(results));

Now, theoretically, if results vector is not empty, then you have collision. However, you will probably get collisions of the actor with itself too, so you need to check if (results.size() > 1) to learn if there is any collisions or not.

EDIT:
Note that since Rect doesn't have a default constructor you will need to specify something like this in the Actor's constructor:

Actor::Actor(whatever) : boundingBox (starting position, size)
{
  ...
}

It might still be a good idea to specify default constructors for the Vec2 and Rect classes, since boost might require them to instantiate blank objects:

struct Vec2
{
   Vec2() { x =0; y = 0; }
};

struct Rect
{
   Rect() {} //maybe specify some starting parameters, but I don't think you will ever need default constructor 
};

Also, you might want to specify a SetSize() method for Rect, but note that you should also recalculate topLeft and bottomRight after changing size.

pkrcel
Member #14,001
February 2012

Ah right, calling delete on the root node would cause issues since you have to explicitly call the constructor again (or if it was static, uhm, what? :P ).

But for how I see it now, calling clear() on your item named quad should not cause issues since it calls delete[] only on the children nodes(as it should, the root node is not part of any array).

EDIT: man, I've read Akei post and now I feel dizzy ;D

EDIT2: I just notice my first paragraph didn't make sense due to bad writing.

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

Mishtiff
Member #15,776
October 2014

pkrcel said:

But for how I see it now, calling clear() on your item named quad should not cause issues since it calls delete[] only on the children nodes(as it should, the root node is not part of any array).

the code does not crash until after 20 units overall have spawned. I have found that the crash happens after the quadrant runs the clear method. this is directly after the split, so im not sure how to go about solving the problem. NOTE: the tree is set to split at 20 units. so it has to do something with this. I am getting a memory read error at this point, but up until then, i do not receive the error. This must mean that it is during the deletion of the nodes?

Aikei_c said:

I will show you how you can use boost RTree for your purposes.

Wow what a post. I have a ton of appreciation for everything there. Ill deffinately look into using it now. I am positive that I will have several problems still, but this is a huge start. Again, thank you for taking the time to do that!

Question: I am currently using lists as my object holders. Does it matter between that and a vector?

UPDATE: Aikei, it seems ive already messed up boost. during installation somewhere. now im getting a constant error: /Microsoft was unexpected at this time. Ill try to figure it out in the mean time unless you have heard of this.

Aikei_c
Member #14,871
January 2013
avatar

Mishtiff said:

Question: I am currently using lists as my object holders. Does it matter between that and a vector?

No. Lists are fine too.

Quote:

UPDATE: Aikei, it seems ive already messed up boost. during installation somewhere. now im getting a constant error: /Microsoft was unexpected at this time. Ill try to figure it out in the mean time unless you have heard of this.

No idea what this could mean. Maybe your boost is installed into a directory which has parentheses in its name (like Program Files (x86)) and you have this path specified somewhere in visual studio? Because visual studio is notorious for having problems with parentheses.
Note that you don't need to link any boost binaries for this, you only need headers.
EDIT: Note by the way, that my rectangles are actually squares, you might want to use width and height instead of a single size parameter, since you probably need actual rectangles, not squares.

pkrcel
Member #14,001
February 2012

Mishtiff said:

the code does not crash until after 20 units overall have spawned. I have found that the crash happens after the quadrant runs the clear method. this is directly after the split, so im not sure how to go about solving the problem. NOTE: the tree is set to split at 20 units. so it has to do something with this. I am getting a memory read error at this point, but up until then, i do not receive the error. This must mean that it is during the deletion of the nodes?

Can't check right now, but this sounds as the qudrant is deleted and THEN the vanished nodes are trying to be accessed (and will likely cause a segfault).

Check if the code clears the nodes array too soon or if you try to access the nodes right after deletition.

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

Mishtiff
Member #15,776
October 2014

pkrcel said:

Check if the code clears the nodes array too soon or if you try to access the nodes right after deletition.

I feel pretty good about this, all i had to do was sleep on it and i have the answer i believe.

During the deletion, it never sets the topmost of the tree to isLeaf = true; thus, when it returns to the AddObjects during the update loop, it skips over the first part of the addobject and goes to the sub nodes, which were just deleted since we are starting over again! here ill post the code again:

#SelectExpand
1void Quadtree::AddObject( GameObject *object ) 2{ 3 if ( isLeaf ) { 4 objects.push_back( object ); 5 bool reachedMaxObjects = ( objects.size() == numObjectsToGrow ); 6 if ( reachedMaxObjects ) { 7 createLeaves(); 8 moveObjectsToLeaves(); 9 isLeaf = false; //This is where the topmost is set to false and never returned during the clear portion. 10 } 11 return; 12 } 13 14 for ( int n = 0; n < NodeCount; ++n ) { 15 if ( nodes[n].contains( object ) ) { 16 nodes[n].AddObject( object ); 17 return; 18 } 19 } 20 21 //objects.push_back( object ); 22} 23 24void Quadtree::Clear() 25{ 26 objects.clear(); 27 28 if ( !isLeaf ) { 29 for ( int n = 0; n < NodeCount; ++n ) { 30 nodes[n].Clear(); 31 } 32 } 33 delete [] nodes; 34}

Initially, when the tree is made, the topmost for isLeaf = true; however, it breaks down upon hitting the max number of units and changes to false, and never gets reset to true. now i have to figure out how to set it back to true... I may need to make a new function that is something like:

void resetLeaf() {isLeaf = true;}

Update:: This did fix the problem! however, frames still drop to ~20. So still having issues, but it did fix the clear function!

Aikei_c said:

aybe your boost is installed into a directory which has parentheses in its name (like Program Files (x86)) and you have this path specified somewhere in visual studio?

well there is a video i was watching about installing it, and it said i need to run the .\b2 install portion, but i never ran it. so now i am just lost. I tried searching my comp for anything that had boost in it, and i cannot find it anywhere.

I think i will just try to call the headers in VS12 and see if they work. If not, i honestly do not know how to fix what i did.

pkrcel
Member #14,001
February 2012

Mishtiff said:

During the deletion, it never sets the topmost of the tree to isLeaf = true; thus, when it returns to the AddObjects during the update loop, it skips over the first part of the addobject and goes to the sub nodes, which were just deleted since we are starting over again!

Right! Haven't looked at this gotcha....the improved clear() method should reset the Leaf status upon deleting the nodes[] array.

void Quadtree::Clear() {
   objects.clear();
   if ( !isLeaf ) {
      for ( int n = 0; n < NodeCount; ++n ) {
         nodes[n].Clear();
      }
   }
   delete [] nodes;
   isLeaf = true; *** 
}

Even thou, seems performances drop anyway...we'll have to look elsewhere.

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén



Go to: