Currently I am updating mouse positions whenever the mouse is moved:

//prev ev.type code

else if(ev.type == ALLEGRO_EVENT_MOUSE_AXES)
{
mousex = ev.mouse.x;
mousey = ev.mouse.y;
}

however this completely shuts off:

if(render && al_is_event_queue_empty(event_queue))

whenever the mouse moves for a period of time. Is there a more efficient way of capturing the mouse location? The only time i need to save its location would be on right mouse click or a key press.

UPDATE: I did find that if I use mouse_event_button_down it will save the data, but using the keyboard to save the data does not seem to work.

If you need to value the mouse position against a specific coordinate (i.e. to check if it's on some GUI element) this is basically overkill.

 if(render && al_is_event_queue_empty(event_queue))

Well, that completely puts me a bit off...I guess you get a lot of stutter, but not a complete rendering stop.

What does "using the keyboard to save the data" mean exactly?

Agreed, that is why i present the question. I suppose my problem is that I am unaware how i can save the mouse position when an event is calling for it outside of a ev.type == mouse_event

Yeah at the moment my coding needs some tweaking for efficiency. So if i constantly move the mouse in the display, the display never updates (since it is constantly updating the mouse_pos every single pixel.

example:

AH now I got it....uhm I guess it wouldn't work by design, since the trapped event is NOT related to the mouse, so (on windows, I suppose...but logically on every system oculd be like that) the trapped OS event message should not contain this info.

This is my speculation of course, but I'm quite confident that you aren't expected to use the event mouse fields when trapping a keystroke.... I may stand corrected of course.

On the other hand why would you do so? just curious...I might imagine but still...

Anyway at any time you should be able to interrogate the mouse through the input API....lesseee.... I guess al_get_mouse_state should do for you.

I suppose you example could read as

if(ev.type == ALLEGRO_EVENT_KEY_DOWN){ 
   switch(ev.keyboard.keycode){
      case ALLEGRO_KEY_SPACE: 
      [SPACE] = true;            // I kind of like this syntax ^___^
      ALLEGRO_MOUSE_STATE state;
      al_get_mouse_state(&state)
      mousex = state.x; 
      mousey = state.y; 
      break; 
      }
   }

Can you show more code? A typical mouse shouldn't produce more events than say 1000 per second - I can't see how that would affect your rendering in any way even on the slowest and most ancient CPU.

1A. currently in the game i'm making, you move your ships to mouse_pos with the space bar(which i have now changed to the right click on mouse, making it much more simple...)
However, saving the mouse position every pixel movement was causing too many event calls and would shut down my rendering because of all the mouse updates. NOTE: I have a system set up in my game for collisions and moment which is VERY inefficient, and is more than likely causing the mouse update to be worse that it should be.
I am still trying to figure out how in the heck KD-Trees work. they are pretty confusing to me at the moment. So what i have done in my game is:
split the screen into 12 quadrants, and save each ship into its quadrant list. when the collision decisions come, all ships are tested with ships in the same quadrant instead of every ship in the game.

2A. this seems to be exactly what i am looking for. However, by the way you are talking it sounds like this is a bad way to go about it?

of course. Ill post my code here soon. its pretty messy so let me clean it up and get some better comments into it.

Store the mouse pos in the mouse events, then only move the ships when space is pressed. could have a next_shipx, next_shipy pair, and then only set the ship's coords after space is pressed?

Mouse events alone won't case that to happen. Just store the mouse coords on mouse update. then once a "tick" (ie: timer tick) run your collision detection, not when ever the mouse is moved.

This. Absolutely this.

I didn't understand fully what was the problem here, and I didn't think it could be related to your other thread about Collision detection.

But if you are running collision detection at each mouse axis event, THEN you're surely wasting a TON of CPU cycles (*even* if the collision detection is perfectly optimized).

Why wasted? Because no object has yet moved when you process the events.

On the other hand:

Well, polling the state API while handling events is sort of double-defeating the purpose of both....BUT in this simple case it should work flawlessly so it might be good enuff.

Nevertheless, Tomasu suggestion is the way to go in my opinion, store the mouse coords and use'em as a "next frame prediction".

At the very heart of the problem, what you have done is the SEED of space partitioning.
Trees are an efficient data structure to store this partition, because there are very efficient algorithms in which you can traverse them.

I woudl say good job, nevertheless.

this was my coding for the mouse update, so i dont see a reason for the slowdown to occur, yet it did:

I already run my collision detection only in the timer tick. I will just attach my code here and see if you guys can find what exactly is causing such dramatic slow downs.

yeah, but as i have stated above, it was not in the same block of code.

ok i understand, and it is beginning to sound like it is due to my coding that is more of the problem, rather than the updating and saving of the mouse coords.

Thank you, i was pretty happy with how my old collision detection worked. i have, however, found an amazing post with a

....a cliffhanger?

I wouldn't use that code. Use:

while (!al_event_queue_is_empty()) {
    // process events
}

if (render) {
    // render
}

Otherwise you could skip a frame sometimes, even if it's just 1 it's not right.

I guess it cut out the rest of what i wrote... What i had said was:

Thank you, i was pretty happy with how my old collision detection worked. i have, however, found an amazing post with a adaptive quadtree. I think i have implemented it well, im just unsure if i am using it efficiently. Ill let you be the judge.

Where am i supposed to put this? in the timer tick? that doesnt make sense to me, sorry.

No put it around your event processing loop.

do {
   if (ev.type == ALLEGRO_EVENT_*_*) {/*...do stuff...*/}
} while (!al_is_event_queue_empty(queue));

if (render) {draw();render = false;}

Okay i have put it around all of my event queues, but it is not drawing any frames now. probably because by the time it makes it through all of the events in timer.tick, it already has a timer.tick in the queue? heres what it looks like:

EDIT::

This corrected the problem. Going to see how it runs now if i add more units.

The al_wait_for_event should be in the do-while loop too, otherwise if there are any events in the queue that loop will never end because they never get removed.

After changing the code to what we have discussed, it freezes at loading ~9-10 units. I checked to see the amount of time it takes for the code to run through the timer.tick part, and it takes around ~.005. im running the game at 60 fps, which means the timer should be every .0166. not sure what is going on to make it stop rendering. ill try to add some std::cout to see why it is not reaching the render state.

EDIT:: after checking, it seems that the game gets stuck with the al_is_event_queue_empty(). After 9 to 10 units have been spawned per base (90-100 ships) the game stays in the do while loop

Ok, what you want to do is use al_get_next_event instead of al_wait_for_event. Something like I had posted before:

while (!al_event_queue_is_empty(queue)) {
    ALLEGRO_EVENT event;
    al_get_next_event(queue, &event);
    // process your events
}

Change your do-while loop to this while loop.

This makes a lot of sense, thank you. Ill mess around some more now that it is running correctly and update on anything further

If you call that function instead, you'll have to make sure to check that there is actually a new event because al_get_next_event always returns right away, even if there is no new event. Ie:

if(!al_get_next_event(&event)) continue;

Otherwise you'll be attempting to handle invalid data (the first time) and old events (any time after the first event).

Or even make that loop:

ALLEGRO_EVENT event;
while(al_get_next_event(&event)) { ... }

Personally, I prefer the layout of the loop I used in the tutorials on the wiki. Keeps from having nested loops. But its just a personal preference.

May i have a link to this? Sorry i'm unsure where to look for this (other than on wiki, not sure what to search for exactly). Ill probably go with a layout that does not require a nested loop.

The way it is currently set up doesnt seem to work anyways, since my game will not update unless i move the mouse... interesting. Hard to understand why that is occurring. the timer loop is running and everything, but until i move the mouse, it wont render, and as long as i move the mouse it will, unless i stop moving.

Try this code.

Thank you for the link, i could not seem to locate it (i did find the camera tut that added a new depth for me to try )

Is the program I am trying to create just too much for A5 to handle, or am I just writing awful code? Having frame rate issues still, which is disappointing considering how little i am actually trying to do.

It's probably your code, or your hardware.

Allegro5 is production-grade software (go look at factorio game for a very good indication), so basically we have to find the culprit in your code (which not necessarily has to be that awful ).

I am also under the impression that we are circling around the problem in framerate but are looking at the input handling, which honestly SHOULDN'T be the issue-dealer.

The thing that tends to cause framerate issues the most with A5 projects is loading bitmaps before you create the display. That creates memory bitmaps which are much slower to draw than display bitmaps.

Thomas, it already did check if there were events... you're just confusing. al_event_queue_is_empty already checks in the code I gave him. That is the best form of the loop, despite what your preference is, in actual games.

1A. Thank you, that is reassuring. It is obviously my coding that is the culprit (not that i wasn't already expecting that).
2A.Well tell me where to start looking and ill start working on fixing up some code. In all honestly, as of now in the game, all I am asking the game to do is:
1.check user input.
2. on timer tick: update render to true, spawn ships if shipspawner == 60, update all objects and add to quadrant system, check collisions, and destroy dead ships
3. Render if true, outside of timer.tick
seems basic enough to me. I am also not using any bitmaps what-so-ever. I'm only drawing primitives. All they consist of is al_draw_circles for every ship and even the bases.

1A. My hardware is strong enough to run most games on high-ultra. Of course most are obviously coded more efficiently than my own But again, i dont see how i can barely run what i am wanting my code to do, since i feel like its so little.
2A. Understood for future notice. If you read above you'll see I use nothing for bitmaps currently.

If this is true i would have no problem using it, but:
It is weird, after I implemented the code to the nested style you had, my game would not render unless I moved my mouse. It is still doing it after i have reverted to the while(!done) only. Not sure how to fix it, still looking into it.

It would only render if you're moving the mouse if you're using al_wait_for_event but it WAITS in that call until it gets an event.

Thank you, even though it clearly says that in the function call, for whatever reaso i wasnt aware that it sits there until something happens. I figured it skipped over it until it had something in the queue.
Also, i see why your while loop makes more sense for a game loop

al_wait_for_event - if there is an event ready, grabs it, otherwise waits

al_get_next_event - if there is an event ready, grabs it and returns true, otherwise returns false without ever waiting

What I was saying about not having to check if there is an event returned from al_get_next_event, is because you already know there is an event in the queue because you called al_is_event_queue_empty.

I honestly don't. They should be functionally identical. My loop just acts as both loops at once.

Feel free to explain it to me.

Your loop does needless processing. Not much but it's not perfect like mine.

Ok, maybe... But I still don't see how it does more than yours. Both check the events, and the queue for more events. Maybe it executes the if(draw) more often, but its almost always 0, so the cpu will predict that out of the pipeline before it becomes a problem.

I am trying to understand both as well now. let me explain what i understand for both.

Trents:

For this version, all i see it doing is running through the while(!done) loop constantly until the event queue has something in it. obviously the render portion will be false until the timer.tick has ran, so it does seem running code this way is unnecessary?

Thomas's:

For Thomas's, it simply waits to run any code until it is given input, then runs the code. if the code was a timer.tick, it will automatically pass over the if(render) statement.

However... In Trents version, i understand that it will do any events in the queue until the queue is empty, then it will run into the render. after that it will circle around and hit the event loop, circle through all saved events, then continue again to the render.

The thing about Trents is that as long as queue events are being added to the queue, will it ever return to the render portion? i do understand that the computer can do most of the processes in the ev.types extremely fast so it may not matter.

you two can tell me if i have the right idea or not on each...

The thing that i still am having an issue with is:

For whatever reason, after i hit about 4-5 units spawned, it will only render if I move the mouse. the game is still constantly running the timer.tick portion (checked with std::couts), but does not render until i have moved the mouse. strange? the render portion of my code is outside of the while(!al_is_event_queue_empty) from trents code.

Hm, that first loop will sit and spin at 100% even when there's nothing to do.

Otherwise they are functionally equivalent. Both will handle events as they come in.

In the bottom loop, it checks for an empty queue to make sure all events are handled, including piled up timer events, before drawing. It's so we always drain the queue, and we get free "Frame dropping" out of the deal, in case the logic and drawing take longer than your timer period, it'll skip frames to catch up. The top loop is similar in that respect, it drains the queue before drawing anything, but it uses an explicit inner loop, instead of making the one loop dual purpose (it drains the events, and handles logic+drawing, where as the inner loop does the event draining and logic, and the outer loop does the drawing).

I actually looked at my code and I guess I do use the second loop most of the time.

What I actually have though is more like:

while (true) {
top:
  ALLEGRO_EVENT event;
  al_wait_for_event(queue, &event);
  // process event
  if (!al_event_queue_is_empty(queue)) {
    goto top;
  }
  if (render) {
    // draw
  }
}

You can replace the goto with a do-while loop very easily:

while (true) {
  do {
    ALLEGRO_EVENT event;
    al_wait_for_event(queue, &event);
    // process event
  } while (!al_event_queue_is_empty(queue));
  if (render) {
    // draw
  }
}

I think I like that last one the best out of all of them. Just remember to add a timer event source for 1/60 of a second so that the loop keeps pumping even without input.

Aside from the two commented lines, that's what I posted earlier. :/

do {
   ALLEGRO_EVENT ev;// implicit
   al_wait_for_event(queue , &ev);// implicit
   if (ev.type == ALLEGRO_EVENT_*_*) {/*...do stuff...*/}
} while (!al_is_event_queue_empty(queue));

if (render) {draw();render = false;}

You were right.

Thanks for the update. Still having the problem of it not rendering until mouse movement... not sure what to do about it. Occurs after about 10 seconds, only renders if i am moving the mouse constantly, else it never renders, but the game loop is still running. IE: the units are spawning, moving, etc. but the render function never goes until i move the mouse.

The best way to do that is...

I see in your last code post you're doing rendering where you set render = true. You should put it all after where you have if (render). If that doesn't work, show your loop as it is now.

Currently my render is outside of the loop after it. I did try to put it before the loop, and still had problems. Here is what my code looks like:

this is my entire while(game running) code. Still having problems with it not doing the render portion after so many units have been spawned. This occurs even if i put the if(render) before the event loop. Any ideas would be excellent. If there is literally anything you see that is inefficient, yell at me. I want criticism to become a more efficient programmer.

Honestly, I still don't understand how the loop with al_wait_for_event() works. I mean, shouldn't it just halt and do nothing on the al_wait_for_event() line, unless it gets some input?
I know I'm probably wrong, but I still don't know why. I tried to read this thread several times, but still can't quite understand it.

EDIT: Oh well, nevermind, I see he catches a timer event.

EDIT2: Mishtiff, do you create register your timer with the event queue properly? You probably do, or your game code would not ever be executed at all.

EDIT3: Ok, look at what you are doing. You are running all your game code, including collision detection etc. WHILE EVENT QUEUE IS NOT EMPTY. But since your game code can take quite some time, you can receive a new event while running through this loop, so you will have to repeat it again... and again... never reaching your render code.

al_wait_for_event() sits in this loop until an event is recieved. after its recieved, it removes the event and places it into the ALLEGRO_EVENT ev, that will be executed from that point on. After it reaches the end of the loop, if no new events were placed into the queue, it should break out of the loop and hit the render.

As for Edit3: I see your point, but does that mean that i should be placing these things outside of the timer loop the same as the render function?

IE:

do{
//process events
}while(!al_is_event_queue_empty());

//process collision detection if true

//process render if true

You can do it like this.
Or, you could make up something else. For example, here is the loop I currently use. Names of functions and variables should be self-explanatory.
All your game code is in logic update, input updates are handled in ProcessAppMessages, and rendering is done by the renderer.
And Rest() just calls al_rest().

EDIT: Your loop however should work just fine . You can process all your game code if render is true, right before rendering everything.

Thanks for the help Aikei_c, my game now updates and renders, but it slows down to about ~20-30 frames when it is supposed to be running at 60 fps. I need to figure out how to run the collision detection in a more efficient way. When i remove the collision detection everything runs fine, but once it is back in, it lags it pretty hard.

Oddly enough, when i increase the amount of units that can be tested for each quadrant (before splitting into new leafs) the game runs better. If i continue to break the quadrant up at lower numbers (such as, only allowing ~3-10 units per quadrant before splitting) it runs at awful frames. I need to find a good source code that uses this type of collision detection to see how to run it in a more efficient way.

When i read about quadtree collision detection, it seemed that most people agreed that it was the way to go in regards to efficiency. Weird that i am having such awful lag due to it (considering that its the only code that could possibly tax the program).

I'd suggest you dive in to profiling your code because seems you can't "debug" the issue further just sectioning the code.

@prkcel As in, Seperating code into different .cpp and .h files? Such as a game.cpp, player.cpp etc?

Sorry, since this thread is getting long can you post your collision detection again? Maybe we can see where the bottleneck is.

EDIT: Mainly the GetObjectsAt and CheckCollisions methods.

I meant profiling as in using a tool (such as the Visual Studio Debugger suite) that might help in identifying where in code you have bottlenecks.

You already know that the collision detection drowns performance, but you don't know which BIT of it.

I'm afraid I can't be of much help here, I haven't profiled code since my old time on TRACE32.

On the other hand, structuring your code better would help a lot in sharing & understanding for people which might look upon your code....first of all yourself.

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.

This is because quadtree also takes time to build every tick. If you specify too low number of units per quadrant, it will have to build more quadrants and will take more time. Depending on your number of actors, some quad trees may actually slow down performance instead of improving it.
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. You could even make two quad trees: one for active objects which gets cleared every tick, and the other for static ones.

Hope this gives some insight.

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.

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.

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.

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

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

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.

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?

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

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.

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:

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.

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.

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?)

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)

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.

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.

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.

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.

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.

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

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.

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.

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

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:

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:

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:

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.

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

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

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

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?

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.

No. Lists are fine too.

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.

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.

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:

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!

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.

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.

I honestly have no idea where to look now. i guess i could try to see how long it takes for the tree to collect all of the units that are in a node? I feel as though it should be faster than it is... But i am pretty new to a lot of this stuff, so im just happy about where I am now i suppose.

my problem with the Boost addition:

My path file is messed up with the microsoft directx SDK path. here is a link to what the problem is:
http://weblogs.sqlteam.com/mladenp/archive/2008/05/28/Serious-Visual-Studio-2008-install-bug-that-can-break-your.aspx

I have the exact same problem, but i cannot figure out how to get the "" out of the path file. i have tried what he suggested but it didnt work. Im not sure how to edit the path file outside of the .bat file though.

You can edit path this way (under windows 7 at least):
1) windows logo -> right click on Computer -> Properties -> Advanced system settings -> Environment variables... -> now find Path -> Click Edit

thank you Aikei, i had no idea where that was. Its all running now!

Well, your code should be profiled as me and Trent suggested, or maybe you can try first to switch to Boost implementation of the r-tree instead of this adaptive quadtree, which should be at least efficinet and robust (the Boost introduction gives times to build the tree and to query the index that shoould very well be under your timing constraints), since usually Boost is.

I too think you're hitting the ceiling too fast.

For example how do you handle gfx? are those primitives or bitmap? In the latter case is bitmap drawing held?

Maybe you could setup a git repository for us to look at? I guess your actual code coudl be shared...

I plan on implementing this now, with much thanks to Aikei for all the help on getting it started. already in the works!

Everything is primitives. so, during drawing this is literally it:

Bases:
al_draw_circle(x, y, 50, HomeBase::GetColor(), 2);
al_draw_textf(font18, HomeBase::GetColor(), x, y-75, 0, "P%i: %i", GetPlayerID(), GetScore());

Ships:
al_draw_circle(x, y, boundX, BaseColor, 1);

the program has to render around 200-400, but i dont see that being a problem if they are just primitives...

of course, would gitHub be a good place to store it?

Which reminds me that GitHub has been banned today in Russia for "suicide propaganda", and I'm not joking. .

thats crazy Aikei!

Im getting around 25 errors now that i have everything implemented. Granted, I may not have everything correct, since i have been up for about and hour or two messing and recoding.

Ill put my stuff up on gitHub once i wake up. No idea whats going on or if i have things in the right place.

What is the first error you have? It is usually the one which causes everything to crash.
Better go with bitbucket, I won't need to configure tor for that, .

ok sounds good ill post there instead.

well i closed the program for a little while, and now its running fine... odd? all of the boost errors went away. game runs fine, but the pRTree is not working correctly im sure, since its saying that there are all objects returned as colliding.

I have set the bounding box, not sure why it is returning all as colliding.

EDIT: it does seem to have a problem with: BOOST_GEOMETRY_REGISTER_POINT_2D(Vec2,float,cs::cartesian,x,y);

saying: Name followed by '::' must be a class or namespace name.

something to do with cartesian

Do you include <boost\geometry\geometry.hpp> (or just boost\geometry) ?

EDIT: If it compiles, though, you should be fine. Visual studio is sometimes wring with its on-the run error detection. Show your code.
EDIT2: Make sure your bounding boxes really don't collide. If all objexts are shown as colliding that's because their bounding boxes are. Check values of topLeft and bottom right corners, even draw them, and make sure they do not collide. This might happen if all of your bounding boxes initialize to zero position or something like that.

There was some debate about that actually. I'd like to see if going the bitmap route may make any difference.

IIRC you come from Mike Geig's tutorial, try to draw your circle into a bitmap (one for base, one for ship) like Mike does for the spaceship at program setup, an then use THAT bitmaps instead of drawing primitives.

Might also use al_hold_bitmap_drawing() when there.

Of course you should solve the Boost rtree implementation before.

And bitbucket is as good as anything else for this matter I guess.

I have my files up on bitbucket. not sure how to link them, but heres a shot:

https://mishtiff@bitbucket.org/mishtiff/basegame.git

bullet is currently unused, but may be used in the future. i cant figure out how to remove Arial, all it is is the font used.

Try and find the public git address, not your personal read/write address

Ill be honest im not sure how to find it. I assumed that was the one, since i could get to it without being logged in

might be as simple as bitbucket.org/mishtiff

I'll have a look.

I haven't looked at it closely, by judging from this line:

al_draw_rectangle(bb.center.x - bb.topLeft.x, bb.center.y - bb.topLeft.y, bb.center.x - bb.bottomRight.x, bb.center.y - bb.bottomRight.y, BaseColor, 1);

You think that topLeft and bottomRight values are relative to the center. They shouldn't be. They should be absolute positions. If all of your bounding boxes are, like, (-15,-15) to (15,15) there is no wonder they all collide...

Also, there is a mess in the Object class. You only need bounding box, that is all. You don't need any additional x, y, boundx, boundy, all this should be represented by your bounding box...

Yeah this seems to be the correct link i hope!

https://bitbucket.org/mishtiff/basegame/src

sorry if not.

Aikei, I was just following your big post earlier i did do some profiling and found that all of my blocks were returning a -1.5 and 1.5 for their topLeft and Bottom right. I assumed it was a mistake i just havent fixed it in my coding yet.

I wasnt aware until then that i needed to save the topLeft and bottomRight Vec2's as their actual position, and not just the bounding position.

I however told you that and even provided a method to move your actor:

Which means, each time you change position of your object, due to its movement or anything, you use SetPosition(). No x = x+velx and that kind of shit! You only use SetPosition() method to set position, nothing else. And you don't need those boundx, boundy, x, y, etc. You already have your position.

Just for the record, but how do you resolve collision?

I see you get the result vector back but you don't seem to do anything with it apart from checking if it's size is bigger that 1.

Anyway I can't seem to find a reasonable reason (ah!), or at least a not subtle one for a slowdown to happen. (apart from batching draw calls into a single al_draw_prim call of course...but that's not the point here I guess)

I'll have to compile it myself, but I am unable right now....

EDIT: ah btw Aikei is right, your code needs further cleanup...at least for clarity, with this disorder one can't rule out some camouflaged gotcha in the code

@aikei yeah you did, I just have been so busy I haven't been able to spams the time needed to clean up my code. I do plan on talking away the unused x, y, bx, by. Sorry, I just wanted to get my code up so you could see where I am at now.
@pkrcel I thought that by running the check through boost (where I send it the actors location and bounds) that it would return whatever classes with said object.

I will program as much as I can tomorrow before work and post an update!

I think what your code could use is a few more functions. You need to separate out functionality and purpose into smaller units that you can then combine. For example, Collision(), Cull(), CheckScore(), things like that.

@Edgar of course, I just need to start working towards it. I just need to sit down and take the time to figure out how to pass the information around. But splitting my code up so that my game loop isn't a wall of text would be spectacular. As I said just before this, I'm trying to clean my code up, it's just hard to accomplish without messing something else up, or paying the right information. Something I'm learning to do

It sure does, but as long as I am not missing something obvious you aren't doing anything to the collided objects, am I wrong?

Yeah that is correct, I was only checking to see if I had implemented the tree correctly by seeing how many objects were returning as collided

UPDATE: I have fixed a bunch of code! Everything is running as intended. I did have to switch a couple lines, but we can talk about it once i get the code uploaded to gitbucket. Im still having some framerate drop, but its only 10-20 frames at most, so not too bad. It was handling 500 units at about 40 frames. So we just need to see if my collision detection code is too heavy.

Still working on cleaning up my code, so i will not be updating it for at least another day or two.

In the mean time, what are the commands to update my remote files with my local ones? I cant seem to find a solid answer (or at least, one that worked when i tried it). Thanks guys!

If your objects are rectangles, you probably don't need any other specific collision detection code, apart from the RTree. Also, make your Rects actual retangles, with width and height parameters instead of just size which makes them squares.
or, at the very least, you would run any additional specific collision detection code only for objects returned by RTree in order to calculate the so-called "collision normal", that is, the direction you need to push two objects to get rid of collision.

Commit, then push. Depending on the client you use, you probably need to select files first when commiting.

@Aikei Sounds good. I think i was confused on what boost does, now i understand that boost does insertion, a tree and checks for collision. i thought it only did the first two so i also added this to it:

This is the version i was using, which wouldnt make sense if the query is returning all actors that intersect each other... .

new code, tell me if that works. Also, i will fix the code for Collided. instead of random movements it will just push in the opposite direction.

This should work, however you are making an assumption here that the object itself you are checking collision with will always be the first to be returned, which I don't think boost guarantees, since the manual doesn't specify any order in which results are returned.
So you should check something like if (*iter)->GetId() != results[i]->GetID()
(If I understand correctly and this is the unique ID of the current instance of class. If not, you probably could also just check pointers for equality, like results[i] != *iter.)

@Aikei good point, will implement it now. Ill update this post in a couple hours with the progress

Update: Im not sure what happened, but i hit a critical error. I closed my program to spend some time with the family today, and got an error, so i had to copy and paste the entire program over again. Something about running git. It somehow moved files or something when i went to push them.

Happened on my desktop as well (on accident). all of my folders are gone that i had created...

Anyways, all is well and ill update soon.