Game Algorithms

Re: Large objects in QuadTrees

Zeta Two — Sat, 04 Jul 2009 19:37:41 GMT

I ended up putting the objects in the parent node. I still only have half the number of collision tests/frame vs using only a linked list. EDIT: also, with some further optimization (only moving objects in the quad tree which acctually have moved), I'm down to 1/5 the tests/frame vs simple list.

Re: Large objects in QuadTrees

Eckish — Fri, 03 Jul 2009 05:47:27 GMT

BenC:

Aright so I've just finished updating my code to place any intersecting objects within the leaf nodes they intersects with... So far so good...except.

...there are instances where lets say two objects intersect with the same leaf nodes... hence via tree traversing, those objects are checked against each other twice.

Besides creating a list of already checked pairs and checking against it, is there anything else I can do to remedy this situation?

I am using the tree for 2d collision detection by the way.

You will get extra checks like that if you go the route of putting large objects into multiple nodes. However, the increase will be constant and shouldn't affect your performance significantly.

One thing you can do is to give each object a unique id. And then only allow objects to only check against objects with a higher id. That way you would get multiple checks from big objects only once.

I also track the collisions instead of acting on them immediately. So, on each collision sweep, my objects only check against every other collision candidate in one direction. And then they also only register one collision against them. Tracking them instead of immediately performing actions (which can mean destroying the object) also means that all of the objects will still exist if a third object happened to also be colliding with them that frame.

Re: Large objects in QuadTrees

Craig Martin — Fri, 03 Jul 2009 03:12:57 GMT

Sometimes it's worth just not using a quad tree for certain objects. If you have only a few 'extra large' objects it might be worth just leaving them out of the quadtree. Depends how determined you are to generalise I guess.

Re: Large objects in QuadTrees

BenC — Fri, 03 Jul 2009 01:53:54 GMT

Eckish:
You should put it in every low level cell that it collides with, if you are going to go that route. And then no, it won't be complicated to check against it. It will exist in more than one cell and may get checked multiple times as a result, but the algorithm doesn't change with that respect.

What gets complicated by that method is the return reference. A good tree design will have a two way reference. The cell nodes will reference the objects, so if a collision exists on the cell, then you know you should check the child objects for collisions too. The objects themselves should also have a reference to the cell it belongs to. Thats for allowing you to remove the object from the cell quickly. Otherwise, you would have to search the tree again in order to find the cell it is located in to remove it. So, if you go with a design that allows the object to exist in more than one cell, then you also need to design the object to hold multiple cell references.

Aright so I've just finished updating my code to place any intersecting objects within the leaf nodes they intersects with... So far so good...except.

...there are instances where lets say two objects intersect with the same leaf nodes... hence via tree traversing, those objects are checked against each other twice.

Besides creating a list of already checked pairs and checking against it, is there anything else I can do to remedy this situation?

I am using the tree for 2d collision detection by the way.

Re: Large objects in QuadTrees

jwatte — Fri, 03 Jul 2009 01:01:46 GMT

If you're talking about "loose" boundaries, then the object is only in one cell. That may be a leaf cell, or it may be a parent cell, but it will always be the cell that contains the center of the object. An object will not be pushed deeper into the tree than the size where a cell size times your looseness alpha is just greater than the radius of the object. Thus, big objects live further up; small objects further down (and you can limit the tree depth if you want).

Re: Large objects in QuadTrees

Eckish — Fri, 03 Jul 2009 00:28:04 GMT

You should put it in every low level cell that it collides with, if you are going to go that route. And then no, it won't be complicated to check against it. It will exist in more than one cell and may get checked multiple times as a result, but the algorithm doesn't change with that respect.

What gets complicated by that method is the return reference. A good tree design will have a two way reference. The cell nodes will reference the objects, so if a collision exists on the cell, then you know you should check the child objects for collisions too. The objects themselves should also have a reference to the cell it belongs to. Thats for allowing you to remove the object from the cell quickly. Otherwise, you would have to search the tree again in order to find the cell it is located in to remove it. So, if you go with a design that allows the object to exist in more than one cell, then you also need to design the object to hold multiple cell references.

Re: Large objects in QuadTrees

Zeta Two — Thu, 02 Jul 2009 23:41:01 GMT

One question: What if I have a large object (say twice or three times the size of a bottom-level cell). Won't it be rather complicated check which cells' loose bounds intersects with the current one?

Re: Large objects in QuadTrees

BenC — Thu, 02 Jul 2009 22:28:03 GMT

Yeah I see what you guys mean... it renders the quad tree somewhat pointless.

For the sake of getting my hands dirty i'll try my hand at this method you mentioned jwatte:

"Add overlapping objects to multiple nodes, and descend a single node when querying. This makes each object more complex, because it needs to know all nodes that it's added to."

I hope it doesn't get too messy.

Thanks for the feedback guys.

Re: Large objects in QuadTrees

jwatte — Thu, 02 Jul 2009 22:10:24 GMT

The problem with parents is that a lot of things will end up in the root node -- anything that crosses the topmost center "cross" will go there. The problem with that, in turn, is that then everything that tests against the quad tree ends up testing against everything in the root node, and the performance will be more like a linked list, and less like a recursive tree.

That being said -- a lot of games get by with just a linked list, and no recursive structure at all. If you want to save time, just pop 'em all into a List<Entity>, and only replace it with a Quadtree<Entity> if and when you really need to.

Re: Large objects in QuadTrees

Eckish — Thu, 02 Jul 2009 21:59:40 GMT

If they overlap with one line, they could over lap with a line in the parent and continue to move up the tree. If a bunch of stuff moves up the tree, you lose all the benefits of having a tree in the first place, because you end up checking against most game objects anyways.

Re: Large objects in QuadTrees

BenC — Thu, 02 Jul 2009 21:49:57 GMT

Thanks for the comment. I expected the method I use to be less efficient than other methods like the ones jwatte mentioned...but you used the word significantly which has me worried.

So I take it you guys highly do not recommend placing objects in parents if they overlap and recommend implementing another way of doing it?

Re: Large objects in QuadTrees

Craig Martin — Thu, 02 Jul 2009 08:15:49 GMT

BenC:
I went with option one... placing it in the parent quad. So far it seems to be working out fine.

That can significantly slow down quad tree lookups.

Re: Large objects in QuadTrees

BenC — Thu, 02 Jul 2009 00:45:55 GMT

I ran into this issue when I first started to implement a quad tree.

I went with option one... placing it in the parent quad. So far it seems to be working out fine.

Re: Large objects in QuadTrees

Eckish — Thu, 02 Jul 2009 00:45:29 GMT

Another alternative that might make sense in some situations is to instead break the larger object up into smaller pieces. Then you can treat each part just like you would normal small objects in the tree. No complexity is added to the tree structure or search algorithms. Instead, when a collision is detected on a piece, it will be responsible for notifying the rest of 'itself' that a collision occurred.

Re: Large objects in QuadTrees

jwatte — Thu, 02 Jul 2009 00:37:33 GMT

There are two ways to solve this problem:

1) Add overlapping objects to multiple nodes, and descend a single node when querying. This makes each object more complex, because it needs to know all nodes that it's added to.

2) Add the object only to the node that contains the center of the object, and recurse multiple nodes when querying. This makes querying somewhat more costly (by a constant factor, it turns out!), but keeps the data structure small and simple.

Basically, the deepest level at which you store an object is determined by the radius of that object. Then you query the tree with an inflation factor for each cell that corresponds to the maximum extent an object may have at that level. If you google for "loose octree" you will find tutorials for how to do this. For octrees, but the same idea works fine for quad trees.