Quadtree progress

The Partridge Family were neither partridges nor a family. Discuss.
albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Quadtree progress

Post by albinopapa » August 24th, 2020, 7:52 am

I don't see the leak you're talking about. m_pChunks is an std::vector so std:move should take care of anything
std::vector<char*> memory_a;
memory_a.push_back( new char[ 100 ] );
std::vector<char*> memory_b;
memory_a = std::move( memory_b );

So, you don't see a leak here? The char pointers will be moved over, but the memory being pointed to by each element in memory_a ( memory_a[0] for instance ) won't be freed.

You'd have to delete each element before you move memory_b onto memory_a to avoid leaks.

For instance, if they were
std::vector<std::unique_ptr<char[]>> uptr_mem_a;
uptr_mem_a.push_back( std::make_unique<char[]>( 100 ) );
std::vector<std::unique_ptr<char[]>> uptr_mem_b;
uptr_mem_a = std::move( uptr_mem_b );

Because each unique_ptr has a destructor that delete's each element, no leaks happen.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Slidy
Posts: 80
Joined: September 9th, 2017, 1:19 pm

Re: Quadtree progress

Post by Slidy » August 24th, 2020, 12:04 pm

Ah I see what you mean, you are right. I'll fix that later, although I don't think I'm using the move assignment on a pre-existing allocator anywhere so not too pressing an issue.

Thanks.

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Quadtree progress

Post by albinopapa » August 24th, 2020, 5:00 pm

You might check the other "allocator" classes as well, I think you might be doing the same on them as well, but I don't recall right now.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Quadtree progress

Post by albinopapa » August 25th, 2020, 1:52 pm

Okay, so I've thought about it and I've made a decision. As stated before, I would have liked to be able to iterate through all the objects using a single iterator, but the more I think about it a quadtree isn't necessarily like other containers like the STL containers. Even std::map which uses a binary tree usually only holds a single object per node and if each node did hold a vector of objects, you'd need to iterate through each vector separately. Since a quadtree will certainly have a vector of objects for each node even if that vector only have one object in it, I've decided that it only makes sense for the iterators to iterate over the only over the nodes. The user will have to iterate over the objects in each node themselves.

The node interface will have access to it's boundary as well as const/non-const access to the vector of objects. This should also make removing and adding during a loop a lot easier since object traversal and node traversal will be separate. In other words, removing an object won't affect any of the node iterators.

I've known for quite some time that this was an option, but have been trying to avoid it. Not for technical reason, I really felt that a single iterator would suffice. After 2+ weeks, I have given up on that thought as it doesn't make much sense with how the structure is laid out and then because of the technical difficulties trying to constantly making sure the values stored in the iterators were valid.

This should keep things efficient as well with fewer checks for invalid values in the iterator and fewer data members to copy over and keep track of.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Quadtree progress

Post by albinopapa » August 26th, 2020, 3:15 am

Well, I think I've gotten the tree as efficient as I personally can make it.

Turns out, one of the most inefficient things I did before was in the qtree::query() function. Before I was collecting a vector of pointers to all the objects and returning that back to the user. At best with 10,000 balls, I would get around 40-50 fps. Instead, I decided to allow passing a functor which seems to be quite a bit better. With the same 10,000 objects, and turning off vsync, it varies widely. The min is around 90 and the max is around 120 fps.

Take it for a test run.

I haven't stressed tested it so different values may not yield similar results
I don't have constraints for template parameters, so there are chances for breakage.
I don't have a minimum size for nodes, so if you make your objects really small and/or create a lot more than 10,000 objects it's possible to trigger a stack overflow because of recursion, but it would take a lot.

Something I haven't tried is a mix of static and dynamic objects. I guess is performance wouldn't change much. What I think I'll try as an experiment is two quadtrees, one for static objects that won't need re-sorted and one for dynamic objects for ones that will.

EDIT: Just checked and current implementation is probably close to 2x faster. Was able to get ~45 fps with and without vsync enabled with about 20,000 balls. By my count, if you were to do nested for loops for all 20,000 balls you'd end up somewhere around 200,010,000 collision checks. Using the tree, if I'm counting correctly, average about 7,000,000 collision checks.
Attachments
quadtree sample.zip
(362.14 KiB) Downloaded 199 times
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Quadtree progress

Post by albinopapa » August 26th, 2020, 4:03 am

Okay, don't use std::unique_ptr as the tree's data type. Went from 35 fps to 15 fps with the same 20,000 balls. The reason 35 instead of 45 is probably because now I'm counting the collisions and writing them out in the title bar of the window. Seems to still be best to create actual objects:

qtree<100, chili_rect_traits, chili_vec2_traits, Ball>
and not
qtree<100, chili_rect_traits, chili_vec2_traits, std::unique_ptr<Ball>>

That being said, if you use traditional polymorphism you're kind of out of luck on this one. May I suggest trying std::variant? LOL
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Quadtree progress

Post by albinopapa » August 26th, 2020, 4:16 am

Added github link to first post in this thread. It's linked to the "value_vector_nodes" branch, which is the more optimized version.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Post Reply