Quadtree progress

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

Quadtree progress

Post by albinopapa » August 11th, 2020, 7:07 pm

Quadtree-value_vector_nodes branch
I'm getting pretty close to completing my templated quatree, but there is a bit of a performance issue.

My current implementation would work quite well if everything in the tree were static ( non-moving ), but currently I only have it setup to be rebuilt from scratch if you move anything.

My current tests are adding 20,000 elements to the tree. I have it broken down into two steps and I'll explain why in a second. Here's the current results:
Adding elements: 2ms
Committing elements: 1,215ms
Retrieving elements contained by a rectangle ( 5527 elements ): .04 ms ( 4.19e5 seconds )
Nested for loops checking for redundant retrieval: 12ms

Add elements would most likely be done in a Scene or World constructor, so wouldn't have an effect on framerate. Committing nothing but static objects ( scenery for instance ) wouldn't affect framerate either since this too would also be done in the constructor. Retrieval is pretty damn quick at less than 1ms. The original reason I checked for duplicates was because I wasn't sure if my method of distributing them was correct, so far no duplicates have been found so I think I have it correct.

Adding an object is just stored in a vector. After you add all the objects, then you commit and the container is iterated over and a pointer to the object and a bounding rectangle is stored at each node. This means that the tree owns the objects and the nodes can just point to those objects, thus avoiding dangling pointers ( pointers to objects no longer valid ).

I could leave as is, and let the user use another method for dynamic ( moving ) entities. Creating these types of structures every frame probably isn't a good way to go. However, I believe something that might work...that I would have to test, would be to allow the user to find the object and remove and reinsert it back into the tree. I think the time complexity would be based on the number of dynamic objects in the tree. Say the tree was used for nothing by dynamic objects ( AI, projectiles, players ) then it would be the same as just recreating the tree after each movement update or recreating all the nodes anyway.

Something like "sweep and prune" might be a better fit for dynamic objects.

One concern of mine with this implementation is overlap. So currently, the tree tries to keep the number of objects to a user-defined limit within each node, but if it won't fit in a child node spatially it is just kept in the parent node. For instance, if the node boundaries won't fit the boundaries of the object being inserted or if the object straddles multiple node boundaries it is inserted into the parent node regardless of the number of objects already stored in the node.

The smallest node boundary size is the object's boundary size.

I don't know if completely rejecting objects would be acceptable if the max_count limit is reached or not, any suggestions?

EDIT: The version described in this post is currently in the main branch, however, the github link takes you to a secondary branch that is way more optimized.
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: 4266
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Quadtree progress

Post by albinopapa » August 12th, 2020, 8:47 am

Performance isn't as bad as I thought it would be. Made some changes though. Instead of filling the top level nodes and then moving them down to lower nodes when parents get full, I just push objects down to the smallest node that will fit the object's bounding box. This seems to be a lot faster for refreshing the tree. Will post example/sample project later today after some sleep.
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: 4266
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Quadtree progress

Post by albinopapa » August 12th, 2020, 9:42 pm

So here's a test sample of my quadtree implementation.

There's 10,000 balls, a "world" size of 10,000x10,000.

Nothing to do, no movement just red balls bouncing around in the world.

If balls are suspected to collide they turn yellow, if they collide they turn green if no collision they turn back to red.

Starting off, the fps is pretty low, but stabilizes around 30fps.

Pay no attention to the inaccurate collision resolution, I apparently don't know how to do that so not all collisions result in a rebound. The point for the upload was to test the performance of the quadtree and how well it worked as a templated structure. I think it turned out better than I ever expected. This isn't my first go at a quadtree, I never finished other attempts because I couldn't figure out a few things. This time I looked at several implementations until something finally clicked.

One implementation of trees that I absolutely hate is using the class itself as a tree. For some reason I prefer the interface class to be separate from the tree ( the list of nodes ).

There are a few things that I could do like adding a function for finding a specific object or get the node an object is in, but for the most part I think it's fine. The point of a quadtree as I see it is to quickly find a list of objects that are near or in a given region ( the bounding box of an entity for instance ). This has been accomplished. There are begin() and end() functions that iterate over all the entities so the tree can be used in a range based for loop.

Something to keep in mind is after you update the entities' position, you'll want to call the commit() function to refresh the tree. If the tree has nothing but static objects, you can avoid committing each frame by just committing after loading the tree with all the objects.

For efficiency, I suppose being able to remove an entity and reinsert it instead of recreating the entire tree would be ideal for trees that might have a mixture of static and dynamic objects. Removing objects would be a good thing to add regardless for removing them from the scene, so that'll be the next thing to add.
Attachments
quadtree sample.zip
(82.21 KiB) Downloaded 10 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: 4266
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Quadtree progress

Post by albinopapa » August 13th, 2020, 1:32 am

Forgot to mention that some C++20 features are used such as initializer statements in ranged for loops.

Also, while trying to implement object removal and reinsertion, I'm realizing that the whole tree would probably need to be reinitialized anyway. The reason I say this is the nodes store pointers to the objects in the tree's base vector. Removing an object from the base vector would change the address of all objects after the object being erased. This means I'd have to find all the objects from the one being removed to the end in all the nodes. Remove them from the nodes, remove the original object being deleted, then reinsert all the newly shifted objects from the base vector back into the tree.

While it is possible, using the steps outlined, I wonder if it would be quicker to just redo the entire tree.

Of course, as far as the tree's performance, it would be quicker if all the object pointers stored in each of the nodes were stable. This could be done if all the objects were stored as pointers, but there would probably be performance issues elsewhere.
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: 4266
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Quadtree progress

Post by albinopapa » August 13th, 2020, 4:40 pm

Woohoo, performance increase!!! Okay, not really.

I decided to implement a find function that allows you to find an object within the tree. The function returns an std::pair<qtree<...>::node, std::vector<T>::iterator>. This way you can iterate over only the objects in the same node. Went from ~30 fps to ~45 fps. I feel that there is an issue though. I have the balls turn yellow for all objects being considered for collision detection and some balls turn yellow when there spread out quite a bit.
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: 4266
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Quadtree progress

Post by albinopapa » August 21st, 2020, 6:55 am

I've been messing with this project for a few days now and kind of frustrated with it.

I can push elements onto the tree and have them load from root node and trickle down once a max occupancy has been reached for each node ( once a node is full, all elements in that node are sorted ).

I can query the tree for all objects contained within a region.

I can iterate over every object within the tree.

Removal is spotty, sometimes it works just fine and sometimes it crashes...haven't nailed down the condition to check for.

If I move/copy an object into a temp vector then remove it, I am able to reinsert it from the temp vector no problems ( with the caveat about removal being spotty ).

What has been frustrating me is not being able to remove/reinsert while iterating. So, if an object crosses a boundary of a node, it needs to be "resorted". This could mean moving the object from a child node to a parent node or it could mean moving it to a sibling node. This means that the size of two vectors change, the node being removed from and the node being added to. The node being removed from probably won't have to resize the vector, but comes with it's own issues. The node being added to may need to reallocate which means all new addresses and the current iterator would be invalid as well as any stored iterators. For instance, a ranged for loop stores begin and end iterators so the end will never be updated.

An option I might be able to take would be to use a list of objects instead. This means iterators won't be invalidated. I think this would solve the issue I'm having, but might reduce the performance. Though, having to move objects to a temporary container and then reinserting them may have a bigger performance hit.

Benchmark time I suppose.
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: 79
Joined: September 9th, 2017, 1:19 pm

Re: Quadtree progress

Post by Slidy » August 21st, 2020, 5:31 pm

Few ways to get around this. Simplest is using linked list which you mentioned.

Another option is to make a chunked allocator. Rather than allocating one big blob of memory and moving all the old data, you would allocate in fixed chunks. So once you run out of memory you create a new chunk for the new data. You can see example implementation of this here: https://github.com/SlidyBat/BatEngine/b ... llocator.h

You could also use a different handle type than pointers. For example you could use the index as a handle instead and make a function to get a reference to the node from it's index. Or a smart handle class that registers itself in a list of handles that are updated when the list is invalidated.

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

Re: Quadtree progress

Post by albinopapa » August 22nd, 2020, 12:33 am

I've thought about using a pool allocator, but I guess chunks would be a better fit. Not sure I want to completely manage the alignment and lifetime of everything else, at least not until I'm comfortable in my implementation.

What I might do once I get things figured out a little better, is take as a template parameter an allocator. This way users can use their own memory management.
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: 4266
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Quadtree progress

Post by albinopapa » August 22nd, 2020, 8:56 am

What? No self check or releasing of old chunk?

Code: Select all

ChunkedAllocator& operator=( ChunkedAllocator&& rhs )
		{
			m_iCapacity = rhs.m_iCapacity;
			m_pChunks = std::move( rhs.m_pChunks );
			m_iObjectSize = rhs.m_iObjectSize;
			return *this;
		}
I smell leakage.

Also, there are a few things I'd suggest.

The biggest being inheriting from pmr::memory_resource. Since C++17, it is common practice for memory allocation to be typeless.

Two, the allocator should just be responsible for allocation, construction, destruction and deallocation.

Three, a container should be worried about finding/accessing elements at a specific memory location.

I was going to ask about "why does everyone insist on overloading assert(), but it seems that some do it to add a message to the assertion.

EDIT: I was drunk when I made this post and hadn't fully read through all the code. While I think the suggestions I made are valid, they unintentionally probably came across a little abrasive and I apologize if that's the case.
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: 79
Joined: September 9th, 2017, 1:19 pm

Re: Quadtree progress

Post by Slidy » August 24th, 2020, 2:56 am

Thanks for the suggestions.

I don't see the leak you're talking about. m_pChunks is an std::vector so std:move should take care of anything (in fact don't think the explicit move constructor/assignment is really needed, it's probably a remnant of older code).

As for your other points, they're not wrong but not really something I would consider a worthwhile change. I called this an "allocator" but really it's just a class that lets you handle chunked arrays as if they were just one contiguous vector, so may not fit your strict definition of an allocator. For constructing/destructing that is done manually when used via placement new: https://github.com/SlidyBat/BatEngine/b ... ity.h#L242

Feel free to improve on it and implement it how you see fit.

Post Reply