Quadtree-like structure for dynamic / moving Game Objects

Game Play & Game Design
#1

Hey guys :slight_smile:

I’m looking for a way to store moving, dynamic objects in quadtrees. Or better: I’m looking for a quadtree-like techneque to store objects, which move and are dynamic. The quadtree-like storage is supposed to only contain dynamic objects, since static objects are stored in a normal quadtree, which is the idea…

So the dynamic quadtree is cleared and filled every frame. Usually quadtrees aren’t supposed to be used like that. What’d you suggest?

One more thing: I’ve also search up on how to use them and I stumbled across this stackoverflow question, which gave 2 ways to do it or 2 ideas:

  1. A quadtree with Nodes being able to be node and leave at the same time, so AABB’s are stored at the smallest node they can be put into.
  2. A quadtree which stores all Rectangles in the leaves as a normal Point-storing-quadtree, but a reference to the Rectangle is hold to every possible leave in the quadtree. (So all leaves the rectangle covers store a reference to it)

So my question is:
Would you suggest a quadtree for storing dynamic objects, if not, what variation of quadtree would you suggest, or what other tree / thing would you suggest?
And:
How would you implement your dynamic quadtree, if you’d go about implementing one: Way 1, or way 2?

#2

Quadtrees are not efficient in today’s CPUs. Use a grid instead.

It’s both incredibly easy to develop, and much, much faster.

which is faster?
#3

What exactly is a grid?
Basically, yeah, I know what a grid is, but … what exactly.

JVM! Give me a grid! … mhmmm… doesn’t work :confused:

#4

Just divide the space into equal-sized rectangles and keep track of what rectangles contain what objects. When the objects move you just update that information.
My experience with grids is that it is very fast unless the density of objects is really uneven. The extreme situation is when all objects are within a single rectangle. I guess that you can deal with this by dynamically constructing sub-grids within the rectangles, but I wouldn’t bother unless you get real performance problems.

In three dimensions this might be a completely different story though…

#5

Normally it isn’t required, but if you’re stressed for performance, adjust the cell dimensions at runtime, and keep adjusting, always converging to a varying optimum.

#6

Checkout my quadtree implementation: https://bitbucket.org/mludwig/ferox/src/b0fc96dafa358ace4ccdf3e92aee468a72afd6f7/ferox-math/src/main/java/com/ferox/math/bounds/QuadTree.java?at=default

It’s a quadtree built on top of a grid.

#7

Uh, it’s a a quadtree without the quadtreey parts?

#8

No, it uses a grid structure for inserts/removals from the spatial index, intersecting pair queries, and AABB queries. Then a quadtree is built on top of the grid and stored in a single int array; this is possible because it’s a complete tree, where the leaves map to the grid cells.

edit
The reason I brought this up was because I implemented it to be a structure that worked well with dynamic objects. Both the grid and quadtree array can be cleared quite quickly, and building the quadtree up from the grid is more efficient than building the tree top-down. In my game system, I then clear the tree each frame, possible updating what its extents are, and then re-insert every object.

#9

I will look at that carefully tomorrow, thank you for sharing this source code. I will look at Frustum.java too, can I use it to compute sub-frusta from 2 quads (typically for portal culling)?

#10

I’m sure you could, but I haven’t implemented that yet. Since it can support generic perspective frustums with arbitrary right/left, top/bottom values, I should assume it’s possible.

#11

Hi all,

In my quest to learn new things, could you explain this a little more?

I would have said it depends entirely on your scene and the implementation of the quad-tree whether grids are faster. I say this because I imagine that the way you store the grid would be exactly the same way you’d store a qt (in that both are essentially just AABB - but, unless I am missing something, you can then cull huge areas of your game world with a qt which you cannot do with a grid). So it would seem to me like the only difference between a grid and a at is you are removing the tree structure?

Thanks,

#12

Okey guys, this gave me some very good ideas… And also thanks for the source code, this game me one idea too :slight_smile:

So I’m back in about half an hour…

#13

I’d say I’d strongly disagree with what Riven is saying, BUT strong agree with the implication. The problem with QuadTree’s is first that it needs to be a good match to the average distribution of things contained. Second that straight forward text-book implementations, which were fine until the mid-90s or so, will blow chunks on modern machines. Thirdly that java is a poor language to implement a modern-ish version due to lack of structures. Forthly (is that a proper word?) the amount of time (in comparison to a uniform grid) is probably exponentially longer and complex to come out with something that’s like 10% (to pull a number out of my bottom) faster for spatial queries and that time could be much better spent on something else…and if speed is an issue then that .1*timeOfSpatialQueries cycles can probably be juiced out of somewhere else and still have some engineering time left over to spend on something else.

IHMO, the bottom line is that for large active worlds…breaking into local spaces is the way to go…and potentially hybrid models depending on the exact kinds of scenes involved.

#14

While you are (always) free to disagree, maybe even strongly, I wonder what the differences are in our points. I decided (due to lazyness) that I would not go into great detail, but my reasoning was exactly the same as yours. So… where do we actually disagree (strongly…) ?

#15

And what actually are your ideas?!? ???

#16

Like I said: use a uniform grid:
List[w][h] or List[w*h]
it’s unlikely you’re going to run into performance problems. Unless ofcourse you’re going to push the algorithm to its extremes, fine-tuning / benchmarking it, moving it to the GPU, and at the end of the day, don’t have a game but a tech demo.

#17

So… a List[(yeah, I have a class doing this)w*h]?

Hmm… I just had the idea to use a HashMap. I’m pretty, pretty sure this will turn out very well :slight_smile:

(also, I need to store AABB’s, so I need to insert them at multiple leaves…)

#18

@Riven: Only in the statement: “Quadtrees are not efficient in today’s CPUs”. They can be worth the effort…it’s just very unlikely to be the case.

#19

Didn’t he just mean that traversing the tree has the same performance problems as a linked list?

#20

That, and you have to do bounds checking (on AABBs) for every level, up to 4 times. All in all, there are lots of conditional jumps and lots of scattered memory access. In modern CPUs you get a rather large penalty for such code.

Needless to say, using a grid is just simpler to code, which, in this case, is probably most important.