4
\$\begingroup\$

I´ve implemented a quadtree spatial partitioning to my game engine as I wanted to try it and see how it affects the performance checks. The results were great (instead of hundreds collision checks only for cursor I was suddenly having just about 10%), however I faced performance problems (not caused by the number of collision checks but by the spatial structure itself [or my implementation]) :

1. At first I was inserting items every frame and at the end of the frame the quadtree was cleared and so on. I realised this slowed down the performance more than 2-3 times.

2. Of cource the next step was to try to make the quadtree dynamic by not clearing it but by checking the moving objects from the quadtree. However this process is also not trivial as I can have a multiple nodes containing the same object (if it doesnt fit to any of the children I "broadcast" and check neighbour nodes so it can be visible in more than 1 node) and I ended up by digging through the entire quadtree again.

How did you solve these problems with the quadtrees? I´ve read that some of the engines use multiple spatial structures to divide work for static/dynamic objects, I would use quadtree for static structure but what would be suitable for dynamic? Also I think I "hurt" myself when I want to make as generic solution as possible so I dont have to change the spatial structures of my game engine no matter what type of game I´m creating with it at the time.

\$\endgroup\$
  • \$\begingroup\$ I am interested in the answer as I ran into the same problem. Quadtree works great for static entities. Not so great for moving ones. \$\endgroup\$ – TheBuzzSaw Nov 12 '17 at 16:33
  • \$\begingroup\$ @TheBuzzSaw You are right. I was thinking about giving an user an option when creating a collidable entity, if its static or dynamic. If its a static(so the user knows that is it not going to change its position [ or if yes, not that frequently - so the performance overhead will not be that visible] ) engine will insert it to a quadtree. If it will be dynamic, there will be another data structure. At the collision checks "close" objects (that can collide) from quadtree and "dynamic structure" will be combined into single structure. \$\endgroup\$ – Pins Nov 12 '17 at 17:42
  • \$\begingroup\$ @TheBuzzSaw Got an answer for you both with all the details you guys should need to quickly implement it. \$\endgroup\$ – user77245 Dec 11 '17 at 1:44
3
\$\begingroup\$

I'd echo Bram and use a grid and actually just for all objects, static and dynamic (though you might store static objects in a separate grid instance, but same data structure for both). You can tune the crap out of it.

\$\endgroup\$
  • \$\begingroup\$ Cheers. I ended up embellishing the code some more to help you get started. Merry xmas! \$\endgroup\$ – user77245 Dec 11 '17 at 21:13
  • 1
    \$\begingroup\$ All right, was feeling generous so I added a full working implementation to the answer. Feel free to use it however you like! \$\endgroup\$ – user77245 Dec 11 '17 at 22:57
  • 1
    \$\begingroup\$ Neat, but one tiny thing I'd change: I'd allow rectangle borders to be outside the grid. Clamping them shouldn't be more complicated than the current check. This makes it easier, for example if an object you want to collide with others is on the edge of your map. Otherwise one might be forced to clamp the values and then do the check anyway. \$\endgroup\$ – Mario Dec 12 '17 at 19:05
  • \$\begingroup\$ Much agreed and my actual C production version handles offscreen cases without clamping as well as floating-point positions and being able to dynamically resize and so forth, though I kinda simplified things a lot for the sake of just illustratory purposes since I imagine anyone starting with the code above would want to tweak the hell out of it for their purposes. It's kinda meant to be as easily adjustable as possible so I tried to eliminate all production fluff in the process of porting it to C++. \$\endgroup\$ – user77245 Dec 12 '17 at 19:10
  • \$\begingroup\$ In my particular use case when elements are offscreen, it doesn't make sense to check for collision so much (what the user doesn't see doesn't hurt him kinda mindset) -- but clamping makes a whole lot of sense if you want to keep looking for things going on with elements that are offscreen. I didn't have a clamp function handy and was somewhat lazy so I just asserted instead. :-D \$\endgroup\$ – user77245 Dec 12 '17 at 19:16
1
\$\begingroup\$

How deep are your quadtrees? How many elements do you tolerate in a leaf node before you subdivide?

How are your entities spread out through the world? If it is extremely uneven, with just a few big clumps here and there, I can see how quadtrees would help.

But if it is better spread out than that, I would use a grid instead of a quadtree.

A grid is much easier to keep updated than a tree. You could dynamically move objects from cell to cell, but because assignment to a cell is so cheap, reconstruction from scratch works too.

You can typically afford busy cells in a grid. It increases the collisions test of course, for those cells, but you still get the easy wins of not testing against remote objects.

If you decide to use a grid, you can either do the grid for dynamic objects only, or use it for static objects too. You will get fewer collision tests if you keep the quadtree for static objects. This is because a quadtree can be more precise in spatially subdividing your world.

But you will have to weigh the reduction in collision tests against the increased complexity of your code due to maintaining two data structures. Personally, I would choose simplicity over performance. Especially if the performance with a grid is "good enough." It's wasteful to code a quadtree indexing before determining that you actually need it, I think.

I would also chose grid-only approach if you need to test dynamic versus static objects. You mentioned you test the cursor against dynamic/static, in which case both a grid and a tree would be less problematic.

Let me conclude with one draw-back for the grid approach: if you want fine-grain subdivision you will be using a lot more memory than a quadtree would require. So determine your constraints: are you short on memory? Are the collision tests dragging down the fluid experience?

\$\endgroup\$
  • \$\begingroup\$ I use 5 items before the nodes subdivide with the maximum depth 5. Do you recommend me to use grid partitioning for dynamic objects? Or for all objects? \$\endgroup\$ – Pins Nov 12 '17 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.