Performance problems with quadtree for dynamic objects

Question

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.

Answer 1

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.

Answer 2

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?