4
\$\begingroup\$

Let's say we have 100 objects of each of few types, that may have an effect if they collide with one other type, or they may not.

Is it better to have quadtrees for each object type, and check collisions directly between the object types we want; or is it better to have a single quadtree holding all objects, then generate collision pairs and check if the collision has effect or not?

Is having a single quadtree slower? Why not having multiple quadtrees, one for each object type?

\$\endgroup\$
4
\$\begingroup\$

Usually you'll just have a single quad tree. Often times this would be better as the different layers of collisions can be quite complex and numerous. Also I don't think a bottleneck has ever been that too many potential pairs are culled by layering instead of being implicitly culled by separating data structures.

It's hard to make something faster and simpler than a bitwise and as far as layer overlap checking goes.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

If you make separate binary trees for different objects, you will destroy the whole purpose of the tree: logarithmic complexity.

Say you sort your objects into different trees. Each tree's contents and ordering will have no bearing on collisions with items in other trees. You will be back to testing each item from one tree against each item from another. That puts you right back at O² complexity.

On top of that, creating sparse or imbalanced trees also wipes out their efficiency. The point is that each branch of the tree reduces the required checks by half. You gain no benefit if all items reside in a single branch. So having trees with fewer items does not make them faster; it makes them slower.

Make a single tree for all item types. This is important enough to edit your code architecture to make it possible.

| improve this answer | |
\$\endgroup\$

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.